**Quine-McCluskey algorithm** is a method used for minimisation of

boolean functions. It is functionally identical to Karnaugh mapping, however the tabular form makes it more convenient for computers, and it also gives a deterministic way to check that the minimal form of a boolean function has been reached

The method involves two steps:

- Finding all prime implicants of the function.
- Using those prime implicants to find the essential prime implicants of the function, as well as using other prime implicants that are necessary to cover the function.

Here's an example minimizing an arbitrary function:''A'' ''B'' ''C'' ''f''(''A'', ''B'', ''C'')
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

All minterms are first placed in a minterm table:Number of 1s Minterm Binary Representation
--------------------------------------------
1 m1 001
m2 010
m4 100
--------------------------------------------
2 m3 011
--------------------------------------------
3 m7 111

At this point, one can start combining minterms with other minterms,Number of 1s Minterm 0-Cube | Size 2 Implicants
------------------------------|-----------------------------
1 m1 001 | m(1,3) 0-1
m2 010 | m(2,3) 01-
m4 100 |-----------------------------
------------------------------| m(3,7) -11
2 m3 011 |
------------------------------|
3 m7 111 |

None of the terms can be combined any futher than this, so at this point we constuct an essential prime implicant table.

| 1 | 2 | 3 | 4 | 7 |

m(4)* | | | | X | |

m(1,3)* | X | | X | | |

m(2,3)* | | X | X | | |

m(3,7)* | | | X | | X |

Because all of the above are essential prime implicants, one can then simply convert it into an equation. Thus, the minimal AND-OR equation of the truth table given earlier is

$f\_\{A,B,C\}\; =\; A\text{'}C\; +\; A\text{'}B\; +\; BC\; +\; AB\text{'}C\text{'}$.

## See also

## External links

- http://134.193.15.25/vu/course/cs281/lectures/simplification/quine-McCluskey.html