Transcript Min terms and logic expression

An algebraic structure
• An algebraic structure consists of
– a set of elements B
– binary operators {+, .}
– and a unary operator { ‘ }
• Such that following holds
– Membership: B contains at least two elements a and b
– Closure:
a+b is in B
and
a.b is in B
– Commutativity: a+b = b+a
and
a.b = b.a
– Associativity: a+(b+c)=(a+b)+c and a.(b.c) = (a.b).c
– Identity
a+0 = a
and
a.1=a
– Distributivity: a+(b.c) = (a+b).(a+c) and a.(b+c)=(a.b)+(a.c)
– Complementarity: a+a’=1
and
a.a’=0
1
Boolean algebra and its axioms and theorems
• Besides being an algebraic structure other useful axioms and
theorems are
– Null:
x+1 = 1
and
x.0 = 0
– Idempotency: x+x = x
and
x.x = x
– Involution:
(x’)’ = x
– Uniting:
x.y+x.y’=x
and
(x+y).(x+y’)=x
– Absorption:
x+x.y=x
and
x.(x+y)=x
– (another form): (x+y’).y=x.y
and
(x.y’)+y=x+y
– de Morgan’s:
(x+y+..)’=x’.y’... and
(x.y…)’=x’+y’+….
– Generalized de Morgan’s:
• f’(x1,x2,…,xn,0,1,+,.) = f(x1’,x2’,…,xn’,1,0,.,+)
2
Duality axioms and theorems
• Duality
– A dual of a Boolean expression is derived by replacing . by
+, + by ., 0 by 1, and 1 by 0 and leaving variables unchanged
– Any theorem that can be proven is thus also proven for
– a meta-theorem (a theorem about theorems)
– duality: (x+y+…)D=x.y…… and (x.y….)D = x+y+…
– general duality: fD(x1,x2,…,xn,0,1,+,.) = f(x1,x2,…,xn,1,0,.,+)
– multiplication and factoring:
• (x+y).(x’+z) = x.z+x’.y and
x.y+x’.z=(x+z).(x’+y)
– Consensus:
• (x.y)+(y.z)+(x’.z)=x.y+x’z and (x+y).(y+z).(x’+z)=(x+y).(x’+z)
3
Proving theorems
• Prove x.y+x.y’=x
• distributivity:
• complementarity:
• identity:
• Prove x+x.y = x
• identity:
• distributivity:
• identity:
• identity:
• NOR is equivalent of AND
• (x+y)’ = x’.y’
• NAND is equivalent of OR
• (x.y)’ = x’+y’
x.y+x.y’ = x.(y+y’)
x.(y+y’) = x.(1)
x.(1) = x
x+x.y = x.1+x.y
x.1+x.y = x.(1+y)
x.(1+y) = x.(1)
x.(1) = x
4
And now try some harder problem
• Simplify Boolean expression for carry function in a 3-bit adder
• Cout = a’.b.cin + a.b’.cin + a.b.cin’ + a.b.cin
– Each of the first, second, and third term can be combined
with the last term
– Use identity to make copies of the last term 3 times (x+x=x)
– Cout = a’.b.cin + a.b’.cin + a.b.cin’ + a.b.cin + a.b.cin + a.b.cin
– Use associativity to bring terms together
– Cout = a’.b.cin + a.b.cin + a.b’.cin + a.b.cin + a.b.cin’ + a.b.cin
– Then use distributivity to combine terms
– Cout = (a’+a).b.cin + (b’+b).a.cin + a.b.(cin’+cin)
– Next use complementarity to reduce
– Cout = (1).b.cin + (1).a.cin + a.b.(1)
– Finally using identity gives Cout = b.cin + a.cin + a.b
5
Multiple forms and equivalence
•
•
•
•
Canonical Sum-of-Product form
Canonical Product-of-sum form
How to convert one from other?
Minterm expansion of F to minterm expansion of F’
– Just take the terms that are missing
F ( A, B, Cin)   m(1,2,4,7)
F ' ( A, B, Cin)   m(0,3,5,6)
• Maxterm expansion of F to maxterm expansion of F’
– Just take the terms that are missing
F ( A, B, Cin)   M (0,3,5,6) F ' ( A, B, Cin)   M (1,2,4,7)
6