## CSE370 (Autumn 03) Assignment 2 Solution

1. CLD-II, Chapter 2, problem 2.2, parts b, and c.

2.2.a Draw Schematic for XY+XZ using AND,OR, and NOT gates

b. Draw Schematic for (X(Y+Z))’

2. CLD-II, Chapter 2, problem 2.4, parts a, and b.

2.4.a Draw a Schematic for (X(Y’Z’))’ using NAND gates and inverters only

b. Draw a Schematic for XY+XZ using NAND gates and inverters only

3. CLD-II, Chapter 2, problem 2.6, parts c, and d.

2.6.c Prove (X+Y’)Y = XY

(X+Y’)Y  = (XY)+(Y’Y)                                  (6b)

XY+Y’Y  = XY+0                                            (7b)

XY+0       = XY                                                (5a)

d. Prove (X+Y)(X’+Z) = X’Y + XZ

Expand:

(X+Y)(X'+Z)          = (X(X'+Z)+Y(X'+Z))          (6b)

(X(X'+Z)+Y(X'+Z) = XX'+XZ+YX'+YZ            (6b)

XX'+XZ+YX'+YZ  = 0+XZ+YX'+YZ                (7b)

0+XZ+YX'+YZ      = X'Y+XZ+YZ                    (5a)

Intuitively the YZ term is unneeded because the only way YZ

will add a 1 is if both Y and Z are 1. If Y and Z are both

replaced with 1, the equation becomes

X'(1)+X(1) = X'+X = 1                                      (7a)

Therefore YZ should be eliminated. To do this we expand YZ

by ANDing it with a 1 in the form of (X+X').

X'Y+XZ+YZ                = X'Y+XZ+YZ(X+X')   (5b,7a)

X'Y+XZ+YZ(X+X')      = X'Y+XZ+XYZ+X'YZ (6b)

X'Y+X'YZ+XZ+XYZ    = X'Y(1+Z)+XZ(1+Y)   (6b)

X'Y(1+Z)+XZ(1+Y)      = X'Y(1)+XZ(1) = X'Y+XZ

4. CLD-II, Chapter 2, problem 2.8, parts b, and d.

2.8.b Use truth tables to prove (A+B’)B = AB

 A  B B’ A+B’ (A+B’)B AB 0  0 1 1 0 0 0  1 0 0 0 0 1  0 1 1 0 0 1  1 0 1 1 1

d. Use truth tables to show that

ABC+A’BC+A’B’C+A’BC’+A’B’C’ = BC+A’B’+A’C’

 A  B  C ABC A’BC A’B’C A’BC’ A’B’C’ ALL BC A’B’ A’C’ 0  0  0 0 0 0 0 1 1 0 1 1 0  0  1 0 0 1 0 0 1 0 1 0 0  1  0 0 0 0 1 0 1 0 0 1 0  1  1 0 1 0 0 0 1 1 0 0 1  0  0 0 0 0 0 0 0 0 0 0 1  0  1 0 0 0 0 0 0 0 0 0 1  1  0 0 0 0 0 0 0 0 0 0 1  1  1 1 0 0 0 0 1 1 0 0

5. CLD-II, Chapter 2, problem 2.10, parts b, and d.

2.10.b Find the Complement of ABC+B(C’+D’)

(ABC+B(C’+D’))’             =     (ABC)’(B(C’+D’))’

(ABC)’(B(C’+D’))’           =     (A’+B’+C’)(B’+(C’+D’)’)

(A’+B’+C’)(B’+(C’+D’)’) =     (A’+B’+C’)(B’+(C’’D’’))

(A’+B’+C’)(B’+(C’’D’’))  =     (A’+B’+C’)(B’+(CD))

(A’+B’+C’)(B’+(CD))

d. Find the Complement of X+YZ’

(X+YZ’)’    = X’(YZ’)’

X’(YZ’)’    = X’(Y’+Z’’)

X’(Y’+Z’’) = X’(Y’+Z)

X’(Y’+Z)

6. CLD-II, Chapter 2, problem 2.12.

2.12 Verify that the following diagram implements an XOR function

Realized function is: (((XY)’Y)’(X(XY)’)’)’

(((XY)’Y)’(X(XY)’)’)’    = XY’+X’Y

((XY)’Y)’’+(X(XY)’)’’   = XY’+X’Y

((XY)’Y)+(X(XY)’)        = XY’+X’Y

((X’+Y’)Y)+(X(X’+Y’)) = XY’+X’Y

(X’Y+Y’Y)+(XX’+XY’) = XY’+X’Y

(X’Y+0)+(0+XY’)          = XY’+X’Y

X’Y+XY’                      = XY’+X’Y

7. CLD-II, Chapter 2, problem 2.17, parts c, and d.

2.17.c Simplify f(X,Y,Z)=Y'Z+X'YZ+XYZ

Y'Z+X'YZ+XYZ  = Y'Z+YZ(X'+X)                               (8d)

Y'Z+YZ(X'+X)    = Y'Z+YZ(1)                                     (5)

Y'Z+YZ(1)          = Y'Z+YZ                                         (1d)

Y'Z+YZ              = Z(Y'+Y)                                         (8d)

