A truth table is a blueprint that writes down the logical behavior we want. A simple decision like “go straight if the light is green and there’s no obstacle” can be turned into a circuit by combining AND, OR, and NOT gates by intuition.
But not every Boolean function breaks down this easily. Fortunately, there is a systematic way to convert any truth table into AND, OR, and NOT.
Make an AND for each input combination whose output is true (1), then combine all of the results with OR.
As an example, let’s build a gate whose output is 1 when its two inputs are equal using only AND, OR, and NOT. Its truth table is:
| A = B | ||
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
It takes three steps.
| A | B | Out | AND condition |
|---|---|---|---|
| 0 | 0 | ||
| 0 | 1 | ||
| 1 | 0 | ||
| 1 | 1 |
Out = ?
The final expression is (¬A ∧ ¬B) ∨ (A ∧ B). Likening AND to
multiplication and OR to addition, this form is called a sum of products.
| ¬A | ¬B | ¬A ∧ ¬B | A ∧ B | (¬A ∧ ¬B) ∨ (A ∧ B) | ||
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
It behaves exactly like the original truth table. With this method, any truth table can be turned into an AND, OR, NOT circuit.
AND, OR, and NOT are intuitive for people, but we don’t actually need all three. With just one kind of gate, the NAND gate, we can build AND, OR, and NOT.
In the next post, let’s find out how NAND gates alone can make up any logic circuit.
Reading inputs A, B, and C as the binary number ABC, the truth table that gives 1 only for 2, 3, 5, and 7 becomes the expression below as a sum of products. If you replace all three ∨s in it with an operation that gives '1 when its two inputs differ', for how many of the 8 possible inputs does the result change? Answer with a number.
(¬A ∧ B ∧ ¬C) ∨ (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ C)