~60 minutes. Fill in truth tables for AND, OR, XOR, NAND; verify De Morgan's law; prove NAND universality on paper.
Goal: fill in truth tables for all six Boolean operations from memory, verify De Morgan's law numerically, and construct OR and NOT from NAND gates.
Estimated time: 60 minutes
Prerequisites: Week 3 lecture
Part A: Two-input truth tables
Fill in the output column for each operation. Do not look at your notes until you have attempted all four.
AND:
| A | B | A AND B |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
OR:
| A | B | A OR B |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
XOR:
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
NAND:
| A | B | A NAND B |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
Part B: Verify De Morgan's law
De Morgan's first law: NOT(A AND B) = (NOT A) OR (NOT B)
Verify this for all 4 input combinations by filling in both sides of the equation:
| A | B | NOT(A AND B) | NOT A | NOT B | (NOT A) OR (NOT B) | Equal? |
|---|---|---|---|---|---|---|
| 0 | 0 | |||||
| 0 | 1 | |||||
| 1 | 0 | |||||
| 1 | 1 |
Do the two columns match for all 4 rows? Write one sentence explaining what De Morgan's law says in plain English for the row where A=1, B=0.
Part C: NAND universality
NOT from NAND: if you connect both inputs of a NAND gate to the same signal A (so both inputs are A), what is the output in terms of A? Fill in:
| A | A NAND A |
|---|---|
| 0 | |
| 1 |
Compare to the NOT truth table. What do you conclude?
AND from NAND: AND(A, B) = NAND(NAND(A,B), NAND(A,B))
Verify this for all 4 input combinations:
| A | B | NAND(A,B) | call it C | NAND(C, C) | Expected AND(A,B) | Match? |
|---|---|---|---|---|---|---|
| 0 | 0 | |||||
| 0 | 1 | |||||
| 1 | 0 | |||||
| 1 | 1 |
OR from NAND (De Morgan's route): OR(A, B) = NAND(NAND(A,A), NAND(B,B))
Verify for all 4 combinations in your worksheet.
Part D: Boolean simplification
Simplify the following Boolean expression using the identities from the week 3 lecture. Show each step:
(A AND 1) OR (A AND NOT A)
Hint: there are two identities that each simplify one term. Write out which identity you applied at each step.
Expected output / artifact
lab-3-1-truth-tables.txt with all filled tables, De Morgan verification, NAND universality verification, and Part D simplification.
git add lab-3-1-truth-tables.txt
git commit -m "lab-3-1: truth tables and NAND universality"
Common pitfalls
- NAND vs NOR confusion: NAND is NOT(A AND B); NOR is NOT(A OR B). They are different.
- Forgetting to invert: NAND is "NOT AND", so for inputs 0,0 AND gives 0 and NAND gives NOT(0) = 1.
- De Morgan's verification: compute both sides independently; if they match for all 4 rows, the law is verified.
Stretch (optional)
Prove that NOR is also universal: construct NOT, AND, and OR using only NOR gates. Show your truth-table verification for each.
Lab 3.1 v0.1.