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(YZ)) 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)+(YY) (6b)

XY+YY = XY+0 (7b)

XY+0 = XY (5a)

 

d. Prove (X+Y)(X+Z) = XY + 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+ABC+ABC+ABC+ABC = BC+AB+AC

 

A B C

ABC

ABC

ABC

ABC

ABC

ALL

BC

AB

AC

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+(CD))

(A+B+C)(B+(CD)) = (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+XY

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

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

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

(XY+YY)+(XX+XY) = XY+XY

(XY+0)+(0+XY) = XY+XY

XY+XY = XY+XY

 

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

 

ABCD+ABCD+ABCD+ABCD+ABCD+ABCD

 

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)(AB+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)

 

ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+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 )