Exercise DET-04.02 – Quine–McCluskey algorithm (Solution)

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

◀️ Back to the task

Solution

Given

Given explicitly:

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)$ with the don’t cares 5, 10 and 14
in each function, the first variable has the highest weight

Known:

Uniting theorem: two product terms that differ in only one variable unite into one without this variable (DET-03)
Codes and groups: a 1 for a variable as it is, a 0 for a negated one, a dash for a variable that has dropped out; the group is the number of ones in the code (DET-04)
Part 1: terms of consecutive groups that differ in exactly one position unite, with their dashes in the same positions; both get a tick; the terms without a tick are the prime implicants (DET-04)
Part 2: the prime implicant chart; a column with a single mark belongs to an essential prime implicant (DET-04)
Don’t cares count as ones while uniting and get no column in the chart (DET-04)

Required

a) to c) the prime implicants, the essential prime implicants and the minimal disjunctive normal form (DNF) of $F_{1}$ , $F_{2}$ and $F_{3}$

a) Three inputs

Part 1 writes each minterm as its code and sorts the codes into groups by the number of their ones (DET-04, 2.1). Minterm 0 (000) has no one, minterms 1 (001) and 2 (010) have one, minterm 3 (011) has two and minterm 7 (111) has three. Then the algorithm compares each term with each term of the next group. Two terms that differ in exactly one position unite into a term with a dash there, and both get a tick (DET-04, 2.2). From the top: minterm 0 (000) and minterm 1 (001) differ only in $C$ and unite into 00-; minterm 0 and minterm 2 (010) differ only in $B$ and unite into 0-0. In the same way, minterm 1 unites with minterm 3 into 0-1, minterm 2 with minterm 3 into 01-, and minterm 3 with minterm 7 into -11. Every minterm has found a partner, so all five are ticked:

Group	Minterm	$A$	$B$	$C$	Ticked
0	0	0	0	0	✓
1	1	0	0	1	✓
1	2	0	1	0	✓
2	3	0	1	1	✓
3	7	1	1	1	✓

The second table holds these five pairs. Now two pairs unite only if their dashes stand in the same position and they differ in exactly one other position. 00- (0, 1) and 01- (2, 3) unite into 0‑‑ (0, 1, 2, 3), and 0-0 (0, 2) and 0-1 (1, 3) yield the same term, which is kept only once. The pair -11 (3, 7) has no partner, because no other pair has its dash in the first position, and it remains without a tick:

Group	Minterms	$A$	$B$	$C$	Ticked
0	0, 1	0	0	-	✓
0	0, 2	0	-	0	✓
1	1, 3	0	-	1	✓
1	2, 3	0	1	-	✓
2	3, 7	-	1	1

The third table holds a single term, and part 1 ends:

Group	Minterms	$A$	$B$	$C$	Ticked
0	0, 1, 2, 3	0	-	-

The terms without a tick are the prime implicants: -11 (3, 7), the term $B \cdot C$ , and 0‑‑ (0, 1, 2, 3), the term $\overline{A}$ .

Part 2 enters them in the prime implicant chart, with a column for each minterm of the function (DET-04, 2.3):

Prime implicant	0	1	2	3	7
$\overline{A}$	●	●	●	●
$B \cdot C$				●	●

The columns 0, 1 and 2 have a single mark each, in the row of $\overline{A}$ , and column 7 has a single mark in the row of $B \cdot C$ . Both prime implicants are therefore essential, and together they cover all five minterms:

F_{1} = \overline{A} + B \cdot C

Check with the minterm list: $\overline{A}$ is 1 in rows 0 to 3, $B \cdot C$ in rows 3 and 7; together, these are rows 0, 1, 2, 3 and 7 ✓

b) Four inputs

The eight minterms fall into five groups, from 0 (0000) with no one to 15 (1111) with four:

Group	Minterm	$A$	$B$	$C$	$D$	Ticked
0	0	0	0	0	0	✓
1	1	0	0	0	1	✓
1	2	0	0	1	0	✓
2	3	0	0	1	1	✓
2	5	0	1	0	1	✓
3	7	0	1	1	1	✓
3	13	1	1	0	1	✓
4	15	1	1	1	1	✓

Comparing the terms of consecutive groups yields ten pairs. Every minterm finds at least one partner, so all eight are ticked in the first table. The second table holds the ten pairs:

Group	Minterms	$A$	$B$	$C$	$D$	Ticked
0	0, 1	0	0	0	-	✓
0	0, 2	0	0	-	0	✓
1	1, 3	0	0	-	1	✓
1	1, 5	0	-	0	1	✓
1	2, 3	0	0	1	-	✓
2	3, 7	0	-	1	1	✓
2	5, 7	0	1	-	1	✓
2	5, 13	-	1	0	1	✓
3	7, 15	-	1	1	1	✓
3	13, 15	1	1	-	1	✓

