QuineMcCluskeyAlgorithmus

Quine–McCluskey algorithm is a systematic method for minimizing Boolean functions. Named after Willard Van Orman Quine and Merrill McCluskey, it provides an exact minimization of a logic expression in sum-of-products form. The algorithm treats the function as a set of minterms (and optionally don't-care terms) and seeks a smallest set of implicants that covers all minterms.

The procedure first expresses each minterm as a binary vector of length n, where n is the number of variables. Minterms are grouped by the number of 1s and then paired with adjacent groups to produce generalised terms that differ in only one variable. When a pair is combined, the differing bit is replaced by a dash, indicating a “don’t care” in that position. This combining step is repeated iteratively until no further combinations are possible; the terms produced in the final stage are the prime implicants.

To obtain a minimal expression, a prime implicant chart is constructed to show which prime implicants cover which minterms. Essential prime implicants are those that cover a minterm not covered by any other implicant; these are always included in the final result. Remaining minterms are then covered using a minimal subset of non-essential prime implicants. The method can incorporate don't-care terms to reduce the final expression, allowing more combinations than would be possible with the on-set alone.

The Quine–McCluskey algorithm is exact and complete, but its worst-case complexity grows exponentially with the number of variables, making it practical mainly for functions with a moderate number of inputs. It is widely used in digital logic design and serves as a foundation for related minimization techniques and software tools.