Exercises — Universal gates (NAND - NOR completeness)

$\text{NAND}(A,B)=\overline{AB}$, $\text{NOR}(A,B)=\overline{A+B}$. Build both tiny truth tables:

$A\uparrow A=\overline{A\cdot A}$. Since $A\cdot A=A$ (a switch AND-ed with itself is itself — idempotence), this is $\overline{A}$. They built a NOT gate (inverter) from one NAND.

• (a) Complete — NAND alone makes NOT, AND, OR.
• (b) Not complete — AND can never invert; feed all-1s and you can only ever get 1 out, so no NOT.
• (c) Complete — NOR is the dual universal gate.
• (d) Not complete — both AND and OR are monotonic (raising an input never lowers the output), so no NOT is reachable. You need at least one inverting operation.

1. Inverter: $A\uparrow A=\overline{A}$ (1 gate) — not actually needed for AND but shows the tool.
2. NAND the inputs: $A\uparrow B=\overline{AB}$ (1 gate).
3. Invert that result with a NAND-inverter: $(A\uparrow B)\uparrow (A\uparrow B)=\overline{\overline{AB}}=AB$ (1 gate). AND from NAND = 2 NANDs. Follow the wiring in the figure below.

Use De Morgan: $A+B=\overline{\overline{A}\cdot \overline{B}}$. The right side is a NAND of the two inverted inputs.

1. $\overline{A}=A\uparrow A$ (1 gate).
2. $\overline{B}=B\uparrow B$ (1 gate).
3. $(A\uparrow A)\uparrow (B\uparrow B)=\overline{\overline{A}\cdot \overline{B}}=A+B$ (1 gate). OR from NAND = 3 NANDs. See the figure.

NOR's native operation is OR-then-invert, so OR is cheap here: $(A\downarrow B)\downarrow (A\downarrow B)=\overline{\overline{A+B}}=A+B.$ OR from NOR = 2 NORs, versus 3 NANDs in L2.2. This is the duality mirror: what costs 3 gates on one side costs 2 on the other.

Let $p=A\uparrow A=\overline{A}$, $q=B\uparrow B=\overline{B}$, then output $=p\uparrow q=\overline{pq}$.

Definition (monotone): a function is monotone if changing any input $0\to 1$ can only keep the output the same or raise it — never lower it. AND is monotone: raising an input can only help both inputs be 1. Key fact: any circuit built purely from monotone gates is itself monotone (composition of monotone maps stays monotone). NOT is not monotone: input $0\to 1$ sends output $1\to 0$ — it drops. Therefore no all-AND circuit can ever realise NOT. A gate set that cannot make NOT cannot make $\{AND,OR,NOT\}$, so it is not complete. ∎

A single NAND with three inputs gives $\overline{ABC}$. Invert it: $F=(A\uparrow B\uparrow C)\uparrow (A\uparrow B\uparrow C)=\overline{\overline{ABC}}=ABC.$ That is 1 three-input NAND + 1 inverter (NAND) = 2 NANDs, same count as 2-input AND, because the extra input rides along inside the one NAND. If only 2-input NANDs are allowed: $\overline{AB}$ needs its invert to give $AB$ (2 gates), then AND with $C$ needs 2 more → 4 two-input NANDs.

Step 1: $g_1=\overline{AB}$. By De Morgan, $\overline{AB}=\overline{A}+\overline{B}$. Step 2: $g_2=A\uparrow g_1=\overline{A{g}_1}=\overline{A(\overline{A}+\overline{B})}$. Distribute: $A\overline{A}+A\overline{B}$. Since $A\overline{A}=0$ (a thing AND its opposite is never both true), this is $\overline{A\overline{B}}$. Step 3: symmetrically $g_3=\overline{B(\overline{A}+\overline{B})}=\overline{\overline{A}B}$. Step 4: $F=g_2\uparrow g_3=\overline{g_2{g}_3}=\overline{\overline{A\overline{B}}\cdot \overline{\overline{A}B}}$. By De Morgan (double form) $=A\overline{B}+\overline{A}B$, which is exactly the definition of $A\oplus B$. ∎

Rewrite with De Morgan: $\overline{A}+B=\overline{A\cdot \overline{B}}=A\uparrow \overline{B}$.

1. $\overline{B}=B\uparrow B$ (1 gate).
2. $F=A\uparrow \overline{B}=A\uparrow (B\uparrow B)$ (1 gate). Total: 2 NANDs. Neat — implication is one inverter plus one NAND. Check the row that should be the only 0: implication $A\to B$ is false only when $A=1,B=0$. There $\overline{B}=1$, $A\uparrow 1=\overline{A}=\overline{1}=0$. ✓

