Quine-McCluskey algorithm

The Quine-McCluskey algorithm, also known as the method of prime implicants or the tabulation method, is a way of minimizing Boolean functions. Willard V. Quine developed it in 1952 and Edward J. McCluskey extended it in 1956, although the general principle had been shown by Hugh McColl in 1878, proved by Archie Blake in 1937, and rediscovered by Edward W. Samson and Burton E. Mills in 1954 and by Raymond J. Nelson in 1955. It is functionally identical to Karnaugh mapping, but its tabular form suits computer implementation and gives a deterministic way to check that the minimal form of a Boolean function has been reached. It works in two steps: it first finds all prime implicants of the function by repeatedly combining minterms that differ in a single bit, then uses a prime implicant chart to pick out the essential prime implicants and any others needed to cover the function. Because the problem it solves is NP-complete, its running time grows exponentially with the number of variables, so large functions are minimized with heuristic methods such as the Espresso logic minimizer.