3.8 Universal Gates: Building Everything from NAND or NOR Alone

Prove that NAND alone (and, symmetrically, NOR alone) can implement NOT, AND, and OR, and explain the concept of functional completeness that follows from this.

This closing topic of Module 3 ties together the universality claims made separately about NAND (Module 3.4) and NOR (Module 3.5) into a single, complete argument: a gate is called 'universal' precisely when every other logic gate — and by extension, every possible Boolean function of any number of variables — can be constructed using only copies of that one gate type. NAND and NOR are the two gates in standard digital electronics with this property, which is why real digital design so often standardizes on one of them (NAND-based standard-cell libraries are especially common) as the single physical building block an entire chip is fabricated from, regardless of how logically complex the final circuit is.

Core Concept: Functional Completeness

A set of logic gates is called functionally complete if any Boolean function whatsoever can be expressed using only gates from that set. NOT, AND, and OR together are the baseline functionally complete set that every Boolean expression in this course is ultimately built from — but the spec's coverage list for this topic narrows the question further: can a single gate type, on its own, already be functionally complete? For NAND and NOR individually, the answer is yes, and proving it requires just one thing: showing that gate alone can build all three of NOT, AND, and OR, since those three are already known to be sufficient for everything else.

This single-gate sufficiency is not just a theoretical curiosity — the spec's coverage explicitly lists 'NAND-only design' and 'NOR-only design' as real, named design styles, because manufacturing an integrated circuit from one repeated gate structure (rather than several different gate structures) simplifies the fabrication process considerably. That practical motivation is exactly why this proof matters enough to warrant its own dedicated topic after NAND and NOR have each already been introduced individually.

• Functional completeness: a gate set from which every possible Boolean function can be built. • NOT, AND, OR together form the baseline functionally complete set used throughout this course. • NAND alone is functionally complete; NOR alone is functionally complete — each is a single-gate complete set. • NAND-only and NOR-only design styles are used in real IC fabrication for manufacturing simplicity.

Step-by-Step: The Three-Stage NAND-Only Proof

The spec's tricky problem sets exactly this task: 'Prove that NAND alone can implement NOT, AND, OR.' The proof proceeds in three deliberate stages, each building on the previous one. Stage 1 — NOT from NAND: tie both inputs of a NAND gate to the same signal A. Since A · A = A (idempotence), (A · A)' reduces to A' — this was shown concretely in Module 3.4. Stage 2 — AND from NAND: feed A and B into one NAND gate to get (A · B)', then feed that result into a second NAND gate wired as a NOT gate (Stage 1's construction) to invert it back: ((A·B)')' = A · B, exactly plain AND, using two NAND gates total.

