Unit 4 — Minterm and Maxterm Expansions
Unit Overview (click to expand)
Welcome to Unit 4, where we formalize something you have already been doing intuitively — writing Boolean functions in their most complete and unambiguous form. These canonical representations, built from minterms and maxterms, give you a precise language for describing any Boolean function. A minterm is an AND term that includes every variable in the function, either in its true form or its complemented form. Each row of a truth table where the output is one corresponds to exactly one minterm. When you OR all of those minterms together, you get the canonical Sum of Products, written compactly using Sigma notation. Maxterms work in the complementary direction. A maxterm is an OR term that includes every variable. Each row where the output is zero corresponds to one maxterm. When you AND all of those maxterms together, you get the canonical Product of Sums, written with Pi notation. Converting between the two canonical forms is simply a matter of swapping the indices. We also revisit the Shannon expansion theorem, which shows that any Boolean function can be decomposed around a chosen variable into two smaller sub-functions. This decomposition underpins the structure of multiplexers, binary decision diagrams, and many synthesis algorithms used by modern design tools. Finally, don't care conditions make a return appearance. In canonical form, don't care minterms are listed separately, preserving the freedom to assign them during later minimization. **Key Takeaways** 1. Minterms and maxterms provide a canonical, unambiguous way to represent any Boolean function as a Sum of Products or Product of Sums. 2. Sigma and Pi notations offer a compact shorthand that maps directly to truth table rows, making conversion between forms quick and mechanical. 3. The Shannon expansion theorem decomposes functions around a variable, forming the basis for multiplexer design and modern synthesis algorithms.Summary
This unit introduces the canonical forms for representing Boolean functions—the most complete and unambiguous way to express any logic function. Canonical forms use minterms (for Sum of Products) or maxterms (for Product of Sums) to create expressions where every variable appears exactly once in every term. Students will learn to derive canonical expressions directly from truth tables, convert between minterm and maxterm representations, and use compact notations (Σ and Π) for efficient specification. The unit also covers the Shannon expansion theorem, which provides a systematic method for decomposing functions, and explores how don't care conditions are represented in canonical form. These concepts establish the foundation for the systematic simplification techniques covered in Unit 5 (Karnaugh Maps).
Concepts Covered
- Canonical Form
- Standard Form
- Minterm
- Maxterm
- Minterm Expansion
- Maxterm Expansion
- Minterm Designation
- Maxterm Designation
- Sum of Minterms
- Product of Maxterms
- Minterm to Maxterm
- Maxterm to Minterm
- Canonical SOP Form
- Canonical POS Form
- Minterm List Notation
- Maxterm List Notation
- Sigma Notation
- Pi Notation
- Complement of Function
- Function from Truth Table
- Minterm from Truth Table
- Maxterm from Truth Table
- Dont Care Condition
- Incompletely Specified
- Dont Care in SOP
- Dont Care in POS
- Converting SOP to POS
- Converting POS to SOP
- Expansion Theorem
- Shannon Expansion
- Cofactor
- On-Set of Function
- Off-Set of Function
- DC-Set of Function
- Literal Count
Prerequisites
Before beginning this unit, students should have:
- Solid understanding of Boolean algebra operations (Unit 2)
- Ability to construct truth tables for any Boolean expression
- Familiarity with SOP and POS forms (Unit 2)
- Understanding of don't care conditions (Unit 3)
4.1 Canonical vs Standard Forms
Boolean expressions can be written in multiple equivalent ways. Two important classifications are canonical forms and standard forms.
A standard form expression is written as either:
- Standard SOP: Sum of product terms (not all variables need appear in each term)
- Standard POS: Product of sum terms (not all variables need appear in each term)
A canonical form is a standardized, unique representation where every variable appears exactly once (either complemented or uncomplemented) in every term.
- Canonical SOP: Every product term contains all n variables → called minterms
- Canonical POS: Every sum term contains all n variables → called maxterms
The canonical form of a function is unique — there is exactly one canonical SOP and one canonical POS for any given function.
| Property | Standard Form | Canonical Form |
|---|---|---|
| Variables per term | May vary | All n variables |
| Unique representation | No | Yes |
| Term names | Product / Sum terms | Minterms / Maxterms |
| Directly from truth table | No | Yes |
| Typically more terms | No | Yes |
Example — Standard SOP
The first term has only A and B, the second has A and C, and the third has B and C — not all three variables appear in every term.
4.2 Minterms
A minterm is a product term containing all n variables of the function, where each variable appears exactly once in either complemented or uncomplemented form. For n variables, there are exactly \(2^n\) possible minterms.
Minterm Construction — For each row of a truth table where the output is 1:
- Include the variable uncomplemented if its value is 1
- Include the variable complemented if its value is 0
Example: For 3 variables (A, B, C), construct the minterm for input 101:
- A = 1 → include A
- B = 0 → include \(\overline{B}\)
- C = 1 → include C
- Minterm: \(A\overline{B}C\)
Minterm Designation
Each minterm has a unique minterm designation (index number) equal to the decimal value of the input combination.
| Row | A | B | C | Decimal | Minterm | Designation |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | \(\overline{A}\overline{B}\overline{C}\) | \(m_0\) |
| 1 | 0 | 0 | 1 | 1 | \(\overline{A}\overline{B}C\) | \(m_1\) |
| 2 | 0 | 1 | 0 | 2 | \(\overline{A}B\overline{C}\) | \(m_2\) |
| 3 | 0 | 1 | 1 | 3 | \(\overline{A}BC\) | \(m_3\) |
| 4 | 1 | 0 | 0 | 4 | \(A\overline{B}\overline{C}\) | \(m_4\) |
| 5 | 1 | 0 | 1 | 5 | \(A\overline{B}C\) | \(m_5\) |
| 6 | 1 | 1 | 0 | 6 | \(AB\overline{C}\) | \(m_6\) |
| 7 | 1 | 1 | 1 | 7 | \(ABC\) | \(m_7\) |
Each minterm equals 1 for exactly one input combination and 0 for all others. This is why minterms are used to build SOP expressions — ORing together the minterms where F=1 creates a function that is 1 precisely for those inputs.
Diagram: Minterm Visualizer
4.3 Maxterms
A maxterm is a sum term containing all n variables of the function, where each variable appears exactly once in either complemented or uncomplemented form. Maxterms are the dual of minterms.
Maxterm Construction — For each row of a truth table where the output is 0:
- Include the variable complemented if its value is 1
- Include the variable uncomplemented if its value is 0
Example: For 3 variables (A, B, C), construct the maxterm for input 101:
- A = 1 → include \(\overline{A}\)
- B = 0 → include B
- C = 1 → include \(\overline{C}\)
- Maxterm: \((\overline{A} + B + \overline{C})\)
Maxterm Designation
Each maxterm has a unique maxterm designation equal to the decimal value of the input combination. Maxterms are denoted with capital M.
| Row | A | B | C | Decimal | Maxterm | Designation |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | \((A + B + C)\) | \(M_0\) |
| 1 | 0 | 0 | 1 | 1 | \((A + B + \overline{C})\) | \(M_1\) |
| 2 | 0 | 1 | 0 | 2 | \((A + \overline{B} + C)\) | \(M_2\) |
| 3 | 0 | 1 | 1 | 3 | \((A + \overline{B} + \overline{C})\) | \(M_3\) |
| 4 | 1 | 0 | 0 | 4 | \((\overline{A} + B + C)\) | \(M_4\) |
| 5 | 1 | 0 | 1 | 5 | \((\overline{A} + B + \overline{C})\) | \(M_5\) |
| 6 | 1 | 1 | 0 | 6 | \((\overline{A} + \overline{B} + C)\) | \(M_6\) |
| 7 | 1 | 1 | 1 | 7 | \((\overline{A} + \overline{B} + \overline{C})\) | \(M_7\) |
Each maxterm equals 0 for exactly one input combination and 1 for all others. This is the dual property to minterms. ANDing together maxterms where F=0 creates a function that is 0 precisely for those inputs.
Relationship Between Minterms and Maxterms
A minterm and maxterm with the same index are complements:
Example: \(m_5 = A\overline{B}C\) and \(M_5 = (\overline{A} + B + \overline{C})\)
By DeMorgan's theorem:
Why Canonical Forms Are Not Minimal
Canonical forms are unique and easy to derive from truth tables, but they carry a high literal count — the total number of variable appearances in the expression. Every term contains every variable, so an n-variable function with k minterms has n × k literals in its canonical SOP.
The gate count — the number of logic gates required — is closely related to literal count but not identical. Reducing literal count almost always reduces gate count.
| Metric | Canonical SOP | Simplified SOP | Savings |
|---|---|---|---|
| Literals | \(n \times k\) | Minimized | 40–70% typical |
| AND gates | \(k\) (each \(n\)-input) | Fewer, narrower | Fewer transistors |
| OR gate | 1 (\(k\)-input) | 1 (fewer inputs) | Reduced fan-in |
| Propagation delay | Higher (wider gates) | Lower | Faster circuit |
This cost difference motivates the entire subject of Boolean minimization covered in Units 5 and 6. Canonical forms are the starting point — they guarantee correctness and uniqueness — while minimized forms are the implementation goal.
Example: Cost of Canonical Form
Consider the 3-variable function \(F(A,B,C) = \Sigma m(3,5,6,7)\).
Canonical SOP (12 literals, 4 AND gates, 1 OR gate):
Simplified SOP (5 literals, 3 AND gates, 1 OR gate):
The simplified form uses fewer than half the literals and one fewer gate.
4.4 Canonical SOP and POS Forms
Sum of Minterms (Canonical SOP)
The canonical SOP form expresses a function as the OR (sum) of all minterms for which the function equals 1. This is also called the minterm expansion or sum of minterms.
Procedure: Function from Truth Table (SOP)
- Identify all rows where F = 1
- Write the minterm for each such row
- OR all minterms together
Example: Given the truth table:
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
F = 1 for rows 1, 3, 5 (decimal indices where output is 1)
Product of Maxterms (Canonical POS)
The canonical POS form expresses a function as the AND (product) of all maxterms for which the function equals 0. This is also called the maxterm expansion or product of maxterms. Maxterms correspond to the F = 0 rows because each maxterm evaluates to 0 for exactly one input combination.
Procedure: Maxterm from Truth Table (POS)
- Identify all rows where F = 0
- Write the maxterm for each such row
- AND all maxterms together
Example: Using the same truth table above, F = 0 for rows 0, 2, 4, 6, 7.
Both canonical forms — the sum of minterms (SOP) and the product of maxterms (POS) — represent the same function F.
Diagram: Minterm/Maxterm Converter
Diagram: Truth Table to Canonical Form Converter
4.5 Compact Notation: Σ and Π
Writing out full canonical expressions is tedious. Compact notations provide efficient representations.
Sigma Notation (Σ) for SOP — The minterm list notation uses the Greek letter sigma (Σ) followed by the list of minterm indices:
This reads: "F equals the sum of minterms 1, 3, and 5." The variable list indicates the order of significance (A is MSB, C is LSB).
Pi Notation (Π) for POS — The maxterm list notation uses the Greek letter pi (Π) followed by the list of maxterm indices:
This reads: "F equals the product of maxterms 0, 2, 4, 6, and 7."
Converting Between Notations
Since a function is 1 for minterm indices and 0 for maxterm indices, conversion is straightforward — the maxterm indices are all indices NOT in the minterm list, and vice versa.
For 3 variables, indices 0–7 exist. If minterms are {1, 3, 5}, maxterms are {0, 2, 4, 6, 7}.
| Given | To Find | Method |
|---|---|---|
| Σm(list) | ΠM(list) | Use indices NOT in minterm list |
| ΠM(list) | Σm(list) | Use indices NOT in maxterm list |
4.6 Complement of a Function
The complement of a function \(\overline{F}\) has the opposite output for every input combination. This leads to elegant relationships in canonical form:
This reveals a beautiful symmetry:
- The minterm indices of \(F\) become the maxterm indices of \(\overline{F}\)
- The maxterm indices of \(F\) become the minterm indices of \(\overline{F}\)
Example:
For 3 variables, the complement takes all remaining indices:
Practical Use
To find \(\overline{F}\) in canonical form:
- From SOP: Swap \(\Sigma m \to \Pi M\), keep same indices
- From POS: Swap \(\Pi M \to \Sigma m\), keep same indices
4.7 Converting Between SOP and POS
Beyond canonical forms, we often need to convert between standard SOP and POS expressions.
Converting SOP to POS — Method 1: Via Truth Table
- Expand SOP to canonical form (all minterms)
- Identify maxterm indices (where F=0)
- Write POS from maxterms
Converting SOP to POS — Method 2: Algebraic (DeMorgan's)
- Find \(\overline{F}\) by complementing the SOP
- Simplify \(\overline{F}\) to SOP form
- Complement again: \(F = \overline{\overline{F}}\)
- Apply DeMorgan's to get POS
Example: Convert \(F = AB + \overline{A}C\) to POS
Step 1: Find \(\overline{F}\) using DeMorgan's:
Step 2: Expand \(\overline{F}\) to SOP by distributing:
The term \(\overline{B}\overline{C}\) is redundant by the consensus theorem, so \(\overline{F} = \overline{A}\overline{C} + A\overline{B}\).
Step 3: Complement \(\overline{F}\) using DeMorgan's to get F in POS:
Result: \(F = (A+C)(\overline{A}+B)\)
Converting POS to SOP
Method 1: Via Truth Table — Expand POS to canonical form, identify minterm indices (where F=1), write SOP from minterms.
Method 2: Algebraic Expansion — Multiply out the POS expression using distribution, then simplify using Boolean algebra.
Example: Convert \(F = (A+B)(A+C)\) to SOP
Diagram: SOP-POS Converter
Verifying Canonical Form Correctness
After converting between SOP and POS or simplifying a canonical expression, you need to verify the result is correct. Two systematic methods guarantee correctness.
Method 1: Truth Table Cross-Check — Evaluate both expressions for all \(2^n\) input combinations. If every row matches, they are equivalent.
Method 2: Algebraic Proof — Use Boolean algebra laws to transform one expression into the other.
Example: Verify SOP-POS Equivalence
Given: \(F = \Sigma m(1,3,5,7) = \Pi M(0,2,4,6)\)
| A | B | C | \(\Sigma m(1,3,5,7)\) | \(\Pi M(0,2,4,6)\) | Match? |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | Yes |
| 0 | 0 | 1 | 1 | 1 | Yes |
| 0 | 1 | 0 | 0 | 0 | Yes |
| 0 | 1 | 1 | 1 | 1 | Yes |
| 1 | 0 | 0 | 0 | 0 | Yes |
| 1 | 0 | 1 | 1 | 1 | Yes |
| 1 | 1 | 0 | 0 | 0 | Yes |
| 1 | 1 | 1 | 1 | 1 | Yes |
All rows match, confirming \(F = C\) (the function equals the variable \(C\) alone).
Algebraic Proof: \(\overline{A}BC + A\overline{B}C + AB\overline{C} + ABC = AB + AC + BC\)
Starting from the left side, pair minterms that differ in one variable:
- \(\overline{A}BC + ABC = BC(A + \overline{A}) = BC\)
- \(A\overline{B}C + ABC = AC(B + \overline{B}) = AC\)
- \(AB\overline{C} + ABC = AB(C + \overline{C}) = AB\)
Therefore: \(F = AB + AC + BC\) ∎
Notice that the minterm \(ABC\) was used three times in different pairings — this is valid because the OR operation is idempotent (\(X + X = X\)). This "sharing" of minterms is exactly what K-maps exploit visually.
4.8 Don't Cares in Canonical Form
Don't care conditions (introduced in Unit 3) have specific representations in canonical notation. A Boolean function can be described by three sets of minterm indices:
| Set | Symbol | Description |
|---|---|---|
| On-set | F = 1 | Minterms where output is 1 |
| Off-set | F = 0 | Minterms where output is 0 |
| DC-set | F = X | Minterms where output is don't care |
These three sets partition all \(2^n\) indices: On-set ∪ Off-set ∪ DC-set = {0, 1, ..., 2n-1}
Notation with Don't Cares
The canonical notation extends to include don't cares:
SOP form: \(F(A,B,C) = \Sigma m(1,3,5) + d(2,6)\) — "F equals 1 for minterms 1, 3, 5, with don't cares at 2 and 6."
POS form: \(F(A,B,C) = \Pi M(0,4,7) \cdot d(2,6)\)
When simplifying:
- Don't care in SOP: Treat as 1 if it helps create larger groups
- Don't care in POS: Treat as 0 if it helps create larger groups
The optimizer chooses the assignment that minimizes the expression.
Example: \(F = \Sigma m(1,3,5) + d(2,6)\)
| Set | Indices |
|---|---|
| On-set | {1, 3, 5} |
| DC-set | {2, 6} |
| Off-set | {0, 4, 7} |
During simplification (K-maps, Unit 5), we may include minterms 2 and/or 6 if it reduces the expression.
Incompletely Specified Functions
An incompletely specified function has at least one don't care condition. The function is not fully defined — it specifies required behavior for some inputs but allows flexibility for others.
Example: BCD Decoder — BCD uses only inputs 0000–1001 (0–9). Inputs 1010–1111 (10–15) never occur, so their outputs are don't cares:
4.9 Shannon Expansion Theorem
The Shannon expansion theorem (also called the expansion theorem) provides a systematic method for decomposing a Boolean function with respect to any variable.
Any Boolean function F can be expanded around a variable X:
where:
- \(F_X\) is the positive cofactor: F evaluated with X = 1
- \(F_{\overline{X}}\) is the negative cofactor: F evaluated with X = 0
A cofactor of function F with respect to variable X is F with X set to a constant.
Example: Given \(F = AB + \overline{A}C + BC\), find cofactors with respect to A.
Positive cofactor (set A = 1):
Negative cofactor (set A = 0):
Verify reconstruction:
The reconstructed expression \(AB + \overline{A}C\) appears different from the original \(AB + \overline{A}C + BC\), but by the consensus theorem, the term \(BC\) is redundant.
Applications of Shannon Expansion
- Multiplexer implementation: The expansion directly maps to a 2:1 MUX with X as select
- Recursive decomposition: Break complex functions into simpler cofactors
- BDD construction: Binary Decision Diagrams use repeated Shannon expansion
- Verification: Check function equivalence by comparing cofactors
Diagram: Shannon Expansion Explorer
Multi-Variable Shannon Expansion
Shannon expansion around a single variable produces two cofactors, each depending on \(n-1\) variables. Applying the expansion recursively produces four sub-functions:
Each successive expansion doubles the number of branches. Expanding around all \(n\) variables produces exactly \(2^n\) branches — one per minterm — recovering the canonical form. This reveals that the canonical SOP is simply the complete Shannon expansion tree.
Example: Two-Level Expansion for \(F(A,B,C) = AB + \overline{A}C\):
Level 1 — expand around \(A\): \(F_A = B\), \(F_{\overline{A}} = C\)
Level 2 — expand each cofactor around \(B\):
- \(F_{AB} = 1\), \(F_{A\overline{B}} = 0\) (from \(F_A = B\))
- \(F_{\overline{A}B} = C\), \(F_{\overline{A}\overline{B}} = C\) (from \(F_{\overline{A}} = C\))
Connections to MUX Trees and BDDs
Each level of Shannon expansion maps to one level of 2:1 multiplexers. A two-variable expansion uses a tree of three MUXes, directly implementing any Boolean function using only multiplexers.
A Binary Decision Diagram (BDD) is a directed acyclic graph that represents Shannon expansion in compact form. Each internal node tests one variable, with two outgoing edges for the 0 and 1 cofactors.
An Ordered BDD (OBDD) fixes a single variable ordering. A Reduced Ordered BDD (ROBDD) applies two rules:
- Merge rule: Combine identical sub-graphs
- Elimination rule: Remove a node whose 0-child and 1-child are identical
ROBDDs are canonical for a given variable ordering — two functions are equivalent if and only if their ROBDDs are identical. This property makes BDDs the foundation of many modern verification and synthesis algorithms.
4.10 Literal Count and Expression Complexity
The literal count is a common metric for expression complexity, counting the total number of variable appearances (complemented or uncomplemented) in an expression.
Canonical forms typically have high literal counts because every term includes all variables:
Why literal count matters:
- Gate inputs: Each literal requires a gate input (or inverter)
- Wiring complexity: More literals = more connections
- Cost: Integrated circuit area and power roughly correlate with literal count
- Speed: More literals can mean longer propagation paths
| Metric | Canonical Form | Simplified Form |
|---|---|---|
| Unique | Yes | May not be unique |
| From truth table | Direct | Requires simplification |
| Literal count | High | Minimized |
| Implementation cost | High | Lower |
The goal of simplification (Unit 5) is to reduce literal count while preserving the function.
Example: \(F = AB + \overline{A}C + BC\)
| Term | Expression | Literals | Count |
|---|---|---|---|
| Term 1 | \(AB\) | A, B | 2 |
| Term 2 | \(\overline{A}C\) | \(\overline{A}\), C | 2 |
| Term 3 | \(BC\) | B, C | 2 |
| Total | 6 |
Example: \(F = \Sigma m(1,3,5)\) in 3 variables — 3 minterms × 3 literals = 9 literals. The simplified form: \(F = C\) has only 1 literal — a 9× reduction!
Summary and Key Takeaways
This unit established canonical forms as the foundation for systematic Boolean function representation:
- Canonical forms are unique representations where every variable appears in every term. They bridge truth tables and algebraic expressions.
- Minterms are product terms with all variables (used for canonical SOP). Each minterm equals 1 for exactly one input combination.
- Maxterms are sum terms with all variables (used for canonical POS). Each maxterm equals 0 for exactly one input combination.
- Minterm/maxterm designations use indices matching the decimal value of the input combination. \(m_i\) and \(M_i\) are complements of each other.
- Compact notation uses \(\Sigma m\)(indices) for sum of minterms and \(\Pi M\)(indices) for product of maxterms.
- Converting between SOP and POS: Use the complementary index set, or build via truth table.
- Function complement: \(\overline{F}\) swaps minterm indices to maxterm indices (and vice versa).
- Don't cares are represented as d(indices) and define the DC-set alongside On-set and Off-set.
- Shannon expansion decomposes \(F = X \cdot F_X + \overline{X} \cdot F_{\overline{X}}\) using positive and negative cofactors.
- Literal count measures expression complexity; canonical forms have high literal counts that simplification reduces.
Self-Check Questions
Convert F = Σm(0,2,5,7) to ΠM notation for 3 variables.
For 3 variables, indices are 0-7. If On-set = {0,2,5,7}, then Off-set = {1,3,4,6}. Therefore: F = ΠM(1,3,4,6)
What is the complement of F = Σm(1,4,6) in Σ notation?
\(\overline{F}\) has the complementary minterm set. For 3 variables: \(\overline{F} = \Sigma m(0,2,3,5,7)\)
Find the positive cofactor of F = ABC + ĀB + BC with respect to B.
Set B = 1: \(F_B = A(1)C + \overline{A}(1) + (1)C = AC + \overline{A} + C = \overline{A} + C\) (by absorption: AC + C = C, and \(\overline{A} + C\) remains)
Interactive Walkthrough
Step through expanding a Boolean expression into canonical minterm form: