Exercise DET-04.02 – Quine–McCluskey algorithm

Prof. Dr. Thorsten Jungmann (last updated 2026-10-25)

Relates to DET-04 Algorithmic minimization of functions with many inputs and hazard analysis

Task

The Quine–McCluskey algorithm minimizes a function by table: part 1 finds all prime implicants, and part 2 selects the fewest of them with the prime implicant chart. Minimize each function with the algorithm. In each function, the first variable has the highest weight.

a) $F_1(A,B,C)=\sum m(0,1,2,3,7)$

b) $F_2(A,B,C,D)=\sum m(0,1,2,3,5,7,13,15)$

c) $F_3(A,B,C,D)=\sum m(0,1,2,8,9)+d(5,10,14)$, where $d$ names the don’t cares

Solution

a) prime implicants $\overline{A}$ and $B\cdot C$, both essential; $F_1=\overline{A}+B\cdot C$
b) prime implicants $\overline{A}\cdot \overline{B}$, $\overline{A}\cdot D$ and $B\cdot D$; essential: $\overline{A}\cdot \overline{B}$ and $B\cdot D$; $F_2=\overline{A}\cdot \overline{B}+B\cdot D$
c) prime implicants $\overline{B}\cdot \overline{C}$, $\overline{B}\cdot \overline{D}$, $\overline{A}\cdot \overline{C}\cdot D$ and $A\cdot C\cdot \overline{D}$, the last one only of don’t cares; essential: $\overline{B}\cdot \overline{C}$ and $\overline{B}\cdot \overline{D}$; $F_3=\overline{B}\cdot \overline{C}+\overline{B}\cdot \overline{D}$

▶️ Full worked solution