Universal gate

Also called: universal logic gate, universal gates

A gate type that can build NOT, AND and OR on its own, and so any Boolean function. NAND and NOR are the two universal gates.

A universal gate is a single gate type that can build every other logic function using only copies of itself. NAND and NOR are universal. AND, OR, NOT, XOR and XNOR are not.

To prove a gate is universal, you only need to build NOT and AND (or NOT and OR) from it. Every Boolean function can be written as a sum of products of AND, OR and NOT, and De Morgan's law turns AND plus NOT into OR.

The classic constructions with 2-input gates:

NOT: one NAND (or NOR) with its inputs tied together.
AND: NAND then a NAND-inverter, 2 gates. From NORs it takes 3.
OR: NOR then a NOR-inverter, 2 gates. From NANDs it takes 3.
NOR from NANDs, or NAND from NORs: 4 gates.

Why it matters: a chip built from one repeated cell is simpler to design and manufacture. In CMOS, NAND and NOR are also the cheapest 2-input gates, so real designs lean on them. Two-level nand nand logic and nor nor logic let you build any function directly.

Why the others fail: AND and OR can never produce an inversion, and XOR gates only ever make parity-style functions. See functional completeness for the general idea, which applies to sets of gates as well as single ones.

Worked example

Example

Y = AB' from NANDs only

Build Y = using only 2-input NAND gates, as drawn above.

1.
is needed, so gate 1 is a NAND with both inputs tied to B.
2.
Gate 2: NAND(A, ) gives .
3.
Gate 3: a tied NAND inverts that back: = .
4.
Check A = 1, B = 0: gate 1 gives 1, gate 2 gives NAND(1, 1) = 0, gate 3 gives NAND(0, 0) = 1. And = 1. ✓
5.
Any function can be built this way: make the inversions with tied NANDs, then use NAND-plus-inverter for each AND.

Common mistakes

Calling XOR universal. Without a constant 1 it can't even make NOT, and it can never make AND.
Calling AND or OR universal. Neither can ever invert a signal.
Mixing up the gate counts. From NAND: NOT 1, AND 2, OR 3, NOR 4. From NOR, AND and OR swap: NOT 1, OR 2, AND 3, NAND 4.

Practice Universal gate

Interactive questions with instant feedback and a worked solution for every wrong answer.

Logic Gates lesson

And 4 more in the Logic Gates lesson.

Practice exams

Learn it step by step

Universal gate is taught in Logic Gates.

Logic Gates →

All terms