3.2.2 NAND and NOR as universal gates; functionally complete sets

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

Σm(1, 4, 5, 6, 7) of 3 variables in ΠM form? from Lesson 3.2.1
De Morgan for (AB)'? from Lesson 3.1.2
Output of NOR when all inputs are 0? from Lesson 3.1.1

1 · The Hook

🎣

Chip factories love to make one kind of gate in huge numbers. Amazingly, a single gate type can build every possible function: NAND alone is enough, and so is NOR. GATE asks how many NAND gates a function needs and, often, whether a strange set of gates (say XOR and AND) is functionally complete.

2 · Predict First

🤔

Connect both inputs of a NAND gate to the same signal A. What does the gate output?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

(A · A)' = A'. A NAND with its inputs tied together is a NOT gate.

🗣️

In plain words

A set of gates is functionally complete if every Boolean function can be built from it. AND, OR and NOT together are complete (every function has a canonical SOP). So if a gate can imitate NOT and AND, or NOT and OR, it is complete on its own. NAND and NOR can, which is why they are called universal gates.

1. Everything from NAND

NOT: A NAND A = A' (1 gate).
AND: NAND followed by a NOT-NAND = AB (2 gates).
OR: invert both inputs, then NAND: (A'B')' = A + B (3 gates).
XOR needs 4 NAND gates (the minimum); XNOR needs 5.

2. Everything from NOR

NOT: A NOR A = A' (1). OR: NOR then NOT (2). AND: invert inputs, then NOR: (A' + B')' = AB (3).
XNOR needs 4 NOR gates; XOR needs 5.

3. Two-level conversions

SOP → NAND–NAND: replace every AND gate and the final OR gate by NAND gates. AB + CD = ((AB)'(CD)')' uses 3 NAND gates.
POS → NOR–NOR: replace every OR gate and the final AND by NOR gates.
A single literal entering the second level must be complemented (or passed through an extra NOT).

4. Is a set of gates complete? (Post's test)

Check five families. A function is:

0-preserving if all-0 inputs give 0.
1-preserving if all-1 inputs give 1.
Self-dual if complementing every input complements the output (F(A', B', …) = F(A, B, …)').
Monotone if turning an input from 0 to 1 never turns the output from 1 to 0.
Linear if it is an XOR of some inputs, possibly with 1 (like A ⊕ C ⊕ 1).

A set is complete exactly when, for each of the five families, at least one gate of the set is outside it. If every gate stays inside one family, so does everything built from them.

Set	Complete?	Reason
{NAND}, {NOR}	yes	each breaks all five
{AND, NOT}, {OR, NOT}	yes	NOT and AND (or OR)
{AND, OR}	no	both monotone: no way to invert
{XOR, AND}	no	both 0-preserving
{XOR, AND, constant 1}	yes	A ⊕ 1 = A' gives NOT
{implication A → B = A' + B}	no	1-preserving
{implication, constant 0}	yes	A → 0 = A', then A' → B = A + B
{majority, NOT}	no	both self-dual

4 · Visual

Diagram: A · A · B · A · B · A' · AB · A + B

NOT (1 NAND), AND (2 NANDs) and OR (3 NANDs) built from NAND gates only.

5 · Worked Examples

Example 1 Easy

How many 2-input NAND gates make a NOT, an AND and an OR?

Solution

1, 2 and 3.

Example 2 Medium

Implement F = AB + CD with NAND gates only. How many?

Solution

NAND–NAND: two first-level NANDs give (AB)' and (CD)'; a third NAND gives ((AB)'(CD)')' = AB + CD → 3 gates.

Example 3 GATE

Is the set {XOR, AND} functionally complete? What if the constant 1 is also available?

Solution

No: both gates output 0 when all inputs are 0, so nothing built from them can output 1 on all-0 inputs (no NOT). With constant 1: A ⊕ 1 = A', so NOT and AND are available → yes.

6 · GATE Traps

⚠️

NAND–NAND realises an SOP; NOR–NOR realises a POS (not the other way round).
Minimum 2-input NAND count: NOT 1, AND 2, OR 3, XOR 4, XNOR 5 (for NOR swap AND ↔ OR and XOR ↔ XNOR).
Completeness needs every one of the five families broken by some gate.
Constants count only if the question says they are available.

7 · Memory Hook

🧠

"Tie a NAND's inputs: NOT. SOP → NAND-NAND, POS → NOR-NOR. Complete = escapes 0-preserving, 1-preserving, self-dual, monotone and linear."

8 · Connect the Dots

How many different Boolean functions of n variables exist at all, and how many are self-dual or symmetric? The next lesson counts them, a regular GATE NAT question, and collects XOR tricks.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markNAND count

Minimum number of 2-input NAND gates needed to build a 2-input OR gate?

Numerical answer: ________

Q2NAT2 marksXOR from NAND

Minimum number of 2-input NAND gates needed to build a 2-input XOR gate?

Numerical answer: ________

Q3MCQ1 markTwo-level

A sum-of-products expression is most directly realised with:

(A) only inverters
(B) NOR gates in two levels
(C) NAND gates in two levels
(D) XOR gates

Q4MSQ2 marksCompleteness

Which of these sets are functionally complete (no constants available)?

(A) {XOR, AND}
(B) {OR, NOT}
(C) {NOR}
(D) {AND, OR}

Q5MCQ2 marksCompleteness

Which set is NOT functionally complete, even though it contains an inverter?

(A) {NOT, majority(A, B, C)}
(B) {NOT, AND}
(C) {NOT, NAND}
(D) {NOT, OR}

10 · Rule Card

NAND: NOT = 1, AND = 2, OR = 3, XOR = 4, XNOR = 5 gates. NOR: NOT 1, OR 2, AND 3, XNOR 4, XOR 5.
SOP → NAND–NAND; POS → NOR–NOR.
Post: complete ⟺ some gate is not 0-preserving, some not 1-preserving, some not self-dual, some not monotone, some not linear.
Complete: {NAND}, {NOR}, {AND, NOT}, {OR, NOT}, {XOR, AND, 1}, {→, 0}. Not: {AND, OR}, {XOR, AND}, {→}, {majority, NOT}.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

universal gatesNOT, AND, OR from NANDNOT, OR, AND from NORminimum NAND/NOR gate countsNAND–NAND realisation of SOPNOR–NOR realisation of POSfunctional completeness0-preserving1-preservingself-dualmonotonelinear functionsPost's completeness test

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

ΠM(0, 2, 3).
A' + B'.