6 / 63 · Concept

Universal gates: building circuits using only NAND

Demonstrate the functional completeness of NAND and NOR by building circuits, and verify an XOR's intermediate signals.

What “any circuit” means here

NAND alone can implement NOT, AND and OR. Any combinational logic function with finitely many inputs can be expressed with these operations. In this sense, NAND is a universal gate^{Universal gate A gate type is universal if repeated instances of that type can implement any Boolean function. NAND and NOR are typical examples.}. This does not mean one NAND solves storage, clocking, wiring and power requirements as well.

\overline a=\operatorname{NAND}(a,a)

ab=\operatorname{NAND}(n,n),\quad n=\operatorname{NAND}(a,b)

a+b=\operatorname{NAND}(\operatorname{NAND}(a,a),\operatorname{NAND}(b,b))

Connecting the same input to both NAND terminals creates NOT. AND adds another inversion^{Inversion The NOT operation, which changes 0 to 1 and 1 to 0. A bar over an expression applies NOT to the entire expression beneath it. Learn more} after NAND; OR follows from De Morgan's laws^{De Morgan's laws Inverting an AND result is equivalent to ORing the inverted inputs; inverting an OR result is equivalent to ANDing the inverted inputs. Learn more}. Tying a NOR's inputs also creates NOT, and similar constructions demonstrate NOR's universality.

Construct XOR with four NAND gates

Define the intermediate signals in this order:

n_0=\overline{ab},\quad n_1=\overline{a n_0},\quad n_2=\overline{b n_0},\quad y=\overline{n_1n_2}

a	b	n0	n1	n2	y
0	0	1	1	1	0
0	1	1	1	0	1
1	0	1	0	1	1
1	1	0	1	1	0

Build XOR with a shared intermediate signal

First NAND: n0 = NAND(a, b)
Two intermediate NANDs: n1 = NAND(a, n0); n2 = NAND(b, n0)
Final NAND: y = NAND(n1, n2)

The two NANDs in the second stage operate in parallel. There are four gates in total, but the longest logic path has three stages. In a simple model with at most 2 ns per gate, the maximum path sum is 6 ns. Actual load and wiring effects must be considered separately.

Compare the four-NAND result with XOR

XOR · Truth table
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

Fill in all four table rows yourself, then compare with the XOR above. Functionally equivalent circuits produce equal outputs for every input; they need not have equal gate counts or propagation delays^{Propagation delay The time from an input change until the output settles to the correct value. Logical equivalence and timing behavior are separate properties. Learn more}.

Try it yourself

Write expressions for NOT and AND using only NOR gates. How many gates and how many stages on the longest path does the AND construction have?

Read the explanation

NOT a=NOR(a,a). AND is NOR(NOR(a,a), NOR(b,b)). Two input inversions and a final NOR use three gates in total, with two stages on the longest path.