makeTextTable[data0_]:=Module[{data},
(* FIXME data=Table[ToString[#,TraditionalForm]&/@(data0[[i]]),{i,1,Length[data0]}];*)

Text@Grid[data0,Background->{None,{Lighter[Yellow,.9],{White,Lighter[Blend[{Blue,Green}],.8]}}},Dividers->{{Darker[Gray,.6],{Lighter[Gray,.5]},Darker[Gray,.6]},{Darker[Gray,.6],Darker[Gray,.6],{False},Darker[Gray,.6]}},ItemSize->Automatic]

];

Boolean Algebra

Boolean Algebra is a powerful mathematical tool from logical circuits design. It takes its name from its founder Geirge Bool in the (19^th)-century.

1. Boolean Expressions

A Boolean Expression in n variables (Subscript[x, 1]), (Subscript[x, 2]), (Subscript[x, 3]), ..., (Subscript[x, n]) is any finite string of symbols formed by applying the following rules:
1)  (Subscript[x, 1]), (Subscript[x, 2]), (Subscript[x, 3]), ..., (Subscript[x, n])  are Boolean expressions.
2) If x and y are Boolean expressions, so are (x+y), (x.y) and x’.

In our context we build a Boolean Algebra on a set B={0,1}. All together with the operations of disjunction, conjunction, and negation.

t1=Text[Grid[{{"\"∨\" \"or\" \"+\"","0","1"},{"0","0","1"},{"1","1","1"}},Frame->{{True,True},{True,True},{{{1,3},{1,3}}->True,{{1,3}}->True}}]];
t2=Text[Grid[{{"\"∧\" \"and\" \".\"","0","1"},{"0","0","0"},{"1","0","1"}},Frame->{{True,True},{True,True},{{{1,3},{1,3}}->True,{{1,3}}->True}}]];
t3=Text[Grid[{{"x","x'"},{"0","1"},{"1","0"}},Frame->{{True,True},{True,True},{{{1,3},{1,3}}->True,{{1,3}}->True}}]];
Row[{t1,"    ",t2,"   ",t3}]

Also remember that always:

Grid[{{"x + 0 = 0","","x + 1 = 1","","x + x = x","","x + x' = 1"},
{""},
{"x.0 = 0","","x.1 = x","","x.x = x","","x.x' = 0"}},Frame->True]

Some complex Bollean expressions:

Grid[{{"x.[x.y + y'(x + y)']"},
{""},
{"(x.y.z') + (x'.y.z) + (x.y'.z)'"}},Frame->True]

can apply truth table, and 2 expressions are said to be equivalent if they have the same truth table.

Theorem 1.1. Let x,y, and z be Boolean Variables, the following identities always hold:

makeTextTable[{{"1. a)","x.y = y.x"," Commutative law ","x + y = y + x"},
{"2. a)","x.(y.z) = (x.y).z"," Associative law ","x + (y + z) = (x + y) + z"},
{"3. a)","x.(y + z) = x.y + x.z"," Distributive law ","x + (y.z) = (x + y).(x + z)"}
}]

Now use theorem 1.1. to show that:

makeTextTable[{{"x.(y + z)' + (x.y) = x.(y + z')"},
{"x.y + x.z' + x.y = x.y + x.y + x.z'"},
{"                 = x.y + x.z' "},
{"                 = x.(y + z')"}
}]

1.1. De Morgan’s Law

Theorem 1.1.1. For all Boolean Expressions x and y:
1) (x + y)’ = x’.y’
2) (x.y)’ = x’ + y’

Theorem 1.1.2. If   x+y = 1  and   x.y = 0   ⟹    x = y’
proof:

x = x.1 = x.(y + y’)    ⟹      x = x.y + x.y’ = 0 + x.y’ = y.y’ + x.y’ = y’(x + y) = y’     ⟹  x = y’


Example 1.1.1. Prove that:

a) (p + q’)’.r’ = p’.q.r’
use De Morgan’s Law:  p’.q.r’