This is the classic 4-NAND MUX (a combinational building block):

1. $\overline{S}=S\uparrow S$ (1 gate).
2. $p=A\uparrow \overline{S}=\overline{A\overline{S}}$ (1 gate).
3. $q=B\uparrow S=\overline{BS}$ (1 gate).
4. $F=p\uparrow q=\overline{\overline{A\overline{S}}\cdot \overline{BS}}$. By De Morgan $=A\overline{S}+BS=\overline{S}A+SB$ (1 gate). Total: 4 NANDs. Verify the two behaviours: $S=0\Rightarrow F=A$; $S=1\Rightarrow F=B$. ✓

NOR's cheap op is OR, and this expression is a sum (OR) of two AND-terms, so we expect NOR to do reasonably. Rewrite each product as a NOR-of-inverses (De Morgan): $\overline{S}A=\overline{\overline{\overline{S}A}}=\overline{S+\overline{A}}$… working it purely in NOR:

1. $\overline{S}=S\uparrow$? — no, NOR self-invert: $\overline{S}=S\downarrow S$ (1).
2. $\overline{A}=A\downarrow A$ (1), $\overline{B}=B\downarrow B$ (1).
3. term1 $=\overline{S}A=\overline{\overline{\overline{S}}+\overline{A}}=(S)\downarrow \overline{A}=S\downarrow (A\downarrow A)$ — since $\overline{\overline{S}}=S$ (1 NOR).
4. term2 $=SB=\overline{\overline{S}+\overline{B}}=\overline{S}\downarrow \overline{B}=(S\downarrow S)\downarrow (B\downarrow B)$ (1 NOR).
5. OR the two terms with a NOR-OR: $F=(\text{term1}\downarrow \text{term2})\downarrow (\text{term1}\downarrow \text{term2})$ (2 NORs). Counting: $\overline{A}$(1), $\overline{B}$(1), $\overline{S}$ reused, term1(1), term2 needs $\overline{S}$(1)+combine(1), final OR(2) → 6 NORs — more than the 4-NAND version here, because this specific expression is written as a sum-of-products (NAND-friendly). The mirror advantage flips when the target is a product-of-sums.

It IS complete.

• NOT: $A\oplus 1=\overline{A}$ (XOR with a constant 1 flips the bit — check: $0\oplus 1=1$, $1\oplus 1=0$). So with a constant-1 line, XOR gives us NOT.
• AND: given directly.
• OR: from NOT + AND via De Morgan, $A+B=\overline{\overline{A}\cdot \overline{B}}$. We recovered NOT, AND, OR ⇒ $\{\text{XOR},\text{AND}\}$ is complete (this set with constant 1 is the Reed–Muller basis, the algebra of $\text{XOR}/\text{AND}$). Note the necessity of a constant: pure XOR alone (no constant, no AND) is not complete because XOR-only circuits are linear/affine.

Trace the longest path. $g_1$ is level 1. $g_2$ and $g_3$ each depend on $g_1$ → level 2. $F$ depends on $g_2,g_3$ → level 3. The critical path is $g_1\to g_2\to F$ (or $g_1\to g_3\to F$), which is 3 gates deep. Worst-case delay $=3t$. (A direct input like $A$ into $g_2$ into $F$ is only 2 levels, so it's not critical.)

Corner values $G(0,0)=1$ and $G(1,1)=0$ are shared by exactly NAND and NOR (both output 1 on all-0 and 0 on all-1; both are the only single-gate universals). They are separated by the mixed rows:

• NAND: $G(0,1)=G(1,0)=1$.
• NOR: $G(0,1)=G(1,0)=0$. So the deciding row is any mixed input, e.g. $G(0,1)$: 1 ⇒ NAND, 0 ⇒ NOR. These are the only two universal 2-input gates — consistent with the parent claim that NAND and NOR are the universal gates.

Cheapest gate for a sum-of-products target ::: NAND (native $\overline{AB}$ matches AND-terms). Cheapest gate for a product-of-sums target ::: NOR (native $\overline{A+B}$ matches OR-terms). Delay of the 4-NAND XOR ::: $3t$ (three gate levels). Deciding row between NAND and NOR ::: any mixed input like $(0,1)$ — NAND gives 1, NOR gives 0.