Katz 2.8c [2 pts]
Verify that (XY' + X'Y)' and XY' + X'Y are duals of each other.
First, find the dual of XNOR:
((X*Y') + (X'*Y))' <=> ((X+Y') * (X'+Y))' (16)
Then, convert the dual using generalized deMorgan's:
((X+Y') * (X'+Y))' = (X'*Y) + (X*Y') (15)
= XY' + X'Y commutativity (6)
This is XOR which is thus dual of XNOR.
Katz 2.8d [2 pts]
Verify that (XY' + X'Y)' = XY + X'Y'.
(XY' + X'Y)' = (X'+Y) * (X+Y') generalized deMorgan's law (15)
= (X'+Y)*X + (X'+Y)*Y' distributivity (8)
= X'X + YX + X'Y' + YY' similarly
= 0 + XY + X'Y' + 0 complementarity (5D), commutativity (6D)
= XY + X'Y' identity (1)
Katz 2.10e [1 pt]
Compute complement of (X+Y)*Z
((X+Y)*Z)' = (X+Y)' + Z' = X'*Y' + Z'
Katz 2.10f [1 pt]
Compute complement of X+(Y*Z)'
(X+(Y*Z)')' = X'*(Y*Z)'' = X'*Y*Z
Katz 2.10g [1 pt]
Compute complement of X * (Y + ZW' + V'S)
(X * (Y + ZW' + V'S))' = X' + (Y + ZW' + V'S)' = = X' + Y'(ZW')'(V'S)' = X' + Y'(Z' + W)(V + S')
Katz 2.11a [3 pts]
Form the complement of (A+(BCD)')*((AD)'+B(C'+A))
( (A+(BCD)')*((AD)'+B(C'+A)) )' = (A+(BCD)')' + ((AD)'+B(C'+A))' deMorgan's (14D) = A'*(BCD)'' + (AD)''*(B(C'+A))' deMorgan's (14) twice = A'BCD + AD(B'+C*A') involution (4), generalized deMorgan's (15) = A'BCD + AB'D + AA'CD distributivity (8), commutativity (6D) = A'BCD + AB'D complementarity (5D), null(2D), identity (1)
Katz 2.11b [3 pts]
Form the complement of AB'C + (A'+B+D)(ABD'+B')
( AB'C + (A'+B+D)(ABD'+B') )' = (A'+B+C') * (AB'D'+(A'+B'+D)*B) generalized deMorgan's (15) = (A'+B+C') * (AB'D' + A'B + BB' + BD) distributivity (8) = (A'+B+C') * (AB'D' + A'B + BD) complementarity/null/identity = AA'B'D' + A'A'B + A'BD + ABB'D' + A'BB + BBD + AB'C'D' + A'BC' + BC'D = A'B + A'BC' + A'BD + BD + BC'D + AB'C'D' = A'B + BD + AB'C'D'
Katz 2.13a [1 pt]
Simplify XY+XY'
XY+XY' = X*(Y+Y') distributivity (8)
= X*1 complementarity (5)
= X identity (1D)
That's 1 literal.
Katz 2.13b [1 pt]
Simplify (X+Y)*(X+Y')
Let's derive this from the previous one using duality: XY+XY' = X <=> (X+Y)*(X+Y') = X So simplified form is again 1 literal.
Katz 2.13c [1 pt]
Simplify YZ'+X'YZ+XYZ
YZ'+X'YZ+XYZ = YZ' + YZ uniting (9)
= Y uniting (9)
1 literal.
Katz 2.13d [1 pt]
Simplify (X+Y)(X'+Y+Z)(X'+Y+Z')
(X+Y)(X'+Y+Z)(X'+Y+Z') = (X+Y)(X'+Y) uniting (9D)
= Y uniting (9D)
1 literal.
Katz 2.13e [2 pts]
Simplify X + XYZ + X'YZ + X'Y + WX + W'X
X + XYZ + X'YZ + X'Y + WX + W'X = = (X+XYZ) + (X'YZ + X'Y) + (WX + W'X) = X + X'Y + X absorption (10) twice; uniting (9) = X + X'Y idempotency (3) = X + Y absorption (11D) 2 literals.
Katz 2.5 [5 pts]
Represent each switch as a variable taking on values 0 (say, when the
switch is down) and 1 (when it's up), thus it's a boolean variable.
Call the two switch variables A and B.
Represent the light with another boolean variable C with values 0
(when the light is off) and 1 (when it's on).
Assume that when both switches are in positions corresponding to 0,
the light is off.
The truth table then is:
A B | C
----------
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0
The boolean formula is:
C = A xor B
It can be implemented with a single XOR gate.