The practical use of algebraic manipulation, Venn diagrams or Karnaugh
maps for minimization of Boolean expressions is limited to problems with
a few variables. The *Quine-McKluskey procedure* for minimization
can be implemented as a computer algorithm and is applicable to expressions
with any number of variables.

**Example**: Given the boolean expression

F(p,q,r,s,t)=m(0,1,3, 4,6,11,14,15,16,18,24,27,28,31)

minimize using the Quine-McKluskey procedure. In this example
there are 5 variables *p, q, r, s* and *t* which give us 32 possible
minterms (0 - 31).

__Step 1__: Separate the minterms into groups based on the number
of 1's in their binary representations.

__Step 2__: Compare neighboring groups and replace pairs of terms
that have exactly one bit different. These terms are said to be *adjacent*.
We can replace any two adjacent terms with a single term that contains
a dash at the location of the unmatched bit. Be sure to mark the
minterms that are used to create common terms so that they can be removed
from the list.

__Step 3__: Repeat the search until no new adjacent terms are found.
Two terms that already contain dashes are considered to be adjacent only
if all dash positions match and all but one literal position contains the
same value.

__Step 4__: Remove duplicates and list all unique surviving terms.
Indicate which of the original minterms are *covered* by the surviving
terms. These are called the *implicants *since they imply the
existence of minterms in the original expression.

More than one minterm is covered by each implicant and some minterms
are covered by more than one implicant. We need to find the smallest
number of implicants that cover all minterms. These will be called
*the
prime implicants*.

__Step 5__: Notice that the prime implicants VI, IX, X and XI shown
above are the only ones that cover minterms 18, 14, 28 and 31 respectively.
These implicants must be included in our selected list. They are
called *essential* prime implicants.

__Step 6__: Next we must select the minimum number of remaining implicants
so as to cover all minterms. This is not an easy problem, in general.
Can you find a better (i.e. smaller) set of prime implicants that cover
all the minterms in this example?

__Step 7__: Finally we use the selected set of prime implicants to
generate a simplified Boolean expression.

**Homework**: Use the Quine-McKluskey procedure to find a minimal
representation of the following Boolean expression:

F(w,x,y,z) = m(0,1,2,5,6,9,11,14,15)

*Use of this material for educational purposes only is governed by*
*the definition of Fair Use (Section
107) of the U.S. Copyright Act.*
*Course material is the property of R. A. Pilgrim*
*All Rights Reserved*