ic
Section 8.3 Minimization
673
Quine–McCluskey Procedure
Remember that the key to reducing the canonical sum-of-products form for a truth
function lies in recognizing terms of the sum that differ in only one factor. In the
Karnaugh map, we see where such terms occur. A second method of reduction,
the Quine–McCluskey procedure, organizes information from the canonical sumof-products form into a table to simplify the search for terms differing by only
one factor.
The procedure is a two-step process paralleling the use of the Karnaugh map.
First we find groupings of terms (just as we looped together marked squares in
the Karnaugh map); then we eliminate redundant groupings and make choices for
terms that can belong to several groups.
ExamplE 29
Let’s illustrate the Quine–McCluskey procedure by using the truth function for
Example 23. We did not write the actual truth function there, but the information
is contained in the Karnaugh map. The truth function is shown in Table 8.13. The
eight 4-tuples of 0s and 1s producing a function value of 1 are listed in Table 8.14,
which is separated into four groupings according to the number of 1s. Note that
terms of the canonical sum-of-products form differing by only one factor must be
in adjacent groupings, which simplifies the search for such terms.
TablE 8.13
x 1
x 2
x 3
x 4 f( x 1 , x 2 , x 3 , x 4 )
1
1
1
1
0
1
1
1
0
0
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
1
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
1
1
1
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
0
0
0
1
1
1
0
0
1
0
1
0
0
0
1
1
0
0
0
0
1
TablE 8.14
Number of 1s
x 1
x 2
x 3
x 4
Three
1
0
1
1
Two
0
1
1
0
0
1
0
1
0
0
1
1
One
1
0
0
0
0
0
1
0
0
0
0
1
None
0
0
0
0