From Truth Table to Circuit: Canonical SOP and POS
Every level in Task mode checks your circuit with test vectors: combinations of bits go in, and the outputs are compared against a table. From any completed truth table you can compute a circuit mechanically, with no flashes of insight and no trial and error. The recipe for rows with ones is called canonical SOP (sum of products); for rows with zeros it is POS (product of maxterms). This article builds both forms from one table and marks the boundary where the recipe stops working.
A circuit without memory is a formula
A combinational circuit with a single output computes a Boolean function: it maps every input combination to 0 or 1. The gates act as ordinary notation: AND multiplies, OR adds, NOT flips a bit. Any function can be assembled from these three parts — the NAND universality from De Morgan's laws is the proof. What remains is learning to build the circuit by recipe instead of by guesswork.
The example table: three judges voting
Three judges vote with buttons A, B, and C. Lamp F lights up when at least two votes are "yes". The full table fits in eight rows:
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Step 1: minterms for the rows with ones
A minterm covers exactly one row of the table. It is written as the AND (conjunction) of all the row's variables, where a variable equal to 1 is taken as is, and a variable equal to 0 is taken with an inversion. The row A = 0, B = 1, C = 1 gives the minterm "NOT A AND B AND C".
The property of a minterm is simple: it equals 1 on its own combination and 0 on all seven others. No other input combination "activates" it.
Step 2: canonical SOP — OR of all minterms
The sum of products is written in one move: connect all the minterms of the rows where F = 1 with OR. The voting table has four such rows:
F = (NOT A AND B AND C) OR (A AND NOT B AND C)
OR (A AND B AND NOT C) OR (A AND B AND C)In Verilog the same formula looks like this:
assign f = (~a & b & c) | (a & ~b & c) |
(a & b & ~c) | (a & b & c);The circuit needs 3 inverters, 4 three-input AND gates, and one four-input OR: 8 gates in total. The minterm property guarantees correct behavior: on every input combination at most one of the four minterms can equal 1 while the rest output 0, so the OR returns the correct value of F on all eight rows.
"Canonical" means every minterm includes all the variables. The recipe works for any table: XOR, for instance, takes two minterms — (NOT A AND B) OR (A AND NOT B).
Step 3: canonical POS — AND of all maxterms
The dual recipe works with the rows where F = 0. A maxterm is written as the OR of all variables, but the inversions are flipped: a one stays as is, a zero gets an inversion. Maxterms are connected with AND. The voting table has four zero rows:
F = (A OR B OR C) AND (A OR B OR NOT C)
AND (A OR NOT B OR C) AND (NOT A OR B OR C)The logic mirrors SOP: a maxterm equals 0 on its own combination (one of its terms is 0, so the whole OR is 0) and equals 1 on all the others. The AND of maxterms outputs 0 as soon as it lands on any zero row. One form is shorter than the other depending on the table: few ones, pick SOP; few zeros, pick POS.
Converting between the forms
SOP and POS are linked by double negation and De Morgan's laws themselves: wrapping the expression in "NOT (...)" turns the OR of minterms into an AND of inversions, and by De Morgan the inversion of each minterm becomes a ready-made maxterm. Both forms are easy to compare in the truth table generator: build tables for the SOP and the POS of voting — they match row for row.
The recipe boundary: circuits with memory
SOP and POS describe combinational logic: the output depends only on the current inputs. A multiplexer, a decoder, and an adder all fit this definition, so the recipe works for them from start to finish.
A flip-flop does not fit: it stores a bit, and its output depends on what arrived earlier. Such circuits are described by a next-state equation Q⁺ = f(inputs, Q), where f is an ordinary combinational function — and the recipe applies to it again. For a D flip-flop f simply repeats the input: Q⁺ = D. How a real flip-flop is born from this equation plus feedback is covered in the articles on the SR latch and the D flip-flop.
Why it matters in the game
Level 1.9 "Crossroads" asks for a 2-to-1 multiplexer: with S = 0 the output repeats A, and with S = 1 it repeats B. SOP gives the answer in two minterms, with no hints at all: (NOT S AND A) OR (S AND B). You will need two ANDs, one OR, and one NOT, four gates in total.
In Part 2 the same technique assembles a decoder: on the "Anatomy of a Decoder" level every output recognizes its own opcode, and each recognizer is a minterm of the three opcode bits. Check your formula in the truth table generator before building: a mismatch with the task is visible at once.
A circuit straight from SOP works immediately but almost always contains extra gates: voting cost 8, while 4 is enough. Where the savings come from is the subject of the next article on Karnaugh maps.
Test yourself
Write down the minterm of the row A = 1, B = 0, C = 1.
A AND NOT B AND C: ones are taken as is, zeros are taken with an inversion.
When does POS turn out shorter than SOP?
When there are fewer zero rows than one rows: each maxterm kills one zero row, so no extra maxterms appear.
Why can't a flip-flop be built from SOP directly?
A flip-flop's output depends on the stored state as well, while SOP describes functions of the current inputs only. SOP does apply to the combinational part: the next-state equation Q⁺ = f(inputs, Q).
Summary
1. A minterm covers one row with a one: variables taken as is, zeros with an inversion.
2. Canonical SOP is the OR of all minterms; it yields a working circuit for any table.
3. A maxterm kills one row with a zero (inversions flipped); canonical POS is the AND of all maxterms.
4. A form is shorter when the table has fewer of the matching rows: rare ones call for SOP, rare zeros call for POS.
5. Both forms describe combinational logic; for circuits with memory the recipe applies to the next-state function.
On level 1.9 "Crossroads" build the multiplexer from SOP and see how four gates pass every test vector. To refresh the basic gates, return to "Logic Gates — AND, OR, NOT", then move on to Karnaugh map minimization.