Stage 3 — OR from NAND: this final stage needs De Morgan's law (formally covered in Module 4.3), which states (A' · B')' = A + B. Building the right-hand side from NAND gates: first invert A and invert B (Stage 1's NOT-from-NAND construction, applied twice, using two NAND gates), then feed those two inverted signals, A' and B', into a third NAND gate. That NAND gate computes (A' · B')', which by De Morgan's law equals exactly A + B — OR, built entirely from NAND gates, using four NAND gates total (two for the input inversions, one... actually the final NAND gate is the third distinct NAND used, for five NAND gates in total across the two inverters plus the final gate). With NOT, AND, and OR all demonstrated using only NAND gates, and since NOT/AND/OR are already known to be sufficient to build any Boolean function, NAND alone is proven functionally complete.

The identical three-stage argument runs for NOR, with every AND replaced by OR and vice versa: NOR ties inputs together for NOT (Module 3.5), NOR builds OR by undoing NOR's own inversion with a NOR-built NOT, and NOR builds AND via the other half of De Morgan's law, (A' + B')' = A · B.

• Stage 1: NOT from NAND — tie both inputs together; A·A=A collapses to a plain inverter. • Stage 2: AND from NAND — one NAND for (A·B)', a second NAND-built NOT to undo the inversion. • Stage 3: OR from NAND — invert A and B individually (NAND-built NOTs), then NAND the two inverted signals; De Morgan's law confirms (A'·B')' = A+B. • The mirror-image argument, swapping AND/OR, proves NOR alone is also functionally complete.

Practical and Real-World Application: Standard-Cell and Discrete Logic

This proof is the theoretical foundation behind two very concrete real-world practices already previewed in the NAND and NOR lessons: the classic 7400-series TTL logic family, where a single dedicated 4-NAND-gate IC package can be wired, using nothing else, into any combinational function a hobbyist or engineer needs, and modern standard-cell ASIC design, where entire chip logic is synthesized down to arrays of a small number of primitive cells (often NAND- and NOR-based) precisely because those primitives are known, mathematically, to be sufficient for anything the design requires.

Functional completeness with a single gate type also matters for fault tolerance and testing in manufacturing: a fabrication process that only needs to produce, test, and characterize one transistor-level structure (rather than four or five distinct gate structures) has fewer failure modes to account for and can achieve tighter, more predictable timing and power characteristics across an entire chip.

Common Mistake and the Tricky Concept

A common shortcut mistake is stopping the proof after Stage 1 (NOT from NAND) and treating universality as essentially established, since that single construction already feels like the 'clever trick'. But functional completeness specifically requires all of NOT, AND, and OR to be demonstrated — Stage 1 alone only proves NAND can build NOT, not that it can build everything; Stages 2 and 3 (building AND and OR as well) are equally necessary parts of the proof, and OR's construction in particular genuinely depends on De Morgan's law, so skipping ahead without that law in hand leaves the proof incomplete.

It's also worth being precise that not every two-input gate is universal on its own: XOR and XNOR, for instance, are each individually insufficient to build every Boolean function (a circuit built purely from XOR gates cannot express every possible function, a fact tied to XOR's linear/self-inverse algebraic structure) — universality is a special property specifically belonging to NAND and NOR among the gates covered in this module, not a general property of 'any gate with an inversion bubble'.

Universality Proof Outline

The AND-from-NAND and OR-from-NOR constructions both reuse the NOT-from-tied-inputs trick as a sub-step. OR-from-NAND and AND-from-NOR both require De Morgan's law, formally proven in Module 4.3.

NAND-only construction:
  NOT:  Y = A NAND A = (A·A)' = A'
  AND:  Y = (A NAND B) NAND (A NAND B)
          = ((A·B)')' = A·B
  OR:   Y = (A NAND A) NAND (B NAND B)
          = (A') NAND (B')
          = (A'·B')' = A + B     [De Morgan's law]

NOR-only construction (mirror image):
  NOT:  Y = A NOR A = (A+A)' = A'
  OR:   Y = (A NOR B) NOR (A NOR B)
          = ((A+B)')' = A+B
  AND:  Y = (A NOR A) NOR (B NOR B)
          = (A') NOR (B')
          = (A'+B')' = A · B     [De Morgan's law]

Code Examples

This is exactly the spec's tricky problem worked through in full. Each stage depends on the one before it: Stage 2 reuses Stage 1's NOT-from-NAND trick to undo NAND's built-in inversion and recover plain AND, and Stage 3 uses two Stage-1-style inverters feeding a final NAND gate, whose result equals OR by De Morgan's law. Once all three base primitives are shown reachable, functional completeness follows because NOT/AND/OR were already established as sufficient for any Boolean function.

NOT + AND + OR, all built from NAND alone, proves NAND is functionally complete.

Goal: prove NAND alone implements NOT, AND, OR.

Stage 1 (NOT):  A NAND A = (A·A)' = A'          [idempotence]
Stage 2 (AND):  (A NAND B) NAND (A NAND B)
                = ((A·B)')'  = A·B              [Stage 1's NOT undoes the inversion]
Stage 3 (OR):   (A NAND A) NAND (B NAND B)
                = A' NAND B'
                = (A'·B')' = A + B               [De Morgan's law]

Conclusion: NOT, AND, OR all constructible from NAND ⇒ NAND is functionally complete.

NAND-Only OR Construction

Three NAND gates total: two configured as inverters, one as the final combiner.

A ──[NAND tied]──o── A'  ──┐
                              D──o── Y = A' NAND B' = A+B
  B ──[NAND tied]──o── B'  ──┘

Two NAND-built inverters feed a third NAND gate;
by De Morgan's law the result equals A + B.

Important Rules

Functional completeness: a gate (or gate set) from which every Boolean function can be built.

NAND alone is functionally complete: NOT, AND, and OR are each constructible from NAND gates only.

NOR alone is functionally complete, by the exact mirror-image (AND↔OR swapped) construction.

Not every gate is universal — XOR and XNOR alone cannot build every Boolean function.

Single-Gate-Type IC Fabrication

The classic 7400-series TTL logic family and modern standard-cell ASIC design both exploit NAND's (and NOR's) functional completeness: an entire chip's combinational logic can be synthesized from arrays of one repeated primitive gate structure, simplifying fabrication, testing, and timing/power characterization compared to manufacturing several distinct gate structures.

