Chapter 04 of 32

Universal Gates: NAND & NOR

In Logic Gates we met seven gate types. Here is a surprising fact: you need only one of them. With enough NAND gates, or enough NOR gates, you can build NOT, AND, OR, XOR, an adder, a flip-flop, even a whole processor. That is why NAND and NOR are called universal gates.

This is not just a puzzle. Real chips lean on it: in CMOS, NAND and NOR are the cheapest and fastest gates (4 transistors for 2 inputs, versus 6 for AND or OR), flash memory is literally named "NAND flash" after its cell arrangement, and old lab kits often had only 7400 NAND chips. In this chapter we build every basic gate from NAND and from NOR, count the gates needed, and learn the standard method to convert any two-level circuit to NAND-only or NOR-only form.


Functional Completeness

A set of operations is functionally complete if every Boolean function can be expressed using only operations from that set.

One detail matters in exam questions: are the constants 0 and 1 available for free (an input tied to VCC or ground)? Some sets are complete only with a constant. In this chapter we always say explicitly when a constant is used; NAND and NOR need none.

We already know that {AND, OR, NOT} is complete: any truth table can be written as an OR of AND terms, one for each row where the output is 1 (we formalise this in Canonical Forms: SOP & POS). So, to prove that some gate G is universal, it is enough to show that NOT, AND and OR can each be made from G alone.

A universal gate is a single gate type that is functionally complete by itself. NAND and NOR are the two universal 2-input gates.

