Quine–McCluskey algorithm

The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for <a href="/facts/Minimization_of_Boolean_functions/7wSV4nut">minimization</a> of <a href="/facts/Boolean_function/uT7E8pqC">Boolean functions</a> that was developed by <a href="/facts/Willard_Van_Orman_Quine/2RrhATxa">Willard V. Quine</a> in 1952 and extended by <a href="/facts/Edward_J._McCluskey/5L7gmj3u">Edward J. McCluskey</a> in 1956. As a general principle this approach had already been demonstrated by the logician <a href="/facts/Hugh_McColl_(mathematician)/Jq7rtxfr">Hugh McColl</a> in 1878, was proved by <a href="/facts/Archie_Blake_(mathematician)/mWbn52zY">Archie Blake</a> 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 <a href="/facts/Albert_A._Mullin/aFkIWQ3B">Albert A. Mullin</a> and Wayne G. Kellner proposed a decimal variant of the method.
The Quine–McCluskey algorithm is functionally identical to <a href="/facts/Karnaugh_mapping/saFd8oNl">Karnaugh mapping</a>, 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 F has been reached. It is sometimes referred to as the tabulation method.
The Quine-McCluskey algorithm works as follows:

<ol><li>Finding all <a href="/facts/Implicant/88HUgzm9">prime implicants</a> of the function.</li>
<li>Use those prime implicants in a prime implicant chart to find the essential prime implicants of the function, as well as other prime implicants that are necessary to cover the function.</li></ol>

Quine–McCluskey algorithm open-in-new

Quine–McCluskey algorithm