yeolyi.comSeongyeol's CS

Sum of Products

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.

Building any Boolean function from 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
001
010
100
111

It takes three steps.

ABOutAND condition
00
01
10
11

Out = ?

  1. Press next to go through all three steps.
  2. Press the output cells to change the truth table, then try again. Any truth table yields an expression through the same steps.

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 ∧ ¬BA ∧ B(¬A ∧ ¬B) ∨ (A ∧ B)
0011101
0110000
1001000
1100011

It behaves exactly like the original truth table. With this method, any truth table can be turned into an AND, OR, NOT circuit.

Wrapping up

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.

Challenge

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)