b) ((p + q’).(r.(p + q’)))’ = p’.q
use De Morgan’s Law: 
 ((p + q’).(r.(p + q’)))’ = (p + q’)’ + (r.(p + q’))’ = p’.q + r’ + (p + q’)’ = p’.q + r’ + p’.q = r’ + p’.q
 
 c) x.y.x’.y + x’.y’ + x.y’ = y’
 
  x.x’.y.y + x’.y’ + x.y’ = 0.y + x’.y’ + x.y’ = y’.(x + x’) = y’.1 = y’
  
d) x.y + x’.y + x’.y’ + x.y’ = 1

x.y + x’.y + x’.y’ + x.y’ = (x + x’).y + (x + x’).y’ = 1.y + 1.y’ = y + y’ = 1

2. Representation of Expressions

What is the best way to write a boolean Expression. We consider first by considering the different functions of Boolean functions.

(Subscript[∀, n⩾1])   let     (F^n) = { f | f : (ℬ^(n ))⟶ ℬ }  , where   ℬ = {0,1}

Example 2.1. List all the elements of (F^1) and (F^2) 
(F^1):  x ∈ ℬ ‘ = ℬ = {0,1}.

makeTextTable[{{"x","(Subscript[f, 0])","(Subscript[f, 1])","(Subscript[f, 2])","(Subscript[f, 3])"},{"0","0","0","1","1"},{"1","0","1","0","1"}}]

for (F^2):

t7 = makeTextTable[{{"(Subscript[x, 1])","(Subscript[x, 2])","(Subscript[f, 0])","(Subscript[f, 1])","(Subscript[f, 2])","(Subscript[f, 3])","(Subscript[f, 4])","...","(Subscript[f, 14])","(Subscript[f, 15])"},{"0","0","0","0","0","0","0","...","1","1"},{"0","1","0","0","0","0","1","...","1","1"},
{"1","0","0","0","1","1","0","...","1","1"},{"1","1","0","1","0","1","0","...","0","1"}}]

(Subscript[f, 1 ])+ (Subscript[f, 2]) = (Subscript[f, 3]),
(Subscript[f, 1 ])+ (Subscript[f, 14]) = (Subscript[f, 15]),
(Subscript[f, 3 ]). (Subscript[f, 4]) = (Subscript[f, 0]),
(Subscript[f, 3])’ = (Subscript[f, 12])

The # of functions in (F^n) is (2^(2^n)).

2.1. Minterms

Since a large number of possible functions for few Boolean Variables, we look for a method of representing them in a canonical form, called set of minters. 

Definition 2.1.1. A minterm is a Boolean function that has exactly one 1 in its truth table.

Example 2.1.1.

g3=Grid[{{makeTextTable[{{"x","y","z","m(x,y,z)"},
{"0","0","0","0"},
{"0","0","1","0"},
{"0","1","0","0"},
{"0","1","1","1"},
{"1","0","0","0"},
{"1","0","1","0"},
{"1","1","0","0"},
{"1","1","1","0"}
}],
 " ⟹  m(x,y,z) = 1  only if x=0, y=1, z=1 ⟹  m(x,y,z) = x'.y.z"
}}]

This is the product representation of the minterm, only conjunction and negation.

2.2 Normal form

Any minterm can be written or expressed only in terms of “and” and “negation”. The next step is to show that any Boolean function can be written as a disjunction of minterms, “sum of Products”.

Theorem 2.2.1. Every Boolean function can be expressed as a disjunction of minterms.

Example 2.2.1.

g4 = Grid[{{makeTextTable[{{"x","y","z","f(x,y,z)"},
{"0","0","0","1"},
{"0","0","1","0"},
{"0","1","0","0"},
{"0","1","1","1"},
{"1","0","0","1"},
{"1","0","1","0"},
{"1","1","0","0"},
{"1","1","1","1"}
}],
 " ⟹ f(x,y,z) = x'.y'.z' + x'.y.z + x.y'.z' + x.y.z "
}}]

2.3. Complete set of operators

Any Boolean Algebra can be represented in terms of “+”, “.” , “ ’ ” . All sets of operators that are sufficient to represent all Boolean expressions is called Complete Set of Operators. 

{+, . , ‘ } is complete set of operators 
{. , ‘ } is also complete set of operators. 

NAND defined as not and is also a Complete Set of operation.

3. Minimization of Boolean Expressions

Now, not only we are interested in finding a form of a set of product, but we want a simpler expression that is equivalent to the original one. This can be done with the use of Karnaugh map.

