Homework solutions for Chapter 2 suggested exercises (Mano & Kime, 2nd edition) =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 2-1: Demonstrate by means of truthtables Points to remember: 1. truth tables ARE proof 2. proof by truthtable is time intensive -- it is better to simplify first. 3. group, then analyze (make it as mechanical as possible) (a) Demorgan's Theorem for three variables: (XYZ)' = X' + Y' + Z' X Y Z XYZ (XYZ)' X'+Y'+Z' 0 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 Observe that the general form (the negation of some expression ABCDEF...XYZ) will follow the same pattern. Why? (b) X + YZ = (X+Y)(X+Z) (algebraic solution: XX+XY+XZ+YZ = X(1+Y+Z)+YZ = X+YZ) (speed tip: note that in + sets you should scan & fill in the leftmost variable first, marking as true, then the rightmost (alternating), and so on -- e.g., in X+YZ below you can fill in the bottom four 1's automatically) truth table: X Y Z YZ X+Y X+Z (X+Y)(X+Z) X+YZ 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 (c) X'Y + Y'Z + XZ' = XY' + YZ' + X'Z Speed: use the leftmost variable in the truth table to isolate sections of the table where the pairs COULD be positive (X is the top half, X' is the bottom half, Z is every even row, Z' is every odd row) and then check the other variable in the pair. Only filling out 1's to illustrate: X Y Z X'Y Y'Z XZ' A XY' YZ' X'Z B 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 2-2 Prove by algebraic manipulation (a) AB + AB' + A'B' = A + B' Factor A or factor B? NO. Factor BOTH: AB+AB'+AB'+A'B' = A(B+B')+B'(A+A') = A+B' ^^^^ A+A = ? A! (b) Y'Z + YZ' + YZ + Y'Z' =1 (Let's reason this one out: if YZ, 1 if neither, 1 if Y', Z one or if Y, Z' the other) by algebra: Y'Z + YZ' + YZ + Y'Z' = 1 FACTOR: Y'(Z+Z') + Y(Z+Z') = 1 Y' + Y = 1 1 = 1 (c) A'+AB+AC'+AB'C' = A' + B + C' FACTOR LARGEST GROUP FIRST: A'+AB+A(C'+B'C') <-- C'+B'C'? Saw this one above. A'+AB+A(C'(1+B')) = A'+AB+AC' A'+A(B+C') = <-- same trick = (A'+A)(A'+B+C') A'+A? 1. 1(anything) = anything = A'+B+C' (d) YZ'+X'Z'+X'Y' = YZ'+X'Y' same trick: want to factor twice. Take: X'Z'(Y+Y') = X'Z'Y + X'Z'Y' X'YZ' + X'Y'Z' + YZ' + X'Y' <-- YZ' and X'YZ' = YZ'(1+X) = YZ' YZ' + X'Y'Z' + X'Y' <-- ditto, for X'Y' YZ' + X'Y'(1 + Z') = YZ' + X'Y' =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 2-3 Prove by Algebraic Manipulation (a) A'B'D+A'B'CD'+A'C'D' + AB' = B'+A'C'D' expand with ANDs FACT: ABC = ABCD + ABCD' then expand the original: A'BC'D'+A'B'C'D' + A'B'CD+A'B'C'D + A'B'CD' + AB' = double A'B'C'D', group, factor C'AB'+A'C'D'+A'B'(1)+AB' = A'B'+AB'+A'C'D' = B'+A'C'D' done (b)XZ+WY'Z'+W'YZ'+W'YZ'+WX'Z'=XZ+WY'Z'+WXY'+W'XY+X'YZ' Both are huge. Suggestion: always work from both sides. (Solving LHS only:) = (WXZY + WXZY' + W'XZY + W'XZY') + (see above) (WY'Z'X + WY'Z'X') + (W'Z'YX + W'YZ'X') + (WX'Z'Y + WX'Z'Y') expand, group, factor = XZ+WY'Z'(1) + WXY'(1) + W'XY(1) + X'YZ'(1) = XZ+WY'Z'+WXY'+W'XY+X'YZ' done (c) CD+AB'+AC+A'C'+A'B+C'D = (A'+B'+C+D')(A+B+C'+D) Same as above, but complement both sides and apply DeMorgan's first =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- 2-4 IMPORTANT FOR FUTURE CLASSES! Expanding definition of boolean AND/OR/NOT to binary strings Goal: define AND/OR/NOT for binary strings _of equal length_ Solution: Define all operations as _bitwise operations_ (a) Define OR as the bitwise OR of each bit in the string: For bytes A, B define A+B s.t. for all bit indices i, 0<=i<=7, let (A+B)i = Ai+Bi (1010 + 0101 = 1111) (b) Define AND as the bitwise AND of each bit in the string: For bytes A, B define AB s.t. for all bit indices i, 0<=i<=7, let (AB)i = AiBi (1010 + 0101 = 0000) (c) Define NOT as the bitwise NOT of each bit in the string: For a byte A, define A' s.t. for all bit indicex i, 0<=i<=7, let A'i = (Ai)' (1010' = 0101) (d) Properties of "1" in ordinary boolean algebra: A+1 = 1 (A)(1) = A To preserve these properties, define the 1 for a string of length t as a string of 1's. (Prove this.) (e) Properties of "0" in ordinary boolean algebra: A+0 = A (A)(0) = 0 To preserve these properties, define the 0 for a string of length t as a string of 0's. (Prove this.) (Bitwise XOR follows the same pattern: 1010 XOR 0101 = 1111. Note that this does NOT have the "obvious" property of XOR in that an "even number of ones" = 0 -- the property is not preserved for strings, only individual bit positions.) =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 2-5 Simplify to minimum number of literals: (a) ABC+ABC'+A'B factor largest group = AB(C+C')+A'B = B(A+A') = B (b) (A+B)'(A'+B) can't do anything until we lose the group' = A'B'(A'+B) multiply it out = A'A'B'+A'B'B' = A'B'+A'B' = A'B' (c) A'BC+AC expand A'BC+ABC+AB'C expand (A'BC+ABC)+(ABC+AB'C) now factor BC(1) + AC(1) eliminate BC+AC (d) BC+B(AD+AD') nothing obvious, expand BC+ABD+ABD' could eliminate D, nothing else BC+AB(1) BC+AB (e) (A+B'+AB')(AB+A'C+BC) expand AAB+AA'C+ABC+ABB'+A'B'C+BB'C+AABB'+AA'B'C+ABB'C lots of zeroes here AB 0 ABC 0 A'B'C 0 0 0 0 AB+ABC+A'B'C = factor largest group AB(1+C) + A'B'C AB+A'B'C =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 2-6 Reduce and simplify as indicated (a) X'Y'+XYZ+X'Y to three literals, factor X'(Y'+Y)+XYZ reduce X'+XYZ real factoring (HARD, practice - goal is to factor s.t. terms cancel as needed) (X'+XY)(X'+Z) hard: FACT: (X'+XY) = (X'+X)(X'+Y) = X'X'+X'Y+X'X+XY = X'+XY (good one for memorization) proceed: (X'+Y)(X'+Z) re-merge X'+YZ (b) X+Y(Z+(X+Z)') to two literals, first DeMorgan X+Y(Z+X'Z') expand X+X'YZ'+YZ real factoring (HARD - YZ in both terms) X+(YZ+X')(YZ+YZ') factor X+(YZ+X')(Y(Z'+Z)) factor X+(YZ+X')(Y) X+YYZ+YX' X+YZ+YX' want to remove X or Y, X (X+X')(X'+Y)+YZ simplify (1)(X'+Y)+YZ simplify X'+Y+YZ factor Y(1+Z)+X' Y+X' done (c) W'X(Z'+Y'Z)+X(W+W'YZ) to one(!) literal XW'Z'+XW'ZY'+XW'YZ+XW factor largest XW'(Z'+ZY'+YZ)+XW regroup, factor XW'(Z'+Z(1))+XW eliminate XW'(1+1)+XW XW'+XW easy now X(W'+W) X (d) (AB+A'B')(C'D'+CD) + (AC)' can't do anything, expand ABC'D' + A'B'C'D' + ABCD + A'B'CD + AC group and factor largest (AC)' + C'D'(AB+A'B') + CD(AB+A'B') two of same problem (familiar) This one's worth looking at: A B AB A'B' S 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 Which is also (A xor B)' Continuing: ABC'D' + A'B'C'D' + ABCD + A'B'CD + (AC)' = expand & factor A'+C'+ABCD = still at 6, goal is 4 expand ... But before expanding we can tell what the answer is. A'+C'+ABCD is true when: A' ALWAYS C' ALWAYS BD when A,C then the answer is A'+C'+BD (prove it) =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 2-7 Express as OR, AND: F=A'B'+AB+B'C' (a) OR gates: fact: (F')' = F (A'B'+AB+B'C')' = (A+B)(A'+B')(B+C) = F' ((A+B)(A'+B')(B+C))' = (F')' = F use grouping: (A+B)'+(A'+B')'+(B+C)' = F. (b) AND gates: Same story. (A+B)'+(A'+B')'+(B+C)' = F. (A'B')(AB)(B'C') = F' ((A'B')(AB)(B'C'))' = F'' <- STOP HERE. F'' = F. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 2-8 Find the complement (a) AB'+A'B (XOR!) (AB'+A'B)' = ((AB')'(A'B)') = (A'+B)(A+B') (b) group and do each in turn (V'W+X)Y+Z = ((V'W+X)Y)'(Z)') = (Z')(Y'+(V'W+X)') = Z'Y'+Z'((V'W)'X') = Z'Y' + Z'X'(V+W') (c) looks complex but still just grouping: WX(Y'Z+YZ')+W'X'(Y'+Z)(Y+Z) = (WX(Y'Z+YZ'))'(W'X'(Y'+Z)(Y+Z))' = ((WX)'+(Y'Z+YZ')')((W'X')'+(Y'+Z')'+(Y+Z)') = ((W'+X'+(Y+Z')(Y'+Z))(W+X+YZ+Y'Z') =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 2-12 (see graphic (postscript version)) mechanical method (no thought required): 1) Draw all inputs in column 2) Negate all inputs which appear negated in formula 3) Draw output line 4) group the formula into pairs [ parenthesize: a(b(c(de))) ] 5) Draw each pair 6) Link the pairs together with sets of AND or OR gates =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 2-11 is also a good problem to try. See 2-7 for a suggestion on how to approach it. It is worth knowing how to build any of the fundamental gates from only NAND and NOR gates.