Rumination # 4: Quine Mcluskey Method

Greetings grasshoppers. As we all gear up for spring break, I would like to raise awareness about a key issue in our society today, the Quine Mcluskey method for reducing Boolean functions.


• Advantages over K-maps
– Can be computerized
– Can handle functions of more than six variables

• Overview of the method
– Given the minterms of a function
– Find all prime implicants (steps 1 and 2)

• Partition minterms into groups according to the number of 1’s

• Exhaustively search for prime implicants
– Find a minimum prime implicant cover (steps 3 and 4)

• Construct a prime implicant chart

• Select the minimum number of prime implicant


f(A,B,C,D) = m(2,4,6,8,9,10,12,13,15)

http://moodle.ucs.louisiana.edu/file.php/12393/chapter_3SP12.pdf

The Resulting Minimal Realization of f

f(A,B,C,D) = PI1 + PI3 + PI4 + PI7

      = 1-0- + -010 + 01-0 + 11-1

      = AC' + B' CD' + A' BD' + ABD

Covering Procedure

Step 1 -- Identify any minterms covered by only one PI.  

Select these PIs for the cover.

Step 2 -- Remove rows covered by the PIs identified in step 1.  

Remove minterms covered by the removed rows.

Step 3 -- If a cyclic chart results from step 2, go to step 5.  

Otherwise, apply the reduction procedure of steps 1 and 2.

Step 4 -- If a cyclic chart results from step 3, go to step 5.  

Otherwise return to step 1.

Step 5 -- Apply the cyclic chart procedure.  Repeat step 5 

until a void chart or noncyclic chart chart is produced.  In 

the latter case, return to step 1

Using the Q-M Procedure with Incompletely 

Specified Functions

1.  Use minterms and don’t cares when generating 

prime implicants

2.  Use only minterms when finding a minimal cover

Minimizing Circuits with Multiple Outputs

1. To each minterm we must affix a flag to identify

the function in which it appears.

2. Two terms or minterms can be combined only if

they both possess one or more common flags and

the term that results from the combination carries

only flags that are common to both minterms.

3. Each term in the minimizing table cab be checked

off only if all the flags that the term possesses

appear in the term resulting from the combination

So there you have it. Simple as pie. Think about that while staking out the Easter bunny.

All images courtesy of http://moodle.ucs.louisiana.edu/file.php/12393/chapter_3SP12.pdf