Z(Y'+Y)              = Z(1)                                                (5)

Z(1)                    = Z                                                    (1d)

f(X,Y,Z)     = Z

d. Simplify f(X,Y,Z)=(X+Y)(X'+Y+Z)(X'+Y+Z')

For the sake of clarity let A=(X'+Y+Z')

(X+Y)(X'+Y+Z)(X'+Y+Z')  = (X+Y)(X'+Y+Z)A

(X+Y)(X'+Y+Z)A               = (X+Y)(X'A+YA+ZA)      (8d)

Expand X'A:

X'(X'+Y+Z')     = X'X'+X'Y+X'Z'                                   (8)

X'X'+X'Y+X'Z' = X'+X'Y+X'Z'                                      (3d)

X'+X'Y+X'Z'    = X'(1+Y+Z')                                        (8)

X'(1+Y+Z')      = X'(1) = X'                                           (2),(1d)

Expand YA:

Y(X'+Y+Z')      = X'Y+YY+YZ'                                    (8)

YY+YX'+YZ'   = Y+YX'+YZ'                                       (3d)

Y+YX'+YZ'      = Y(1+X'+Z')                                        (8)

Y(1+X'+Z')       = Y(1) = Y                                           (2),(1d)

Expand ZA:

Z(X'+Y+Z')      = X'Z+YZ+ZZ'                                     (8)

X'Z+YZ+ZZ'    = X'Z+YZ+0     = X'Z+YZ                     (5d),(1)

X'Z+YZ            = Z(X'+Y)

Recombine, keeping only one copy of each term:

(X+Y)(X'+Y+Z(X'+Y)) = (X+Y)((X'+Y)(1+Z))              (8)

(X+Y)((X'+Y)(1+Z))     = (X+Y)((X'+Y)(1))                  (2)

(X+Y)((X'+Y)(1))         = (X+Y)(X'+Y)                         (1d)

(X+Y)(X'+Y)                = (X(X'+Y)+Y(X'+Y))              (8)

X(X'+Y)+Y(X'+Y)        = XX'+XY+YX'+YY                 (8)

XX'+XY+YX'+YY        = 0+YX+YX'+Y                       (3d,5d)

YX+YX'+Y                  = Y(1+X+X')                            (8)

Y(1+X+X')                   = Y(1) = Y                               (2,1d)

8. CLD-II, Chapter 2, problem 2.20, all parts

2.20.a     Write f(A,B,C,D)=∑m(1,2,3,5,8,13) in canonical minterm form

A’B’C’D+A’B’CD’+A’B’CD+A’BC’D+AB’C’D’+ABC’D

b. Write f in canonical maxterm form

(A+B+C+D)(A+B’+C+D)(A+B’+C’+D)(A+B’+C’+D’)(A’+B+C+D’)(A’+B+C’+D)(A’+B+C’+D’)(A’B’+C+D’)(A’+B’+C’+D)(A’+B’+C’+D’)

c. Write the complement of f in “little m” notation and as a canonical minterm expression

f’(A,B,C,D)=∑m(0,4,6,7,9,10,11,12,14,15)

A’B’C’D’+A’BC’D’+A’BCD’+A’BCD’+AB’C’D+AB’CD’+AB’CD+ABC’D’+ABCD’+ABCD

d. Write the complement of f in “big M” notation and as a canonical maxterm expression

f’(A,B,C,D)=∏M(1,2,3,5,8,13)

(A+B+C+D’)(A+B+C’+D)(A+B+C’+D’)(A+B’+C+D’)(A'+B+C+D)(A’+B’+C+D’)

Comments to: cse370-webmaster@cs.washington.edu (Last Update: 10/21/03 )