Chapter 07 of 32

Canonical Forms: SOP & POS

The same Boolean function can be written in many different ways. AB + BC + CA, (A + B)(B + C)(C + A) and A′BC + AB′C + ABC′ + ABC all describe the same 3-input majority function. That flexibility is great for simplification, but it is a problem when you want to compare two functions, store them, or hand them to a computer program. We need one standard way of writing a function that follows directly from its truth table.

That standard is the canonical form. There are two of them: the canonical sum of products (SOP), built from minterms, and the canonical product of sums (POS), built from maxterms. Every simplification method in the following chapters (Karnaugh Maps, K-Maps with Don't-Care Conditions and the Quine-McCluskey Method) starts from a list of minterms or maxterms, so this chapter is the foundation for all of them.

A canonical form expresses a Boolean function in a unique standard way: the canonical SOP is the OR of all minterms for which the function is 1, and the canonical POS is the AND of all maxterms for which the function is 0.

We use A′ for NOT A, AB for AND and A + B for OR, as in De Morgan's Theorems. Every minterm list in this chapter was verified by enumerating the truth table in Python.


Basic Vocabulary

Term

Meaning

Example

Literal

A variable or its complement

A, B′

Product term

AND of literals

AB′C

Sum term

OR of literals

A + B′ + C

SOP (sum of products)

OR of product terms

AB + B′C

POS (product of sums)

AND of sum terms

(A + B)(B′ + C)

Minterm

Product term containing every variable exactly once

AB′C (for variables A, B, C)

Maxterm

Sum term containing every variable exactly once

A + B′ + C

The words standard and canonical are used differently by different books, so be careful:

  • A standard (or simply "SOP"/"POS") form allows terms with missing variables. AB + B′C is a standard SOP.

  • A canonical form uses only minterms (or only maxterms). Every term has every variable. A′BC + AB′C + ABC′ + ABC is canonical.

Expressions such as A(B + CD) are in neither form; they have more than two levels of gates.


Minterms and Maxterms

Minterms

A minterm mi is a product of all n variables, each complemented or not, that equals 1 for exactly one input combination: the row whose binary number is i.

Rule: write the row number in binary. A 1 bit gives the plain variable, a 0 bit gives the complemented variable. For row 5 = 101, the minterm is AB′C, which is 1 only when A = 1, B = 0, C = 1.

Maxterms

A maxterm Mi is a sum of all n variables, each complemented or not, that equals 0 for exactly one input combination: row i.

Rule: the opposite of minterms. A 0 bit gives the plain variable, a 1 bit gives the complemented variable. For row 5 = 101, M5 = A′ + B + C′. It is 0 only if every literal is 0: A′ = 0, B = 0, C′ = 0, that is A = 1, B = 0, C = 1.

The Complete Table for Three Variables

Row i

A B C

Minterm mi

Maxterm Mi

0

0 0 0

A′B′C′

A + B + C

1

0 0 1

A′B′C

A + B + C′

2

0 1 0

A′BC′

A + B′ + C

3

0 1 1

A′BC

A + B′ + C′

4

1 0 0

AB′C′

A′ + B + C

5

1 0 1

AB′C

A′ + B + C′

6

1 1 0

ABC′

A′ + B′ + C

7

1 1 1

ABC

A′ + B′ + C′

Look at any row: the maxterm is exactly the De Morgan complement of the minterm. For example (AB′C)′ = A′ + B + C′. So:

Mi = (mi)′        and        mi = (Mi)′

Also note: the variable order matters. The row number is read with the first-listed variable as the most significant bit. F(A, B, C) and F(C, B, A) give different minterm numbers for the same function.


Canonical SOP: Sum of Minterms

Here is the key idea. Each minterm is a "detector" for one row. If we OR together the detectors for every row where F = 1, the result is 1 exactly on those rows, which is F itself.

Example 1: The Majority Function

F(A, B, C) is 1 when at least two of the three inputs are 1.

Row

A B C

F

Use

0

0 0 0

0

M0 = A + B + C

1

0 0 1

0

M1 = A + B + C′

2

0 1 0

0

M2 = A + B′ + C

3

0 1 1

1

m3 = A′BC

4

1 0 0

0

M4 = A′ + B + C

5

1 0 1

1

m5 = AB′C

6

1 1 0

1

m6 = ABC′

7

1 1 1

1

m7 = ABC

Canonical SOP:
F = m3 + m5 + m6 + m7
  = A′BC + AB′C + ABC′ + ABC
Short form:  F(A, B, C) = Σm(3, 5, 6, 7)

The Σ (sigma) notation simply lists the row numbers where F = 1. It is how almost every exam question gives you a function.


Canonical POS: Product of Maxterms

Now the mirror idea. Each maxterm is 0 on exactly one row. If we AND together the maxterms for every row where F = 0, the product is 0 on each of those rows (one factor is 0) and 1 everywhere else (every factor is 1).

Same majority function: F = 0 on rows 0, 1, 2, 4

Canonical POS:
F = M0 · M1 · M2 · M4
  = (A + B + C)(A + B + C′)(A + B′ + C)(A′ + B + C)
Short form:  F(A, B, C) = ΠM(0, 1, 2, 4)

Notice that Σm(3, 5, 6, 7) and ΠM(0, 1, 2, 4) together use every row number 0 to 7 exactly once. That is always true.

F′ is 1 exactly where F is 0, so F′ = Σm(0, 1, 2, 4) = m0 + m1 + m2 + m4. Complement both sides:

F = (m0 + m1 + m2 + m4)′
  = m0′ · m1′ · m2′ · m4′        generalised De Morgan
  = M0 · M1 · M2 · M4            because Mi = mi′
  = ΠM(0, 1, 2, 4)              ✓

Converting Between Forms

For a function of n variables, the row numbers run from 0 to 2n − 1. Let S be the list of rows where F = 1 and Z the list of rows where F = 0.

Want

Rule

For F(A,B,C) = Σm(3, 5, 6, 7)

F as Σm

Σm(S)

Σm(3, 5, 6, 7)

F as ΠM

ΠM(Z): the missing numbers

ΠM(0, 1, 2, 4)

F′ as Σm

Σm(Z)

Σm(0, 1, 2, 4)

F′ as ΠM

ΠM(S)

ΠM(3, 5, 6, 7)

Memory aid: switching between Σ and Π for the same function uses the other numbers; complementing the function while keeping the same symbol (Σ or Π) also uses the other numbers.


Expanding a Standard Form to Canonical Form

Often you are given a simplified expression and asked for its minterms. There are two methods.

Method 1: Algebra (Multiply in the Missing Variables)

For SOP, any term missing a variable X is multiplied by (X + X′), which equals 1 and so changes nothing.

Example 2. Expand F(A, B, C) = A + B′C.

A    = A(B + B′)(C + C′)
     = ABC + ABC′ + AB′C + AB′C′              → m7, m6, m5, m4
B′C  = (A + A′)B′C
     = AB′C + A′B′C                           → m5, m1

F = A′B′C + AB′C′ + AB′C + ABC′ + ABC         (AB′C appears twice; X + X = X keeps one)
F = Σm(1, 4, 5, 6, 7) = ΠM(0, 2, 3)

For POS, any sum term missing a variable X gets XX′ added (which equals 0), and then the distributive law X + YZ = (X + Y)(X + Z) splits it.

Example 3. Expand F(A, B, C) = (A + B)(B′ + C).

A + B    = A + B + CC′
         = (A + B + C)(A + B + C′)             → M0, M1
B′ + C   = AA′ + B′ + C
         = (A + B′ + C)(A′ + B′ + C)           → M2, M6

F = ΠM(0, 1, 2, 6) = Σm(3, 4, 5, 7)

Method 2: Binary Patterns (Faster)

Write each term as a pattern with a dash for missing variables, then list every row that matches.

F(A, B, C) = A + B′C
Term A    → 1 – –   → 100, 101, 110, 111 → 4, 5, 6, 7
Term B′C  → – 0 1   → 001, 101           → 1, 5
Union                                    → Σm(1, 4, 5, 6, 7)   ✓ same as Example 2

For a POS term, list the rows where the term is 0:
A + B     → 0 0 –   → 000, 001 → 0, 1
B′ + C    → – 1 0   → 010, 110 → 2, 6
F = (A + B)(B′ + C) = ΠM(0, 1, 2, 6)                             ✓ same as Example 3

A term with k missing variables covers 2k rows. That fact is the whole reason Karnaugh maps group cells in powers of two.

Example 4 (four variables). F(A, B, C, D) = AB′ + C′D.

AB′   → 1 0 – –  → 8, 9, 10, 11
C′D   → – – 0 1  → 1, 5, 9, 13
F = Σm(1, 5, 8, 9, 10, 11, 13) = ΠM(0, 2, 3, 4, 6, 7, 12, 14, 15)

Doing It in Code

This Python program builds both canonical forms from any function you give it:

from itertools import product

def canonical(f, names):
    n = len(names)
    minterms, maxterms = [], []
    sop, pos = [], []
    for i, bits in enumerate(product([0, 1], repeat=n)):
        if f(*bits):
            minterms.append(i)
            sop.append("".join(v if b else v + "'" for v, b in zip(names, bits)))
        else:
            maxterms.append(i)
            pos.append("(" + " + ".join(v + "'" if b else v for v, b in zip(names, bits)) + ")")
    print("F = sum m" + str(tuple(minterms)) + " = product M" + str(tuple(maxterms)))
    print("Canonical SOP:", " + ".join(sop))
    print("Canonical POS:", "".join(pos))

# F = A + B'C
canonical(lambda a, b, c: a or (not b and c), "ABC")

Output:

F = sum m(1, 4, 5, 6, 7) = product M(0, 2, 3)
Canonical SOP: A'B'C + AB'C' + AB'C + ABC' + ABC
Canonical POS: (A + B + C)(A + B' + C)(A + B' + C')

itertools.product generates rows in binary counting order with the first variable as the most significant bit, which matches the minterm numbering.


Canonical vs Minimal Forms

Canonical forms are unique and easy to write, but they are expensive to build in hardware.

Form of the majority function

Expression

Terms

Literals

Canonical SOP

A′BC + AB′C + ABC′ + ABC

4

12

Minimal SOP

AB + BC + CA

3

6

Canonical POS

(A + B + C)(A + B + C′)(A + B′ + C)(A′ + B + C)

4

12

Minimal POS

(A + B)(B + C)(C + A)

3

6

Both canonical and minimal SOP are two-level circuits (AND gates feeding one OR gate), which can also be built as NAND-NAND; POS is OR-AND or NOR-NOR, as shown in De Morgan's Theorems. Going from the canonical list to the minimal expression is the job of the next three chapters.

Property

Canonical SOP

Canonical POS

Built from

Minterms (rows where F = 1)

Maxterms (rows where F = 0)

Notation

Σm(…)

ΠM(…)

Two-level circuit

AND-OR, or NAND-NAND

OR-AND, or NOR-NOR

Shorter when

F has few 1s

F has few 0s

Unique?

Yes (for a fixed variable order)

Yes (for a fixed variable order)


Counting Boolean Functions

Canonical forms make counting questions easy, and these questions are popular in GATE.

  • n variables give 2n minterms. A function is fully described by choosing which minterms to include, and each can be in or out, so there are 22n distinct functions: 4 for n = 1, 16 for n = 2, 256 for n = 3, 65,536 for n = 4.

  • Functions with exactly k minterms: C(2n, k). For n = 3 and k = 2, that is C(8, 2) = 28.

  • Self-dual functions (F equals its dual): these satisfy F(x′) = F(x)′, so the value on row i fixes the value on row 2n − 1 − i. Only half the rows are free, giving 22n−1 functions: 4 for n = 2 and 16 for n = 3 (a brute-force check of all 16 and all 256 functions confirms both counts).

The Dual from the Minterm List

Since Fd(x) = F′(x′), row i of the dual is 1 exactly when row 2n − 1 − i of F is 0. For F(A, B, C) = A + B′C = Σm(1, 4, 5, 6, 7), the zeros are 0, 2, 3, so the dual is Σm(7 − 0, 7 − 2, 7 − 3) = Σm(4, 5, 7). Check: the dual expression A(B′ + C) is 1 for 100, 101, 111, which is rows 4, 5, 7. ✓


Common Mistakes

  • Mixing up the maxterm rule. In a maxterm, a 1 bit gives a complemented variable. M5 (101) is A′ + B + C′, not A + B′ + C.

  • Using the ones for ΠM. ΠM lists the rows where F is 0. F = Σm(3, 5, 6, 7) is ΠM(0, 1, 2, 4), not ΠM(3, 5, 6, 7) (that is F′).

  • Ignoring variable order. F(A, B, C) and F(C, B, A) number the rows differently. Always check which variable is the MSB.

  • Forgetting the missing variables. For F(A, B, C, D) = AB′, the term covers four minterms (8, 9, 10, 11), not one.

  • Counting a minterm twice. When two terms cover the same row (like m5 in Example 2), it appears once in the list, because X + X = X.

  • Calling a simplified SOP "canonical". AB + BC + CA is an SOP but not canonical.


Interview and GATE-Style Questions

Q1. Express F(A, B, C) = Σm(1, 3, 6, 7) in canonical POS form.

The missing rows are 0, 2, 4, 5, so F = ΠM(0, 2, 4, 5) = (A + B + C)(A + B′ + C)(A′ + B + C)(A′ + B + C′).

Q2. Find the minterm expansion of f(P, Q, R) = PQ + QR′ + PR′.

PQ → 11– → 6, 7. QR′ → –10 → 2, 6. PR′ → 1–0 → 4, 6. Union: f = Σm(2, 4, 6, 7).

Q3. Which maxterm is 0 only for A = 1, B = 0, C = 1?

Row 101 = 5, so M5 = A′ + B + C′.

Q4. If F(A, B, C) = Σm(0, 2, 5), write F′ as a sum of minterms and as a product of maxterms.

F′ = Σm(1, 3, 4, 6, 7) = ΠM(0, 2, 5).

Q5. How many Boolean functions of 3 variables are there, and how many of them are self-dual?

223 = 256 functions. Self-dual: 222 = 24 = 16.

Q6. Why is the minimal SOP of a function not necessarily unique, while the canonical SOP is?

The canonical SOP is fixed by the truth table: one minterm per 1-row. A minimal SOP is chosen from many possible groupings, and sometimes two different choices have the same cost (cyclic functions, covered in Karnaugh Maps).

Q7. Convert F(A, B, C, D) = AB′ + C′D to canonical SOP notation.

AB′ → 10–– → 8, 9, 10, 11. C′D → ––01 → 1, 5, 9, 13. F = Σm(1, 5, 8, 9, 10, 11, 13).


Summary

  • A minterm mi is 1 only on row i (0 bit → complemented variable). A maxterm Mi is 0 only on row i (1 bit → complemented variable). Mi = mi′.

  • Canonical SOP = OR of minterms where F = 1, written Σm(…). Canonical POS = AND of maxterms where F = 0, written ΠM(…).

  • Σm and ΠM of the same function use complementary lists of row numbers.

  • Expand a standard form by multiplying in (X + X′) or adding XX′, or faster, by writing each term as a binary pattern with dashes.

  • There are 22n functions of n variables and 22n−1 self-dual ones.

  • Canonical forms are unique but costly. The next chapter, Karnaugh Maps, shows how to turn a minterm list into a minimal expression visually.