Universal gates (NAND - NOR completeness) — Hardware notes

WHAT / WHY / HOW

WHAT — "Functional completeness" means a set of gates can express any truth table. The classic complete set is $\{\text{AND}, \text{OR}, \text{NOT}\}$ . If a single gate can reproduce all three of these, that gate alone is complete = universal.

WHY does one gate suffice? Because AND/OR/NOT are themselves built from more primitive operations, and both NAND and NOR already contain a NOT inside them. Once you have NOT for free, you can un-invert your way to AND and OR.

HOW — Strategy: show NAND (or NOR) can make NOT, AND, OR. Since $\{AND, OR, NOT\}$ is known complete, that transitively proves the single gate is complete.

Definitions

Deriving everything from NAND (first principles)

Let $\uparrow$ denote NAND, so $A \uparrow B = \overline{A B}$ .

Step 1 — NOT from NAND

Tie both inputs together: set $B = A$ . $A \uparrow A = \overline{A\cdot A} = \overline{A}$

Why this step? $A\cdot A = A$ (idempotence), so $\overline{A\cdot A}=\overline{A}$ . We now own inversion.

Step 2 — AND from NAND

NAND already gives $\overline{AB}$ ; we just invert it using our Step-1 NOT: $\overline{(A\uparrow B)} = (A\uparrow B)\uparrow(A\uparrow B) = \overline{\overline{AB}} = AB$

Why this step? Double negation cancels: $\overline{\overline{AB}}=AB$ . So AND = NAND followed by a NAND-inverter (2 NANDs).

Step 3 — OR from NAND (De Morgan is the key)

De Morgan: $A + B = \overline{\overline{A}\cdot\overline{B}}$ . That right side is exactly a NAND of the two inverted inputs: $A + B = \overline{\overline A \cdot \overline B} = (A\uparrow A)\uparrow(B\uparrow B)$

Why this step? Invert each input (Step 1 uses one NAND each = 2 gates), then NAND those together (1 gate). OR = 3 NANDs.

Since we produced NOT, AND, OR — NAND is universal. ∎

Deriving everything from NOR (the dual)

Let $\downarrow$ denote NOR, so $A\downarrow B=\overline{A+B}$ . By duality every NAND result flips AND↔OR:

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

Why the swap? NOR bunches inputs with OR-then-invert, so its cheap operation is OR (2 gates) while AND needs 3 gates — the mirror image of NAND.

Figure — Universal gates (NAND - NOR completeness)

Worked examples

Worked example Build XOR from NAND

Target: $A\oplus B = A\overline B + \overline A B$ . A known 4-NAND circuit:

$g_1 = A\uparrow B$
$g_2 = A\uparrow g_1$
$g_3 = B\uparrow g_1$
$F = g_2\uparrow g_3$

Why it works: $g_2 = \overline{A\,\overline{AB}} = \overline{A(\overline A+\overline B)} = \overline{A\overline B}$ , similarly $g_3=\overline{\overline A B}$ . Then $F=\overline{g_2 g_3}=\overline{\overline{A\overline B}\cdot\overline{\overline A B}}=A\overline B+\overline A B=A\oplus B$ . Only 4 NANDs — this is why ALUs love NAND.

Common mistakes

Recall Feynman: explain to a 12-year-old

Imagine you have only one kind of LEGO brick, but it's a magic brick that says "NOT both." With enough of these magic bricks snapped together, you can build any toy machine — a calculator, a game, anything. You never need a different brick. The trick: the magic brick already knows how to say "no" (invert), and once you can say "no," you can rebuild all the other bricks (AND, OR, NOT) out of it. NAND and NOR are those magic bricks.

Active-recall flashcards

#flashcards/hardware

What makes a gate "universal"?

You can build every Boolean function (i.e. reproduce NOT, AND, OR) using only that gate.

Which single gates are universal?

NAND and NOR.

How do you make NOT from a NAND?

Tie both inputs together:

A\uparrow A=\overline A

How do you make AND from NANDs, and how many?

NAND the inputs then invert the result; 2 NANDs:

(A\uparrow B)\uparrow(A\uparrow B)=AB

How do you make OR from NANDs, and how many?

Invert each input, then NAND them; 3 NANDs:

(A\uparrow A)\uparrow(B\uparrow B)=A+B

Why can't AND alone be universal?

AND is monotonic and can't invert (produce NOT); a universal gate must include inversion.

Which Boolean identity is central to OR-from-NAND?

De Morgan:

A+B=\overline{\overline A\cdot\overline B}

How many NAND gates for XOR?

For NOR, which of AND/OR is cheaper (fewer gates)?

OR is cheaper (2 NORs); AND needs 3 NORs — mirror of NAND.

Formula for NAND and NOR?

\overline{AB}

and

\overline{A+B}

Connections

Boolean Algebra & Logic Gates
De Morgan's Laws — the engine behind OR/AND conversions
Truth Tables — how to verify each construction
Logic Gate Symbols
Combinational Circuits — where universal gates get assembled (adders, MUX)
CMOS Transistors — why NAND/NOR are the cheapest to fabricate physically
Duality Principle — explains the NAND↔NOR mirror

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Universal gate ka matlab hai ek aisa single gate jisse aap koi bhi Boolean function bana sakte ho. NAND aur NOR dono universal hain. Iska practical fayda ye hai ki factory ko sirf ek hi type ka chip banana padta hai — sasta, standard, aur usi se pura CPU, memory, adder sab ban jaata hai.

Kaam kaise karta hai? Dhyaan do — NAND ke andar pehle se hi ek NOT chhupa hua hota hai ( $\overline{AB}$ ). Agar dono input same kar do ( $A\uparrow A$ ), toh $\overline{A}$ mil jaata hai, matlab NOT free me. Ek baar NOT mil gaya, toh AND banao NAND ko invert karke (2 gates), aur OR banao De Morgan se — dono input pehle invert karo phir NAND karo (3 gates). Jab NOT, AND, OR teeno ban gaye, toh proof complete: NAND universal hai. NOR ke liye bilkul ulta — OR sasta (2 gate), AND mehnga (3 gate), duality ki wajah se.

Sabse common galti: log sochte hain AND ya OR bhi universal hain. Nahi! AND/OR invert nahi kar sakte (monotonic hain) — jab tak gate me NOT nahi hoga, universal nahi ho sakta. Isliye sirf NAND/NOR hi jaadu ki brick hain. Exam me yaad rakho: OR-from-NAND me pehle inputs invert karna De Morgan ke wajah se zaroori hai, warna answer galat aayega.

Universal gates (NAND - NOR completeness)

WHAT / WHY / HOW

Definitions

Deriving everything from NAND (first principles)

Step 1 — NOT from NAND

Step 2 — AND from NAND

Step 3 — OR from NAND (De Morgan is the key)

Deriving everything from NOR (the dual)

Worked examples

Common mistakes

Active-recall flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Boolean Algebra & Logic Gates

Connections