boolgebra

README

Package boolgebra provide basic boolean algebra operations.

It is possible to compare, expand, reduce, parse boolean expressions.

It makes it possible to resolve logic puzzles, like Smullyan's, or logic grid.

Because I cannot solve those puzzles without trying to get the computer doing it for me.

Let's solve this Smullyan's problem:

Alice and Bob are residents of the island of knights and knaves, where knights always tell the truth and knaves always tell a lie.

Alice says, "We are both knaves”.

Can you tell who is a knight, and who is knave?

In the island of knights and knaves, when you know for sure that "Alice says it is raining" you cannot tell for sure if it rains, but you can be certain that if Alice is a knight, then she is telling the truth then it is raining, therefore Alice is knight => it is raining. Also, if it is raining, then Alice told the truth, then she must be a knight. it is raining => Alice is a knight. Therefore, when you know for sure that "Alice says it is raining" you can write for sure that Alice is a knight <=> it is raining.

Solving Smullyan's puzzles with boolgebra is all about writing correctly what you know for certain in the puzzle.

back to our problem, knowing for sure that Alice said "We are both knaves”, you can write, for sure that Alice is a knight <=> Alice is not a knight & Bob is not a knight

using boolgebra you can compute the solution by just doing:

	problem, _ := Parse(`Alice is a Knight <=> Alice is not a Knight & Bob is not a Knight`)
	fmt.Println(Simplify(problem))
	// Output: Alice is not a Knight & Bob is a Knight

Documentation

Index

• type Expr
  • func And(expressions ...Expr) Expr
  • func AtLeast(n int, terms ...Expr) Expr
  • func AtMost(n int, terms ...Expr) Expr
  • func Eq(A, B Expr) Expr
  • func Exactly(n int, terms ...Expr) Expr
  • func Factor(x Expr) (f, rem Expr)
  • func ID(id string) Expr
  • func Impl(A, B Expr) Expr
  • func Lit(val bool) Expr
  • func Neq(A, B Expr) Expr
  • func Not(x Expr) Expr
  • func Or(x ...Expr) Expr
  • func Parse(src string) (Expr, error)
  • func Simplify(x Expr) Expr
  • func Xor(A, B Expr) Expr
• type TermBuilder
  • func (t *TermBuilder) And(id string, val bool)
  • func (t *TermBuilder) Build() Expr
  • func (t TermBuilder) IsFalse() bool

Examples

• And
• ID
• Lit
• Not
• Or
• Simplify (Smullyan2)
• Simplify (Smullyan3)
• Simplify (Smullyan4)

Types

type Expr

type Expr interface {
	String() string
	// return the negation of receiver
	Not() Expr
	// Is return true if the Expr is literally equals to value.
	Is(val bool) bool
	// Terms return the number of Terms in this Expression.
	Terms() int
	// Term return the ith Term or nil.
	Term(i int) Expr
	// IDs return a set of all the IDs in this expression.
	IDs() (ids map[string]struct{})
	// ID return the value of the given ID.
	ID(id string) (x Expr, positive bool)
}

Expr is the interface that all elements of a boolean algebra share

func And

func And(expressions ...Expr) Expr

And returns the disjunction of all the expressions passed in parameters.

By convention, if 'x' is empty it returns Lit(true). See https://en.wikipedia.org/wiki/Empty_product

Example

A := ID("A")
B := ID("B")
C := ID("C")
fmt.Println(And(A, Lit(true)))
fmt.Println(And(A, Lit(false)))
fmt.Println(And(A, B, C))
fmt.Println(And(A, Not(B)))

Output:

A
false
A & B & C
A & not B

func AtLeast

func AtLeast(n int, terms ...Expr) Expr

AtLeast retuns an expression that is true if and only if at least 'n' terms are True.

func AtMost

func AtMost(n int, terms ...Expr) Expr

AtMost retuns an expression that is true if and only if at most 'n' terms are True.

func Eq

func Eq(A, B Expr) Expr

Eq returns the logical equality of A,B ( A and B have both the same truth value)

It can also be the logical equivalence A <=> B. Both are in fact the same boolean function.

see https://en.wikipedia.org/wiki/Boolean_algebra#Secondary_operations

