Logic basics
What is a NAND gate?
A NAND gate answers one question: are all my inputs on? Then it says the opposite. That small piece of contrariness is enough to build every computer ever made.
NAND is short for NOT AND. An AND gate outputs 1 only when every input is 1. A NAND gate does the same check and inverts the answer, so its output is 0 only when every input is 1, and 1 in every other case.
The NAND truth table
A truth table lists every combination of inputs and the output for each. With two inputs there are four rows:
| A | B | A NAND B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Compare it with AND, which has a single 1 in the bottom row. NAND is the same column flipped: three 1s and a single 0. A NAND gate with three or four inputs follows the same rule. It outputs 0 only when all of its inputs are 1.
Symbol and notation
The NAND symbol is the AND symbol with a small circle, or bubble, at the output. In the rectangular IEC symbols used in many European textbooks, it is a box marked & with the same bubble.
In Boolean algebra NAND is written in several ways:
Q = ¬(A ∧ B)orQ = (A · B)′: “not (A and B)”.Q = A ↑ B: the Sheffer stroke, named after the logician who made it famous (more on him below).- In code,
!(a && b)for booleans, or~(a & b)for every bit of a word at once.
One property often catches people out. NAND is commutative (A ↑ B equals B ↑ A), but it is not associative. With A = 1, B = 1, C = 0, (A ↑ B) ↑ C gives 1 but A ↑ (B ↑ C) gives 0. So chaining two-input NANDs does not give you a three-input NAND. Wider gates take a little more thought.
Why one gate is enough
NAND is a universal gate. Any logic function, whether it is a gate, an adder or the control logic of a processor, can be built from NAND gates alone, with no other kind of part. Logicians call this functional completeness. Why NAND can build every other gate explains why it works, and why AND, OR or XOR on their own cannot.
NOR, its sibling, is universal too. The logic of the Apollo Guidance Computer that flew to the Moon was built almost entirely from one chip type: a small package holding two three-input NOR gates. Using one standard part made the machine much easier to manufacture and test.
Why chip designers like NAND
In CMOS, the technology inside almost every modern chip, the cheapest gates are the inverting ones. A two-input NAND needs four transistors. Two p-type transistors in parallel pull the output up to 1 if either input is 0, and two n-type transistors in series pull it down to 0 only if both inputs are 1. A plain AND gate is a NAND followed by an inverter, which costs six transistors and is slower. This is why NAND, NOR and inverters are the bread and butter of standard-cell libraries, and why the classic 7400 chip, four two-input NANDs in one package, was one of the first parts in Texas Instruments’ famous 7400 logic family in the 1960s.
A short history
In 1913 the American logician Henry M. Sheffer published a paper showing that all the operations of Boolean algebra could be defined from a single one, the “stroke” that now carries his name. Charles Sanders Peirce had already noticed the same thing around 1880, for both NAND and NOR, but his notes were only published decades later. For half a century this was a curiosity of logic. Then transistors made it practical engineering: if one kind of gate can do everything, you can build a whole computer from thousands of copies of one part.
What you can do with a NAND
On its own a NAND is a tiny decision. A few of them make the other gates. A few dozen make an adder. Feed a gate’s output back into its own inputs and it starts to remember (see flip-flops and memory). Stack those ideas and you get a CPU. Nothing new is added on the way up. It is the same gate, used in cleverer arrangements.