Visual walkthrough — Universal gates (NAND - NOR completeness)

---

Step 0 — What a gate even is (the black box)

WHAT. A logic gate is a tiny machine with input wires and one output wire. Each wire carries either a 0 (low, "off") or a 1 (high, "on"). Nothing else exists — no 2, no 0.5, just those two symbols. (See Logic Gate Symbols for the shapes.)

WHY start here. Before we can "build" anything we must agree what the pieces are: wires that hold 0 or 1, and boxes that turn some 0/1 inputs into a 0/1 output. That is the entire alphabet.

PICTURE. Below is the NAND box. Two inputs $A$ and $B$ enter on the left, one output leaves on the right. The little bubble on the nose means "invert" — flip the answer at the very end. We write NAND as $A\uparrow B$ (the up-arrow is just a shorthand name, nothing mystical).

Its full truth table (the whole personality of the gate — see Truth Tables):

$A$	$B$	$A\cdot B$	$A\uparrow B$
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

---

Step 1 — NOT, by making the gate look in a mirror

WHAT. Take one signal $A$ and feed it into both input holes of a single NAND. Now $A=B$ everywhere. The output is $\overline{A}$ — the opposite of $A$.

WHY this trick. Look at the truth table above, but only the rows where $A=B$: those are the first row ($0,0\to 1$) and the last row ($1,1\to 0$). So when both inputs match, the box outputs the flip of that shared value. That is exactly NOT. Formally, $A\cdot A=A$ (a thing AND-ed with itself is just itself — called idempotence), so $\underset{\text{tie both inputs}}{\underbrace{A\uparrow A}}=\overline{A\cdot A}=\overline{A}.$ Here $A\cdot A$ collapses to $A$, then the NAND's built-in bar flips it. We now own inversion — for free, from one gate.

PICTURE. The wire splits and both branches enter the same NAND. Trace a $1$ in: it becomes $0$. Trace a $0$ in: it becomes $1$.

---

Step 2 — AND, by un-flipping the NAND

WHAT. A NAND already computes $\overline{AB}$ — that is AND with an unwanted flip stuck on the end. To get plain AND, just flip it back using the NOT-machine we built in Step 1.

WHY. Flipping twice returns the original — $\overline{\overline{X}}=X$ (double negation). Apply our Step-1 inverter to the NAND's output:

$$\underset{\text{this is }\overline{AB}}{\underbrace{(A\uparrow B)}}\uparrow \underset{\text{same wire, tied to both inputs}}{\underbrace{(A\uparrow B)}}=\overline{\overline{AB}}=AB.$$

The first NAND makes $\overline{AB}$; the second NAND (with both inputs tied to that wire) is a Step-1 inverter that cancels the bar. AND = 2 NANDs.

PICTURE. Two boxes in a row. Box 1 = NAND. Box 2 = inverter (its two inputs joined). Watch $(1,1)$ flow: box 1 gives $0$, box 2 flips to $1$ ✓. Watch $(1,0)$: box 1 gives $1$, box 2 flips to $0$ ✓.

---

Step 3 — Meet the engine: De Morgan's Law

WHAT. OR is trickier because NAND has no OR hiding inside it — only AND-then-flip. We need a bridge that rewrites OR using only AND and NOT. That bridge is De Morgan's Law: $A+B=\overline{\overline{A}\cdot \overline{B}}.$

WHY this tool and not another. We are stuck: our gate speaks only "AND" and "NOT," but we want "OR." De Morgan is the only identity that translates an OR ($+$) into a sentence made purely of NOTs ($\overline{}$) and an AND ($\cdot$) — precisely the two things NAND provides. It answers the exact question "how do I say OR without ever writing OR?"

PICTURE — why it's true. Think in overlapping circles (a Venn picture). "$A$ OR $B$" = everything inside either circle. De Morgan says the same region equals: not (the area outside $A$ and outside $B$) — i.e. not the little corner touching neither circle. Both shadings land on identical territory.

---

Step 4 — OR, assembling De Morgan out of NANDs

WHAT. Now literally build the right-hand side $\overline{\overline{A}\cdot \overline{B}}$ from gates. Notice its shape: it is "$\overline{A}$ and $\overline{B}$, then flipped" — and "AND then flipped" is a NAND! So OR = NAND of the two inverted inputs.

