Chapter 2: Boolean Algebra and Logic Gates

1 1cs309 cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceChapter 2: Boolean Algebra andLogic Gatescs309 cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceBoolean AlgebraThe algebraic system usually used to work with binary Logic expressionsPostulates:1. Closure:Any defined operation on (0, 1) gives (0,1)2. Identity:0 + x = x ; 1 x = x3. Commutative:x + y = y + x ; xy = yx4. Distributive:x (y + z) = xy + xz; x + (yz) = (x + y)(x + z)5. Def of Complement:x + x = 1;x x = 06. At least 2 elements (0 and 1)Precedence rule: (1) parentheses(2) NOT(3) AND(4) cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceThe Duality Principle A Boolean expression that is always true is still true if we exchange OR with AND and 0 with 1 Examples:x + x = 1so: xx = 0x + y = y + xso: xy = yxNote that we cannot use Duality to say thatx + y =1, so xy = 0 Why not?

2 Cs309 cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceUseful Postulates and Theorems(a)(b)Postulate 2x + 0 = xx 1 = xPostulate 5x + x = 1xx = 0 Theorem 1x + x = xxx = xTheorem 2x + 1 = 1x 0 = 0 Theorem 3 (involution)(x ) = xPostulate 3 (commutative)x + y = y + xxy = yxTheorem 4 (associative)x + (y + z) = (x + y) = zx(yz) = (xy)zPostulate 4 (distributive)x(y + z) = xy + xzx + yz = (x + y)(x + z)Theorem 5 (deMorgan s Law)(x + y) = x y (xy) = x + y Theorem 6 (absorption)x + xy = xx (x + y) = cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceProving the TheoremsExample:Theorem 1: x + x = x; xx = xProof:x + x = (x + x) 1postulate 2(b)= (x + x)(x + x )5(a)= x + xx 4(b)= x + 05(b)= x2(a)xx = x by dualitycs309 cs309 G.

3 W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceProving by Truth TableTwo Boolean expressions are equal in all cases if and only if they have the same Truth Table. (You may use this to prove the expressions are equal unless I say otherwise).Example:Prove deMorgan s Law: (x + y) = x y x y (x + y) (x + y) x y x y 0 0 0 1 1110 1 1010010 100101 1 10000 The Truth Table of (x + y) is equal to the Truth Table of x y , so we know that (x + y) = x y for all values of x and cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceBoolean functions and circuit equivalentscs309 cs309 G.

4 W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceImplementing a Boolean expression as a circuitF1 = x + y zxy zF1F1xy zF1xzy zy zy y5cs309 cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceSimplifying expressions There are many different ways to write the same expression Example: x y z + x yz + xy = xy + x z Different forms of the expression will require different numbers of Gates to implement Proof? See page 45 in text Generally, longer expressions with more terms require more Gates and/or more complex Gates More Gates higher power, higher cost, larger size, .. So finding a way to simplify expressions will pay off in terms of the circuits we designcs309 cs309 G.

5 W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceA metric for use in simplifying expressions Define a literal as each occurrence of a variable in the expression Example: F2 = x y z + x yz + xy 8 literals If we can write the expression with fewer literal, we will consider it to be simpler (and to take fewer Gates ). Note that this is a rule of thumb and does not always give an optimum answer6cs309 cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceSimplifying expressions using the postulates and theorems of Boolean AlgebraFrom page 46-47 of (x + y) (3 literals)= xx + xyp4a= 0 + xyp5b= xyp2a (2 literals) + x y= x+yThe dual of (1)3.

