Learn › Topic 3

Truth tables and canonical forms: Σm and ΠM

8 min read · bitGateLab Team

Almost every digital design problem starts with a statement in words ("the alarm sounds if...") that is turned into a truth table. The next step is to get from that table an equation you can build with gates. Here you will learn the systematic method for doing it: minterms and maxterms, the canonical sum-of-products and product-of-sums forms, and the compact Σm and ΠM notation used by textbooks, simulators and Karnaugh maps.

How a truth table is ordered

With n variables there are 2ⁿ rows. They are written in ascending binary order, with the first variable as the most significant bit. That way each row is identified by a decimal number: in a table of A, B and C, the row A = 1, B = 0, C = 1 is 101₂ = 5. That number is the one you will use as the minterm or maxterm index, so the order of the variables matters: change the order and the numbers change.

Minterms and sum of products

A minterm is a product (AND) that contains every variable exactly once, either complemented or uncomplemented. It is built like this: a variable that is 1 in that row goes without a bar, and one that is 0 goes with a bar. The minterm is 1 only in its own row and 0 in all the others. It is named m_i, where i is the row number.

Row	A	B	C	Minterm	Maxterm
0	0	0	0	m₀ = ABC	M₀ = A + B + C
1	0	0	1	m₁ = ABC	M₁ = A + B + C
2	0	1	0	m₂ = ABC	M₂ = A + B + C
3	0	1	1	m₃ = ABC	M₃ = A + B + C
4	1	0	0	m₄ = ABC	M₄ = A + B + C
5	1	0	1	m₅ = ABC	M₅ = A + B + C
6	1	1	0	m₆ = ABC	M₆ = A + B + C
7	1	1	1	m₇ = ABC	M₇ = A + B + C

If you sum (OR) the minterms of all the rows where the function is 1, you get an equation that is 1 in exactly those rows. That is the canonical sum of products (SOP for short), or first canonical form. In compact notation it is written F = Σm(list of rows with a 1).

Maxterms and product of sums

A maxterm is a sum (OR) that contains every variable. The rule is the opposite: a variable that is 0 in the row goes without a bar, and one that is 1 goes with a bar. A maxterm is 0 only in its own row. It is named M_i (with a capital M).

If you multiply (AND) the maxterms of all the rows where the function is 0, you get an equation that is 0 right there and 1 everywhere else: the canonical product of sums (POS), or second canonical form. It is written F = ΠM(list of rows with a 0).

The minterm and the maxterm of the same row are complements: m_i = M_i. So if you know the Σm list of a function, the ΠM list is made up of all the numbers that do not appear in it.

Example 1: from the table to both forms. A three-variable function is 1 in rows 1, 3, 6 and 7.

#	A	B	C	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

Compact notation: F = Σm(1, 3, 6, 7) = ΠM(0, 2, 4, 5).
Canonical sum of products: F = ABC + ABC + ABC + ABC.
Canonical product of sums: F = (A + B + C)(A + B + C)(A + B + C)(A + B + C).
Simplify the SOP: ABC + ABC = AC and ABC + ABC = AB. So F = AC + AB.

Check in row 5 (A = 1, B = 0, C = 1): AC = 0 and AB = 0, so F = 0, the same as in the table.

Which form is better?

Both forms describe the same function, but they are not the same size. Use the one with fewer terms: if the function has few ones, Σm is shorter; if it has few zeros, ΠM is shorter. With 8 rows, a function with 2 ones has an SOP of 2 terms and a POS of 6.

The implementation matters too. A sum of products is built with AND gates feeding an OR, and that two-level structure converts directly into NAND-NAND. A product of sums is built with OR gates feeding an AND, and it converts into NOR-NOR.

Example 2: from the problem statement to the equation. A tank has three level sensors: A (low), B (middle) and C (high). Each sensor outputs 1 when the water reaches it. An "invalid level" lamp must light when the combination is physically impossible: a higher sensor active while a lower one is inactive.

Valid combinations (ABC): 000, 100, 110, 111. That is, rows 0, 4, 6 and 7.
The lamp lights in all the others: F = Σm(1, 2, 3, 5).
Equivalently: F = ΠM(0, 4, 6, 7).
Simplify: m₁ + m₃ = AC, m₁ + m₅ = BC, m₂ + m₃ = AB. Using m₁ and m₃ twice (idempotence), F = BC + AB.

Check: row 1 (001) gives BC = 1; row 2 (010) gives AB = 1; row 3 (011) gives AB = 1; row 5 (101) gives BC = 1. In 000, 100, 110 and 111 both terms are 0. It reads "C active without B" or "B active without A".

The complement of a function

If F = Σm(1, 3, 6, 7), its complement is 1 wherever F is 0: F = Σm(0, 2, 4, 5). This is useful when you want the simplified POS: you simplify F as a sum of products and then apply De Morgan. For example, F = AC + AB (check it against rows 0, 2, 4 and 5), and complementing gives F = (A + C)(A + B). If you multiply it out: AB + AC + BC, and by consensus that is AB + AC, the same result as in example 1.

To go deeper into these manipulations, review Boolean algebra; to simplify graphically, continue with Karnaugh maps.

Common mistakes

Reversing the rule for the bars: in minterms the 0 gets the bar; in maxterms it is the 1 that gets the bar.
Putting the rows where the function is 1 into ΠM. ΠM lists the zeros, Σm lists the ones.
Changing the order of the variables between the table and the equation. With the order C, B, A, row "5" is no longer the same row.
Leaving a variable out of a canonical term. A four-variable minterm always has four literals; if it has fewer, it is already simplified and is not canonical.

Try it in the simulator

The truth table module lets you enter a function row by row and immediately see its canonical forms and the simplified equation, so you can check every step you do by hand.

Create a table with three inputs and one output.
Set rows 1, 3, 6 and 7 from example 1 to 1 and leave the rest at 0.
Look at the Σm and ΠM expressions that are generated and compare them with yours.
Convert the table to a circuit and toggle the inputs to confirm that the output follows the table.
Repeat with the tank problem and verify that the lamp lights only for the impossible combinations.

Exercises

Write the minterm m₉ and the maxterm M₉ of a function of four variables A, B, C, D.
Answer
9 = 1001. m₉ = ABCD and M₉ = A + B + C + D.
If F(A, B, C) = Σm(0, 1, 5), write F in ΠM notation.
Answer
F = ΠM(2, 3, 4, 6, 7).
Find the canonical sum of products of a two-variable function that is 1 only when A and B are equal, and simplify it if possible.
Answer
F = Σm(0, 3) = AB + AB. It cannot be reduced: it is the XNOR.
Write the canonical product of sums of F(A, B, C) = Σm(1, 2, 3, 4, 5, 6, 7).
Answer
It is 0 only in row 0, so F = ΠM(0) = A + B + C. A single three-input OR.