Digital Logic Toolkit — Universal gates
Universal gates: build any logic circuit from NAND or NOR alone
Rebuild any of the other gates using only NAND, or only NOR, with the gate count.
Expression to convert
Accepts + · ' ¬ ∧ ∨ ⊕ ~ ! & | and the words AND, OR, NOT, XOR.
read as ((A · B) + C)
Notation used on this page
- Positive logic
- 1 = HIGH = asserted, 0 = LOW = deasserted. An active-low signal is written with an overbar in figures and a trailing _n in copyable text, for example CLR_n.
- Operators
- · AND (also written by juxtaposition, AB) · + OR · ′ complement (postfix; an overbar in figures) · ⊕ XOR · ⊙ XNOR · ↑ NAND (Sheffer stroke) · ↓ NOR (Peirce arrow).
- Precedence, highest first
- ( ) then ′ then · (including juxtaposition) then ⊕ and ⊙ then ↑ and ↓ then +. The parser echoes the fully parenthesised reading back, and warns without blocking when ⊕, ↑ or ↓ appears un-parenthesised beside · or +, because textbooks disagree there.
- Truth-table row order
- Binary counting order from all-zeros to all-ones. The first-listed variable is the most significant bit. Row index k is the integer value of the input vector, and the row is labelled mₖ.
- Minterms and maxterms
- Σm(…) lists the rows where F = 1. ΠM(…) lists the rows where F = 0. Mᵢ complements a variable wherever bit i is 1 — the opposite way round from mᵢ.
- Symbol standards
- IEEE means ANSI/IEEE Std 91-1984 with its 91a-1991 supplement — the distinctive shapes. IEC means IEC 60617-12 — the rectangular shapes with a qualifying symbol. The header toggle switches every figure on the page between them.
- Symbol-set toggle
- Both symbol standards are in this page’s HTML. The toggle in the header chooses which one is drawn, before the first frame is painted, and it changes nothing else on the page — not a truth table, not a gate count, not an answer.
Cost of each build
| Target | NAND gates | NAND levels | NOR gates | NOR levels |
|---|---|---|---|---|
| buffer | 2 | 2 | 2 | 2 |
| NOT | 1 | 1 | 1 | 1 |
| AND | 2 | 2 | 3 | 2 |
| NAND | 1 | 1 | 4 | 3 |
| OR | 3 | 2 | 2 | 2 |
| NOR | 4 | 3 | 1 | 1 |
| XOR | 4 | 3 | 5 | 3 |
| XNOR | 5 | 4 | 4 | 3 |
The circuit as written
IEC 60617-12:1997 is a paid standard and its per-symbol dimensions are not public. These rectangular symbols follow the published module-grid construction (module M = 6.5 units, so 4M = 26 matches the IEEE body height; line width M/10; qualifying symbol top-centre; connection pitch 2M; negation circle radius M/2 tangent outside the outline). The shapes and qualifying symbols are standard; the exact metrics are our construction, not a quotation.
Circuit description
Logic gate schematic. 3 inputs: A, B and C. 2 gates: 1 AND and 1 OR. The output F is driven by an OR gate. The longest signal path passes through 2 gates.
g0 = AND(A, B)= A · Bg1 = OR(g0, C)= A · B + C
2 gates2 levels4 gate inputs
NAND-only circuit
IEC 60617-12:1997 is a paid standard and its per-symbol dimensions are not public. These rectangular symbols follow the published module-grid construction (module M = 6.5 units, so 4M = 26 matches the IEEE body height; line width M/10; qualifying symbol top-centre; connection pitch 2M; negation circle radius M/2 tangent outside the outline). The shapes and qualifying symbols are standard; the exact metrics are our construction, not a quotation.
Circuit description
Logic gate schematic. 3 inputs: A, B and C. 3 gates: 3 NAND. The output F is driven by a NAND gate. The longest signal path passes through 2 gates. 1 junction dot marks where a signal fans out to more than one gate.
g0 = NAND(A, B)= A ↑ Bg1 = NAND(C, C)= C ↑ Cg2 = NAND(g0, g1)= A ↑ B ↑ (C ↑ C)
3 gates2 levels6 gate inputs
Equivalence check
Verified equivalent to the original over all 8 input combinations.More than one right answer
More than one network of this size computes the same function: which input of a gate carries the shared signal, and which of several equally cheap factorings is used, are both free choices. This is one minimum-size answer, not the only one.What “universal” means
A set of gates is functionally complete — universal — when every Boolean function of every arity can be built from it. The three-step argument for NAND is short enough to reproduce in an exam. First, {AND, OR, NOT} is complete, because every function has a canonical sum-of-products expansion built from exactly those three. Second, NAND alone produces all three: NOT(A) = NAND(A, A), AND(A, B) = NAND(NAND(A, B), NAND(A, B)) and OR(A, B) = NAND(NAND(A, A), NAND(B, B)). Third, therefore NAND alone is complete. The same argument runs for NOR with every step dualised.
Bubble pushing: converting a circuit by drawing, not by algebra
R1 — double bubble
(A′)′ = A. Two bubbles on one wire annihilate. This is the rewrite that lets you insert a cancelling pair anywhere you like for free.
R2 — De Morgan on a node
An AND body with an output bubble is the same element as an OR body with input bubbles, and an OR body with an output bubble is the same as an AND body with input bubbles. That is De Morgan drawn rather than written.
R3 — SOP becomes NAND-NAND
Insert a cancelling bubble pair on every AND→OR wire. The AND gates absorb the added output bubble and become NANDs; the OR absorbs the added input bubbles and becomes a NAND by R2. A literal that arrives already complemented becomes a NAND(x, x) inverter — the step students miss.
R4 — POS becomes NOR-NOR
The dual of R3, applied to a two-level OR-AND network.
Two-level conversions are free
Any two-level sum of products becomes NAND-NAND with the same gate count and the same number of levels. F = A·B + C·D is two ANDs and an OR — three gates, two levels — and converts to NAND(NAND(A, B), NAND(C, D)), three gates, two levels. Likewise F = (A + B)·(C + D) becomes three NORs. That is why standard-cell libraries are built around NAND and NOR and why hand-drawn SOP circuits are so often redrawn this way.
The corollary matters more than the theorem: minimise first, convert second. Converting an unminimised expression faithfully reproduces every redundant term as gates.
Which gate sets are not universal
- {AND, OR}
- Not universal. Every function built from AND and OR alone is monotone — changing an input from 0 to 1 can never change the output from 1 to 0 — and NOT is not monotone, so no AND/OR network computes it.
- {AND, NOT}
- Universal. OR follows from De Morgan: A + B = (A′ · B′)′.
- {OR, NOT}
- Universal, by the dual argument: A · B = (A′ + B′)′.
- {XOR}
- Not universal. Every function built from XOR alone is affine — a constant plus an XOR of some inputs — and AND is not affine.
- {XOR, AND}
- Universal. Together with the constant 1 they generate NOT (A ⊕ 1 = A′), and NOT with AND is already complete.
- {NAND}
- Universal on its own. So is {NOR}. Those are the only two single-gate complete sets.
The XOR / XNOR asymmetry
XOR costs four NANDs but five NORs; XNOR costs five NANDs but four NORs. The two four-gate builds are structural duals of each other — swap every NAND for a NOR and the function complements — which is exactly why the cheap one flips when the primitive does.
Why hardware cares
In static CMOS a NAND or a NOR is four transistors; AND and OR are six, because they are a NAND or NOR followed by an inverter. Building from the inverting primitive is therefore cheaper in area and in delay, not just tidier on paper. Universality also buys single-part-type designs: the Apollo Guidance Computer was assembled from roughly 2,800 packages of one part, each holding two 3-input NOR gates, which reduced qualification and sourcing for a flight computer to a single component.
Start from a worked example
Worked examples
- NOT from NANDintrothe base case
- AND from NANDintroNAND then invert
- OR from NANDcoreinvert both inputs, then NAND
- XOR from NANDcorewith one shared subexpression
- NOR from NANDcorecrossing between the families
- NOT, OR, AND from NORexamthe dual cost table
- Σm(0,1,2,5,6,7) as a NAND-only networkexamthe mechanical SOP-to-NAND conversion
- XOR from NOR gates onlyedge caseone more than the NAND version
Sources
- H. M. Sheffer, “A Set of Five Independent Postulates for Boolean Algebras, with Application to Logical Constants,” Transactions of the American Mathematical Society, vol. 14, no. 4, pp. 481–488, October 1913.
- C. S. Peirce, “A Boolian Algebra with One Constant” (c. 1880), in Collected Papers of Charles Sanders Peirce, vol. 4, Harvard University Press, 1933 — the first statement that one connective suffices.
- E. L. Post, The Two-Valued Iterative Systems of Mathematical Logic, Annals of Mathematics Studies no. 5, Princeton University Press, 1941 — the classification of the functionally complete sets.
- C. E. Shannon, “A Symbolic Analysis of Relay and Switching Circuits,” Transactions of the AIEE, vol. 57, pp. 713–723, 1938.
- ANSI/IEEE Std 91-1984 with IEEE Std 91a-1991, IEEE Standard Graphic Symbols for Logic Functions.
- IEC 60617-12:1997, Graphical symbols for diagrams — Part 12: Binary logic elements. (Paid standard; see the construction note beside every rectangular symbol.)