Universal gates (NAND - NOR completeness): Worked examples

Before anything, one picture to anchor the only symbols we use. A gate is a little box: signals go in on the left, one signal comes out on the right. A signal is either $0$ (off, low) or $1$ (on, high). The small bubble on a gate's output means "invert" — flip $0 \leftrightarrow 1$ .

Figure — Universal gates (NAND - NOR completeness)

We write $A ↑ B = \overline{A B}$ (NAND, "not-and") and $A ↓ B = \overline{A + B}$ (NOR, "not-or"). The bar means NOT. The dot $\cdot$ (often dropped) means AND; the plus $+$ means OR. That is the entire alphabet.

The scenario matrix

Every buildable-from-a-single-gate problem falls into one of these cells. The examples below are labelled with the cell they cover.

Cell	Case class	Covered by
C1	Degenerate input: NOT (self-tie)	Ex 1
C2	Basic 2-input rebuild: AND, OR	Ex 2, Ex 3
C3	Zero / constant inputs (feed a $0$ or $1$ )	Ex 4
C4	Multi-variable expression (3+ inputs)	Ex 5
C5	The dual gate (NOR side)	Ex 6
C6	Non-monotonic target (XOR / XNOR)	Ex 7
C7	Real-world word problem	Ex 8
C8	Exam twist: minimise gate count / spot the trap	Ex 9

Worked examples

Worked example Ex 1 — NOT from one NAND (Cell C1, degenerate input)

Build $\overline{A}$ using exactly one NAND.

Forecast: guess — do you need one gate or two? Where does the second input go?

A NAND needs two inputs, but we only have $A$ . Tie both inputs to the same wire $A$ . Why this step? We must not leave an input floating — a floating input has no defined value, so the output is garbage. Feeding $A$ into both slots is the fix.
Now the gate computes $A ↑ A = \overline{A \cdot A}$ . Why this step? That is just the NAND definition applied with $B = A$ .
Use idempotence $A \cdot A = A$ (an AND of a thing with itself is that thing — a lamp AND-ed with itself is just the lamp). So $\overline{A \cdot A} = \overline{A}$ . Why this step? It collapses the product to a single $A$ so the bar becomes a plain NOT.

Verify: $A = 0 \Rightarrow 0 ↑ 0 = \overline{0} = 1$ . $A = 1 \Rightarrow 1 ↑ 1 = \overline{1} = 0$ . Output is the exact opposite of input — that is NOT. ✓ One gate.

Worked example Ex 4 — Constant inputs (Cell C3, zero/degenerate)

What does a NAND do if one input is held at constant $0$ ? At constant $1$ ? Use this to build a NOT of the other input.

Forecast: guess the output when one input is pinned to $0$ regardless of the other input.

Pin one input to $0$ : $A ↑ 0 = \overline{A \cdot 0} = \overline{0} = 1$ . Why this step? Anything AND-ed with $0$ is $0$ ; NOT of $0$ is $1$ . So a $0$ input forces the output to $1$ — the gate ignores $A$ entirely. This is the degenerate case to watch for.
Pin one input to $1$ : $A ↑ 1 = \overline{A \cdot 1} = \overline{A}$ . Why this step? AND-ing with $1$ leaves $A$ unchanged, so the bar makes it $\overline{A}$ . A NAND with one input tied high is a working inverter of the other input.
Compare with Ex 1: tying both inputs to $A$ also gives $\overline{A}$ . Two valid ways to invert — but tying to a stray $0$ does not work (it jams the output to $1$ ). Why this step? Shows which "constant trick" is safe and which is a trap.

Verify: $A ↑ 1$ : $0 ↑ 1 = \overline{0} = 1$ , $1 ↑ 1 = \overline{1} = 0$ ✓ inverter. $A ↑ 0$ : $0 ↑ 0 = 1$ , $1 ↑ 0 = 1$ ✓ constant $1$ (input ignored).

Worked example Ex 6 — The dual: OR & AND from NOR (Cell C5)

Build $A + B$ (cheap) and $A \cdot B$ (dear) using only NORs.

Forecast: NOR is the mirror of NAND. Which is now the 2-gate build — OR or AND?

NOT from NOR: $A ↓ A = \overline{A + A} = \overline{A}$ (idempotence $A + A = A$ ). 1 gate. Why this step? Same self-tie trick; NOR also has a built-in NOT.
OR from NOR: $(A ↓ B) ↓ (A ↓ B) = \overline{\overline{A + B}} = A + B$ . NOR then invert = 2 NORs. Why this step? NOR's native operation is OR-then-invert, so one extra invert cancels the bar — OR is the cheap build here.
AND from NOR: $A \cdot B = \overline{\overline{A} + \overline{B}} = (A ↓ A) ↓ (B ↓ B)$ . Invert both, then NOR = 3 NORs. Why this step? Duality Principle: everything swaps AND↔OR versus the NAND case. AND is now the expensive 3-gate build.

Verify: OR: $A = B = 0 \Rightarrow A ↓ B = 1$ , then $1 ↓ 1 = \overline{1} = 0$ ✓ (0 only when both 0). AND: $A = B = 1 \Rightarrow \overline{A} = \overline{B} = 0$ , $0 ↓ 0 = \overline{0} = 1$ ✓. OR=2 NORs, AND=3 NORs.