Two facts that the proofs use (the second is one of De Morgan's Theorems, which gets its own chapter; here we can simply check it by truth table):

(A·A)′ = A′                 (A + A)′ = A′
(A′·B′)′ = A + B            (A′ + B′)′ = A·B

Building Everything from NAND

NOT from NAND (1 gate)

Tie both inputs together: (A·A)′ = A′. (Alternatively, tie one input to 1: (A·1)′ = A′.)

  A ──┬──┐
      │  NAND ──── A′
      └──┘

AND from NAND (2 gates)

A NAND followed by a NAND-inverter undoes the inversion: ((AB)′)′ = AB.

  A ──┐                 ┌──┐
      NAND ── (AB)′ ──┬─┤  NAND ──── AB
  B ──┘               └─┤
                        └──┘

OR from NAND (3 gates)

Invert each input first, then NAND them: (A′·B′)′ = A + B.

  A ── NAND(A,A) ── A′ ──┐
                         NAND ──── (A′B′)′ = A + B
  B ── NAND(B,B) ── B′ ──┘

NOR from NAND (4 gates)

Build OR (3 gates) and invert the result (1 more gate).

XOR from NAND (4 gates)

This is the famous 4-NAND XOR. Let G1 = (AB)′. Then:

               ┌── NAND(A, G1) = G2 ──┐
  A ──┐        │                      │
      NAND ─ G1┤                      NAND ──── Y = A ⊕ B
  B ──┘        │                      │
               └── NAND(B, G1) = G3 ──┘

G2 = (A·(AB)′)′ = (A·(A′ + B′))′ = (AB′)′
G3 = (B·(AB)′)′ = (A′B)′
Y  = (G2·G3)′  = ((AB′)′·(A′B)′)′ = AB′ + A′B = A ⊕ B ✓

Why this beats the obvious way: AB′ + A′B written directly needs 2 inverters + 2 ANDs + 1 OR. Sharing G1 between both branches saves gates. XNOR needs one extra NAND to invert the XOR output, 5 in total.


Building Everything from NOR

NOR is the dual of NAND: swap AND with OR in every construction above.

  • NOT (1 gate): (A + A)′ = A′, or tie one input to 0.

  • OR (2 gates): NOR followed by a NOR-inverter: ((A + B)′)′ = A + B.

  • AND (3 gates): invert both inputs, then NOR: (A′ + B′)′ = AB.

  • NAND (4 gates): AND (3) followed by an inverter.

  • XNOR (4 gates): the same 4-gate pattern as the NAND XOR, but with NOR gates, gives XNOR. Let G1 = (A + B)′; G2 = (A + G1)′; G3 = (B + G1)′; Y = (G2 + G3)′ = (A ⊕ B)′.

  • XOR (5 gates): XNOR plus one inverter.

AND from NOR:
  A ── NOR(A,A) ── A′ ──┐
                        NOR ──── (A′ + B′)′ = AB
  B ── NOR(B,B) ── B′ ──┘

Minimum Gate Counts (2-input gates only)

Function

Using only NAND

Using only NOR

NOT

1

1

AND

2

3

OR

3

2

NAND

1

4

NOR

4

1

XOR

4

5

XNOR

5

4

Half adder (sum and carry)

5

5

These minimums were confirmed by an exhaustive computer search over all circuits of 2-input gates (inputs A and B only, no constants). Notice the symmetry: every NAND count matches the NOR count of the dual function. The 5-NAND half adder is the 4-NAND XOR plus one NAND that inverts G1 = (AB)′ back to the carry AB. (Half adders are built properly in Half & Full Adders.)


NAND and NOR Are Not Associative

AND is associative, so (AB)C = A(BC) = ABC. NAND is not: chaining two 2-input NANDs does not give a 3-input NAND.

NAND(NAND(A, B), C) = ((AB)′·C)′ = AB + C′        (expand with De Morgan)
3-input NAND        = (ABC)′     = A′ + B′ + C′

To build a 3-input NAND from 2-input ones, first make AB with a NAND plus an inverter, then NAND that with C: three 2-input gates. The same holds for NOR.


Alternative Symbols: Thinking in Bubbles

De Morgan's law lets us draw each gate in two equivalent ways:

Gate

Standard view

Equivalent view

Read the equivalent view as

NAND

AND with output bubble: (AB)′

OR with bubbles on both inputs: A′ + B′

"Negative-OR": output is HIGH if any input is LOW

NOR

OR with output bubble: (A + B)′

AND with bubbles on both inputs: A′B′

"Negative-AND": output is HIGH only if all inputs are LOW

   NAND                       same NAND, drawn as negative-OR
  A ──┐                      A ──o╲
      AND o── (AB)′               OR ──── A′ + B′  (= (AB)′)
  B ──┘                      B ──o╱

Bubble rule: two bubbles on the same wire (an output bubble feeding an input bubble) cancel, because (X′)′ = X. This rule is all you need to convert circuits.


Two-Level NAND-NAND Implementation (from SOP)

A sum-of-products (SOP) expression such as AB + CD is naturally an AND-OR circuit: one level of AND gates feeding one OR gate.

Rule: An AND-OR (SOP) circuit becomes a NAND-NAND circuit by replacing every gate with a NAND. A term that is a single literal must be fed to the second-level NAND in complemented form.

Why it works: replace each AND with "AND + output bubble" and the OR with its negative-OR form "OR with input bubbles". Each new output bubble meets an input bubble and they cancel, so the logic is unchanged, and every gate is now a NAND.

Example 1: F = AB + CD

AND-OR:                              NAND-NAND:

A ──┐                                A ──┐
    AND ── AB ──┐                        NAND ── (AB)′ ──┐
B ──┘           OR ── F              B ──┘               NAND ── F
C ──┐           │                    C ──┐               │
    AND ── CD ──┘                        NAND ── (CD)′ ──┘
D ──┘                                D ──┘

Check: F = ((AB)′·(CD)′)′ = AB + CD ✓      (3 NAND gates, all 2-input)

Example 2: F = A′B + AC

Step 1: we need A′ → one NAND as inverter: NAND(A, A) = A′
Step 2: first level:  P = NAND(A′, B) = (A′B)′,   Q = NAND(A, C) = (AC)′
Step 3: second level: F = NAND(P, Q) = A′B + AC

Total: 4 NAND gates.

Example 3: A Single-Literal Term, F = AB + C

The term C has no AND gate. In the NAND-NAND form the second-level NAND sees the output of first-level NANDs, which are complemented, so C must enter as C′:

F = NAND( NAND(A, B), C′ ) = ((AB)′·C)′ = AB + C ✓

Common error: F = NAND(NAND(A, B), C) gives AB + C′  ✗

Two-Level NOR-NOR Implementation (from POS)

A product-of-sums (POS) expression such as (A + B)(C + D) is an OR-AND circuit.

Rule: An OR-AND (POS) circuit becomes a NOR-NOR circuit by replacing every gate with a NOR. A single-literal factor must be fed to the second-level NOR in complemented form.

Example 4: F = (A + B)(C + D)

A ──┐
    NOR ── (A + B)′ ──┐
B ──┘                 NOR ── F = ((A + B)′ + (C + D)′)′ = (A + B)(C + D) ✓
C ──┐                 │
    NOR ── (C + D)′ ──┘
D ──┘

So SOP pairs naturally with NAND and POS pairs naturally with NOR. (You can also implement SOP with NOR gates, but it needs extra inverters or more levels.) How to obtain minimal SOP and POS expressions is the job of Canonical Forms: SOP & POS and Karnaugh Maps.


Multi-Level Circuits

For circuits with more than two levels, use the bubble method:

  1. Replace each AND by a NAND (AND + output bubble), and each OR by a NAND drawn as negative-OR (input bubbles).

  2. Wherever a bubble is not matched by another bubble on the same wire, insert an inverter (a NAND with tied inputs), or complement the input variable if it comes straight from an input.

Example 5: F = A(B + CD) with NAND Only

Original:  CD → AND,  B + CD → OR,  A·(...) → AND

G1 = NAND(C, D)          = (CD)′                 AND → NAND (output bubble)
G2 = NAND(B, B)          = B′                    B enters the negative-OR without a bubble: invert it
G3 = NAND(G1, G2)        = ((CD)′·B′)′ = CD + B  OR drawn as negative-OR; G1's bubble cancels
G4 = NAND(A, G3)         = (A(B + CD))′          AND → NAND, but now F is inverted ...
G5 = NAND(G4, G4)        = A(B + CD) = F ✓       ... so add an inverter at the output

Total: 5 NAND gates.

Verifying the Constructions in Python

The program below builds each gate from NAND or NOR only, checks every input combination, and demonstrates that NAND is not associative.

from itertools import product

def nand(*x):
    return 0 if all(x) else 1

def nor(*x):
    return 0 if any(x) else 1

# Gates built ONLY from NAND
def not_n(a):     return nand(a, a)
def and_n(a, b):  return nand(nand(a, b), nand(a, b))
def or_n(a, b):   return nand(nand(a, a), nand(b, b))
def xor_n(a, b):
    g1 = nand(a, b)
    return nand(nand(a, g1), nand(b, g1))

# Gates built ONLY from NOR
def not_r(a):     return nor(a, a)
def or_r(a, b):   return nor(nor(a, b), nor(a, b))
def and_r(a, b):  return nor(nor(a, a), nor(b, b))

ok = True
for a, b in product([0, 1], repeat=2):
    ok &= not_n(a) == 1 - a and and_n(a, b) == (a & b)
    ok &= or_n(a, b) == (a | b) and xor_n(a, b) == (a ^ b)
    ok &= not_r(a) == 1 - a and or_r(a, b) == (a | b) and and_r(a, b) == (a & b)
print("All NAND/NOR constructions correct:", ok)

# Two-level NAND-NAND for F = AB + CD
bad = [(a, b, c, d) for a, b, c, d in product([0, 1], repeat=4)
       if nand(nand(a, b), nand(c, d)) != ((a & b) | (c & d))]
print("NAND-NAND mismatches for AB + CD:", bad)

# NAND is not associative
for a, b, c in product([0, 1], repeat=3):
    if nand(nand(a, b), c) != nand(a, b, c):
        print(f"A={a} B={b} C={c}: NAND(NAND(A,B),C) = {nand(nand(a, b), c)}, "
              f"3-input NAND = {nand(a, b, c)}")

Output:

All NAND/NOR constructions correct: True
NAND-NAND mismatches for AB + CD: []
A=0 B=0 C=1: NAND(NAND(A,B),C) = 0, 3-input NAND = 1
A=0 B=1 C=1: NAND(NAND(A,B),C) = 0, 3-input NAND = 1
A=1 B=0 C=1: NAND(NAND(A,B),C) = 0, 3-input NAND = 1
A=1 B=1 C=1: NAND(NAND(A,B),C) = 1, 3-input NAND = 0

The four mismatching rows are exactly the rows where C = 1, matching our algebra: the chain gives AB + C′, the true 3-input NAND gives A′ + B′ + C′.


Other Functionally Complete Sets

Set

Complete?

Reason

{AND, OR, NOT}

Yes

Any truth table can be written as SOP

{AND, NOT}

Yes

OR = (A′B′)′

{OR, NOT}

Yes

AND = (A′ + B′)′

{NAND}, {NOR}

Yes

Shown above

{AND, OR}

No

Cannot make NOT: if all inputs go from 0 to 1, an AND/OR circuit's output can never go from 1 to 0 (monotone)

{XOR, NOT}

No

Can only produce functions like A ⊕ B ⊕ ... ⊕ constant (linear); cannot make AND

{XOR, AND} with constant 1

Yes

NOT A = A ⊕ 1, and {AND, NOT} is complete

{→} (implication A′ + B) with constant 0

Yes

A → 0 = A′; then (A′) → B = A + B; {OR, NOT} is complete

The general test (Post's theorem) says a set is complete exactly when it is not entirely inside any of five special classes (functions that preserve 0, preserve 1, are monotone, are linear, or are self-dual). For exams, the practical method is the one used above: try to build NOT and then AND or OR.


Common Mistakes

  • Forgetting to complement single-literal terms in NAND-NAND (SOP) or NOR-NOR (POS) conversion.

  • Chaining 2-input NANDs to make a 3-input NAND. NAND is not associative.

  • Using NAND-NAND for a POS expression directly. NAND-NAND realises SOP; NOR-NOR realises POS. Converting the other way needs extra inverters.

  • Mixing up the counts: AND needs 2 NANDs but 3 NORs; OR needs 3 NANDs but 2 NORs.

  • Thinking AND or OR is universal. Neither can produce NOT.

  • Forgetting the output inverter in multi-level conversions when the final gate is an AND (as in Example 5).


GATE and Interview Questions

Q1. What is the minimum number of 2-input NAND gates required to implement A ⊕ B? A ⊙ B?

XOR: 4. XNOR: 5 (with NOR gates the counts swap: XNOR 4, XOR 5).

Q2. What is the output of NAND(NAND(A, B), NAND(A, B))?

Let P = (AB)′. NAND(P, P) = P′ = AB, an AND gate.

Q3. Implement F = XY + Z using only 2-input NAND gates. How many are needed?

F = NAND(NAND(X, Y), Z′), with Z′ = NAND(Z, Z). Total: 3 gates.

Q4. The function f(x, y) = x′y. Is {f} functionally complete? What about {f, 1}?

{f} alone is not: f(0, 0) = 0, so any circuit of f gates outputs 0 when all inputs are 0 and can never make NOT. With constant 1: f(x, 1) = x′ gives NOT, and f(f(y, 1), x) = (y′)′x = xy gives AND. {NOT, AND} is complete, so {f, 1} is complete.

Q5. Why are NAND gates preferred over AND gates in CMOS?

A CMOS 2-input NAND needs only 4 transistors; an AND is a NAND plus an inverter (6 transistors) and has an extra stage of delay. NAND is also preferred over NOR because its series transistors are the faster n-type ones, while NOR puts the slower p-type transistors in series.

Q6. Implement F = (A + B)(A′ + C) using NOR gates only.

Need A′ = NOR(A, A). Then P = NOR(A, B) = (A + B)′, Q = NOR(A′, C) = (A′ + C)′, F = NOR(P, Q) = (A + B)(A′ + C). Total 4 NOR gates.

Q7. An XOR gate has one input tied to 1. A NOR gate has one input tied to 0. What does each do?

Both act as inverters: A ⊕ 1 = A′ and (A + 0)′ = A′.


Summary

  • A set of gates is functionally complete if it can build every Boolean function. NAND alone and NOR alone are complete: they are the universal gates.

  • NAND counts: NOT 1, AND 2, OR 3, NOR 4, XOR 4, XNOR 5. NOR counts: NOT 1, OR 2, AND 3, NAND 4, XNOR 4, XOR 5. A half adder needs 5 of either.

  • NAND = negative-OR; NOR = negative-AND. Two bubbles on one wire cancel.

  • SOP → NAND-NAND, POS → NOR-NOR: replace every gate, and complement single-literal terms.

  • NAND and NOR are not associative.

  • {AND, OR} and {XOR, NOT} are not complete; {AND, NOT}, {OR, NOT}, {XOR, AND, 1} are.

  • Next, Boolean Algebra Laws gives us the rules to simplify expressions before we build them.