func Exactly

func Exactly(n int, terms ...Expr) Expr

Exactly retuns an expression that is true if and only if exactly 'i' terms are True.

func Factor

func Factor(x Expr) (f, rem Expr)

Factor computes the greatest common factor between terms of x

x = \sum t_i \arrow f \and \sum r_i

x is currently a sum of terms, this function returns f and rem so that

x = And(f, rem)
f.Terms() ==1 : it's a minterm

func ID

func ID(id string) Expr

ID returns an Expr equivalent to a single ID 'id'

Example

A := ID("A")
fmt.Println(A)

Output:

A

func Impl

func Impl(A, B Expr) Expr

Impl returns the logical implication of A,B

see https://en.wikipedia.org/wiki/Boolean_algebra#Secondary_operations

func Lit

func Lit(val bool) Expr

Lit returns an Expr equivalent to a boolean literal 'val'

Example

A := Lit(true)
fmt.Println(A)

B := Lit(false)
fmt.Println(B)

Output:

true
false

func Neq

func Neq(A, B Expr) Expr

Neq returns the logical '!='

It is the same as Xor.

see https://en.wikipedia.org/wiki/Boolean_algebra#Secondary_operations

func Not

func Not(x Expr) Expr

Not returns the negation of 'x'.

Example

fmt.Println(Not(ID("A")))
fmt.Println(Not(Lit(true)))
fmt.Println(Not(Lit(false)))

Output:

not A
false
true

func Or

func Or(x ...Expr) Expr

Or return the conjunction of all the expression passed in parameter.

By convention, if 'x' is empty it returns Lit(false). See https://en.wikipedia.org/wiki/Empty_sum

Example

A := ID("A")
B := ID("B")

fmt.Println(Or(A, Lit(true)))
fmt.Println(Or(A, Lit(false)))
fmt.Println(Or(A, Not(B)))

Output:

true
A
A | not B

func Parse

func Parse(src string) (Expr, error)

Parse a boolean expression in src, and returns its Expr.

Literal: `true` or `false` are the two possible literal.

Variables: any usual identifier `<letter> (digit|letter)*`

an ID is made of one or more Variables.

'not' can be inserted in a list of variables to form the negation of an ID: e.g. `John is not a Knight` is equivalent to `not John is a Knight` or `John not is a Knight`.

Note that the 'not' can be placed anywhere in the ID. 'not' can also be used as a prefix operator `not a & b`.

The following operators in increasing binding power (precedence)

• 'Reduce' reduce expression to a minimal form using prime implicant
• Ascertain factor an expression x in two implicant expressions a,b so that `x <=> a and b` and return 'a', that can be considered the part of 'x' that is certain.
• 'or' long or, same operation as '|' but with low binding power.
• 'and' long and, same operation as '&' but with low binding power.
• '<=>' logically equivalent
• '!=' not logically equivalent, same operation as '^' but with low binding power
• '=>' imply.
• '|' or
• '^' xor
• '&' and
• 'not' not

So that `a | b & c` is equivalent to `a | (b&c)`

Note: '!=' and '^' are the same operation, just with different precedence.

func Simplify

func Simplify(x Expr) Expr

Simplify returns a simpler version of 'x' by applying simplification rules.

Example (Smullyan2)

// this example cannot use the bool language, yet, as support for Exactly 1 is not available yet.

// A Knight is someone that always tells the truth.
// A Knaves is someone that always tells a lie.

// The hero meets three guys 'a','b', 'c', each one can be a Knight or a Knaves
A_is_a_knight := ID("A is a Knight")
B_is_a_knight := ID("B is a Knight")
C_is_a_knight := ID("C is a Knight")

// the goal is to find out who is a Sorcerer

A_is_Sorcerer := ID("A is a Sorcerer")
B_is_Sorcerer := ID("B is a Sorcerer")
C_is_Sorcerer := ID("C is a Sorcerer")

// But only one can be a Sorcerer
Fact1 := Exactly(1, A_is_Sorcerer, B_is_Sorcerer, C_is_Sorcerer)