How It's Built From Other Gates

A, A (tied together) NOT from a single NAND: tie both NAND inputs to the same signal A. A NAND A = (A·A)′ = A′ — a NAND used this way is simply an inverter.

How It's Built From Other Gates

(A·B)′ tied together AND from two NANDs: the first NAND computes (A·B)′; a second NAND, wired as an inverter (both its inputs tied to that result), inverts it back to true A·B.

How It's Built From Other Gates

OR from three NANDs: invert A and invert B, each with a NAND wired as an inverter, then NAND the two inverted signals together. By De Morgan's law, (A′·B′)′ = A+B.

Concluding a gate is 'universal' after showing it can build NOT alone, without also showing AND and OR.

Universality requires demonstrating that a single gate type can construct all three of NOT, AND, and OR (the full baseline functionally complete set) — NOT alone is only the first of three required stages.

The spec's tricky problem explicitly asks to prove NAND implements 'NOT, AND, OR' — all three, not just one. Stage 1 (NOT) is necessary but not sufficient; Stages 2 and 3 (AND and OR) complete the proof.

[tricky-problem] The spec's tricky problem asks you to prove that NAND alone can implement NOT, AND, and OR, and concludes that therefore any Boolean function can be built from NAND gates. Why does proving just these three specific gates suffice for 'any Boolean function'? A. Because NOT, AND, and OR happen to be the three most common gates used in practice. B. Because NOT, AND, and OR together are already an established functionally complete set — every Boolean function can be expressed using just those three — so reconstructing all three from NAND transfers that same completeness to NAND alone. C. Because any circuit can always be simplified down to exactly three gates. D. Because NAND gates are cheaper to manufacture than other gates.

B. Because NOT, AND, and OR together are already an established functionally complete set — every Boolean function can be expressed using just those three — so reconstructing all three from NAND transfers that same completeness to NAND alone. — The logical structure of the proof is: (1) NOT+AND+OR is already known to be functionally complete, and (2) NAND alone can build NOT, AND, and OR. Combining these two facts, anything buildable from NOT+AND+OR is buildable from NAND alone, which is exactly what functional completeness of NAND means.

[interview] Which step of the NAND-only universality proof specifically requires De Morgan's law? A. Building NOT from NAND (tied inputs) B. Building AND from NAND (undoing NAND's own inversion with a second NAND-built NOT) C. Building OR from NAND (inverting both inputs first, then NAND-ing the inverted signals) D. None of the steps require De Morgan's law

C. Building OR from NAND (inverting both inputs first, then NAND-ing the inverted signals) — Building OR from NAND relies on the identity (A'·B')' = A+B, which is exactly De Morgan's law (formally covered in Module 4.3). The NOT construction uses only idempotence (A·A=A), and the AND construction uses only double-inversion cancellation ((X')'=X) — neither of those needs De Morgan's law, but the OR construction does.

Using only two-input NAND gates, derive a working XOR gate (Y = A ⊕ B = A'B + AB'). How many NAND gates does your construction need, and which sub-constructions from this lesson does it reuse?

A standard construction uses 4 NAND gates: Gate 1 = A NAND B; Gate 2 = A NAND Gate1; Gate 3 = B NAND Gate1; Gate 4 = Gate2 NAND Gate3 = Y. Expanding algebraically confirms Gate 4 equals A'B + AB'. This reuses the same principle as the lesson's stage-by-stage proof — combining several NAND gates to realize a target Boolean expression that is not itself a primitive.

Expand A'B + AB' and note it needs both inverted and non-inverted versions of A and B, ANDed in two different pairings, then ORed — every AND/OR/NOT you need is separately buildable from NAND per this lesson's proof.