In the previous post, we examined the three basic logic gates AND, OR, and NOT, and confirmed that by combining them, we can build any logic circuit expressible as a truth table.
But from the perspective of a hardware engineer building computers, things look a bit different. Since computers aren’t humans, intuitiveness and ease of understanding matter far less than how efficiently and simply something can be physically implemented. If everything could be built from just one type of component, the manufacturing process would be much simpler and costs would be reduced.
Any complex logic circuit can be built using only NAND gates. This is called NAND’s completeness or universality. In this post, let’s learn about the NAND gate and actually build the other basic gates from it.
As the name suggests, the NAND gate applies a NOT operation to the result of an AND operation. It outputs false only when both inputs are true; in all other cases, it outputs true. If A is “I like mom” and B is “I like dad,” then A NAND B means “it’s not the case that I like both mom and dad.”
The truth table for the NAND gate is as follows:
| A NAND B | ||
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Let’s start with the relatively simple NOT gate. What happens if we connect the same value to both inputs of a NAND gate?
Click the square node to change the input value. You can see that the output is always the opposite of the input.
A NAND gate outputs the exact opposite of AND. So what if we invert the output of a NAND gate?
Connecting the output of a NAND gate to the inputs of another NAND gate gives us an AND gate.
The OR gate requires a bit more thought. We can use De Morgan’s law. De
Morgan’s law states that NOT(A AND B) = (NOT A) OR (NOT B), meaning AND and OR
can be swapped using NOT. Intuitively, not both true means the same thing as
at least one is false. We can express OR using NAND step by step:
A OR BNOT ((NOT A) AND (NOT B))(NOT A) NAND (NOT B)Here is the implementation following this approach:
We’ve confirmed that a NAND gate alone can implement NOT, OR, and AND gates. In the previous post, we learned that with AND, OR, and NOT, any logic circuit can be built.
Therefore, it is possible to construct any digital logic circuit using only NAND gates. This is known as NAND gate universality.
From the perspective of mass-producing computer hardware, fewer types of components make the production process more efficient and simpler. You only need to manufacture and connect one type of basic component, reducing manufacturing costs and complexity.
Complex computer hardware can ultimately be composed of simple combinations of NAND like this.
Now we understand how the bits (0 and 1) that computers use gain logical meaning and are implemented as physical components. We’ve also learned that combining basic logic gates can build any logic circuit.
In the next post, let’s see how these logic gates are combined to build circuits that select between multiple signals.