Challenge Problems: Minterm & Maxterm Expansions
These challenge problems test deeper understanding. Only final answers are provided — work through each problem on your own.
Challenge 1: Convert Between Minterm and Maxterm List Forms
A function of four variables (\(A\), \(B\), \(C\), \(D\)) is defined as:
Express \(F\) in maxterm list form \(\prod M(\ldots)\) and identify the pattern in the function.
Show Answer
\(F(A, B, C, D) = \prod M(0, 2, 4, 6, 8, 10, 12, 14)\)
Pattern: \(F = D\) — the function equals 1 exactly when the least significant bit \(D = 1\) (all odd minterms).
Challenge 2: Expand a Complex Expression to Canonical SOP
Expand the following expression into canonical sum-of-minterms form for variables \(A\), \(B\), \(C\), \(D\):
Show Answer
Expansion of each term:
\(A\overline{C}\): A=1, C=0, B and D free → \(m(8, 9, 12, 13)\)
\(\overline{B}\,D\): B=0, D=1, A and C free → \(m(1, 3, 9, 11)\)
\(\overline{A}\,BC\): A=0, B=1, C=1, D free → \(m(6, 7)\)
Union: \(F = \sum m(1, 3, 6, 7, 8, 9, 11, 12, 13)\)
Challenge 3: Shannon Decomposition Application
Given the function \(F(A, B, C, D) = \sum m(0, 1, 4, 5, 6, 7, 14, 15)\), apply Shannon decomposition about variable \(A\) to express \(F\) in the form:
where \(F_0 = F|_{A=0}\) and \(F_1 = F|_{A=1}\). Give both cofactors as simplified expressions.
Show Answer
Cofactor \(F_0 = F|_{A=0}\):
Minterms with A=0: \(m(0, 1, 4, 5, 6, 7)\) → as 3-variable function of B, C, D: \(m_3(0, 1, 4, 5, 6, 7)\)
Simplified: \(F_0 = \overline{B} + C\)
Cofactor \(F_1 = F|_{A=1}\):
Minterms with A=1: \(m(14, 15)\) → as 3-variable function: indices 6, 7 → \(m_3(6, 7)\)
Simplified: \(F_1 = BC\)
Final decomposition: \(F = \overline{A}(\overline{B} + C) + A \cdot BC\)
Challenge 4: POS-to-SOP Conversion via Complement
A function is given in POS form:
Find \(\overline{F}\) in SOP form, then use it to derive \(F\) in SOP form.
Show Answer
The maxterms present: \((A + B + C) = M_0\), \((A + \overline{B} + C) = M_2\), \((\overline{A} + B + \overline{C}) = M_5\)
So \(F = \prod M(0, 2, 5)\)
\(\overline{F} = \sum m(0, 2, 5) = \overline{A}\,\overline{B}\,\overline{C} + \overline{A}\,B\,\overline{C} + A\overline{B}\,C\)
\(F = \sum m(1, 3, 4, 6, 7)\)
Simplified SOP: \(F = \overline{A}\,C + A\overline{C} + AB\)
Challenge 5: Find the Function from a Minterm/Maxterm List Pair
A function of three variables satisfies both of these conditions simultaneously:
- \(F(A, B, C) + G(A, B, C) = \sum m(0, 1, 2, 3, 5, 6, 7)\) (the OR of \(F\) and \(G\))
- \(F(A, B, C) \cdot G(A, B, C) = \sum m(1, 5, 7)\) (the AND of \(F\) and \(G\))
If \(F = \sum m(1, 3, 5, 7)\), find \(G\) as a minterm list and simplified expression.
Show Answer
Since \(F \cdot G = \sum m(1, 5, 7)\), \(G\) must include minterms {1, 5, 7}.
Since \(F + G = \sum m(0, 1, 2, 3, 5, 6, 7)\), every minterm in this set must be in \(F\) or \(G\) (or both).
\(F = \{1, 3, 5, 7\}\). Minterms in \(F + G\) but not in \(F\): {0, 2, 6} — these must be in \(G\).
\(G\) cannot include minterm 3 (it's in \(F\), so \(F \cdot G\) would include 3 — but \(F \cdot G\) does NOT include 3). Minterm 4 is not in \(F + G\), so \(G\) cannot include 4.
\(G = \sum m(0, 1, 2, 5, 6, 7)\)
Simplified: \(G = \overline{B}\,\overline{C} + \overline{A}\,\overline{B} + AB + BC\)
Challenge 6: Canonical Form of XOR
Express the 3-variable XOR function $F = A \oplus B \oplus C$ in both canonical SOP and canonical POS forms. What pattern do you notice about the minterm indices?
Show Answer
\(A \oplus B \oplus C = 1\) when an odd number of variables are 1.
Minterms with odd number of 1s: 001(1), 010(2), 100(4), 111(7)
SOP: \(F = \Sigma m(1,2,4,7)\)
POS: \(F = \Pi M(0,3,5,6)\)
Pattern: The minterm indices are exactly those with an odd number of 1-bits in their binary representation (odd parity). The maxterm indices have an even number of 1-bits. This is the parity function.
Challenge 7: Don't Cares and Dual Implementations
A BCD digit detector outputs 1 for valid BCD digits (0–9). Express this function as $F(A,B,C,D) = \Sigma m(?) + d(?)$, where the don't cares correspond to invalid BCD codes. Find both the minimum SOP and minimum POS using don't cares.
Show Answer
Valid BCD: 0000–1001 (0–9). Invalid: 1010–1111 (10–15).
\(F = \Sigma m(0,1,2,3,4,5,6,7,8,9) + d(10,11,12,13,14,15)\)
With don't cares set to 1: all 16 minterms are covered → \(F = 1\). But that's trivial.
Actually, the function that detects invalid BCD is more interesting: \(G = \Sigma m(10,11,12,13,14,15)\) (no don't cares).
Minimum SOP for valid BCD detector: \(F = \overline{A} + \overline{B}\,\overline{C} + \overline{B}\,\overline{D}\)
Minimum POS: \(F = (\overline{A} + \overline{B})(\overline{A} + \overline{C} + \overline{D})\)
Challenge 8: Shannon Expansion Application
Given $F(A,B,C,D) = \Sigma m(0,1,4,5,6,11,14,15)$, use Shannon expansion around variable $A$ to decompose $F$ into cofactors $F_A$ and $F_{\overline{A}}$. Express each cofactor as a minterm list over $\{B,C,D\}$.
Show Answer
Split minterms by A's value (A is the MSB in ABCD):
A=0 (minterms 0–7): {0,1,4,5,6} → \(F_{\overline{A}}(B,C,D) = \Sigma m(0,1,4,5,6)\)
A=1 (minterms 8–15, subtract 8): {11−8,14−8,15−8} = {3,6,7} → \(F_A(B,C,D) = \Sigma m(3,6,7)\)
\(F_{\overline{A}} = \overline{B}\,\overline{D} + \overline{B}\,\overline{C} + B\,C\,\overline{D}\) (simplified)
\(F_A = B\,C + \overline{B}\,C\,D = C(B + \overline{B}D) = C(B+D)\) (simplified)