By the end of this chapter you should be able to:
- Write the minterm and the maxterm for any row of an \(n\)-variable truth table, and explain why the complement convention is reversed between them.
- Read the canonical SOP and the canonical POS of a function directly off its truth table and express both in \(\Sigma m\) and \(\Pi M\) notation.
- Expand a standard (non-canonical) SOP or POS expression into canonical form.
- Convert between \(\Sigma m\), \(\Pi M\), and the same notations for the complement of the function.
- Analyse a multi-level gate circuit to its truth table, and synthesise a minimal two-level circuit from a specification given in words.
Chapter 6 showed how to move between expressions that describe the same function, and Worked Example 6.4 turned twenty-four literals into four. That freedom is useful for minimisation and a nuisance for everything else. If two engineers hand you \(\overline{A}\,\overline{C} + \overline{B}\,\overline{C}\) and \(\overline{C}(\overline{A} + \overline{B})\), you cannot tell at a glance that these are the same circuit, and no program can either without doing algebra.
What is needed is a form that a function has exactly one of. This chapter develops the two standard forms — the canonical sum of products and the canonical product of sums — together with the compact \(\Sigma m\) and \(\Pi M\) notation for them. It then uses both in the two directions every combinational design runs: analysis, from a given circuit to its truth table, and synthesis, from a statement in words to a circuit.
1 Why a Function Needs a Standard Form
Some vocabulary first, because the names are used precisely from here on. A literal is a variable or its complement: \(A\) and \(\overline{A}\) are two literals. A product term is an AND of literals, such as \(A\overline{B}D\); a sum term is an OR of literals, such as \((A + \overline{C})\). A sum of products (SOP) is an OR of product terms and realises as a two-level AND-OR circuit; a product of sums (POS) is an AND of sum terms and realises as a two-level OR-AND circuit.
Both \(A\overline{C} + \overline{B}\,\overline{C}\) and \(A + \overline{B}C\) are sums of products, but neither is canonical, because their terms do not all contain every variable of the function. A form is canonical when each of its terms contains every variable exactly once, either complemented or not. The canonical form is sometimes called the expanded or standard form, though careful writers reserve "standard" for the non-canonical case, and this course does.
Why insist on it? Because a canonical form is unique. A function of \(n\) variables has one truth table, and as Section 3 shows, the canonical SOP is a direct transcription of the rows in which the output is 1. Two expressions therefore denote the same function if and only if they expand to the same canonical form — which is exactly the equivalence test a synthesis tool performs, and the reason both the Karnaugh map of Chapter 8 and the Quine–McCluskey algorithm of Chapter 9 begin by putting a function into canonical form before they minimise it.
The price is size. A canonical SOP for a function that is 1 in half its rows has \(2^{n-1}\) product terms of \(n\) literals each. Canonical form is the starting point for minimisation, never the end point of a design.
2 Minterms, Maxterms and Their Numbering
A minterm of \(n\) variables is a product term containing all \(n\) of them, each appearing exactly once. There are \(2^n\) of them, one for each row of the truth table, and the minterm belonging to a row is formed by writing each variable uncomplemented where that row has a 1 and complemented where it has a 0. Row 5 of a three-variable table is \(ABC = 101\), so \(m_5 = A\overline{B}C\).
A maxterm is a sum term containing all \(n\) variables, and here the convention reverses: each variable is written uncomplemented where the row has a 0 and complemented where the row has a 1. Row 5 gives \(M_5 = (\overline{A} + B + \overline{C})\). The reversal is not perversity; it is what makes the following true.
A minterm is a product, so it is 1 only when every one of its literals is 1 — which happens for exactly one input combination. A maxterm is a sum, so it is 0 only when every one of its literals is 0 — again for exactly one combination. Compare the two and you find \(M_i = \overline{m_i}\), which is De Morgan's theorem applied to a single term.
| Row \(i\) | A | B | C | Minterm \(m_i\) | Maxterm \(M_i\) |
|---|---|---|---|---|---|
| 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′) |
The numbering follows the binary value of the row with the first-listed variable as the most significant bit. That ordering is a convention, but it must be stated and kept: if the variables of a function are listed as \(B\), \(A\), \(C\) instead, every index changes. Data sheets and textbooks always give the variable order alongside the \(\Sigma m\) list, and so should you.
Two consequences are worth noting. Since each minterm is 1 on a different row, the sum of all \(2^n\) minterms is 1 for every input, so \(\sum_{i} m_i = 1\). Dually, \(\prod_i M_i = 0\). And since a minterm and its maxterm are complements, checking \(M_5 = \overline{m_5} = \overline{A\overline{B}C} = \overline{A} + B + \overline{C}\) reproduces the table entry exactly.
3 Canonical SOP and POS from a Truth Table
Given the truth table, both canonical forms can be written down without any algebra at all.
- For the canonical SOP, take every row in which \(F = 1\) and OR their minterms together. Each minterm makes \(F\) equal 1 on its own row and contributes nothing anywhere else, so the OR is 1 on exactly the rows required.
- For the canonical POS, take every row in which \(F = 0\) and AND their maxterms together. Each maxterm forces \(F\) to 0 on its own row and is 1 everywhere else, so the AND is 0 on exactly the rows required.
Take the function below, which will be used again in Section 7:
| Row | A | B | C | F | Contributes |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | \(M_0 = (A+B+C)\) |
| 1 | 0 | 0 | 1 | 0 | \(M_1 = (A+B+C')\) |
| 2 | 0 | 1 | 0 | 1 | \(m_2 = A'BC'\) |
| 3 | 0 | 1 | 1 | 1 | \(m_3 = A'BC\) |
| 4 | 1 | 0 | 0 | 0 | \(M_4 = (A'+B+C)\) |
| 5 | 1 | 0 | 1 | 1 | \(m_5 = AB'C\) |
| 6 | 1 | 1 | 0 | 0 | \(M_6 = (A'+B'+C)\) |
| 7 | 1 | 1 | 1 | 1 | \(m_7 = ABC\) |
Reading the four 1-rows gives the canonical SOP, and the four 0-rows give the canonical POS:
The \(\Sigma m\) and \(\Pi M\) notation is simply a list of row indices, and it is how a function is written when only the specification matters and not yet the implementation. The two lists always partition the numbers \(0\) to \(2^n - 1\) between them: a row makes the output either 1 or 0, so it supplies either a minterm or a maxterm and never both.
Figure 7.1 draws the canonical SOP as a circuit, and the shape is always the same: one AND gate per 1 in the output column, every AND gate carrying all \(n\) variables, and one OR gate collecting them. The canonical POS is the mirror image — one OR gate per 0 in the output column, feeding a single AND. This regularity is why a read-only memory can implement any function of its address lines, and why the programmable arrays of Chapter 28 are built as a fixed AND plane followed by a fixed OR plane.
4 Expanding a Standard Form to Canonical Form
Expressions rarely arrive in canonical form. \(F = A + \overline{B}C\) is a perfectly good SOP, but its first term has one literal and its second has two, where a three-variable canonical form needs three in each. Expanding it is a matter of multiplying each deficient term by 1, written in the form that introduces the missing variable.
Express \(F = A + \overline{B}C\) as a sum of minterms.
The term \(A\) is missing \(B\) and \(C\). Multiply by \((B + \overline{B})\) and then by \((C + \overline{C})\):
The term \(\overline{B}C\) is missing \(A\):
Collecting and applying idempotence to the repeated \(m_5\):
The repetition is expected — \(m_5\) satisfies both original terms — and dropping it is legitimate because \(m_5 + m_5 = m_5\). Evaluating \(A + \overline{B}C\) on all eight rows confirms that it is 1 exactly on rows 1, 4, 5, 6 and 7. Since the 0-rows are 0, 2 and 3, the same function is \(\Pi M(0,2,3)\).
The dual procedure expands a POS. A deficient sum term is missing variable \(X\); add \(X\overline{X}\), which is 0 and therefore changes nothing, then split the result with the distributive law \(P + QR = (P+Q)(P+R)\).
Express \(G = A(\overline{B} + C)\) as a product of maxterms.
The factor \(A\) is missing \(B\) and \(C\):
which is \(M_0 M_1 M_2 M_3\). The factor \((\overline{B}+C)\) is missing \(A\):
Collecting, and discarding the repeated \(M_2\) because \(M_2 M_2 = M_2\),
Checked against \(A(\overline{B}+C)\) on all eight rows: the expression is 1 for \(ABC = 100\), \(101\) and \(111\), which is rows 4, 5 and 7 as claimed.
5 Converting Between Σm, ΠM and the Complement
Once a function is in \(\Sigma m\) form every other standard description follows by arithmetic on the index list, with no algebra at all. There is only one fact to hold on to: a row supplies a minterm to \(F\) or a maxterm to \(F\), never both, and the two index lists are complementary subsets of \(\{0, 1, \ldots, 2^n-1\}\).
| Starting from | To get | Rule | Example on \(F = \Sigma m(2,3,5,7)\) |
|---|---|---|---|
| \(F = \Sigma m(S)\) | \(F = \Pi M(\cdot)\) | list the indices not in \(S\) | \(F = \Pi M(0,1,4,6)\) |
| \(F = \Sigma m(S)\) | \(\overline{F} = \Sigma m(\cdot)\) | list the indices not in \(S\) | \(\overline{F} = \Sigma m(0,1,4,6)\) |
| \(F = \Sigma m(S)\) | \(\overline{F} = \Pi M(\cdot)\) | keep the same indices | \(\overline{F} = \Pi M(2,3,5,7)\) |
| \(F = \Pi M(T)\) | \(F = \Sigma m(\cdot)\) | list the indices not in \(T\) | from \(\Pi M(0,1,4,6)\), \(F = \Sigma m(2,3,5,7)\) |
The third line is the one worth pausing over. If \(F = \Sigma m(S)\) then \(\overline{F}\) is 1 exactly on the rows not in \(S\), so \(\overline{F} = \Sigma m(\overline{S})\). But \(F = \Pi M(\overline{S})\) as well, from line one. Comparing the two gives
In words: complementing a function turns its sum of minterms into a product of maxterms carrying the same index list. That is De Morgan's theorem operating on whole canonical forms rather than on single terms, and it is the cleanest statement of the SOP–POS relationship. For the function of Section 3, \(F = \Sigma m(2,3,5,7)\) gives \(\overline{F} = \Pi M(2,3,5,7) = \Sigma m(0,1,4,6)\), and \(F\) itself is \(\Pi M(0,1,4,6)\).
One practical use. If a function is 1 in most of its rows, its canonical SOP is long and its canonical POS is short; if it is 1 in few rows, the reverse holds. Since a two-level AND-OR circuit and a two-level OR-AND circuit cost about the same per term, it is always worth counting the 1s and the 0s before choosing which form to minimise. Chapter 8 makes the same choice on a K-map by grouping the 0s instead of the 1s.
6 Analysis: From a Circuit to Its Truth Table
Analysis answers the question: given this circuit, what does it do? The procedure is mechanical and should be followed even when the circuit looks obvious.
- Check that the circuit is combinational — no feedback path from any output back to an input, or the methods of Part 5 are needed instead.
- Label every gate output that is not the final output with an intermediate name.
- Write the Boolean expression for each labelled node in terms of the nodes and inputs that drive it, working from the inputs forwards.
- Build the truth table one column per node, in that same order.
- Read the canonical forms off the final column.
Applying the procedure to Figure 7.2, the node expressions are \(T_1 = \overline{AB}\), \(T_2 = B \oplus C\), \(T_3 = T_1 T_2\), \(T_4 = \overline{C}\), \(T_5 = A T_4\) and finally \(F = T_3 + T_5\). Substituting gives \(F = \overline{AB}(B \oplus C) + A\overline{C}\), which tells you very little. The table does.
| A | B | C | \(T_1 = \overline{AB}\) | \(T_2 = B \oplus C\) | \(T_3 = T_1T_2\) | \(T_4 = \overline{C}\) | \(T_5 = AT_4\) | \(F = T_3 + T_5\) |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
The output column is 1 on rows 1, 2, 4, 5 and 6, so
Now the analysis pays for itself. The complement is 1 on only three rows, and those three collapse easily: \(\overline{F} = \Sigma m(0,3,7) = \overline{A}\,\overline{B}\,\overline{C} + \overline{A}BC + ABC = \overline{A}\,\overline{B}\,\overline{C} + BC\). Complementing that with De Morgan gives
Two gates and two inverters, against the six gates of Figure 7.2 — and both were checked to agree on all eight rows. The best SOP form, for comparison, is \(F = \overline{B}C + B\overline{C} + A\overline{B}\), needing four gates. Reading a circuit into a truth table and back out again is often the quickest route to a cheaper circuit, which is why analysis is a design skill and not merely an examination exercise.
7 Synthesis: From a Word Statement to a Circuit
Synthesis runs the other way: from a statement of what is wanted to a circuit that does it. The procedure mirrors the last one.
- Decide how many inputs and outputs there are and name them, fixing the variable order.
- Translate the statement into a truth table, row by row. This is the step where specifications are found to be ambiguous, and it is the step worth doing slowly.
- Write the canonical SOP, or the canonical POS if there are fewer 0s than 1s.
- Simplify — algebraically for now, by K-map from Chapter 8.
- Draw the circuit and count the gates.
A three-bit code \(ABC\), with \(A\) as the most significant bit, arrives from a rotary selector. Design a circuit whose output \(F\) is 1 when the code represents a prime number.
The primes below 8 are 2, 3, 5 and 7, so \(F = \Sigma m(2,3,5,7)\) — the truth table already tabulated in Section 3. The canonical SOP is the four-term expression of Figure 7.1, needing four three-input AND gates, one four-input OR and three inverters. Simplify it by pairing terms that differ in one variable:
Four literals, two two-input AND gates, one OR and one inverter. The result was checked against the specification on all eight rows: it is 1 for 010, 011, 101 and 111 and 0 elsewhere. Taking the POS route instead, \(\overline{F} = \Sigma m(0,1,4,6) = \overline{A}\,\overline{B} + A\overline{C}\), and complementing gives \(F = (A + B)(\overline{A} + C)\) — the same gate count in OR-AND form, which is the one to use if NOR gates are the cheap part.
Three signal lines are to be accompanied by a parity bit \(P\) that is 1 when an odd number of the lines is 1. Design the generator.
| A | B | C | number of 1s | P |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 2 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 2 | 0 |
| 1 | 1 | 0 | 2 | 0 |
| 1 | 1 | 1 | 3 | 1 |
So \(P = \Sigma m(1,2,4,7) = \overline{A}\,\overline{B}C + \overline{A}B\overline{C} + A\overline{B}\,\overline{C} + ABC\). Try to simplify it and nothing happens: no two of these four minterms differ in only one variable, so no pair combines and the canonical SOP is already the minimal SOP. Four three-input AND gates and a four-input OR is genuinely the cheapest two-level realisation.
It is not the cheapest realisation. Recognising the specification rather than grinding the algebra gives
which is two XOR gates, verified equal to \(\Sigma m(1,2,4,7)\) on all eight rows. This is the standing limitation of two-level minimisation: it searches only over AND-OR forms, and a function whose natural description is a parity will always defeat it. Chapter 17 builds parity generators this way, and Chapter 8 will show the same function as a K-map with no two adjacent 1s — the visual signature of a function that resists SOP minimisation.
8 Summary and Key Results
| Item | Rule | Note |
|---|---|---|
| Minterm \(m_i\) | Product of all variables; complement where the row bit is 0 | Equals 1 on row \(i\) only |
| Maxterm \(M_i\) | Sum of all variables; complement where the row bit is 1 | Equals 0 on row \(i\) only; \(M_i = \overline{m_i}\) |
| Canonical SOP | OR the minterms of the rows where \(F = 1\) | Two-level AND-OR; one AND per 1 |
| Canonical POS | AND the maxterms of the rows where \(F = 0\) | Two-level OR-AND; one OR per 0 |
| Complement | \(\overline{\Sigma m(S)} = \Pi M(S)\) | Same index list, notation swapped |
| Analysis | Label nodes, tabulate column by column | Truth table then \(\Sigma m\) |
| Synthesis | Statement → table → canonical form → simplify → gates | \(\Sigma m(2,3,5,7) \to \overline{A}B + AC\) |
9 Common Mistakes
For row 5 of a three-variable table, \(ABC = 101\), the minterm is \(A\overline{B}C\) but the maxterm is \((\overline{A} + B + \overline{C})\) — the complements fall on the opposite bits. The check is instant: substitute the row's own values and confirm that the minterm gives 1 and the maxterm gives 0. Getting this backwards silently produces the complement of the intended function.
\(\Sigma m(1,4,5,6,7)\) means nothing until you say which variable is the most significant bit. With the order \(A,B,C\) the list describes \(A + \overline{B}C\); with the order \(C,B,A\) the very same list describes a different function. Always write the order alongside the list, as \(F(A,B,C) = \Sigma m(1,4,5,6,7)\).
For one function the two lists are complementary: \(F = \Sigma m(2,3,5,7) = \Pi M(0,1,4,6)\). The index list is preserved only when you also complement the function: \(\overline{F} = \Pi M(2,3,5,7)\). Writing \(F = \Pi M(2,3,5,7)\) gives the complement of what was wanted, and the truth table will not agree in a single row.
10 Chapter Review
1. Write \(m_6\) and \(M_6\) for a four-variable function \(F(A,B,C,D)\), and verify the defining property of each.
Row 6 is \(ABCD = 0110\). The minterm complements the variables whose bits are 0: \(m_6 = \overline{A}BC\overline{D}\), which is 1 only when \(A=0, B=1, C=1, D=0\). The maxterm complements the variables whose bits are 1: \(M_6 = (A + \overline{B} + \overline{C} + D)\), which is 0 only for the same combination, since every literal is then 0.
2. Expand \(F = \overline{A}C + B\) to canonical SOP form for three variables.
\(\overline{A}C = \overline{A}(B+\overline{B})C = \overline{A}BC + \overline{A}\,\overline{B}C = m_3 + m_1\). \(B = (A+\overline{A})B(C+\overline{C}) = ABC + AB\overline{C} + \overline{A}BC + \overline{A}B\overline{C} = m_7 + m_6 + m_3 + m_2\). Collecting and removing the repeated \(m_3\): \(F = \Sigma m(1,2,3,6,7)\), and therefore \(F = \Pi M(0,4,5)\).
3. A function of three variables is \(F = \Pi M(1,3,5,7)\). Write it as \(\Sigma m\), simplify it, and name the circuit.
The maxterm list is 1, 3, 5, 7, so the minterm list is the complement, \(F = \Sigma m(0,2,4,6)\). Those are exactly the rows in which \(C = 0\), so \(F = \overline{C}\): a single inverter on the least significant input, with \(A\) and \(B\) unconnected. Checked on all eight rows, \(F = 1\) precisely when \(C = 0\).
4. In the circuit of Figure 7.2, what would the truth table become if the inverter on \(C\) were removed and \(C\) taken directly to the second AND gate?
\(T_5\) becomes \(AC\) rather than \(A\overline{C}\), so \(F = \overline{AB}(B \oplus C) + AC\). Recomputing the last column row by row gives 0, 1, 1, 0, 0, 1, 0, 1, that is \(F = \Sigma m(1,2,5,7) = \Pi M(0,3,4,6)\). Three rows change: rows 4 and 6 fall from 1 to 0 because \(A\overline{C}\) no longer holds them up, and row 7 rises from 0 to 1 because \(AC\) is now satisfied.
5. Why can the canonical SOP of \(\Sigma m(1,2,4,7)\) not be reduced by combining terms, and what does that tell you about the function?
Two minterms combine only when they differ in exactly one variable. The binary codes 001, 010, 100 and 111 differ from one another in two or three bit positions in every pair, so no combination is possible and the canonical form is already the minimal SOP. The function is the three-variable odd-parity function \(A \oplus B \oplus C\), which is cheap in XOR gates and expensive in AND-OR form — a reminder that two-level minimisation searches only over AND-OR realisations.