ELEN 500

Spring 1999

Solution for Homework Assignment 1

98765

 

For f(w,x,y,z) = w'y' + x'yz + xy'z + w'z'
1a. Draw a NAND gate implementation (you can use inverters for complemented inputs).
1b. List all of the minterms.

w'x'y'z', w'x'y'z, w'x'yz', w'x'yz, w'xy'z', w'xy'z, w'xyz', wx'yz, wxy'z


1c. What is the maximum number of minterms that a 4 input function can have?

24 = 16

2a. Draw the graph with vertices V = {A, B, C, D, E, F, O, W, X, Y, Z} and edges E ={(A,D), (B,E),

(E,F), (F,O), (A,C), (A,E), (C,F), (D,F), (W,B), (X,A), (X,D), (Y,A), (Y,C), (Z,A), (Z,C), (Z,D)}.

2b. Is the graph a DAG? Yes

2c. What, if any, are the source vertices W, X, Y, Z

 

2d. What, if any are the sink vertices? O

2e. What is the longest path?

There are several possible answers to this question:

(W, B, E, F, O)

(X, A, E, F, O)

(X, A, D, F, O)

(X, A, C, F, O)

(Y, A, E, F, O)

(Y, A, D, F, O)

(Y, A, C, F, O)

(Z, A, E, F, O)

(Z, A, D, F, O)

(Z, A, C, F, O)