Lesson 11 · Logic gates

NAND: one gate to build them all

NAND is functionally complete: with enough NAND gates and nothing else you can build any digital circuit. Wire one NAND as a NOT, two as an AND and three as an OR (thanks to De Morgan's law), watch each truth table play row by row, see that NOR can do the same, and look inside a NAND at its four CMOS transistors to see why chip designers like it.

12 min9 steps6 questionsBeginner

Fig 11 · Interactive

Loading figure…

or ← →

Check yourself

6 quick questions

Pick an answer to see why. Your score saves with your progress.

01You wire input A to both inputs of a NAND gate. What does the gate now do?

Both inputs are always equal: NAND(0, 0) = 1 and NAND(1, 1) = 0, so the output is the opposite of A.

02How do you make an AND gate from NAND gates only?

NAND is AND with the answer flipped. Flipping it back with a joined-input NAND gives AND, using two gates.

03Which law explains why NOT A and NOT B fed into a NAND give A OR B?

De Morgan's law says NOT (X AND Y) = NOT X OR NOT Y. With X = NOT A and Y = NOT B, the double NOTs cancel and you get A OR B.

04What does 'functionally complete' mean for a set of gates?

A functionally complete set can make every Boolean function. NAND on its own is such a set, and so is NOR.

05How many transistors does a two-input CMOS NAND gate use?

Four: two pMOS in parallel to power and two nMOS in series to ground. An AND needs six, because it is a NAND plus a NOT.

06A CMOS NAND and a CMOS NOR both use 4 transistors. Why is the NAND usually faster?

In a NAND the two transistors in series are nMOS; in a NOR they are pMOS. pMOS are slower because holes move about 2 to 3 times more slowly than electrons, so NAND is usually preferred.

Key terms

Glossary

NAND: NOT AND: a gate that gives 0 only when all of its inputs are 1, and 1 otherwise.
NOR: NOT OR: a gate that gives 1 only when all of its inputs are 0, and 0 otherwise.
Functionally complete: A set of gates is functionally complete if it can build every possible truth table. NAND alone is; so is NOR alone.
Universal gate: A gate that is functionally complete on its own, such as NAND or NOR.
De Morgan's law: NOT (A AND B) = NOT A OR NOT B, and NOT (A OR B) = NOT A AND NOT B.
Joined inputs: Connecting one signal to every input of a gate; for NAND or NOR this turns the gate into a NOT.
CMOS: Complementary MOS: the way most chips build gates, from pairs of nMOS transistors (on at 1) and pMOS transistors (on at 0).

Fine print

Notes and sources

Henry Sheffer showed in 1913 that one operation, now called NAND (the Sheffer stroke), is enough to write every rule of Boolean logic. Charles Peirce had found the same for NOR in a note of about 1880, first published in 1933 (Collected Papers, vol. 4, paragraphs 12-20).
Inside a chip, 1 and 0 are two voltage levels (high and low); the lamps just show them. On the gate bench, a coloured wire with moving dashes carries a 1 and a white wire carries a 0. On the transistor board, colour and dashes mark the path the switched-on transistors open: from power to Y (Y is 1) or from Y to ground (Y is 0).
De Morgan's laws: NOT (A AND B) = NOT A OR NOT B, and NOT (A OR B) = NOT A AND NOT B (Harris and Harris, Digital Design and Computer Architecture, section 2.3).
Static CMOS counts with two inputs: NOT 2, NAND 4, NOR 4, AND 6 (NAND + NOT), OR 6 (NOR + NOT) (Harris and Harris, section 1.7).
pMOS transistors are slower than nMOS because holes move about 2 to 3 times more slowly than electrons, so a NOR (pMOS in series) is slower than a NAND (nMOS in series) of the same size (Weste and Harris, CMOS VLSI Design, 4th ed.).
Real parts: Texas Instruments' SN74HC00 holds four 2-input NAND gates and the SN74HC02 four 2-input NOR gates, each in a 14-pin package.
In Python, a & b on the numbers 0 and 1 is AND, and 1 - x flips a bit (~x would give -(x + 1)).

Quiz Unlocks after the last step.