Canonical Forms: Minterms, Maxterms and Shannon Expansion

Write a truth table as minterms or maxterms, convert between the two lists, and split a function around one variable.

You Will Be Able To

  • Name the minterm and the maxterm of each row.
  • Write a function as Σm and as ΠM, and convert between them.
  • Tell a canonical form from a minimal one.
  • Split a function around one variable by Shannon expansion.
Lesson
G2.8
Time
25 min
Runs on
Your browser
Check
5 questions

Two engineers wrote the same function in a review. One wrote Σm(1, 3, 4, 6). The other wrote ΠM(0, 2, 5, 7). Both lists describe one truth table.

One Truth Table, Two Lists of Row NumbersOne row per step, abc from 000 to 111. A row with f = 1 joins the minterm list. A row with f = 0 joins the maxterm list.
01234567row m01234567a b c000001010011100101110111f = a'c + ac'listΠMΣmΠMΣmΠMΣmΠM
Scroll horizontally ↔
  1. Cycle 0

    Row 0 gives f = 0. Its number goes to the maxterm list.

  2. Cycle 1

    Row 1 gives f = 1. Its number goes to the minterm list.

  3. Cycle 7

    Every row lands in exactly one list. So each list is the complement of the other.

Computed from the expression and checked on Icarus.

Minterms and Maxterms

A literal is a variable or its complement: a or a'. A minterm is an AND of every variable once, each as a literal. It is 1 on exactly one row. A maxterm is an OR of every variable once. It is 0 on exactly one row.

