NAND Universality

5 min read

Parent
🌐
Universal Gates
NAND and NOR can build anything
Current
🔧
NAND Universality
Building any gate from NAND alone

NAND Universality

Part of Boolean Logic and Gates

How to implement every Boolean function using only NAND gates — the practical consequence of NAND’s universal completeness.

Why This Matters

NAND universality is one of the most useful facts in digital design. It means that if you have only one type of gate — NAND — you can build any logic circuit: AND, OR, NOT, XOR, flip-flops, adders, multiplexers, everything. You do not need a variety of gate types.

This has immense practical consequences. When building from discrete components, you stock one IC type. When designing a chip, you optimize one cell library. When programming an FPGA, the fabric is mostly NAND-like LUTs. The entire edifice of digital computation rests on NAND universality.

The proof is constructive: showing how to build NOT, AND, and OR from NAND is sufficient, because these three gates can build anything (they are a functionally complete set). From NAND, you derive the complete set.

NOT from NAND

Connect both inputs of a 2-input NAND gate to the same signal A:

Y = NAND(A, A) = NOT(A AND A) = NOT(A) [by idempotent law: A AND A = A]

This is a NAND gate used as an inverter. Drawing the circuit: tie both input pins together and connect to the input signal. The output is the logical complement.

You use one gate and one input signal to get a NOT gate. Every NAND-based system uses this trick constantly.

AND from NAND

AND requires two NAND gates:

  1. First gate: P = NAND(A, B) = NOT(A AND B)
  2. Second gate (as inverter): Y = NAND(P, P) = NOT(P) = A AND B

So AND(A,B) = NAND(NAND(A,B), NAND(A,B)).

The first NAND computes NAND, and the second NAND (wired as inverter) cancels the inversion to restore AND. Two NAND gates implement one AND gate.

In practice, if you need AND in a NAND-only design, you use this two-gate substitution. Some designers prefer to draw the schematic with an AND symbol for clarity and note that it is implemented as NAND-NAND.

OR from NAND

OR requires three NAND gates, using DeMorgan’s theorem:

OR(A,B) = NOT(NOT-A AND NOT-B) [DeMorgan] = NAND(NOT-A, NOT-B) = NAND(NAND(A,A), NAND(B,B))

  1. Gate 1: P = NAND(A, A) = NOT-A
  2. Gate 2: Q = NAND(B, B) = NOT-B
  3. Gate 3: Y = NAND(P, Q) = NOT(NOT-A AND NOT-B) = A OR B

So three NAND gates implement one OR gate.

The insight is to pre-invert both inputs with NAND-as-inverters, then feed them into a final NAND. DeMorgan transforms the overall operation from NAND to OR.

NOR, XNOR, and XOR from NAND

NOR: NOR(A,B) = NOT(OR(A,B)). Build OR from 3 NANDs as above, then invert with a 4th NAND: total 4 NAND gates.

XOR: XOR requires 4 NAND gates in an elegant circuit:

  1. M = NAND(A, B)
  2. P = NAND(A, M)
  3. Q = NAND(B, M)
  4. Y = NAND(P, Q) = A XOR B

This four-NAND XOR is standard in TTL design. The 74LS86 XOR IC internally uses this topology. Verify with the truth table:

  • A=0, B=0: M=1, P=NAND(0,1)=1, Q=NAND(0,1)=1, Y=NAND(1,1)=0 ✓
  • A=0, B=1: M=1, P=NAND(0,1)=1, Q=NAND(1,1)=0, Y=NAND(1,0)=1 ✓
  • A=1, B=0: M=1, P=NAND(1,1)=0, Q=NAND(0,1)=1, Y=NAND(0,1)=1 ✓
  • A=1, B=1: M=0, P=NAND(1,0)=1, Q=NAND(1,0)=1, Y=NAND(1,1)=0 ✓

XNOR: add a 5th NAND as inverter after the XOR circuit.

SR Latch from NAND

Two cross-coupled NAND gates form an SR latch (Set-Reset latch):

  • Gate 1: Q = NAND(S, NOT-Q)
  • Gate 2: NOT-Q = NAND(R, Q)

This is the fundamental memory cell. When S goes low (active-low set), Q is forced to 1 regardless of NOT-Q. When R goes low (active-low reset), NOT-Q is forced to 1 regardless of Q. With both S and R high (inactive), the latch holds its previous state.

The SR latch from NAND is the building block for all flip-flops. Every D flip-flop, JK flip-flop, and T flip-flop inside a TTL or CMOS IC ultimately resolves to cross-coupled NAND or NOR gates at the transistor level.

This demonstrates the full chain of NAND universality: from single-gate NOT, AND, OR derivations to multi-gate memory elements, everything derives from NAND.

Practical NAND-Only Design Strategy

When designing a circuit to use only one gate type:

  1. Express the circuit in terms of AND, OR, NOT using standard methods.
  2. Substitute each primitive: AND → 2 NANDs, OR → 3 NANDs, NOT → 1 NAND.
  3. Simplify: adjacent inversions cancel. A NAND followed immediately by a NOT-NAND inverter reduces to AND. Look for these cancellations.
  4. Count gates and group into IC packages. A 74LS00 has 4 NAND gates; a 74LS10 has three 3-input NANDs.

Optimizing gate count matters for reducing IC packages. Every package eliminated reduces cost, power consumption, and board space.

Example: build a 2-bit comparator (output 1 when A = B) using only NAND:

  • A equals B when XNOR(A,B) = 1
  • XNOR = NOT(XOR) = NAND(NAND(P,Q), NAND(P,Q)) where P and Q are the XOR intermediate nodes
  • Total: 5 NAND gates per bit, with a final AND gate (2 NANDs) across all bit XNORs for a multi-bit comparator