Worked example Ex 7 — XOR from NAND (Cell C6, non-monotonic)

Build $A \oplus B = A \overline{B} + \overline{A} B$ (output $1$ when inputs differ) using only NANDs.

Forecast: XOR flips direction — going $A : 0 \to 1$ can turn the output $1 \to 0$ or $0 \to 1$ depending on $B$ . Plain AND/OR can never do that. How many NANDs?

$g_{1} = A ↑ B = \overline{A B}$ . Why this step? A shared "not-both" signal we will feed into both branches.
$g_{2} = A ↑ g_{1} = \overline{A \cdot \overline{A B}} = \overline{A (\overline{A} + \overline{B})} = \overline{A \overline{B}}$ (using $A \overline{A} = 0$ ). Why this step? This isolates the $A \overline{B}$ term (still inverted).
$g_{3} = B ↑ g_{1} = \overline{\overline{A} B}$ , symmetrically. Why this step? Isolates the $\overline{A} B$ term.
$F = g_{2} ↑ g_{3} = \overline{\overline{A \overline{B}} \cdot \overline{\overline{A} B}} = A \overline{B} + \overline{A} B = A \oplus B$ (De Morgan). Why this step? NAND of the two inverted terms = OR of the terms = XOR.

Verify: $A = 1, B = 0$ : $g_{1} = \overline{0} = 1$ , $g_{2} = 1 ↑ 1 = 0$ , $g_{3} = 0 ↑ 1 = 1$ , $F = 0 ↑ 1 = 1$ ✓. $A = B = 1$ : $g_{1} = 0$ , $g_{2} = 1 ↑ 0 = 1$ , $g_{3} = 1 ↑ 0 = 1$ , $F = 1 ↑ 1 = 0$ ✓. 4 NANDs.

Worked example Ex 8 — Real-world word problem (Cell C7)

A safe opens only when neither of two tamper sensors is triggered ( $A = B = 0$ means "all clear"). You are given a bin of NAND gates only. Wire the "open" signal.

Forecast: "open when both are $0$ " — is that AND, OR, or NOR of the sensors?

"Open exactly when $A = 0$ AND $B = 0$ " is $\overline{A} \cdot \overline{B}$ , which by De Morgan equals $\overline{A + B}$ — i.e. NOR. Why this step? Translate the English condition into Boolean before choosing gates.
We only have NANDs. Build NOR $=$ (OR from NAND) then invert. OR $= (A ↑ A) ↑ (B ↑ B)$ (3 NANDs, Ex 3); invert it with a self-tied NAND (1 NAND). Why this step? NOR from NAND = OR(3) + NOT(1) = 4 gates.
Total: 4 NANDs, output $open = \overline{A + B}$ . Why this step? Confirms the buildable signal matches the safe's rule.

Verify: $A = B = 0 \Rightarrow A + B = 0 \Rightarrow \overline{A + B} = 1$ (safe opens) ✓. Any sensor triggered $\Rightarrow A + B = 1 \Rightarrow$ output $0$ (stays locked) ✓.

Worked example Ex 9 — Exam twist: spot the trap & count (Cell C8)

A student claims: " $A + B = A ↑ B$ , so OR needs just 1 NAND." Mark it, correct it, and give the minimum-gate OR.

Forecast: is a single raw NAND ever equal to OR? Test one row before trusting the algebra.

Test $A = 1, B = 1$ : OR gives $1 + 1 = 1$ ; but $A ↑ B = \overline{1 \cdot 1} = 0$ . They disagree — the claim is false. Why this step? One counterexample row kills the equation instantly (the fastest exam check).
The bug: they forgot to invert the inputs first. De Morgan needs $\overline{A}, \overline{B}$ before the final NAND (see the parent mistake list). Why this step? Names the exact slip so it isn't repeated.
Correct minimum: $A + B = (A ↑ A) ↑ (B ↑ B)$ = 3 NANDs (proved in Ex 3). You cannot do OR in fewer than 3 two-input NANDs. Why this step? Gives the right answer and its true cost.

Verify: $A = 1, B = 1$ in the correct build: $\overline{A} = 0, \overline{B} = 0$ , $0 ↑ 0 = \overline{0} = 1$ ✓. Raw-NAND claim fails this same row, confirming the correction. 3 NANDs.

Scenario coverage check

Recall Did we hit every cell?

C1 degenerate/self-tie ::: Ex 1 (NOT) C2 basic AND & OR rebuild ::: Ex 2, Ex 3 C3 constant/zero inputs ::: Ex 4 C4 multi-variable (3 inputs) ::: Ex 5 C5 dual NOR side ::: Ex 6 C6 non-monotonic XOR ::: Ex 7 C7 word problem ::: Ex 8 C8 exam trap & min-count ::: Ex 9

Connections

Boolean Algebra & Logic Gates
De Morgan's Laws — the engine behind every OR/AND swap above
Truth Tables — how each "Verify" line was checked
Logic Gate Symbols — the boxes and bubbles in the figures
Combinational Circuits — where these builds get assembled
CMOS Transistors — why NAND/NOR are the cheapest physical primitives
Duality Principle — the NAND↔NOR mirror used in Ex 6

Worked examples — Universal gates (NAND - NOR completeness)