Combining the three basic logic gates, AND, OR, and NOT, lets us build any logic circuit that can be expressed as a truth table.
But do we really need all three? The guidance computer of the Apollo spacecraft that sent people to the Moon built almost all of its logic from thousands of chips that held just one kind of gate.
How can a single kind of gate build every circuit? In this post, let’s try it ourselves with the NAND gate. The property that any logic circuit can be built from NAND alone is called the completeness, or universality, of NAND.
What happens if we connect the same value to both inputs of a NAND gate?
Click the square node to change the input, and the output becomes the opposite of the input.
NAND gives the exact opposite of AND. So what happens if we invert NAND’s output once more?
To build OR, we need De Morgan’s laws, which swap AND and OR using NOT. They come in two forms.
¬(A ∧ B) = ¬A ∨ ¬B: Not both are true is the same as at least one is
false.¬(A ∨ B) = ¬A ∧ ¬B: Not even one is true is the same as both are
false.Let’s check the second form with a truth table.
| ¬(A ∨ B) | ¬A ∧ ¬B | ||
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
Let’s change A and B and see whether the two output columns always match.
Inverting both sides of the second form once more gives A ∨ B = ¬(¬A ∧ ¬B).
Since ¬(… ∧ …) is exactly NAND, A ∨ B = ¬A NAND ¬B. In other words, invert
each input and feed them into NAND, and you get OR. We already built NOT from
NAND, so OR is complete with NAND alone.
We built NOT, AND, and OR all from NAND. Since AND, OR, and NOT are enough to build any logic circuit, NAND alone can build every digital logic circuit.
NAND is a basic building block in real chips, too. In today’s chips, a NAND is made from 4 transistors, and AND is actually made by adding a NOT after a NAND.
In the next post, let’s combine these gates to build a circuit that picks one of several signals.
You want to build a circuit that gives 1 only when its two inputs are equal, using only NAND. Which of the following expressions is correct?