Quine–McCluskey algorithm
The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a general principle this approach had already been demonstrated by the logician Hugh McColl in 1878, was proved by Archie Blake in 1937, and was rediscovered by Edward W. Samson and Burton E. Mills in 1954 and by Raymond J. Nelson in 1955. Also in 1955, Paul W. Abrahams and John G. Nordahl as well as Albert  A. Mullin and Wayne G. Kellner proposed a decimal variant of the method. The Quine–McCluskey algorithm is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean function has been reached. It is sometimes referred to as the tabulation method. The method involves two steps: Complexity. Although more practical than Karnaugh mapping when dealing with more than four variables, the Quine–McCluskey algorithm also has a limited range of use since the problem it solves  is NP-complete. The running time of the Quine–McCluskey algorithm grows exponentially with the number of variables. For a function of "n" variables the number of prime implicants can be as large as formula_1 , e.g. for 32 variables there may be over 534 × 10 prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal heuristic methods, of which the Espresso heuristic logic minimizer was the de facto standard in 1995. Step two of the algorithm amounts to solving the set cover problem; NP-hard instances of this problem may occur in  this algorithm step. Example. Input. In this example, the input is a Boolean function in four variables, formula_2 which evaluates to formula_3 on the values formula_4 and formula_5, evaluates to an unknown value on formula_6 and formula_7, and to formula_8 everywhere else (where these integers are interpreted in their binary form for input to formula_9 for succinctness of notation). The inputs that evaluate to formula_3 are called 'minterms'. We encode all of this information by writing This expression says that the output function f will be 1 for the minterms formula_4 and formula_5 (denoted by the 'm' term) and that  we don't care about the output for formula_6 and formula_7 combinations (denoted by the 'd' term). Step 1: finding prime implicants. First, we write the function as a table (where 'x' stands for don't care): One can easily form the canonical sum of products expression from this table, simply by summing the minterms (leaving out don't-care terms) where the function evaluates to one: which is not minimal. So to optimize, all minterms that evaluate to one are first placed in a minterm table. Don't-care terms are also added into this table (names in parentheses), so they  can be combined with minterms: At this point, one can start combining minterms with other minterms. If two terms differ by only a single digit, that digit can be replaced with a dash indicating that the digit doesn't matter. Terms that can't be combined any more are marked with an asterisk (*). For instance codice_1 and codice_2 can be combined to give codice_3, indicating that both minterms imply the first digit is codice_4 and the next two are codice_5. When going from Size 2 to Size 4, treat codice_6 as a third bit value. Match up the codice_6's  first. The terms represent products and to combine two product terms they must have the same variables. One of the variables should be complemented in one term and uncomplemented in the other. The remaining variables present should agree. So to match two terms the codice_6's must align and all but one of the other digits must be the same. For instance, codice_9 and codice_10 can be combined to give codice_11, as can codice_9 and codice_13 to give codice_14, but codice_9 and codice_16 cannot since the codice_6's do not align. codice_9 corresponds to BCD' while codice_16 corresponds to  A'BC, and BCD' + A'BC is not equivalent to a product term. Note: In this example, none of the terms in the size 4 implicants table can be combined any further. In general this process should be continued (sizes 8, 16 etc.) until no more terms can be combined. Step 2: prime implicant chart. None of the terms can be combined any further than this, so at this point we construct an essential prime implicant table. Along the side goes the prime implicants that have just been generated, and along the top go the minterms specified earlier. The don't  care terms are not placed on top—they are omitted from this section because they are not necessary inputs. To find the essential prime implicants, we run along the top row. We have to look for columns with only one "✓". If a column has only one "✓", this means that the minterm can only be covered by one prime implicant. This prime implicant is "essential". For example: in the first column, with minterm 4, there is only one "✓". This means that m(4,12) is essential. So we place a star next to it. Minterm 15 also has only one  ✓, so m(10,11,14,15) is also essential. Now all columns with one "✓" are covered. The second prime implicant can be 'covered' by the third and fourth, and the third prime implicant can be 'covered' by the second and first, and neither is thus essential. If a prime implicant is essential then, as would be expected, it is necessary to include it in the minimized boolean equation. In some cases, the essential prime implicants do not cover all minterms, in which case additional procedures for chart reduction can be employed. The simplest "additional procedure" is trial and error, but a more  systematic way is Petrick's method. In the current example, the essential prime implicants do not handle all of the minterms, so, in this case, the essential implicants can be combined with one of the two non-essential ones to yield one equation: or Both of those final equations are functionally equivalent to the original, verbose equation: