University of California at Berkeley
College of Engineering
Department of Electrical Engineering and Computer Science
EECS 150R. H. Katz
Fall 2000
Problem Set # 3 Solution
3a. Assume each gate has the same delay.
IN
U1
U3
U4
U2
3b.
IN
U1
U3
U2
This circuit does not have an oscillating output. Since signal U2 is high all the time, signal U3 will remain low and is constant, independent of signal U1.
4.
1a) F(A,B,C,D) = (ABC+A’B’) (C+D)
A / B / C / D / F0 / 0 / 0 / 0 / 0
0 / 1 / 1
1 / 0 / 1
1 / 1 / 1
0 / 1 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 0
1 / 0 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 0
1 / 1 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 1
1 / 1 / 1
D
1
0
0
0 F
0
0
1
A B C
1b) G(B,C) = B’C’; F(A,B,C,D) = [(A+B) (A’+C) + G]G’ (A’C’ + G)
A / B / C / D / F0 / 0 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 0
0 / 1 / 0 / 0 / 1
0 / 1 / 1
1 / 0 / 0
1 / 1 / 0
1 / 0 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 0
1 / 1 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 0
0
0
1
0
0 F
0
0
0
A B C
1c) F(A,B,C,D) = [A’+B’+C) (B+C’) (C+D’)’ (A+B’+C’)’] + ACD’ +BC’D’
A / B / C / D / F0 / 0 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 0
0 / 1 / 0 / 0 / 1
0 / 1 / 0
1 / 0 / 0
1 / 1 / 0
1 / 0 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 1
1 / 1 / 0
1 / 1 / 0 / 0 / 1
0 / 1 / 0
1 / 0 / 1
1 / 1 / 0
0
0
D’
0
0 F
D’
D’
D’
A B C
2c) F(A,B,C,D) = B’CD + A’B’D + A’C
A / B / C / D / F0 / 0 / 0 / 0 / 0
0 / 1 / 1
1 / 0 / 1
1 / 1 / 1
0 / 1 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 1
1 / 1 / 1
1 / 0 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 1
1 / 1 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 0
D
1
0
1
0 F
D
0
0
A B C
2a) F(A,B,C) = AB + BC + AC
A / B / C / F0 / 0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 1
1 / 0 / 0 / 0
0 / 1 / 1
1 / 0 / 1
1 / 1 / 1
0
C F
C
1
A B
2b) F(A,B,C) = A’B’C + A’BC’ + AB’C’ + ABC
A / B / C / F0 / 0 / 0 / 0
0 / 1 / 1
1 / 0 / 1
1 / 1 / 0
1 / 0 / 0 / 1
0 / 1 / 0
1 / 0 / 0
1 / 1 / 1
C
C’ F
C’
C
A B
5. First, you have to write out the truth tables for each function and use K-map to reduce
their sum of product forms.
1a. F(A,B,C,D) = (ABC+A’B’) (C+D)
= A’B’C’D + A’B’CD’ + A’B’CD + ABCD’ + ABCD
= ABC + A’B’C + A’B’D
1b. G(B,C) = B’C’; F(A,B,C,D) = [(A+B) (A’+C) + G]G’ (A’C’ + G)
= A’BC’D’ + A’BC’D
= A’BC’
1c. F(A,B,C,D) = [A’+B’+C) (B+C’) (C+D’)’ (A+B’+C’)’] + ACD’ +BC’D’
= A’BC’D’ + AB’CD’ + ABC’D’ + ABCD’
= BC’D’ + ACD’
2a. F(A,B,C) = AB + BC + AC
2b. F(A,B,C) = A’B’C + A’BC’ + AB’C’ + ABC
2c. F(A,B,C,D) = B’CD + A’B’D + A’C
Distinct Products Terms in the above equations:
ABC A’B’C A’BC’ AB’C’ A’B’D ACD’ BC’D’ B’CD A’C AC AB BC
A B C D
ABC
A’B’C
A’BC’
AB’C’
A’B’D
ACD’
BC’D’
B’CD
A’C
AC
AB
BC
A A’ B B’ C C’ D D’
F1a F1b F1c F2a F2b F2c