CSE 370, Autumn 2000
Homework 2 Solutions
1. Draw a schematic in Design Works for the following function: f(A,B,C,D)=(AB'+C'D)'
(a) Using only two-input NOR gates:
(b) Using only two-input NAND gates:
2. Prove using truth-table method:
(a) (A + B') B = AB
| A | B | A + B' | (A + B') B | AB |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
| Result: (A + B') B = AB | ||||
(b) (A + B) (A' + C) = AC + A'B
| A | B | C | AC | A'B | A + B | A' + C | AC + A'B | (A + B) (A' +C) |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| Result: (A+B)(A'+C)= AC + A'B | ||||||||
3. Prove the following using other theorems and laws (listing the number of the law at each step).
(a) (A + B).(A +C) = A + BC
(A + B).(A +C) = (A + B).(A)+ (A + B).(C) (Distributive law)
= (A.A + B.A) + (A.C +B.C) (Distributive law)
= A.A + B.A +A.C + B.C (Associative law)
= A + B.A + A.C + B.C (Idempotent Theorem)
= A + A.B + A.C + B.C (Commutative law)
= A + B.C (Simplification Theorem X + X.Y = X) X)
(b) AB + A'C = (A + C).(A' + B)
(A + C).(A' + B) = (A + C).(A') + (A + C).B (Distributive law)
= (A.A' + C.A') + (A.B + C.B) (Distributive law)
= A.A' + C.A' + A.B + CB (Associative law)
= C.A' + AB + CB (Theorem of complementarity A.A' = 0)
= A'C + AB + CB (Commutative law)
= A'C + AB (Consensus Theorem)
4. Use DeMorgan's theorem to invert the following expressions:
(a) ABC + B(C' + D') : (ABC + B(C' + D'))' = (A' + B' + C').(B' + (CD))
(b) A + (BC)' : (A + (BC)')' = A'(B' + C')' = A'BC
5. Demonstrate that a 2-input NOR gate is a universal logic element. Is an XOR gate universal? Why? What about NAND ?
We show that we can implement NOT, AND and OR gates using NOR gates only to show that NOR is a universal logic element. We show that using a design works schematic below :
We show that NAND gates can create all other logic functions, and in particular AND, OR and NOT gates.
To implement a NOT gate using NAND : (A NAND A) = NOT A = A'
A NAND gate with its output inverted gives us an AND gate.
|
NAND -> OR | |||||
| X | Y | X' | Y' | (X' Y')' | X + Y |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
| X' NAND Y' = X OR Y | |||||
|
A NAND gate with its inputs inverted creates an OR gate, and adding another inverter to the output yields a NOR gate. | |||||
Thus, having created all other logic gates from NAND gates, we can say that NAND is a universal logic function.
An XOR gate is clearly not a universal element, because there is no way to create an AND or OR gate using only XOR gates.
6. f(A, B, C, D) = Σm(1, 2, 3, 5, 8, 13)
(a) Rewrite as Boolean expression in canonical minterm 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
(b) Rewrite 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) Rewrite the complement of f in "little m" notation and in canonical minterm form.
f'(A, B, C, D) = Σm(0, 4, 6, 7, 9, 10, 11, 12, 14, 15)
= 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
(d) Rewrite the complement of f in "big M" notation and in canonical maxterm form.
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')
7. Consider the function f(A,B,C) = AB + B'C' + AC'
(a) Express the function in canonical sum-of-products form. Use "little m" notation.
f(A,B,C) = ABC + ABC' + AB'C' + A'B'C' = Σm(0, 4, 6, 7)
(b) Express the complement of the function in canonical product-of-sums form. Use "big M" notation.
f'(A,B,C) = (A + B + C).(A + B' + C').(A' + B' + C).(A' + B' +C') = ΠM(0 , 4, 6, 7)
Created by: Krishna Gummadi
10/6/00