// The hero asked 'a': are you a Sorcerer ? 'a' answered, yes
// as always with knights and knaves, we can say that:
Fact2 := Eq(A_is_a_knight, A_is_Sorcerer)

// He asked the same question to 'b'
Fact3 := Eq(B_is_a_knight, B_is_Sorcerer)

// But 'c', said that, at most one of them was a Knight !!
Fact4 := Eq(C_is_a_knight, AtMost(1, A_is_a_knight, B_is_a_knight, C_is_a_knight))

// The answer is straightforward.
fmt.Println(Simplify(And(Fact1, Fact2, Fact3, Fact4)))

Output:

A is not a Knight & A is not a Sorcerer & B is not a Knight & B is not a Sorcerer & C is a Knight & C is a Sorcerer

Example (Smullyan3)

// The hero finds two guies 'a' and 'b'
A_is_a_knight := ID("A is a Knight")
B_is_a_knight := ID("B is a Knight")
// exactly one of them is a Sorcerer
A_is_Sorcerer := ID("A is a Sorcerer")
B_is_Sorcerer := ID("B is a Sorcerer")
Fact1 := Exactly(1, A_is_Sorcerer, B_is_Sorcerer)

// he asks 'a': is the sorcerer a knight?

Sorcerer_is_a_knight := ID("The Sorcerer is a Knight")

// Knowing that the sorcerer is a knight means that beeing a sorcerer => beeing a knight.
Fact2 := Impl(Sorcerer_is_a_knight, Impl(A_is_Sorcerer, A_is_a_knight))
Fact3 := Impl(Sorcerer_is_a_knight, Impl(B_is_Sorcerer, B_is_a_knight))
Fact4 := Impl(Not(Sorcerer_is_a_knight), Impl(A_is_Sorcerer, Not(A_is_a_knight)))
Fact5 := Impl(Not(Sorcerer_is_a_knight), Impl(B_is_Sorcerer, Not(B_is_a_knight)))

Facts := And(Fact1, Fact2, Fact3, Fact4, Fact5)

// if A answered yes
Hypothesis1 := Eq(A_is_a_knight, Sorcerer_is_a_knight)
// what can be deduced is what is always true, i.e y, so that x = y AND something else
Deduction1, _ := Factor(And(Facts, Hypothesis1))

// if A answered no
Hypothesis2 := Eq(A_is_a_knight, Not(Sorcerer_is_a_knight))
Deduction2, _ := Factor(And(Facts, Hypothesis2))
// If nothing can be deduced, then Deduction is "True" (the least thing that is always true)
//So we can do

fmt.Println(Simplify(And(Deduction1, Deduction2)))

Output:

A is not a Sorcerer & B is a Sorcerer

Example (Smullyan4)

// A Knight is someone that always tells the truth.
// A Knaves is someone that always tells a lie.

// there are two persons accused 'b' and 'c'.
B_is_a_knight := ID("B is a Knight")
C_is_a_knight := ID("C is a Knight")

// 'b' pretend that 'c' said "I lied, yesterday"
// there are two statement in this sentences
// I spoke yesterday, and it was a lie
//
C_Spoke := ID("C Spoke")
C_Lied := ID("C Lied")
Story := And(C_Spoke, C_Lied)

Fact1 := Eq(B_is_a_knight, Eq(C_is_a_knight, Story))

Fact2 := Eq(C_Lied, Not(C_is_a_knight))
deduction, _ := Factor(And(Fact1, Fact2))
fmt.Println(deduction)
// The only thing that is certain is "True". There is not relevant information here

Output:

true

func Xor

func Xor(A, B Expr) Expr

Xor returns the logical Xor

see https://en.wikipedia.org/wiki/Boolean_algebra#Secondary_operations

type TermBuilder

type TermBuilder struct {
	// contains filtered or unexported fields
}

TermBuilder can be used to efficiently append ID ( or Not(ID)) into a big And

func (*TermBuilder) And

func (t *TermBuilder) And(id string, val bool)

And append a variable to the current term

func (*TermBuilder) Build

func (t *TermBuilder) Build() Expr

func (TermBuilder) IsFalse

func (t TermBuilder) IsFalse() bool

IsFalse returns true if the term under construction is already degenerated to False