Boolean Functions & Canonical Forms

Boolean Algebra & Digital Logic

Chapter 4 · Boolean Functions & Canonical Forms

Chapters 2-3 gave the vocabulary and the laws. This chapter gives the actual, mechanical procedure: given any truth table at all, how do you write down a Boolean expression that produces it? The answer works for every possible function, every time, with no cleverness required.

How Many Boolean Functions Even Exist?

A Boolean function of n variables has 2ⁿ rows in its truth table, and each row's output can independently be 0 or 1 — so there are exactly 2^(2ⁿ) possible functions of n variables.

Verified directly

2 variables: 2^(2²) = 16 possible functions (AND, OR, XOR, NAND, NOR, XNOR, and 10 others, including the two constant functions "always 0" and "always 1"). 3 variables: 2^(2³) = 256 possible functions.

Minterms: A Building Block for Exactly One Row

A minterm is an AND of every variable (each either plain or complemented) that evaluates to 1 for exactly one input combination and 0 everywhere else. For two variables x,y, the minterm for the row x=1,y=0 is xy' — it's only 1 when x=1 and y=0.

Sum-of-Products: Reconstructing Any Truth Table

The mechanical procedure

For every row where the truth table's output is 1, write down that row's own minterm. OR all of them together. The result is guaranteed to reproduce the exact original truth table — this is the sum-of-products (SOP) form, and it works for any Boolean function, not just convenient ones.

Maxterms & Product-of-Sums: The Dual Construction

A maxterm is the dual idea — an OR of every variable that evaluates to 0 for exactly one input combination. Taking the maxterm for every row where the output is 0, and AND-ing them together, gives the product-of-sums (POS) form — the same truth table, built from the opposite direction.

A Real Worked Example: The Majority Function

majority(x,y,z) outputs 1 exactly when at least two of its three inputs are 1 — a genuinely useful function, not a toy: it's the core of triple modular redundancy (TMR), the real fault-tolerance technique used in spacecraft and other safety-critical computers, where three independent copies of a circuit vote and the majority result is trusted even if one copy has been corrupted (by a cosmic ray flipping a bit, for instance).

Verified directly — the full truth table

Output is 1 for exactly 4 rows: (0,1,1), (1,0,1), (1,1,0), (1,1,1). Output is 0 for the other 4: (0,0,0), (0,0,1), (0,1,0), (1,0,0).

Both forms verified directly, all 8 combinations

SOP: x'yz + xy'z + xyz' + xyz (one minterm per 1-row). POS: (x+y+z)(x+y+z')(x+y'+z)(x'+y+z) (one maxterm per 0-row). Both expressions were evaluated against the actual majority() function for all 8 input combinations — every single one matches, both forms and the original function agree perfectly.

Real Relevance: Specifying Business Logic From Test Cases

Anywhere requirements arrive as a table of "given these flags, the system should do X" — SOP construction turns that table directly into a correct, complete Boolean condition, mechanically, without needing to guess a clever simplified form first. Chapter 5 picks up immediately from here: an SOP expression built this way is always correct, but rarely the shortest way to say it — simplification is the next problem.

Canonical Forms in Code

def majority(x, y, z):
    return 1 if (x + y + z) >= 2 else 0

def sop(x, y, z):
    # x'yz + xy'z + xyz' + xyz -- one minterm per 1-row
    return ((1-x)&y&z) | (x&(1-y)&z) | (x&y&(1-z)) | (x&y&z)

def pos(x, y, z):
    # (x+y+z)(x+y+z')(x+y'+z)(x'+y+z) -- one maxterm per 0-row
    return (x|y|z) & (x|y|(1-z)) & (x|(1-y)|z) & ((1-x)|y|z)

from itertools import product
assert all(majority(x,y,z) == sop(x,y,z) == pos(x,y,z)
           for x,y,z in product([0,1], repeat=3))
print("SOP and POS both exactly reproduce majority() for all 8 inputs")

Hands-On Exercises

Exercise 1

A 2-variable function f(x,y) is 1 only when x=0, y=1 or x=1, y=0 (this is XOR). Write out its SOP form using minterms, and verify it matches the actual XOR truth table for all 4 input combinations.

📄 View solution

Exercise 2

Using the same XOR function from Exercise 1, write out its POS form using maxterms (from the rows where the output is 0), and verify it also matches the actual XOR truth table for all 4 combinations.

📄 View solution

Exercise 3

A requirements table says a discount applies (output 1) only when is_member=1, is_holiday=0 or when is_member=0, is_holiday=1 — and never applies in any other combination of the two flags. Using this chapter's own SOP procedure, write the exact Boolean expression this requirements table describes, and name which well-known 2-input function it turns out to be.

📄 View solution

Chapter 4 Quick Reference

A function of n variables has exactly 2^(2ⁿ) possible truth tables — 16 for 2 variables, 256 for 3
Minterm: an AND term that's 1 for exactly one row. Maxterm: an OR term that's 0 for exactly one row
Sum-of-Products (SOP): OR together the minterms of every 1-row — reconstructs any truth table, mechanically
Product-of-Sums (POS): AND together the maxterms of every 0-row — the dual construction, same guarantee
Verified on a real, useful function (3-input majority, the core of triple modular redundancy) — both forms matched exactly
SOP built this way is always correct, but rarely shortest — Chapter 5 covers simplification
Next chapter: Simplifying Boolean expressions