Universal Gate

A universal gate is one from which any Boolean function can be built. The two universal gates in standard logic are NAND and NOR — each is enough by itself to construct AND, OR, NOT, and therefore any combinational circuit.

That makes universality more than a curiosity. A chip foundry can stock a single library of NAND cells and synthesize any logic, simplifying manufacturing. NAND in particular is the cheapest gate to fabricate in CMOS (4 transistors, fast pull-down via NMOS), so much of modern silicon is built from NAND-dominated cell libraries.

NAND universality

Build the basic gates from NAND alone:

• NOT: tie the inputs together. $\overline{x\cdot x}=\overline{x}$.
• AND: NAND followed by NAND-as-NOT. $\overline{\overline{xy}}=xy$.
• OR: invert both inputs first, then NAND. By De Morgan’s Laws, $(x\text{ NAND }x)\text{ NAND }(y\text{ NAND }y)=\overline{\overline{x}\overline{y}}=x+y$.

NOR universality

Symmetrically:

• NOT: $\overline{x+x}=\overline{x}$.
• OR: NOR + NOR-as-NOT. $\overline{\overline{x+y}}=x+y$.
• AND: invert inputs first, then NOR. $(x\text{ NOR }x)\text{ NOR }(y\text{ NOR }y)=xy$ by De Morgan.

Why this is true

Both proofs hinge on De Morgan’s Laws. NAND can express NOT (by tying inputs), and NAND of inverted inputs is OR. So NAND can produce NOT, AND (via two NANDs), and OR (via three NANDs). Any combinational function can be written in SOP form using just AND, OR, NOT — therefore using just NAND.

Same argument with NOR using POS as the canonical form.

Practical use

In CMOS design, NAND is preferred over NOR because pull-down via NMOS in series is faster than pull-up via PMOS in series. Most ASIC standard-cell libraries supply both but NAND-based logic synthesis tends to produce smaller, faster designs.

For NAND-NAND synthesis (converting a SOP expression directly into a 2-level NAND network) and NOR-NOR synthesis (the POS counterpart), see those notes.