Transcript Boolean Algebra

Combinational logic
--- outputs logical functions of inputs
--- new outputs appear shortly after changed inputs
(propagation delay)
--- no feedback loops
--- no clock
Sequential logic
--- outputs logical functions of inputs and previous
history of circuit (memory)
--- after changed inputs, new outputs appear in
the next clock cycle
--- frequent feedback loops
Fundamentals of Boolean algebra

Named after George Boole


He presented an algebraic formulation of the
process of “logical thought and reason”
This formulation come to be known as
Boolean Algebra
Postulates of Boolean algebra
1)
Definition


A Boolean algebra is a closed algebraic
system containing a set K of two or more
elements and the two operators ‘•’ or ‘/\’ or
‘’, called AND, and ‘+’ or ‘\/’ or ‘’, called
OR;
Closed system: for every a and b in set K,
a•b belongs to K and a+b belongs to K.
Postulates of Boolean algebra
2)
Existence of 1 and 0

There exist unique elements 1 (one) and 0
(zero) in set A" such that for every a in K
a) a + 0 = a,
b) a • 1 = a,

where 0 is the identity element for the +
operation and 1 is the identity element for
the • operation.
Postulates of Boolean algebra
3)
Commutativity of the + and • operations

For every a and b in K
a) a + b = b + a.
b) a • b = b • a
4)
Associativity of the + and operations

For every a, b, and c in K
a) a + (b + c) = (a + b) + c.
b) a • (b • c) = (a • b) • c.
Postulates of Boolean algebra
5)
Distributivity of + over • and • over +

For every a, b, and c in K
a) a + (b • c) = (a + b) • (a + c),
b) a • (b + c) = (a • b) + (a • c).
6)
Existence of the complement

For every a in K there exists a unique
element called ā (complement of a) in K
such that
a) a + ā = 1.
b) a • ā = 0.
Venn diagrams for the postulates
• Operations on sets
Sets  closed regions
Sets correspond to elements
Intersection  corresponds to •
Union  corresponds to +
Venn diagrams for the postulates
Venn diagrams
Examples of Venn diagrams
Venn diagrams
a + b • c = (a + b) • (a + c)
Venn diagrams
a + b • c = (a + b) • (a + c)
Boolean algebra
• Duality
– If an expression
f(x1, x2, … xn, +, •, 0, 1)
is valid, then
f(x1, x2, … xn, •, +, 1, 0)
obtained by interchanging + and •, 0 and 1 is also
valid
a • (b + c) = (a • b) + (a • c)
a + (b • c) = (a + b) • (a + c)
Postulates 2 – 6 are stated in dual form
Fundamental theorems of Boolean
algebra
– Prove part (b) by exchanging + with •, and use the
dual form of the postulates
Fundamental theorems of Boolean
algebra
Fundamental theorems of Boolean
algebra
a•ā=0
a+ā=1
[P6(b)]
[P6(a)]
Therefore, ā is the complement of a, and also a is the
complement of ā. Because the complement of ā is
unique, it must be equal to a.
Fundamental theorems of Boolean
algebra
Fundamental theorems of Boolean
algebra
• Why a + ab = a
a
ab
b
Fundamental theorems of Boolean
algebra
Fundamental theorems of Boolean
algebra
Fundamental theorems of Boolean
algebra
Fundamental theorems of Boolean
algebra
Fundamental theorems of Boolean
algebra
Fundamental theorems of Boolean
algebra
• Example using DeMorgan’s theorem
Fundamental theorems of Boolean
algebra
Boolean algebra postulates and
theorems
Theorems
Proofs by exhaustion:
Let variables
assume
all possible values and show
• Proofs
by perfect
induction
validity of result in all cases
Example: Show X + 0 = X
(a) Keep axioms handy
(b) Elaborate cases:
if X = 0, have
X+0=0+0=0=X
if X = 1, have
X+0=1+0=1=X
X 1 X  0
X  0  X 1
X  0  X '1
X 1 X ' 0
00  0
11  1
11  1
00  0
0 1  1 0  0
0 1  1 0  1
More Theorems
Can prove by exhaustion....but have more cases
For distributive laws,
T8 looks like ordinary algebra
T8’ also true (swap operators, factor, swap back)
T9, T10 for logic minimization - drop irrelevant terms
T9, T10, T11 for logic minimization - drop superfluous terms
T9 (Covering): X + XY = X and X(X+Y)=X
Proof: X + XY = X1 + XY = X(1+Y) = X1 = X
X(X+Y) = (X+0)(X+Y) = X+(0Y) = X+0 = X
T10 (Combining): XY + XY’ = X and (X + Y)  (X + Y’) = X
Proof: XY + XY’ = X(Y + Y’) = X1 = X
(X + Y)(X + Y’) = X + (YY’) = X + 0 = X
T11 (Consensus): XY+X’Z+YZ = XY+X’Z and (X+Y)(X’+Z)(Y+Z)= (X+Y)(X’+Z)
Proof: If YZ = 0
XY+X’Z+YZ = XY+X’Z+ 0 = XY+X’Z
else
Y=Z=1
left side: XY+X’Z+YZ = something + YZ = something + 1 =1
right side: XY+X’Z = X + X’ = 1
So, in either case, XY+X’Z+YZ = XY+X’Z
If Y+Z = 1
(X+Y)(X’+Z)(Y+Z)= (X+Y)(X’+Z)1= (X+Y)(X’+Z)
else
Y=Z=0
left side: (X+Y)(X’+Z)(Y+Z)= something  (Y + Z) = something  0 = 0
right side: (X+Y)(X’+Z) = (X+0)(X’+0) = XX’ = 0
So, in either case, (X+Y)(X’+Z)(Y+Z)= (X+Y)(X’+Z)
Duality
• De Morgan’s Theorems:
(X + Y)’ = X’  Y’
(X  Y)’ = X’ + Y’
• Dual: Swap 0 & 1, AND & OR, but leave variables unchanged
– Result: Theorems still true
• Why?
– f(X, Y) = g(X, Y)
– complement[f(X, Y)] = complement[g(X, Y)]
– dual[f(X’, Y’)] = dual[g(X’, Y’)]
– but X’, Y’ just dummy variables, replace with originals
• Counterexample?
X + (X  Y) = X (T9)
X + X  Y = X (T9)
X  (X + Y) = X (dual)
X  X + Y = X (dual)
(X  X) + (X  Y) = X (T8)
X + Y = X (T3)
X + (X  Y) = X (T3)
!! error ?
parentheses,
operator precedence
N-variable Theorems
• Prove via induction
• Most important: DeMorgan theorems
DeMorgan Symbol Equivalence
Bubble-pushing...
Likewise for OR