6 (x + y)(x + y )(4 literals)= x + yy p4b= x + 0p5b= xp2a (1 literal) + x z + yz(6 literals)= xy + x z + yz(1)p2b= xy + x z + yz(x + x )p5a= xy + x z + yzx + yzx p4a= xy + x z + xyz + x zyp3b twice= xy + xyz + x z + x zyp3a twice= xy1 + xyz + x z1 + x zyp2b twice= xy(1 + z) + x z(1 + y)p4a twice= xy1 + x z1T2a twice= xy + x zp2a twice(4 literals)5.(x+y)(x +z)(y+z) = (x+y)(x +z)The dual of (4)TheConsensusTheoremcs309 cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceComplementing a functiondeMorgan s Law says:(x + y) = x y To take(A + B + C) Let y = B+CThen (A + B + C) = (A + y) = A y = A (B + C) = A B C In general:(A+B+C+D+..) = A B C D .. ;( ) = A +B +C +D ..A more complex function:F = x yz + x y zF = (x yz + x y z) = (x yz ) (x y z) = (x + y + z)(x + y + z )7cs309 cs309 G.

7 W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceA shortcut for complementing a functionTo complement a function, you can take the dual of the function, and complement each the previous example:F = x yz + x y zdual of F= (x + y + z )(x + y + z)so F = (x + y + z)(x + y + z )cs309 cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceStandard forms of Boolean Expressions8cs309 cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceDefinitions Product terma term consisting of literals ANDed together Example: AB F Minterma Product term in which all variables appear Example: ABC D where A,B,C, and D are the variables of the function Sum terma term consisting of literals ORed together Example: A + B + F Maxterma Sum term in which all variables appear Example: A + B + C + D where A, B, C, and D are the variables of the functioncs309 cs309 G.

8 W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceSOP and Canonical SOP Form A function is in Sum of Products (SOP) form if it is written as product terms ORed together Example: f(x y z) = xy z + xz + y A function is in Canonical SOP form if it is in SOP form and all terms are minterms Example:g(x y z) = xy z + x yz + xyz9cs309 cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer SciencePOS and Canonical POS form A function is in Product of Sums (POS) form if it is written as sum terms ANDed together Example:f(x y z) = (x + y + z) ( x + z ) (y) A function is in Canonical POS form if it is written in POS form and all terms are Maxterms Example:g(x y z) = (x + y + z ) ( x + y + z)cs309 cs309 G.

9 W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceMinterms and the Truth TableEach row of a Truth Table corresponds to a mintermx y z f(x y z) minterm0 0 0 0 m0x y z 0 0 1 1 m1x y z0 1 0 0 m2x y z 0 1 1 0 m3x y z1 0 0 1 m4x y z 1 0 1 1 m5x y z1 1 0 0 m6x y z 1 1 1 1 m7x y zf(x y z) = x y z + xy z + xy z + x y z The 1 s of the Truth Tableshow the minterms that arein the Canonical SOP expressionMinterm List Form: f(x y z) = m(1, 4, 5, 7)10cs309 cs309 G. W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceExamplesx y z f(xyz)0 0 0 00 0 1 10 1 0 00 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1f(x y z) = x y z + xy z + xyz= m(1,4,7)A B C D g(ABCD)0 0 0 0 00 0 0 1 10 0 1 0 00 0 1 1 00 1 0 0 00 1 0 1 00 1 1 0 00 1 1 1 01 0 0 0 01 0 0 1 01 0 1 0 11 0 1 1 01 1 0 0 01 1 0 1 11 1 1 0 01 1 1 1 0g(A B C D) = A B C D + AB CD + ABC D= m(1, 10, 13)cs309 cs309 G.

10 W. Cox Spring 2010 The University Of Alabama in Huntsville Computer ScienceThe University Of Alabama in Huntsville Computer ScienceMaxterms and the Truth TableEach row of a Truth Table corresponds to a maxtermx y z f(x y z) Maxterm0 0 0 0 M0x + y + z0 0 1 1 M1x + y + z 0 1 0 1 M2x + y + z0 1 1 0 M3x + y + z 1 0 0 1 M4x + y + z1 0 1 1 M5x + y + z 1 1 0 0 M6x + y + z1 1 1 1 M7x + y + z f(x y z) = (x+y+z)(x+y +z)(x +y +z )The 0 s of the Truth Tableshow the maxterms that arein the Canonical POS expressionMaxterm List Form: f(x y z) = M(0,3,6)Note the differences from the way minterms are complemented11cs309 cs309 G.