The ten pairs unite into three terms with four minterms each, and all ten pairs are ticked. Each of the three terms arises twice, each time from two pairs: 0‑‑1 (1, 3, 5, 7), for example, from 00-1 (1, 3) and 01-1 (5, 7) and again from 0-01 (1, 5) and 0-11 (3, 7). A term that arises more than once is kept only once:

Group	Minterms	$A$	$B$	$C$	$D$
0	0, 1, 2, 3	0	0	-	-
1	1, 3, 5, 7	0	-	-	1
2	5, 7, 13, 15	-	1	-	1

No two of the three terms have their dashes in the same positions, so none of them can be united any more, and part 1 ends. The prime implicants are the three terms of the third table: $\overline{A} \cdot \overline{B}$ (0, 1, 2, 3), $\overline{A} \cdot D$ (1, 3, 5, 7) and $B \cdot D$ (5, 7, 13, 15).

The prime implicant chart has a column for each of the eight minterms:

Prime implicant	0	1	2	3	5	7	13	15
$\overline{A} \cdot \overline{B}$	●	●	●	●
$B \cdot D$					●	●	●	●
$\overline{A} \cdot D$		●		●	●	●

The columns 0 and 2 have a single mark in the row of $\overline{A} \cdot \overline{B}$ , the columns 13 and 15 in the row of $B \cdot D$ : both are essential. Their rows have marks in all eight columns. The row of $\overline{A} \cdot D$ is not needed: its minterms 1 and 3 lie in $\overline{A} \cdot \overline{B}$ , and 5 and 7 in $B \cdot D$ , so it is a redundant prime implicant (DET-04, 1.2):

F_{2} = \overline{A} \cdot \overline{B} + B \cdot D

Check with the minterm list: $\overline{A} \cdot \overline{B}$ is 1 in rows 0 to 3, $B \cdot D$ in rows 5, 7, 13 and 15; together, these are the eight ones of $F_{2}$ ✓

c) With don’t cares

Don’t cares count as ones while terms are united, so that the united terms become as large as possible (DET-04, 3.2). The first table therefore holds the five minterms of the ones and the three don’t cares 5, 10 and 14:

Group	Minterm	$A$	$B$	$C$	$D$	Ticked
0	0	0	0	0	0	✓
1	1	0	0	0	1	✓
1	2	0	0	1	0	✓
1	8	1	0	0	0	✓
2	5	0	1	0	1	✓
2	9	1	0	0	1	✓
2	10	1	0	1	0	✓
3	14	1	1	1	0	✓

Comparing consecutive groups yields nine pairs:

Group	Minterms	$A$	$B$	$C$	$D$	Ticked
0	0, 1	0	0	0	-	✓
0	0, 2	0	0	-	0	✓
0	0, 8	-	0	0	0	✓
1	1, 5	0	-	0	1
1	1, 9	-	0	0	1	✓
1	2, 10	-	0	1	0	✓
1	8, 9	1	0	0	-	✓
1	8, 10	1	0	-	0	✓
2	10, 14	1	-	1	0

Seven of them unite into two terms with four minterms each; the pairs 0-01 (1, 5) and 1-10 (10, 14) find no partner and remain without a tick:

Group	Minterms	$A$	$B$	$C$	$D$	Ticked
0	0, 1, 8, 9	-	0	0	-
0	0, 2, 8, 10	-	0	-	0

The two terms of the third table have their dashes in different positions, and part 1 ends. Four terms remain without a tick, the prime implicants: $\overline{B} \cdot \overline{C}$ (0, 1, 8, 9), $\overline{B} \cdot \overline{D}$ (0, 2, 8, 10), $\overline{A} \cdot \overline{C} \cdot D$ (1, 5) and $A \cdot C \cdot \overline{D}$ (10, 14).

In the chart, only the ones get a column, because don’t cares need not be covered (DET-04, 3.2). The prime implicant $A \cdot C \cdot \overline{D}$ contains only the don’t cares 10 and 14; it has nothing to cover and gets no row:

Prime implicant	0	1	2	8	9
$\overline{B} \cdot \overline{C}$	●	●		●	●
$\overline{B} \cdot \overline{D}$	●		●	●
$\overline{A} \cdot \overline{C} \cdot D$		●

Column 9 has a single mark in the row of $\overline{B} \cdot \overline{C}$ , column 2 in the row of $\overline{B} \cdot \overline{D}$ : both are essential, and their rows cover all five ones. The row of $\overline{A} \cdot \overline{C} \cdot D$ is not needed, because its only one, minterm 1, lies in $\overline{B} \cdot \overline{C}$ :

F_{3} = \overline{B} \cdot \overline{C} + \overline{B} \cdot \overline{D}

Check with the minterm list: $\overline{B} \cdot \overline{C}$ is 1 in rows 0, 1, 8 and 9, $\overline{B} \cdot \overline{D}$ in rows 0, 2, 8 and 10. Together, they cover the five ones 0, 1, 2, 8 and 9 and, besides, row 10, a don’t care, but no row with a 0 ✓

Wattsinside