In short: NAND and NOR are called universal gates because each one, on its own, can reproduce the three primitive operations (NOT, AND, OR) that span all of Boolean algebra, so any logic function whatsoever can be built using nothing but copies of a single gate type.
Ask a VLSI interviewer to name the one idea that quietly sits underneath every digital chip ever fabricated, and "universal gates" is a strong answer. The reason a billion-transistor SoC can be manufactured, characterized, and verified at all is that its vast functional variety reduces to a tiny, repeated building block. This article explains why NAND and NOR earn the label "universal," proves it constructively, and connects the theory to how real synthesis tools like Synopsys Design Compiler and Cadence Genus actually map your RTL onto a standard-cell library.
What "functionally complete" really means
A set of logic operators is called functionally complete (or a universal set) if every possible Boolean function can be expressed using only operators from that set. The textbook complete set is {AND, OR, NOT}, because any truth table can be written in sum-of-products form: OR together the minterms (AND combinations) of the input variables, inverting where needed. If you can reproduce all three of these primitives using only one kind of gate, then that gate is, by transitivity, universal.
NAND and NOR each pass this test. A single two-input gate type, wired cleverly, gives you NOT, AND, and OR. That is the whole claim — and the proof is short enough to derive on a whiteboard.
Key fact: {AND, OR, NOT} is functionally complete, but it is redundant. NAND alone and NOR alone are each complete on their own; AND-alone, OR-alone, and even {AND, OR} without NOT are not complete, because they cannot invert a signal.
Building the three primitives from NAND
NAND computes Y = (A·B)'. Watch how the three primitives fall out:
- NOT: tie both inputs together.
(A·A)' = A'. One gate, one inverter. - AND: NAND the inputs, then invert the result with a second NAND.
((A·B)')' = A·B. Two gates. - OR: invert each input first, then NAND them.
(A'·B')' = A + Bby De Morgan's law. Three gates.
The OR construction is pure De Morgan: (A'·B')' = A''+B'' = A+B. That single identity — that complementing an AND of complements yields an OR — is the engine behind the entire universality argument.
The NOR picture is the dual
NOR computes Y = (A+B)' and is universal by the mirror-image argument. Tying inputs together gives NOT; a NOR followed by an inverting NOR gives OR; inverting both inputs first gives AND, via the other De Morgan identity (A'+B')' = A·B. NAND is the "AND-first" universal gate and NOR is the "OR-first" one — a symmetry that is not accidental, since the two gates are duals under input/output complementation.
| Primitive | From NAND | From NOR |
|---|---|---|
| NOT | 1 | 1 |
| AND | 2 | 3 |
| OR | 3 | 2 |
Why hardware designers actually care
Universality is more than an exam trick — it shapes silicon economics. In static CMOS, a NAND or NOR is the natural gate: a 2-input NAND is just four transistors (two series NMOS, two parallel PMOS), the same count as a NOR. A standalone AND or OR, by contrast, is a NAND or NOR followed by an inverter — two extra transistors and an extra stage of delay. CMOS is inherently inverting, so building a library around NAND/NOR plus inverters is both the cheapest and the fastest choice.
Key fact: A 2-input CMOS NAND costs 4 transistors; the equivalent AND costs 6. Because NAND/NOR are the "free" primitives, foundry standard-cell libraries (TSMC, SCL180, GPDK045) are dominated by NAND, NOR, inverter, and AOI/OAI compound cells.
This is exactly what logic synthesis exploits. When Synopsys Design Compiler or Cadence Genus reads your Verilog, it first builds a technology-independent generic netlist, then runs technology mapping, covering that netlist with cells from the .lib timing library. Siemens (Mentor) tools in the DFT and formal flows reason over the same gate-level netlist. Because NAND, NOR, and inverter cells have the best area-delay-power figures, the optimizer gravitates toward them — your elegant a & b | c often emerges as a single AOI21 compound cell, not literal AND and OR gates. Understanding universality is what lets you read and trust that mapped netlist.
A worked example: XOR from NAND
To cement the idea, realize a 2-input XOR — A⊕B = A·B' + A'·B — using only NAND gates. The canonical implementation needs exactly four 2-input NANDs:
- G1 = (A·B)'
- G2 = (A·G1)' and G3 = (B·G1)'
- G4 = (G2·G3)' = A⊕B
Four gates, two logic levels after G1, no inverters, no other gate type. This is the structure you will see if you synthesize assign y = a ^ b; and inspect the netlist on a library whose cheapest XOR path happens to be NAND-based. See our companion deep-dive on the NAND gate for the transistor-level view, and our note on De Morgan's theorem for the algebra that makes all of this work.
Common pitfalls and interview traps
- "AND is universal too." False. Without inversion you can never produce a
0output from an all-1input pattern's complement; AND-only and OR-only sets cannot express NOT. - "XOR is universal." No — XOR and XNOR are linear functions; you cannot build AND from them alone. They need an AND or constant to become complete.
- Delay cost. Replacing one AND with a NAND+inverter adds a gate delay; in a timing-critical path on a 7nm node, naive gate-by-gate substitution can blow your setup budget. Real synthesis re-optimizes globally rather than substituting one-for-one.
Teams building real chips at firms like Avecas VLSI design services rely on exactly this foundation when they hand RTL to Genus or Design Compiler and reason about the mapped result.
Want to go from "I can prove NAND is universal" to taping out a real block? CourseTron's Digital Electronics and RTL-to-GDSII tracks walk you through synthesis, mapping, and standard-cell design hands-on. Explore the CourseTron courses →
FAQ
Why are NAND and NOR preferred over AND and OR in real chips?
In static CMOS, NAND and NOR are built with the fewest transistors (four for a 2-input gate) and are inherently inverting, which matches CMOS behavior. AND and OR require an extra inverter stage, costing more area, power, and delay, so libraries and synthesis tools favor NAND/NOR.
Is NAND or NOR "more universal"?
Both are equally universal — each alone can build any Boolean function. In practice NAND is often slightly preferred because the series-NMOS, parallel-PMOS arrangement of NAND tends to give better drive and symmetry than the series-PMOS NOR at the same transistor count.
Can a single XOR gate be used as a universal gate?
No. XOR (and XNOR) are linear/affine functions and cannot generate AND without an additional nonlinear element or a constant input, so neither is functionally complete on its own.
How does universality relate to logic synthesis tools?
Synthesis tools such as Synopsys Design Compiler and Cadence Genus map a technology-independent netlist onto standard cells. Because NAND, NOR, inverter, and AOI/OAI cells have the best area-delay-power metrics, the optimizer naturally expresses your logic using these universal and compound gates.