Worked examples — Quine-McCluskey method

Before we start, one reminder of the only rule that does any work here (from Boolean Algebra Laws):

The scenario matrix

Every QM problem you can be handed falls into one of these case classes. Each row is a "cell" we must cover with at least one worked example.

Example 1 — Case C1 (standard, EPIs finish)

Forecast: Guess how many terms survive. (Hint: minterms 0,2,4,6 are all even → $C=0$. Smell a big group.)

1. Group by number of 1s. $\{0=000\}\mid \{2=010,4=100\}\mid \{5=101,6=110\}$. Why this step? Grouping by 1-count means a Hamming-distance-1 neighbour must sit in the adjacent group — it limits comparisons and blocks illegal 2-bit merges automatically.

2. Combine adjacent groups (size-2).

   • $0,2\to 0\text{-}0$ ✓✓
   • $0,4\to \text{-}00$ ✓✓
   • $2,6\to \text{-}10$ ✓✓
   • $4,5\to 10\text{-}$ ✓✓
   • $4,6\to 1\text{-}0$ ✓✓

   Why this step? Each pair differs in one bit, so one variable cancels via $X+\bar{X}$.

3. Combine again (size-4). Terms with a dash in the same position and differing in one bit:

   • $0,2,4,6$: from $0\text{-}0$ and $1\text{-}0$ (both dash at $B$) → $\text{-}\text{-}0=\bar{C}$. Why this step? $\bar{C}$ covers all four even minterms in one shot — that's the big group we forecast.

4. List primes (never-ticked terms). After step 3, only $4,5\to 10\text{-}=A\bar{B}$ was never absorbed into a quad. So: $P{I}_1=\bar{C}(0,2,4,6),P{I}_2=A\bar{B}(4,5).$

5. PI chart → EPIs.

   • $m5$ is covered only by $A\bar{B}$ → EPI.
   • $m0,m2,m6$ are covered only by $\bar{C}$ → EPI.

   Both are essential, so: $\boxed{f=\bar{C}+A\bar{B}}$

Verify: $\bar{C}$ covers $\{0,2,4,6\}$, $A\bar{B}$ covers $\{4,5\}$; union $=\{0,2,4,5,6\}$ = every requested minterm. ✔ Two terms, three literals — nothing smaller possible.

Example 2 — Case C2 (cyclic chart, no EPIs)

