CSE 370, Spring 2000
Homework 2 Solutions
NOTE: leaving a question worth 0 points blank (i.e. not handing in DesignWorks schematics or doing truth tables) resulted in a 1 point deduction from your homework grade.
1. (0 pts.) Katz 2.2 using only 2-input NOR gates, and give DesignWorks schematics for the circuits:
2.2a: (X' + (Y + Z)')'
2.2b: ((X' + Y')' + (X' + Z')')'
2. (0 pts.) Katz 2.7 using truth-table method:
a: (X + Y) (X + Y') = X
| X | Y | X + Y | X + Y' | (X + Y) (X + Y') | X |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| Result: (X + Y) (X + Y') = X | |||||
c: (X + Y') Y = X Y
| X | Y | X + Y' | (X + Y') Y | X Y |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
| Result: (X + Y') Y = X Y | ||||
3. (4 pts.) Prove (X' + Y') (Y' + Z') (X + Z') = (X' + Y') (X + Z') using the laws of Boolean algebra.
By substituting A = X', B= Y', and C = Z' we can apply the convolution theorem directly to obtain the answer. Or, this can be proved by multiplying out both sides and collecting terms, which is what I'll show here:
| (X' + Y') (Y' + Z') (X + Z') | (X' + Y') (X + Z') |
| (X' Y' + X' Z' + Y' Y' + Y' Z') (X + Z') | X' X + X' Z' + X Y' + Y' Z' |
| (X' Y' + X' Z' + Y' + Y' Z') (X + Z') | X Y' + X' Z' + Y' Z' |
| X X' Y' + X X' Z' + X Y' + X Y' Z' + X' Y' Z' + X' Z' + Y' Z' | |
| X Y' + X Y' Z' + X' Y' Z' + X' Z' + Y' Z' | |
| Y' Z' (X + X') + X Y' + X' Z' + Y' Z' | |
| X Y' + X' Z' + Y' Z' |
4. (4 pts.) Katz 2.10: Use DeMorgan's theorem to invert the expression.
e: (X + Y) Z
|
f: X + (Y Z)'
|
5. (0 pts.) Katz 2.12: Verify the given schematic implements the XOR function using DesignWorks:
6. (4 pts.) Demonstrate that a 2-input NAND gate is a universal logic element. Is an XOR gate universal? Why?
Show that NAND gates can create all other logic functions:
| NAND -> NOT | ||
| X | (X X)' | X' |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| X NAND X = NOT X | ||
A NAND gate with its inputs tied together creates a NOT gate (inverter). |
||
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. |
|||||
The XOR function is already demonstrated by problem 5 in this assignment. Therefore, the XOR function can be implemented using only NAND gates, and by adding an inverter to the output we've created an XNOR 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.
7. (4 pts.) f(A, B, C, D) = Σm(0, 3, 4, 7, 9, 11, 12, 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 + 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')
c: Rewrite the complement of f in "little m" notation and in canonical minterm form.
f'(A, B, C, D) = Σm(1, 2, 5, 6, 8, 10, 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
d: Rewrite the complement of f in "big M" notation and in canonical maxterm form.
f'(A, B, C, D) = ΠM(0, 3, 4, 7, 9, 11, 12, 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') (A' + B' + C + D) (A' + B' + C + D')
8. (4 pts.) f(X, Y, Z) = XY + YZ + X'Z
let's first create a truth table for this problem:
| X | Y | Z | X' | XY | YZ | X'Z | f(X, Y, Z) | f'(X, Y, Z) |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
a: Express in canonical sum-of-products form using "little m" notation.
f(X, Y, Z) = Σm(1, 3, 6, 7).
b: Express the complement of f in canonical product-of-sums form using "big M" notation.
because we're going to pick out the zeros of the inverted function, those will be the same terms as the ones we just found!
f(X, Y, Z) = ΠM(1, 3, 6, 7).
Created by: Valdis Riekstins
4/12/00