Karnaugh map with 3 variables

t8 = makeTextTable[{{"","xy","xy'","x'y'","x'y"},{"z"," "," "," "," "},{"z'"," "," "," "," "}}]

Karnaugh map with 4 variables

t9 = makeTextTable[{{"","xy","xy'","x'y'","x'y"},
{"zw"," "," "," "," "},
{"z'w"," "," "," "," "},
{"z'w'"," "," "," "," "},
{"zw'"," "," "," "," "}
}]

Example 3.1. f(x,y,z) = x’y’z’ + x’yz + xy’z’ + xyz’ + xyz

r1=Row[{makeTextTable[{{"","xy","xy'","x'y'","x'y"},{"z","1"," "," ","1"},{"z'"," ","1","1"," "}}],"   f(x,y,z) = yz + y'z'"}]

Example 3.2.

r2 = Row[{makeTextTable[{{"","xy","xy'","x'y'","x'y"},{"z","1"," "," ","1"},{"z'","1"," "," ","1"}}],"   f(x,y,z) = x"}]

Example 3.3.

r3 = Row[{makeTextTable[{{"","xy","xy'","x'y'","x'y"},
{"zw","1"," "," ","1"},
{"z'w"," ","1","1"," "},
{"z'w'"," ","1","1"," "},
{"zw'","1"," "," ","1"}
}],"  f(x,y,z,w) = z'y' + yz"
}]

4. Switching Theory

Application to binary devices. Combinational devices or network.

Basic combinational circuit - Gates;

p1=;
p2=;
p3 =;
p4=;
g5 = Grid[{{"OR gate","NOT gate/inverter","AND gate","NAND gate"},{p1,p2,p3,p4}}]

Composed circuits - logical network

p5=;
Print[p5];

Example 4.1. 
A hall light is controlled by two light swiches one at each eand. Find (a) a truth function (b) a Boolean Expression (c) a logic network that allows the light to be swiched on or off by either side.

a=Grid[{{"(Subscript[x, 1])","(Subscript[x, 2])","f((Subscript[x, 1]),(Subscript[x, 2]))"},{"0","0","0"},{"0","1","1"},{"1","0","1"},{"1","1","0"}},Frame->{{True,True,True},{True}}];
b="(Subscript[x, 1])(Subscript[x, 2])' + (Subscript[x, 1])'(Subscript[x, 2])";
c=;
r4 = Row[{"a)  ",a,"    b)    ",b,"     c)    ",c}]

Example 4.2.
A mail order cosmetic firm, an automatic contro; device is used to supervise the package of orders. The firm sells lipstick, perfume, makeup and nail polish. As a bonus item, shampoo is included with any order that includes perfume or any order that includes lipstick, makeup, and nail polish. How can we design the logic network that control wheter shampoo is packaged with an order ?

Input to the network : 4 items 

(Subscript[x, 1 ]): lipstick
(Subscript[x, 2 ]): perfume
(Subscript[x, 3 ]): makeup
(Subscript[x, 4 ]): nail polish

(Subscript[x, i]) = 1   ⟹    item is ordered.
f((Subscript[x, 1 ]),(Subscript[x, 2 ]),(Subscript[x, 3 ]),(Subscript[x, 4 ])) = 1    ⟹    shampoo to be included.

p6=;
r5 = Row[{
Grid[{
{"(Subscript[x, 1])","(Subscript[x, 2])","(Subscript[x, 3])","(Subscript[x, 4])","f((Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3]),(Subscript[x, 4]))"},
{"0","0","0","0","0"},
{"0","0","0","1","0"},
{"0","0","1","0","0"},
{"0","0","1","1","0"},
{"0","1","0","0","1"},
{"0","1","0","1","1"},
{"0","1","1","0","1"},
{"0","1","1","1","1"},
{"1","0","0","0","0"},
{"1","0","0","1","0"},
{"1","0","1","0","0"},
{"1","0","1","1","1"},
{"1","1","0","0","1"},
{"1","1","0","1","1"},
{"1","1","1","0","1"},
{"1","1","1","1","1"}
}
,Frame->{{True,True,True,True,True},{True}}]
,"    ",p6}]