Forecast: This is the famous cyclic function. Guess whether any single PI is essential. (It won't be — every minterm has two suitors.)

1. Group by 1s. $\{1=001,2=010,4=100\}\mid \{3=011,5=101,6=110\}$.

2. Combine (size-2).

   • $1,3\to 0\text{-}1=\bar{A}C$
   • $1,5\to \text{-}01=\bar{B}C$
   • $2,3\to 01\text{-}=\bar{A}B$
   • $2,6\to \text{-}10=B\bar{C}$
   • $4,5\to 10\text{-}=A\bar{B}$
   • $4,6\to 1\text{-}0=A\bar{C}$

   Why this step? Each is a valid Hamming-1 merge. No size-4 combine is possible (no two share a dash position and differ in one bit), so all six are prime implicants.

3. Build the PI chart and scan columns for essentials.

Why this step? Look at the chart: every column has exactly two ✗ marks. No minterm is covered by a lone PI → no essential prime implicants. The chart is cyclic: this is the case the parent note never showed.

4. Choose a minimal cover (Petrick idea). Because nothing is forced, we hunt for the smallest subset covering all 6. Notice the six PIs form a ring; picking alternating ones works. Take: $f=\bar{A}C+B\bar{C}+A\bar{B}.$ Coverage: $\bar{A}C\to \{1,3\}$, $B\bar{C}\to \{2,6\}$, $A\bar{B}\to \{4,5\}$ → all six. The other alternating triple $\{\bar{A}B,A\bar{C},\bar{B}C\}$ is equally minimal — this function has two minimal SOPs. Why this step? With no EPIs you must decide; Petrick's method formalises finding the smallest such subset.

Verify: $\{1,3\}\cup \{2,6\}\cup \{4,5\}=\{1,2,3,4,5,6\}$. ✔ Three terms, six literals; two literals per term is the floor here, so minimal. ✔

Example 3 — Case C3 (EPIs first, then a leftover choice)

Forecast: Guess: will the whole thing collapse into two clean 4-groups, or leave a stray?

1. Group by 1s. $\{0\}\mid \{1,4\}\mid \{5,10\}\mid \{11,14\}\mid \{15\}$ where $0=0000,1=0001,4=0100,5=0101,10=1010,11=1011,14=1110,15=1111$.

2. Combine (size-2).

   • $0,1\to 000\text{-}$; $0,4\to 0\text{-}00$; $1,5\to 0\text{-}01$; $4,5\to 010\text{-}$
   • $10,11\to 101\text{-}$; $10,14\to 1\text{-}10$; $11,15\to 1\text{-}11$; $14,15\to 111\text{-}$

3. Combine (size-4).

   • $0,1,4,5\to 0\text{-}0\text{-}=\bar{A}\bar{C}$
   • $10,11,14,15\to 1\text{-}1\text{-}=AC$ Why this step? These are the two clean quads. Every original minterm got absorbed, so these two are the only primes.

4. PI chart.

   • $\bar{A}\bar{C}$ covers $\{0,1,4,5\}$; $AC$ covers $\{10,11,14,15\}$.
   • $m0$ is covered only by $\bar{A}\bar{C}$ → EPI. $m10$ only by $AC$ → EPI. Both essential; together they cover all 8. No leftover after all — the two EPIs finish it.

$\boxed{f=\bar{A}\bar{C}+AC}$

Verify: $\bar{A}\bar{C}\to \{0,1,4,5\}$, $AC\to \{10,11,14,15\}$; union = all 8 minterms. ✔ (This is the XNOR of $A$ and $C$: $f=\overline{A\oplus C}$ — a nice sanity link to Logic Gate Minimization.)

Example 4 — Case C4 (don't-cares)

Forecast: Don't-cares are free 1s to combine with, but you never have to cover them. Guess: can we grab a single term covering all of $\{1,3,7,11,15\}$?

1. Bring don't-cares into the grouping. Treat $0,2,5$ as available 1s: $\{0\}\mid \{1,2\}\mid \{3,5\}\mid \{7,11\}\mid \{15\}$. Why this step? Including $d$ while combining can grow bigger PIs — that's their only benefit.

2. Key merges. The required minterms $1,3,7,11,15$ all have $D=1$. And $0,1,2,3$ (with help of don't-cares $0,2$) form $00\text{-}\text{-}=\bar{A}\bar{B}$; then bring $3,7\to 0\text{-}11$, $7,15\to \text{-}111$, $11,15\to 1\text{-}11$, $3,11\to \text{-}011$. Chasing the $D=1$ family:

   • $1,3,5,7\to 0\text{-}\text{-}1=\bar{A}D$ (uses $d5$)
   • $3,7,11,15\to \text{-}\text{-}11=CD$
   • $1,3,9,11$… no $9$, skip.

3. Prime implicants that cover the required set. $PI:\bar{A}D(1,3,5,7),CD(3,7,11,15).$ Together: $\bar{A}D$ covers $\{1,3,7\}$ (required) $+5$ (don't-care, ignored). $CD$ covers $\{3,7,11,15\}$. Why this step? $m11$ and $m15$ are only reachable via $CD$; $m1$ only via $\bar{A}D$ → both EPIs.

$\boxed{f=\bar{A}D+CD}$

Verify: Required minterms only. $\bar{A}D\to \{1,3,7\}$, $CD\to \{3,7,11,15\}$; union $\supseteq \{1,3,7,11,15\}$. ✔ Don't-cares $0,2$ were never covered (both give $f=0$ here) and that's perfectly legal. ✔

Example 5 — Case C5 (degenerate: function is always 1)

Forecast: All four rows of a 2-variable truth table are 1. Guess the answer before doing any tabulation.

1. Group & combine. $\{0=00\}\mid \{1=01,2=10\}\mid \{3=11\}$.
   • $0,1\to 0\text{-}$; $0,2\to \text{-}0$; $1,3\to \text{-}1$; $2,3\to 1\text{-}$.
2. Combine again. $0,1,2,3\to \text{-}\text{-}$ — both positions dashed. Why this step? A term with every variable cancelled means "no variable matters" — the constant $1$.

$\boxed{f=1}$

Verify: $\text{-}\text{-}$ decodes to the empty product = $1$. Output is 1 for all $2^2=4$ inputs, matching $\sum m(0,1,2,3)$. ✔ This is the limiting case: full minterm set ⇒ tautology.

Example 6 — Case C6 (degenerate: function is always 0)

Forecast: No minterm is 1. What's there even to combine?

1. List minterms. There are none. The grouping table is empty. Why this step? QM combines 1-rows; with zero of them, step 1 produces nothing.
2. Result. $\boxed{f=0}$

Verify: An empty SOP (sum of no terms) is $0$ by definition, and the truth table is all-0. ✔ The mirror image of Example 5.

Example 7 — Case C7 (real-world word problem)

Forecast: Guess: does "emergency pressed" ever let the motor run in more than one situation?

1. Translate English → conditions. $f=1$ when:

   • $\bar{A}\bar{B}\bar{C}$ (door closed, no overload, no emergency) → $ABC=000\Rightarrow m0$.
   • $A\bar{B}C$ (door open, no overload, emergency pressed) → $101\Rightarrow m5$. All other rows: motor off. Why this step? You must convert the sentence into a truth table before QM can touch it — QM has no idea what "elevator" means.

2. Minterm list: $f=\sum m(0,5)$.

3. Group & combine. $\{0=000\}\mid \{5=101\}$. Groups differ by two bits ($0000$ vs $0101$: bits $A$ and $C$ both change) → cannot combine. Why this step? Hamming distance is 2, so no variable cancels. Both minterms are already prime.

4. Decode.

   • $m0=000=\bar{A}\bar{B}\bar{C}$.
   • $m5=101=A\bar{B}C$.

$\boxed{f=\bar{A}\bar{B}\bar{C}+A\bar{B}C}$

Verify (in English + logic): Both terms contain $\bar{B}$ — motor never runs on overload, as required. First term = all-safe idle-close; second = the emergency-open creep. No other input pattern gives 1. Only 2 terms because the two run-conditions differ in 2 variables and refuse to merge. ✔

Example 8 — Case C8 (exam twist: 5 vars + decode trap)

Forecast: Four minterms, all with $C=D=0$. Guess how big the group gets.

1. Binary (order $ABCDE$, 5 bits). $0=00000,1=00001,16=10000,17=10001$.

2. Group by 1s. $\{0\}\mid \{1,16\}\mid \{17\}$.

3. Combine (size-2).

   • $0,1\to 0000\text{-}$; $0,16\to \text{-}0000$; $1,17\to \text{-}0001$; $16,17\to 1000\text{-}$.

4. Combine (size-4). Same-dash-position + one-bit-difference:

   • $0,1,16,17\to \text{-}000\text{-}$. Why this step? Two variables ($A$ and $E$) cancel simultaneously — the group spans all four.

5. Decode -000- (order $ABCDE$). Dash at $A$ (drop), $B=0,C=0,D=0$, dash at $E$ (drop): $\text{-}000\text{-}\Rightarrow \bar{B}\bar{C}\bar{D}.$ Why this step (the trap): a rushed reader might write $\bar{A}\bar{B}\bar{C}$ by reading the first three bits. No — the dashed columns ($A$ and $E$) are the ones that disappear; the surviving literals come from the fixed $0$s in $B,C,D$.

$\boxed{f=\bar{B}\bar{C}\bar{D}}$

Verify: $\bar{B}\bar{C}\bar{D}$ = "1 whenever $B=C=D=0$, regardless of $A,E$" → $A,E\in \{0,1\}$ each → $2\times 2=4$ input rows → minterms $00000,00001,10000,10001=\{0,1,16,17\}$. ✔ Exactly our set, one term, three literals — collapsed from four minterms.

Recap of the matrix

Connections

• Quine-McCluskey method — the parent algorithm these examples exercise.
• Prime Implicants and Petrick's Method — how to choose when the chart is cyclic (Example 2).
• Karnaugh Maps — the same adjacency, drawn instead of tabulated.
• Sum of Products (SOP) — the output form of every answer above.
• Boolean Algebra Laws — the combining theorem doing all the work.
• Logic Gate Minimization — why fewer literals means cheaper hardware.

Flashcards