WHY, step by symbol.

$$A+B=\overline{\overline{A}\cdot \overline{B}}=\underset{=\overline{A}}{\underbrace{(A\uparrow A)}}\uparrow \underset{=\overline{B}}{\underbrace{(B\uparrow B)}}.$$

• $(A\uparrow A)=\overline{A}$ — one Step-1 inverter (gate #1).
• $(B\uparrow B)=\overline{B}$ — another Step-1 inverter (gate #2).
• $\overline{A}\uparrow \overline{B}=\overline{\overline{A}\cdot \overline{B}}=A+B$ — the final NAND (gate #3), which supplies De Morgan's outer bar.

OR = 3 NANDs.

PICTURE. Two inverters feed a final NAND. Trace $(0,0)$: inverters give $(1,1)$, final NAND of $(1,1)=0$ — correct, since $0+0=0$ ✓. Trace $(1,0)$: inverters give $(0,1)$, final NAND $=1$ — correct, $1+0=1$ ✓.

---

Step 5 — The finish line: transitivity

WHAT. We have now produced NOT (Step 1), AND (Step 2), and OR (Step 4) using nothing but NAND gates.

WHY that's the whole proof. The set $\{\text{AND},\text{OR},\text{NOT}\}$ is already known to be functionally complete — anything expressible as a truth table can be written with those three (see Combinational Circuits). Since NAND can impersonate all three, NAND inherits their power. This chain — NAND ⟹ {AND, OR, NOT} ⟹ everything — is called a transitive argument.

PICTURE.

Therefore NAND is universal. ∎

---

Step 6 — The NOR mirror (the degenerate-symmetry case)

WHAT. NOR is $A\downarrow B=\overline{A+B}$ — "OR then flip." Run the identical playbook and every result appears with AND↔OR swapped.

WHY the swap happens. NOR's cheap native move is OR-then-invert, whereas NAND's was AND-then-invert. So the gate counts mirror: with NOR, OR is cheap (2 gates) and AND is dear (3 gates) — the exact reverse of NAND. This is the Duality Principle in action.

Function	From NOR ($\downarrow$)	Gates
NOT	$A\downarrow A=\overline{A+A}=\overline{A}$	1
OR	$(A\downarrow B)\downarrow (A\downarrow B)=\overline{\overline{A+B}}=A+B$	2
AND	$(A\downarrow A)\downarrow (B\downarrow B)=\overline{\overline{A}+\overline{B}}=AB$	3

PICTURE. Same three constructions, mirror-imaged.

Recall Why only inverting gates? (edge case)

Try to make a universal gate from AND alone. AND is monotonic: raising an input from 0→1 can never lower the output. Feed all 1s and you can never squeeze out a 0 — so AND can never build NOT, and without NOT you can't reach De Morgan or OR. NAND/NOR break monotonicity via their bubble. That inversion is the seed of everything above.

---

The one-picture summary

Recall Feynman retelling (say it to a 12-year-old)

You get one magic LEGO brick that only knows how to say "NOT both." That built-in "not" is the whole gift. First, feed the brick the same signal twice — it just says "no" to whatever you gave it: that's NOT. Next, a brick already secretly does "AND then flip"; so slap a second brick on the end to flip it back — now you have plain AND. For OR you use a clever swap called De Morgan: "$A$ or $B$" is the same as "not (not-$A$ and not-$B$)," so flip both inputs with two bricks, then NAND them with a third — three bricks and you've got OR. Once you can do NOT, AND, and OR, you can build any machine — a calculator, a whole computer. And NOR is the same story looked at in a mirror: cheap OR, pricey AND. One brick, infinite worlds.

---

Connections

• Boolean Algebra & Logic Gates — the parent chapter
• De Morgan's Laws — the engine of Steps 3–4
• Truth Tables — how every step was verified
• Logic Gate Symbols — the box-and-bubble shapes drawn here
• Combinational Circuits — where these constructions get assembled
• CMOS Transistors — why NAND/NOR are physically cheapest
• Duality Principle — the NAND↔NOR mirror of Step 6