Functional Completeness in Digital Logic: NAND, NOR and Worked Examples

Calling NAND and NOR "universal" is a conclusion, not a proof. In GATE CS preparation, the harder question is whether an allowed operator set can express every Boolean function when gate names are replaced by truth vectors or constants disappear. Universal Gates for GATE owns bubble-pushing, fan-in assumptions and minimum gate counts, while Universal Realization with NAND and NOR Gates owns SOP-to-NAND and POS-to-NOR circuit conversion; functional completeness starts one level earlier, with a proof that the permitted operators can generate every function.

Functional completeness is a property of an operator set

An n-variable Boolean function is a mapping f: {0,1}^n -> {0,1}. A set of connectives is functionally complete when expressions built only from that set can represent every Boolean function, for every finite number of inputs.

The basis {AND, OR, NOT} is complete because every truth table can be written as a disjunctive normal form: make one product term for each 1-row, then OR those terms. Therefore, recovering AND, OR and NOT from another set is enough to prove that set complete.

Keep operator, gate and basis separate. An operator is a truth-table rule, a gate is one circuit realisation, and a basis is the full set of allowed operators. One circuit proves that one target function is expressible; it does not prove that the basis can express every function.

Two proof routes: recover a basis or apply Post's criterion

Constructive route. Derive a known complete basis such as {AND, OR, NOT}, or derive NAND or NOR. This is usually the shortest proof when useful constants or repeated inputs are available.

Closure route. Show that every expression made from the set remains inside a property that not all Boolean functions have. For example, {AND, OR} remains monotone, so it can never produce NOT X. Likewise, {XOR, NOT} remains affine, so it cannot produce X AND Y.

Post's criterion packages the closure route into five classes: T0 preserves 0; T1 preserves 1; M is monotone; L is affine, meaning an XOR of selected inputs plus an optional constant; and S is self-dual, satisfying f(NOT x)=NOT f(x). A set is complete exactly when it is not contained in any one class. For a multi-operator set, each class needs at least one operator outside it; one operator need not escape all five.

The constructive identities below use De Morgan's law and normal forms developed in the Boolean Algebra and K-map Minimization Guide.

NAND and NOR recover NOT, AND and OR

Write NAND as X NAND Y = NOT(X AND Y). Repeated NAND gives:

• NOT X = X NAND X

• X AND Y = (X NAND Y) NAND (X NAND Y)

• X OR Y = (X NAND X) NAND (Y NAND Y)

The dual construction starts from X NOR Y = NOT(X OR Y):

• NOT X = X NOR X

• X OR Y = (X NOR Y) NOR (X NOR Y)

• X AND Y = (X NOR X) NOR (Y NOR Y)

At X=1, Y=0, tied NAND inputs give NOT X=0 and tied NOR inputs give the same result. The NAND reconstruction produces X AND Y=0 and X OR Y=1; the NOR reconstruction produces those same target values. Since either operator recovers the complete standard basis, NAND alone and NOR alone are complete.

Worked Post-class test: NAND passes, implication fails

In input order 00,01,10,11, NAND has vector 1,1,1,0. It is outside T0 because f(0,0)=1, and outside T1 because f(1,1)=0. It is not monotone because 00 <= 11 while the output falls from 1 to 0.

An affine two-input function has form c XOR ax XOR by. NAND's first three values force c=1, a=0, b=0, which predicts f(1,1)=1 instead of 0, so NAND is outside L. It is outside S because f(0,1)=1 but NOT f(1,0)=0. NAND escapes all five classes, matching the constructive proof.

Now test implication g(x,y)=NOT x OR y, whose vector is 1,1,0,1. Because g(1,1)=1, implication preserves 1. Every composition made only from implication also preserves 1, so {g} is contained in T1 and is incomplete. If a constant 0 is supplied, g(x,0)=NOT x; that is a different basis because constants are operators too.

Worked constructive test: {AND, XOR, 1} is complete

The constant 1 turns XOR into negation: NOT X = X XOR 1. AND is already available. OR follows from X OR Y = X XOR Y XOR (X AND Y), so the set recovers {AND, OR, NOT} and is complete.

Removing 1 changes the answer. Every expression made from AND and XOR alone maps the all-zero input to 0, so {AND, XOR} is trapped in T0 and is incomplete. A proof must use exactly the basis named in the question.

Four-gate NAND trace: expressibility is not completeness

For F(A,B,C)=(A + NOT B)C, four reusable NAND stages are enough:

1. nA = NAND(A,A) = NOT A

2. S = NAND(nA,B) = A + NOT B

3. nF = NAND(S,C) = NOT(SC)

4. F = NAND(nF,nF) = SC

The eight-row trace verifies the circuit. It does not establish universality by itself; the earlier recovery of NOT, AND and OR supplies that proof.

For the accepting row 001, the nodes are nA=1, S=1, nF=0, F=1. For the rejecting row 011, they are nA=1, S=0, nF=1, F=0. The original expression gives the same outputs, and the full output set is {001,101,111}.

Functional-completeness exam procedure and proof traps

Use this order for a named gate, truth vector or unfamiliar operator set:

1. Write the exact operator definitions and note whether constants are available.

2. Try tied or repeated inputs to obtain NOT.

3. Recover AND, OR, NAND or NOR. Stop once a known complete basis is available.

4. If construction stalls, test Post's five closed classes or a simpler invariant such as monotonicity or 0-preservation.

5. Verify identities on a discriminating row, then count gates only under the stated fan-in and sharing model.

• One successful circuit proves completeness. Wrong. It proves only that one function is expressible.

• {XOR, NOT} is complete. Wrong. Its compositions remain affine.

• Constants are free. Wrong. Adding 0 or 1 can change the closure class and the answer.

• Every identity needs separate gates. Wrong. Shared intermediates are counted once when the model allows fan-out.

• Every operator must escape every Post class. Wrong. For a set, each class needs some member outside it.

Functional completeness: the short version

• Completeness belongs to the allowed set, including any constants.

• A constructive proof recovers a known complete basis.

• A closure proof shows incompleteness; Post's criterion provides the full five-class test.

• NAND and NOR each recover NOT, AND and OR.

• A worked circuit verifies one function, not the whole basis.

The four-gate construction outputs 1 on 001, 101, 111, while the implication and {AND, XOR} examples show how one preserved property blocks completeness. Use Zero to Hero, Complete CS Course to place these proof methods alongside Boolean algebra, combinational circuits and the rest of core Computer Science.