From truth table to expression

You have the table. Where is the circuit?

By now you can describe what you want a circuit to do by writing its truth table: one row for every combination of the inputs, and against each row the output you want, 1 or 0. What you do not yet have is a way to get from that table to a set of gates. This lesson gives you one. It is a recipe that works for any truth table at all, with no cleverness required. The price is that the circuit it produces is nearly always bigger than it needs to be, and the rest of this stage is about making it smaller.

One row, one AND gate

Look at a single row where the output is 1. Say the inputs are a, b and c, and on this row they are 0, 1 and 1. Can you build a term that is 1 on this row and on no other? Yes: AND all three inputs together, with a NOT in front of any input that is 0 on the row. Here that gives NOT a, AND b, AND c. When a is 0 and b and c are 1, every part of the AND is 1, so the term is 1. Change any input and one part becomes 0, so the whole term does. The term picks out exactly one row.

Numbering the rows

Every row has a number. Read the inputs on the row as a binary number, with the first input as the most significant bit, exactly as you did when counting in binary. The row with a = 0, b = 1, c = 1 reads as 011, which is 3, so its minterm is called m3. The row a = 1, b = 0, c = 1 is 101, which is 5, so its minterm is m5 = a·b̅·c. With three inputs the rows run from m0 to m7, and with four from m0 to m15. Engineers list the rows where a function is 1 as Σm(1, 3, 6, 7), read "the sum of minterms 1, 3, 6 and 7", which says everything about the function in a few characters.

OR them all together: the sum of products

Now take every row where the output is 1, write its minterm, and OR all those minterms together. The result is an expression that matches the truth table on every row. Here is why it always works. On a row where the table says 1, that row's own minterm is 1, and an OR with any 1 in it is 1. On a row where the table says 0, no minterm was written for that row, and every minterm that was written belongs to some other row, so all of them are 0, and an OR of 0s is 0. Whatever the table, the expression agrees with it.

The table below starts with that same function. Click the output cells and watch the expression rewrite itself, one minterm per 1.

Why it is usually too big

Look again at the worked example. The last line of the widget shows the same function as a·b + a̅·c: two AND gates with two inputs each and one OR gate, instead of four three-input ANDs and a four-input OR. Both give the same output on all eight rows, so they are the same function and either circuit would do. The canonical form is big because it treats every 1 as a separate case, when several rows often share a simpler reason for being 1. Rows 6 and 7 are both 1 because a and b are 1; c does not matter, so c should not be in the term. Spotting those shared reasons is the job of the next three lessons.

The mirror image: product of sums

There is a second recipe that uses the rows where the output is 0. For each such row, write an OR of every input, this time with a bar on the inputs that are 1. That term, called a maxterm, is 0 on exactly its own row. AND all the maxterms together and you get an AND of OR terms, a product of sums, which is 0 exactly where the table is 0. It is the same function again. When a table has only a few 0s the product of sums is the shorter of the two, which is why the sum of products calculator shows both.

What to remember

• A minterm is an AND of every input, barred where the row has a 0, so it is 1 on one row only.
• Rows are numbered by reading their inputs as a binary number, so m5 is the row 101.
• OR the minterms of every row that is 1 and you have the canonical sum of products, which always works.
• It is usually far bigger than necessary because rows often share a simpler reason for being 1.
• Doing the same with the 0 rows, ORs inside an AND, gives the product of sums.