Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 57 · Boolean Algebra

Sum of Products and Product of Sums

Turn any truth table into a Boolean expression: learn minterms, maxterms and canonical SOP and POS forms, with a Python expression generator you can run live.

You can describe a logic function in many ways: in words, as a truth table, as an expression, or as a circuit. The truth table is the most honest one, because it lists every case, but it is also the least useful for building hardware. How do you get from a table to gates? There is a mechanical recipe that always works, and it produces the two standard shapes of logic expressions: sum of products and product of sums.

In this lesson you will learn minterms and maxterms, write the canonical forms for any truth table, and build a small Python program that does the conversion for you and checks its own work.

Terms: products and sums

Some vocabulary first. A literal is a variable or its complement (A or A′).

  • A product term is literals joined by AND, such as A·B′·C.
  • A sum term is literals joined by OR, such as A + B′ + C.
  • A sum of products (SOP) is product terms joined by OR: AB + A′C. It maps to an AND layer feeding one OR gate.
  • A product of sums (POS) is sum terms joined by AND: (A + B)(A′ + C). It maps to an OR layer feeding one AND gate.

Both shapes have only two levels of logic (not counting input inverters), which makes them fast, and every function can be written in both.

Minterms: one term per 1

A minterm is a product term that contains every variable exactly once, in true or complemented form. For three variables A, B, C there are 2³ = 8 minterms, and each one is 1 for exactly one input combination. The minterm is true when each variable matches its row: uncomplemented where the row has a 1, complemented where the row has a 0.

Row A B C Minterm Shorthand
0 0 0 0 A′B′C′ m0
1 0 0 1 A′B′C m1
2 0 1 0 A′BC′ m2
3 0 1 1 A′BC m3
4 1 0 0 AB′C′ m4
5 1 0 1 AB′C m5
6 1 1 0 ABC′ m6
7 1 1 1 ABC m7

The number in m5 is just the row read as a binary number (101 is 5, with A as the most significant bit). To write a function as a canonical sum of products, OR together the minterms of every row where the function is 1. For example, the majority function (output 1 when at least two inputs are 1) is 1 on rows 3, 5, 6 and 7:

F = Σm(3, 5, 6, 7) = A′BC + AB′C + ABC′ + ABC

Maxterms: one term per 0

A maxterm is a sum term containing every variable once. It is the opposite of a minterm: a maxterm is 0 for exactly one input combination. To build it, use the variable as it is where the row has a 0, and complemented where the row has a 1. So row 5 (101) gives A′ + B + C′: it is 0 only when A = 1, B = 0, C = 1.

A canonical product of sums ANDs the maxterms of every row where the function is 0. Because each maxterm kills exactly one row, the product is 0 on those rows and 1 everywhere else. For the majority function, the zero rows are 0, 1, 2 and 4:

F = ΠM(0, 1, 2, 4) = (A + B + C)(A + B + C′)(A + B′ + C)(A′ + B + C)

Two ways to read a truth table

Minterms One product term for every row with output 1.
Maxterms One sum term for every row with output 0.

Both give the same function, so pick the shorter list.

1 / 2

A useful relationship: the minterms of F are exactly the rows missing from its maxterm list. If Σm lists {3, 5, 6, 7}, then ΠM lists the other four rows {0, 1, 2, 4}.

Generating the expressions in Python

The program below takes a function as a Python lambda and builds the table, then writes the canonical SOP and POS in text form. Complements are marked with a prime. To prove that the generated formulas are correct, the program also evaluates each formula on every row with eval and compares the result with the table.

Python Truth table to canonical SOP and POS

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output lists minterms and maxterms for both functions. Both functions have four ones and four zeros, so neither form is shorter here. For a function with few ones, SOP is the compact choice; with few zeros, POS is.

Checking the formulas

A generator is only useful if you can trust it. The second program converts the formula strings into real Python expressions and evaluates them over all inputs. It uses a small helper that turns A' into (1-A), + into | and adjacent letters into &, and then compares with the original function.

Python Verify generated formulas

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Four functions, eight checks, and all of them print True. The generated expressions are correct by construction, but they are not minimal: the canonical SOP of A xor B is A′B + AB′, which cannot be reduced, while the canonical SOP of 3-in NAND has seven terms where the simplified form A′ + B′ + C′ has three. Reducing them is the job of the next chapter.

Canonical versus minimal

The recipes in this lesson are guaranteed to work, but they are wasteful. Every term has every variable, so a 4-variable function with eight ones becomes eight 4-input AND gates and an 8-input OR gate. The canonical form is a standard way of writing a function; a minimal form is the cheapest equivalent form. Boolean laws (such as AB + AB′ = A) combine adjacent minterms into shorter terms, and Karnaugh maps do this visually.

Starting from a truth table with mostly 1s? Write the zeros instead. Write the SOP of the zero rows, which gives you the complement F′, then complement the result with De Morgan's theorems. This yields the POS of F directly. See De Morgan's Theorems and Bubble Pushing.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A function of 3 variables is 1 on rows 1 and 6. How many minterms are in its canonical SOP?

    Each row with output 1 contributes exactly one minterm, so rows 1 and 6 give two minterms.
  2. 2. Which maxterm is 0 only for the input A=1, B=0, C=1?

    A maxterm uses the variable complemented where the row has a 1 and uncomplemented where it has a 0. Row 101 gives A′ + B + C′.
  3. 3. The function F has ones on rows {0, 3} of a 2-variable truth table. Which list is its maxterm list?

    Maxterms come from the rows where F is 0, which are all the rows missing from the minterm list, namely 1 and 2.
  4. 4. Why is a canonical SOP usually not the smallest circuit?

    Canonical terms are full-width. Boolean laws or Karnaugh maps can merge terms that differ in one variable, giving shorter terms and fewer gates.

Summary

  • A literal is a variable or its complement; a product term ANDs literals and a sum term ORs them.
  • Minterm m_i is the full product that is 1 only on row i; the canonical SOP ORs the minterms of all rows where F = 1.
  • Maxterm M_i is the full sum that is 0 only on row i; the canonical POS ANDs the maxterms of all rows where F = 0.
  • Σm and ΠM lists are complementary: together they cover every row once.
  • Canonical forms always exist but are rarely minimal; Boolean laws and Karnaugh maps shrink them.

Next: Karnaugh Maps.