Universal Gates

5 min read

Parent
🔢
Boolean Logic & Gates
AND, OR, NOT circuits
Current
🌐
Universal Gates
NAND and NOR can build anything
Sub-Topics
🚫
NAND Gate
NOT-AND, the most versatile single gate
⛔
NOR Gate
NOT-OR, equally universal
🔧
NAND Universality
Building any gate from NAND alone

Universal Gates

Part of Boolean Logic and Gates

NAND and NOR as functionally complete gate sets — how a single gate type can implement any possible Boolean function, and why this matters for circuit construction.

Why This Matters

A universal gate is a gate from which any Boolean function can be constructed using only gates of that type. NAND and NOR are both universal gates. AND, OR, and NOT individually are not universal — you cannot build NOT from AND alone, for example.

This property has profound practical consequences. If you have only one type of gate available — one IC type, one fabrication cell, one relay configuration — you can still implement any digital circuit. You do not need a variety of gate types to build a complete computing system.

The universality of NAND and NOR is not just theoretical. It directly informs how chip designers work (standard cell libraries dominated by NAND/NOR), how FPGAs are structured (look-up tables that behave like universal logic elements), and how engineers stock components (one gate IC type per design rather than five).

Functional Completeness

A set of Boolean operations is functionally complete if every Boolean function can be expressed using only those operations. The simplest functionally complete sets are:

  • {AND, NOT} — AND and NOT alone are complete
  • {OR, NOT} — OR and NOT alone are complete
  • {NAND} — NAND alone is complete
  • {NOR} — NOR alone is complete
  • {AND, OR, NOT} — this set is redundant (OR and NOT alone suffice)

The key insight is that {AND, NOT} is complete (because you can build OR from them: A OR B = NOT(NOT-A AND NOT-B) by DeMorgan). Since NAND can produce both AND and NOT (see NAND universality article), NAND alone is complete.

What is NOT functionally complete:

  • {AND} alone — cannot build NOT
  • {OR} alone — cannot build NOT
  • {XOR} alone — cannot build AND (XOR can only produce even-parity functions)
  • {AND, OR} without NOT — cannot complement variables

Why NAND is the Industrial Choice

NAND dominates because it is the most natural gate in bipolar transistor technology (TTL, ECL). The multi-emitter transistor input stage of a TTL gate directly implements the AND function, and the inverting output stage naturally inverts it — producing NAND. To build AND in TTL requires a NAND gate followed by an inverter, costing an extra transistor stage.

NAND also has the lowest transistor count in bipolar: a 2-input NAND gate uses 4 transistors (multi-emitter input, phase splitter, totem-pole output). AND needs 5 (same plus inverter).

In CMOS, NOR is slightly more efficient than NAND in terms of switching speed because NMOS transistors (the pull-down network) are faster than PMOS. But the standard cell industry uses NAND because the historical tooling, libraries, and engineer training were all built around NAND.

Why NOR is Used in CMOS

CMOS NOR is natural because of transistor symmetry:

  • NMOS transistors in parallel (OR behavior) pull the output LOW when any input is HIGH
  • PMOS transistors in series pull the output HIGH only when ALL inputs are LOW

This directly implements NOR. To implement NAND in CMOS requires NMOS in series (slower) and PMOS in parallel (faster PMOS helps, but series NMOS degrades pull-down speed).

At large transistor counts (4+ inputs), NOR gates have better performance in CMOS because the series-NMOS chain in a NAND gate becomes very resistive. For this reason, complex CMOS logic cells (4+ inputs) often use NOR-based implementations.

Building Any Function from NAND Only

The practical synthesis procedure:

Step 1: Express the function in any standard form (SOP, POS, or truth table).

Step 2: Convert to NAND-only:

  • NOT: NAND(A,A)
  • AND: NAND(NAND(A,B), NAND(A,B))
  • OR: NAND(NAND(A,A), NAND(B,B))

Step 3: Optimize — adjacent NAND-NOT pairs cancel:

  • An AND feeding into an OR: (A AND B) OR (C AND D) = NAND(NAND(A,B), NAND(C,D)) This collapses directly to two-level NAND: the first level computes NAND terms, the second level computes NAND of those — which equals AND-OR.

Step 4: A two-level SOP circuit (AND-OR) is equivalent to a two-level NAND-NAND circuit. Every SOP expression maps directly to a NAND-NAND structure with no additional gates.

This is the fundamental NAND synthesis result: SOP → NAND-NAND. Write the sum of products, implement each product term as a first-level NAND, combine with a second-level NAND. No substitution or conversion needed beyond recognizing this duality.

Building Any Function from NOR Only

NOR synthesis uses the dual: POS → NOR-NOR.

Step 1: Express the function in product-of-sums (POS) form.

Step 2: Each sum term becomes a first-level NOR (since NOR is the complement of OR, and after the second NOR inversion you recover the OR of the sum terms).

The complete conversion:

  • A POS expression (OR-AND structure) maps directly to a NOR-NOR circuit.
  • First level NORs compute the complement of each sum term.
  • Second level NOR of those outputs: NOR(NOR terms) = NOT(NOT-OR1 OR NOT-OR2…) = OR1 AND OR2… [by DeMorgan] — which is the AND of the sum terms = POS. ✓

Verification: The Completeness Test

To verify that a gate G is universal, show you can build NOT from G, and either AND or OR from G.

For NAND:

  • NOT(A) = NAND(A, A): tie both inputs together.
  • AND(A,B) = NOT(NAND(A,B)) = NAND(NAND(A,B), NAND(A,B)): shown above.
  • With NOT and AND, you have a complete set. ✓

For NOR:

  • NOT(A) = NOR(A, A): tie both inputs together.
  • OR(A,B) = NOT(NOR(A,B)) = NOR(NOR(A,B), NOR(A,B)): two NOR gates.
  • With NOT and OR, you have a complete set. ✓

For XOR alone: XOR(A,A) = 0 (not a NOT gate — can only produce even-parity functions). XOR is not universal. ✗