Rowa b cMinterm (1 on this row only)Maxterm (0 on this row only)
0000a'b'c'(a + b + c)
1001a'b'c(a + b + c')
2010a'bc'(a + b' + c)
3011a'bc(a + b' + c')
4100ab'c'(a' + b + c)
5101ab'c(a' + b + c')
6110abc'(a' + b' + c)
7111abc(a' + b' + c')

Minterm: a 0 in the row gives a primed literal. Maxterm: a 1 in the row gives a primed literal. Each maxterm is the complement of the minterm of its row.

Sum of Minterms and Product of Maxterms

Any function is the OR of the minterms of its 1 rows. This is the canonical sum of products, written Σm with the row numbers. It is also the AND of the maxterms of its 0 rows: the canonical product of sums, written ΠM.

FormWritten asBuilt from
ΣmΣm(1, 3, 4, 6)a'b'c + a'bc + ab'c' + abc'
ΠMΠM(0, 2, 5, 7)(a + b + c)(a + b' + c)(a' + b + c')(a' + b' + c')

Both forms of f = a'c + ac'. The two number lists split 0 to 7 between them.

To convert, list the numbers that are missing. The maxterms of f are the rows where f is 0, so they are exactly the numbers not in Σm.

Click a Row, Watch Both Lists
abcf
000
001
010
011
100
101
110
111

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

Click a Row, Watch Both Listsg0 · NOTinv_a=1g1 · ANDterm0=0g2 · NOTinv_c=1g3 · ANDterm1=0g4 · ORf=0a=0b=0c=0
a=0 b=0 c=0
g0 · NOTa=0 → inv_a=1
g1 · ANDinv_a=1, c=0 → term0=0
g2 · NOTc=0 → inv_c=1
g3 · ANDa=0, inv_c=1 → term1=0
g4 · ORterm0=0, term1=0 → f=0
Read the connections
GateKindInputsOutput
g0NOTainv_a
g1ANDinv_a, cterm0
g2NOTcinv_c
g3ANDa, inv_cterm1
g4ORterm0, term1f

Outputs: f. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

The canonical pane shows Σm and ΠM. Click an output cell to change one row: one number moves from one list to the other.

The complement f' has the 0 rows of f as its minterms. So f' = Σm of the same numbers that ΠM lists for f.

Canonical Against Minimal

A canonical form uses one full term for each row in its list. It is unique: two functions are equal exactly when their Σm lists are equal.

A standard form is any sum of products or product of sums, with terms that may leave out variables. The minimal one is usually far smaller.

Canonical Beside Minimal
abcdf
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Canonical: Σm(1, 4, 6, 9, 14) = ΠM(0, 2, 3, 5, 7, 8, 10, 11, 12, 13, 15)

Minimum SOP

~b & ~c & d | ~a & b & ~d | b & c & ~d

3 terms · 9 literals

Minimum POS

(b | d) & (~b | ~d) & (~c | ~d) & (~a | c | d)

4 sum terms · 9 literals

The lab function, Σm(1, 4, 6, 9, 14). The canonical form has five terms of four literals each. Compare it with the minimal pane.

Canonical forms are the safe way to state a function. Minimization, in module G3, makes it cheap.

Shannon Expansion

Shannon expansion splits a function around one variable. Set a = 0 to get the cofactor f₀. Set a = 1 to get f₁. Then f = a'·f₀ + a·f₁.

Majority Split Around AArrows show the two cofactors feeding a selector on a. The selector is a two-input multiplexer.
  • Neutral
  • Datapath
  • I/O
  • Structure
  • Data
CallValueReturnWaiting
Majority split around aArrows show the two cofactors feeding a selector on a. The selector is a two-input multiplexer. neutral f = ab + ac + bc majority of three datapath f₀ = f with a = 0 bc datapath f₁ = f with a = 1 b + c datapath Select on a a'·f₀ + a·f₁ io f the same function a = 0a = 1when a = 0when a = 1
  1. neutral f = ab + ac + bcmajority of three
    • a = 0 → f₀ = f with a = 0
    • a = 1 → f₁ = f with a = 1
  2. datapath f₀ = f with a = 0bc
    • when a = 0 → Select on a
  3. datapath f₁ = f with a = 1b + c
    • when a = 1 → Select on a
  4. datapath Select on aa'·f₀ + a·f₁
    • f
  5. io fthe same function
  1. Set a = 0

    ab and ac vanish. What is left is bc.

    Follow the calls, values and waits
    1. data bc: f = ab + ac + bc → f₀ = f with a = 0
  2. Set a = 1

    ab becomes b and ac becomes c. b + c + bc is b + c by absorption.

    Follow the calls, values and waits
    1. data b + c: f = ab + ac + bc → f₁ = f with a = 1
  3. Join them

    f = a'(bc) + a(b + c). A multiplexer on a picks the right cofactor.

    Follow the calls, values and waits
    1. data a'(bc) + a(b + c): Select on a → f
Read the diagram as text
  • f = ab + ac + bc: majority of three
  • f₀ = f with a = 0: bc
  • f₁ = f with a = 1: b + c
  • Select on a: a'·f₀ + a·f₁
  • f: the same function
  • f = ab + ac + bc → f₀ = f with a = 0: a = 0
  • f = ab + ac + bc → f₁ = f with a = 1: a = 1
  • f₀ = f with a = 0 → Select on a: when a = 0
  • f₁ = f with a = 1 → Select on a: when a = 1
  • Select on a → f

The expansion is exact for every function. Lesson G4.2 builds functions from multiplexers this way.

Asked in interviews
  1. What is the difference between a minterm and a maxterm?

    A minterm is an AND of all variables that is 1 on exactly one row. A maxterm is an OR of all variables that is 0 on exactly one row. M_m is the complement of m_m.

  2. How do you convert Σm to ΠM?

    List the row numbers that are missing from Σm. Those rows are the 0s of the function, and each gives one maxterm.

  3. What is Shannon expansion used for?

    It splits a function into two smaller cofactors selected by one variable. It maps a function onto multiplexers and lookup tables, and it is the basis of decision diagrams.

Try It

The constant F = 16'h4252 sets bits 1, 4, 6, 9, 14. So the function is Σm(1, 4, 6, 9, 14).

The module sum_of_minterms has one product per minterm, but the product for row 14 is missing. The bench finds it.

Add | (a & b & c & ~d) and run again. The bench prints equal on 16 of 16.

Now write the product of maxterms instead: one sum term for each of the eleven 0 rows. The bench must print 16 of 16 again.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: differ at m = 14 (abcd = 1110): table 1, sum 0 equal on 15 of 16
Read included file: tb.sv
// tb.sv: compares the sum of minterms with the table on all 16 rows (read-only).
module tb;
  logic a, b, c, d;
  logic f, g;
  int   equal = 0;

  from_table      u_f (.a(a), .b(b), .c(c), .d(d), .f(f));
  sum_of_minterms u_g (.a(a), .b(b), .c(c), .d(d), .g(g));

  initial begin
    for (int m = 0; m < 16; m++) begin
      {a, b, c, d} = m[3:0];
      #1;
      if (f === g) equal++;
      else $display("differ at m = %0d (abcd = %b%b%b%b): table %b, sum %b", m, a, b, c, d, f, g);
    end
    $display("equal on %0d of 16", equal);
  end
endmodule

Check Yourself

ConceptA function of a, b and c is Σm(1, 2, 5). What is it as a product of maxterms?
ConceptWhich row number does the maxterm (a' + b + c') belong to?
ConceptWhy is a sum of minterms called canonical?
ConceptWhat is the cofactor of f = ab + a'c with a = 1?
Predict the outputThe program prints f = ab' + c on the rows abc = 000 to 111. Predict the exact line, then read off the minterm list.
module tb;
  logic a, b, c;
  logic [7:0] col;
  initial begin
    for (int m = 0; m < 8; m++) begin
      {a, b, c} = m[2:0];
      col[7 - m] = (a & ~b) | c;
    end
    $display("%b", col);
  end
endmodule

Common Mistakes

Wrong Number the rows with the variables in the wrong order.

The minterm number is the binary value of the inputs in the stated order. a b' c d' is 1010 = 10, but read backwards it is 0101 = 5.

Fix Write the variables in order, a first, as a binary number.

Wrong Complement the literals of a minterm the wrong way when writing a maxterm.

A maxterm is 0 on exactly one row. Its literals are complemented where the row has a 1, not where it has a 0.

Fix Row 101 gives the maxterm (a' + b + c'): a 1 becomes a primed literal.

Wrong Think that canonical means minimal.

A canonical form has one full term per row. It is unique, but it is usually much larger than the minimum.

Fix Use Σm and ΠM to state a function exactly. Use minimization (module G3) to make it small.

Wrong List don't-care rows among the minterms.

A don't-care row may be 0 or 1. Listing it as a minterm fixes it to 1, which the spec never asked for.

Fix Write the don't-cares as a separate list: f = Σm(...) + d(...).

Remember

  • A minterm is 1 on one row, a maxterm is 0 on one row. The row number is the inputs read as a binary number.
  • Σm lists the 1 rows. ΠM lists the 0 rows. Each list is the complement of the other.
  • Canonical forms are unique but large. Minimal forms are small.
  • Shannon expansion: f = a'·f₀ + a·f₁, a multiplexer on a.

Practice

Report a problem with this page