Editing Quine–McCluskey algorithm

{{short description|Algorithm for the minimization of Boolean functions}}
{{use dmy dates|date=August 2019|cs1-dates=y}}
{{use list-defined references|date=January 2022}}
[[File:QmcSearchGraph3 Ab+c svg.svg|thumb|400px|[[Hasse diagram]] of the search graph of the algorithm for 3 variables. Given e.g. the subset <math>S = \{abc, a\overline{b}c, \overline{a}bc, \overline{a}b\overline{c}, \overline{a}\overline{b}c \}</math> of the bottom-level nodes (light green), the algorithm computes a minimal set of nodes (here: <math>\{ \overline{a}b, c \}</math>, dark green) that covers exactly <math>S</math>.]]
The '''Quine–McCluskey algorithm''' ('''QMC'''), also known as the '''method of prime implicants''', is a method used for [[Minimization of Boolean functions|minimization]] of [[Boolean function]]s that was developed by [[Willard Van Orman Quine|Willard V. Quine]] in 1952<ref name="Quine_1952"/><ref name="Quine_1955"/> and extended by [[Edward J. McCluskey]] in 1956.<ref name="McCluskey_1956"/> As a general principle this approach had already been demonstrated by the logician [[Hugh McColl (mathematician)|Hugh McColl]] in 1878,<ref name="McColl_1878"/><ref name="Ladd_1883"/><ref name="Brown_2010"/> was proved by [[Archie Blake (mathematician)|Archie Blake]] in 1937,<ref name="Blake_1937"/><ref name="Blake_1932"/><ref name="Blake_1938"/><ref name="Brown_2010"/> and was rediscovered by Edward W. Samson and Burton E. Mills in 1954<ref name="Samson_1954"/><ref name="Brown_2010"/> and by Raymond J. Nelson in 1955.<ref name="Nelson_1955"/><ref name="Brown_2010"/> {{anchor|Decimal tabulation}}Also in 1955, Paul W. Abrahams and John G. Nordahl<ref name="Nordahl_2017"/> as well as [[Albert A. Mullin]] and Wayne G. Kellner<ref name="Mullin_Kellner_1958"/><ref name="Caldwell_1958"/><ref name="Mullin_1959"/><ref name="McCluskey_1960"/> proposed a decimal variant of the method.<ref name="Abrahams_Nordahl_1955"/><ref name="Caldwell_1958"/><ref name="Mullin_1959"/><ref name="McCluskey_1960"/><ref name="Fielder_1966"/><ref name="Kämmerer_1969"/><ref name="Holdsworth_2002"/><ref name="Majumder_2015"/>

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 F has been reached. It is sometimes referred to as the tabulation method.

The Quine-McCluskey algorithm works as follows:
# Finding all [[implicant|prime implicants]] of the function.
# 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.

==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 [[Boolean satisfiability problem|problem]] it solves is [[NP-complete]].<ref name="Masek_1979"/><ref name="Czort_1999"/><ref name="Umans_2006"/> The [[running time]] of the Quine–McCluskey algorithm grows [[exponential growth|exponentially]] with the number of variables. For a function of ''n'' variables the number of prime implicants can be as large as <math>3^n/\sqrt{n}</math> ,<ref name="ChandraMarkowsky_1978"/> e.g. for 32 variables there may be over 534 × 10<sup>12</sup> prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal [[Heuristic algorithm|heuristic]] methods, of which the [[Espresso heuristic logic minimizer]] was the de facto standard in 1995.{{update inline|date=May 2017|reason=The reference correctly describes the situation in 1995. We need to expand this to include the changes of the past twenty years, however.}}<ref name="Nelson_1995"/> For one natural class of functions <math>f</math>, the precise complexity of finding all prime implicants is better-understood: Milan Mossé, Harry Sha, and Li-Yang Tan discovered a near-optimal algorithm for finding all prime implicants of a formula in [[conjunctive normal form]].<ref>{{Cite journal |last1=Mossé |first1=Milan |last2=Sha |first2=Harry |last3=Tan |first3=Li-Yang |date=2022 |title=A Generalization of the Satisfiability Coding Lemma and Its Applications |journal=DROPS-IDN/V2/Document/10.4230/LIPIcs.SAT.2022.9 |series=Leibniz International Proceedings in Informatics (LIPIcs) |volume=236 |pages=9:1–9:18 |language=en |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |doi=10.4230/LIPIcs.SAT.2022.9|doi-access=free |isbn=978-3-95977-242-6 }}</ref>

Step two of the algorithm amounts to solving the [[set cover problem]];<ref name="Feldman_2009"/> [[NP-hard]] instances of this problem may occur in this algorithm step.<ref name="Gimpel_1965"/><ref name="Paul_1974"/>

==Example==
===Input===
In this example, the input is a Boolean function in four variables, <math>f :\{0,1\}^4 \to \{0,1\}</math> which evaluates to <math>1</math> on the values <math>4,8,10,11,12</math> and <math>15</math>, evaluates to an unknown value on <math>9</math> and <math>14</math>, and to <math>0</math> everywhere else (where these integers are interpreted in their binary form for input to <math>f</math> for succinctness of notation). The inputs that evaluate to <math>1</math> are called 'minterms'. We encode all of this information by writing

:<math>f(A,B,C,D) =\sum m(4,8,10,11,12,15) + d(9,14). \,</math>
This expression says that the output function f will be 1 for the minterms <math>4,8,10,11,12</math> and <math>15</math> (denoted by the 'm' term) and that we don't care about the output for <math>9</math> and <math>14</math> combinations (denoted by the 'd' term). The summation symbol <math>\sum</math> denotes the logical sum (logical OR, or disjunction) of all the terms being summed over.

===Step 1: Finding the prime implicants===
First, we write the function as a table (where 'x' stands for don't care):
:{| class="wikitable"
|-
!   !! A !! B !! C !! D !! f
|-
| m0 || 0 || 0 || 0 || 0 || 0
|-
| m1 || 0 || 0 || 0 || 1 || 0
|-
| m2 || 0 || 0 || 1 || 0 || 0
|-
| m3 || 0 || 0 || 1 || 1 || 0
|-
| m4 || 0 || 1 || 0 || 0 || 1
|-
| m5 || 0 || 1 || 0 || 1 || 0
|-
| m6 || 0 || 1 || 1 || 0 || 0
|-
| m7 || 0 || 1 || 1 || 1 || 0
|-
| m8 || 1 || 0 || 0 || 0 || 1
|-
| m9 || 1 || 0 || 0 || 1 || x
|-
| m10 || 1 || 0 || 1 || 0 || 1
|-
| m11 || 1 || 0 || 1 || 1 || 1
|-
| m12 || 1 || 1 || 0 || 0 || 1
|-
| m13 || 1 || 1 || 0 || 1 || 0
|-
| m14 || 1 || 1 || 1 || 0 || x
|-
| m15 || 1 || 1 || 1 || 1 || 1
|}

One can easily form the canonical [[sum of products]] expression from this table, simply by summing the [[minterm]]s (leaving out [[Don't-care (logic)|don't-care terms]]) where the function evaluates to one:

:''f''{{sub|A,B,C,D}} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.

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:

:{| class="wikitable"
|-
! Number<br/>of 1s !! Minterm !! Binary<br/>Representation
|-
| rowspan="2" | 1
| m4 || {{mono|0100}}
|-
| m8 || {{mono|1000}}
|-
| rowspan="3" | 2
| (m9) || {{mono|1001}}
|-
| m10 || {{mono|1010}}
|-
| m12 || {{mono|1100}}
|-
| rowspan="2" | 3
| m11 || {{mono|1011}}
|-
| (m14) || {{mono|1110}}
|-
|| 4
| m15 || {{mono|1111}}
|}

At this point, one can start combining minterms with other minterms in adjacent groups; as in, we compare minterms in nth group with (n+1)th group. So for the m4 minterm in with only one Number of 1s, we compare it to m9, m10, and m12 which have two Number of 1s.

If two terms differ by only a single digit, that digit is replaced with a dash indicating that the digit doesn't matter. For instance <code>1000</code> and <code>1001</code> can be combined to give <code>100-</code>, indicating that both minterms imply the first digit is <code>1</code> and the next two are <code>0</code>. Terms that can't be combined any more are marked with an asterisk ({{color|red|*}}).

:{| class="wikitable"
|-
! Number<br/>of 1s !! Minterm !! 0-Cube !! colspan="2" | Size 2 Implicants 
|-
| rowspan="4" | 1
| m4 || {{mono|0100}} || m(4,12) || {{mono|-100 {{color|red|*}}}}
|-
| m8 || {{mono|1000}} || m(8,9) || {{mono|100-}}
|-
| colspan="2" {{sdash}} || m(8,10) || {{mono|10-0}}
|-
| colspan="2" {{sdash}} || m(8,12) || {{mono|1-00}}
|-
| rowspan="4" | 2
| m9 || {{mono|1001}} || m(9,11) || {{mono|10-1}}
|-
| m10 || {{mono|1010}} || m(10,11) || {{mono|101-}}
|-
| colspan="2" {{sdash}} || m(10,14) || {{mono|1-10}}
|-
| m12 || {{mono|1100}} || m(12,14) || {{mono|11-0}}
|-
| rowspan="2" | 3
| m11 || {{mono|1011}} || m(11,15) || {{mono|1-11}}
|-
| m14 || {{mono|1110}} || m(14,15) || {{mono|111-}}
|-
| rowspan="1" | 4
| m15 || {{mono|1111}} || colspan="2" {{sdash}}
|}

When going from Size 2 to Size 4, treat <code>-</code> as a third bit value. Match up the <code>-</code>'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 <code>-</code>'s must align and all but one of the other digits must be the same. For instance, <code>-110</code> and <code>-100</code> can be combined to give <code>-1-0</code>, as can <code>-110</code> and <code>-010</code> to give <code>--10</code>, but <code>-110</code> and <code>011-</code> cannot since the <code>-</code>'s do not align. <code>-110</code> corresponds to BCD' while 
<code>011-</code> corresponds to A'BC, and BCD' + A'BC is not equivalent to a product term.
:{| class="wikitable"
|-
! Number<br/>of 1s !! Minterm !! 0-Cube !! colspan="2" | Size 2 Implicants !! colspan="2" | Size 4 Implicants
|-
| rowspan="4" | 1
| m4 || {{mono|0100}} || m(4,12) || {{mono|-100 {{color|red|*}}}} ||colspan="2" {{sdash}}
|-
| m8 || {{mono|1000}} || m(8,9) || {{mono|100-}} || m(8,9,10,11) || {{mono|10-- {{color|red|*}}}}
|-
| colspan="2" {{sdash}} || m(8,10) || {{mono|10-0}} || m(8,10,12,14)  || {{mono|1--0 {{color|red|*}}}}
|-
| colspan="2" {{sdash}} || m(8,12) || {{mono|1-00}} ||colspan="2" {{sdash}}
|-
| rowspan="4" | 2
| m9 || {{mono|1001}} || m(9,11) || {{mono|10-1}} ||colspan="2" {{sdash}}
|-
| m10 || {{mono|1010}} || m(10,11) || {{mono|101-}} || m(10,11,14,15) || {{mono|1-1- {{color|red|*}}}}
|-
| colspan="2" {{sdash}} || m(10,14) || {{mono|1-10}} ||colspan="2" {{sdash}}
|-
| m12 || {{mono|1100}} || m(12,14) || {{mono|11-0}} ||colspan="2" {{sdash}}
|-
| rowspan="2" | 3
| m11 || {{mono|1011}} || m(11,15) || {{mono|1-11}} ||colspan="2" {{sdash}}
|-
| m14 || {{mono|1110}} || m(14,15) || {{mono|111-}} ||colspan="2" {{sdash}}
|-
| rowspan="1" | 4
| m15 || {{mono|1111}} || colspan="2" {{sdash}}
| colspan="2" {{sdash}}
|}

Note: In this example, none of the terms in the size 4 implicants table can be combined any further. In general, this process is continued in sizes that are powers of 2 (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 (these are the ones that have been marked with a "{{color|red|*}}" in the previous step), 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.

:{| class="wikitable" style="text-align:center;"
|-
!                             || 4 || 8 || 10 || 11 || 12 || 15 || ⇒ || A || B || C || D
|-
| style="text-align:left;" | m(4,12) {{color|blue|<sup>#</sup>}}        || {{Ya|✓}} || || || || {{Ya|✓}} ||   || ⇒ || {{sdash}} || 1 || 0 || 0
|-
| style="text-align:left;" | m(8,9,10,11)    || || {{Ya|✓}} || {{Ya|✓}} || {{Ya|✓}} || || || ⇒ || 1 || 0 || {{sdash}} || {{sdash}}
|-
| style="text-align:left;" | m(8,10,12,14)   || || {{Ya|✓}} || {{Ya|✓}} || || {{Ya|✓}} || || ⇒ || 1 || {{sdash}} || {{sdash}} || 0
|-
| style="text-align:left;" | m(10,11,14,15) {{color|blue|<sup>#</sup>}} || || || {{Ya|✓}} || {{Ya|✓}} || || {{Ya|✓}} || ⇒ || 1 || {{sdash}} || 1 || {{sdash}}
|}

To find the essential prime implicants, we 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 (hence marked by {{color|blue|<sup>#</sup>}}). Minterm 15 also has only one "✓", so m(10,11,14,15) is also essential. Now all columns with one "✓" are covered. The rows with minterm m(4,12) and m(10,11,14,15) can now be removed, together with all the columns they cover.

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:

:''f''{{sub|A,B,C,D}} = BC'D' + AB' + AC<ref name="Logic_Friday"/>
or
:''f''{{sub|A,B,C,D}} = BC'D' + AD' + AC

Both of those final equations are functionally equivalent to the original, verbose equation:
:''f''{{sub|A,B,C,D}} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.

== Algorithm ==

=== Step 1: Finding the prime implicants ===
The pseudocode below recursively computes the prime implicants given the list of minterms of a boolean function. It does this by trying to merge  all possible minterms and filtering out minterms that have been merged until no more merges of the minterms can be performed and hence, the prime implicants of the function have been found. 
 // Computes the prime implicants from a list of minterms. 
 // each minterm is of the form "1001", "1010", etc and can be represented with a string. 
 '''function''' getPrimeImplicants(list minterms) '''is''' 
     primeImplicants ← empty list
     merges ← new boolean array of length equal to the number of minterms, each set to false
     numberOfmerges ← 0 
     mergedMinterm, minterm1, minterm2 ← empty strings 
 
     '''for''' i = 0 '''to''' length(minterms) '''do'''
         '''for''' c = i + 1 '''to''' length(minterms) '''do'''
             minterm1 ← minterms[i]
             minterm2 ← minterms[c]
             // Checking that two minterms can be merged
             '''if''' CheckDashesAlign(minterm1, minterm2) && CheckMintermDifference(minterm1, minterm2) '''then'''
                 mergedMinterm ← MergeMinterms(minterm1, minterm2) 
                 '''if''' primeImplicants Does Not Contain mergedMinterm then
                     primeImplicants.Add(mergedMinterm) 
                 numberOfMerges ← numberOfMerges + 1
                 merges[i] ← true
                 merges[c] ← true
 
     // Filtering all minterms that have not been merged as they are prime implicants. Also removing duplicates
     '''for''' j = 0 '''to''' length(minterms) '''do'''
         '''if''' merges[j] == false && primeImplicants Does Not Contain minterms[j] '''then'''
             primeImplicants.Add(minterms[j]) 
 
     // if no merges have taken place then all of the prime implicants have been found so return, otherwise 
     // keep merging the minterms. 
     '''if''' numberOfmerges == 0 '''then'''
         '''return''' primeImplicants
     '''else''' 
         '''return''' getPrimeImplicants(primeImplicants)
In this example the <code>CheckDashesAlign</code> and <code>CheckMintermDifference</code> functions perform the necessary checks for determining whether two minterms can be merged. The function <code>MergeMinterms</code> merges the minterms and adds the dashes where necessary. The utility functions below assume that each minterm will be represented using strings.  
 '''function''' MergeMinterms(minterm1, minterm2) '''is'''
     mergedMinterm ← empty string
     '''for''' i = 0 '''to''' length(minterm1) '''do''' 
         //If the bits vary then replace it with a dash, otherwise the bit remains in the merged minterm.
         '''if''' minterm[i] != minterm2[i] '''then'''
             mergedMinterm ← mergedMinterm + '-'
         '''else'''
             mergedMinterm ← mergedMinterm + minterm1[i] 
     '''return''' mergedMinterm
 
 '''function''' CheckDashesAlign(minterm1, minterm2) '''is'''
     '''for''' i = 0 '''to''' length(minterm1) '''do''' 
         // If one minterm has dashes and the other does not then the minterms cannot be merged. 
         '''if''' minterm1[i] != '-' && minterm2[i] == '-' '''then'''
             '''return''' false 
     '''return''' true
 
 '''function''' CheckMintermDifference(minterm1, minterm2) '''is''' 
     // minterm1 and minterm2 are strings representing all of the currently found prime implicants and merged 
     // minterms. Examples include '01--' and '10-0'
     m1, m2 '''←''' integer representation of minterm1 and minterm2 with the dashes removed, these are replaced with 0
     // ^ here is a bitwise XOR
     res ← m1 '''^''' m2
     '''return''' res != 0 && (res & res - 1) == 0

=== Step 2: Prime implicant chart ===
The pseudocode below can be split into two sections: 

# Creating the prime implicant chart using the prime implicants 
# Reading the prime implicant chart to find the essential prime implicants. 

==== Creating the prime implicant chart ====
The prime implicant chart can be represented by a dictionary where each key is a prime implicant and the corrresponding value is an empty string that will store a binary string once this step is complete. Each bit in the binary string is used to represent the ticks within the prime implicant chart. The prime implicant chart can be created using the following steps: 

# Iterate through each key (prime implicant of the dictionary). 
# Replace each dash in the prime implicant with the <code>\d</code> character code. This creates a regular expression that can be checked against each of the minterms, looking for matches. 
# Iterate through each minterm, comparing the regular expression with the binary representation of the minterm, if there is a match append a <code>"1"</code> to the corresponding string in the dictionary. Otherwise append a <code>"0"</code>.
# Repeat for all prime implicants to create the completed prime implicant chart. 

When written in pseudocode, the algorithm described above is: 
 '''function''' CreatePrimeImplicantChart(list primeImplicants, list minterms) 
     primeImplicantChart ← new dictionary with key of type string and value of type string
     // Creating the empty chart with the prime implicants as the key and empty strings as the value. 
     '''for''' i = 0 '''to''' length(primeImplicants) '''do'''
         // Adding a new prime implicant to the chart. 
         primeImplicantChart.Add(primeImplicants[i], "")
     
     '''for''' i = 0 '''to''' length(primeImplicantChart.Keys) '''do'''
         primeImplicant ← primeImplicantChart.Keys[i]
         // Convert the "-" to "\d" which can be used to find the row of ticks above.
         regularExpression ← ConvertToRegularExpression(primeImplicant)
         '''for''' j = 0 '''to''' length(minterms) '''do'''
             // If there is a match between the regular expression and the minterm than append a 1 otherwise 0. 
             '''if''' regularExpression.matches(minterms[j]) '''then'''
                 primeImplicantChart[primeImplicant] += "1"
             '''else''' 
                 primeImplicantChart[primeImplicant] += "0"
 
     // The prime implicant chart is complete so return the completed chart. 
     '''return''' primeImplicantChart
The utility function, <code>ConvertToRegularExpression</code>, is used to convert the prime implicant into the regular expression to check for matches between the implicant and the minterms. 
 '''function''' ConvertToRegularExpression(string primeImplicant)
     regularExpression ← new string 
     '''for''' i = 0 '''to''' length(primeImplicant) '''do'''
         '''if''' primeImplicant[i] == "-" '''then'''
             // Add the literal character "\d". 
             regularExpression += @"\d"
         '''else'''
             regularExpression += primeImplicant[i]
     '''return''' regularExpression

==== Finding the essential prime implicants ====
Using the function, <code>CreatePrimeImplicantChart</code>, defined above, we can find the essential prime implicants by simply iterating column by column of the values in the dictionary, and where a single <code>"1"</code> is found then an essential prime implicant has been found. This process is described by the pseudocode below.  
 '''function''' getEssentialPrimeImplicants(Dictionary primeImplicantChart, list minterms)
     essentialPrimeImplicants ← new list 
     mintermCoverages ← list with all of the values in the dictionary 
     '''for''' i = 0 '''to''' length(ticks) '''do'''
         mintermCoverage ← ticks[i] 
         '''for''' j = 0 '''to''' length(mintermCoverage) '''do'''
             '''if''' mintermCoverage[j] == "1" '''then'''
                 essentialPrimeImplicants.Add(primeImplicantChart.Keys[i])
 
     '''return''' essentialPrimeImplicants
Using the algorithm above it is now possible to find the minimised boolean expression, by converting the essential prime implicants into the canonical form ie. <code>-100 -> BC'D'</code> and separating the implicants by [[Logical disjunction|logical OR]]. The pseudocode assumes that the essential prime implicants will cover the entire boolean expression.

==See also==
* [[Blake canonical form]]
* [[Buchberger's algorithm]] &ndash; analogous algorithm for algebraic geometry
* [[Petrick's method]]
* [[Qualitative comparative analysis]] (QCA)

==References==
{{reflist|refs=
<ref name="Quine_1952">{{cite journal |last=Quine |first=Willard Van Orman |author-link=Willard Van Orman Quine |date=October 1952 |title=The Problem of Simplifying Truth Functions |jstor=2308219 |journal=[[The American Mathematical Monthly]] |volume=59 |issue=8 |pages=521–531 |doi=10.2307/2308219}}</ref>
<ref name="Quine_1955">{{cite journal |last=Quine |first=Willard Van Orman |author-link=Willard Van Orman Quine |date=November 1955 |title=A Way to Simplify Truth Functions |jstor=2307285 |journal=[[The American Mathematical Monthly]] |volume=62 |issue=9 |pages=627–631 |doi=10.2307/2307285 |hdl=10338.dmlcz/142789}}</ref>
<ref name="McCluskey_1956">{{cite journal |last=McCluskey |first=Edward Joseph Jr.|author-link=Edward Joseph McCluskey, Jr. |date=November 1956 |title=Minimization of Boolean Functions |journal=[[Bell System Technical Journal]] |volume=35 |issue=6 |pages=1417–1444 |doi=10.1002/j.1538-7305.1956.tb03835.x |url=https://archive.org/details/bstj35-6-1417 |access-date=2014-08-24 |hdl=10338.dmlcz/102933}}</ref>
<ref name="Nelson_1995">{{cite book |last1=Nelson |first1=Victor P. |first2=H. Troy |last2=Nagle |first3=Bill D. |last3=Carroll |first4=J. David |last4=Irwin |author-link4=J. David Irwin |date=1995 |title=Digital Logic Circuit Analysis and Design |url=https://books.google.com/books?id=8V5TAAAAMAAJ |publisher=[[Prentice Hall]] |page=234 |edition=2 |access-date=2014-08-26 |isbn=978-0-13463894-2}}</ref>
<ref name="Logic_Friday">[[Logic Friday]] program</ref>
<ref name="Masek_1979">{{cite book |first=William J. |last=Masek |title=Some NP-complete set covering problems |publisher=unpublished |date=1979}}</ref>
<ref name="Czort_1999">{{cite thesis |type=Master's thesis |first=Sebastian Lukas Arne |last=Czort |title=The complexity of minimizing disjunctive normal form formulas |institution=University of Aarhus |date=1999}}</ref>
<ref name="Umans_2006">{{cite journal |first1=Christopher |last1=Umans |author-link1=Christopher Umans |first2=Tiziano |last2=Villa |first3=Alberto Luigi |last3=Sangiovanni-Vincentelli |author-link3=Alberto Luigi Sangiovanni-Vincentelli |title=Complexity of two-level logic minimization |journal=[[IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems]] |volume=25 |number=7 |pages=1230–1246 |date=2006-06-05 |doi=10.1109/TCAD.2005.855944 |s2cid=10187481}}</ref>
<ref name="Feldman_2009">{{cite journal |first=Vitaly |last=Feldman |title=Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries |journal=[[Journal of Computer and System Sciences]] |volume=75 |pages=13–25 [13–14] |date=2009 |doi=10.1016/j.jcss.2008.07.007|doi-access=free }}</ref>
<ref name="Gimpel_1965">{{cite journal |first=James F. |last=Gimpel |title=A Method for Producing a Boolean Function Having an Arbitrary Prescribed Prime Implicant Table |journal=[[IEEE Transactions on Computers]] |volume=14 |pages=485–488 |date=1965 |doi=10.1109/PGEC.1965.264175}}</ref>
<ref name="Paul_1974">{{cite journal |first=Wolfgang Jakob |last=Paul |author-link=:de:Wolfgang Paul (Informatiker) |title=Boolesche Minimalpolynome und Überdeckungsprobleme |language=de |journal=[[Acta Informatica]] |volume=4 |issue=4 |pages=321–336 |date=1974 |doi=10.1007/BF00289615 |s2cid=35973949}}</ref>
<ref name="Abrahams_Nordahl_1955">{{cite book |first1=Paul William |last1=Abrahams |first2=John "Jack" G. |last2=Nordahl |title=The Modified Quine–McCluskey Reduction Procedure |date=November 1955 |location=Electrical Engineering Department, [[Massachusetts Institute of Technology]], Massachusetts, USA |type=Class memorandum}} (4 pages) (NB. Some sources list the authors as "{{citeref|Caldwell|1958|P. W. Abraham|style=plain}}"<!-- without pending "s", forenames unconfirmed --> and "{{citeref|Kämmerer|1969|I.<!-- rather than J. --> G. Nordahl|style=plain}}", the title is also cited as "{{citeref|Caldwell|1958|Modified McCluskey–Quine Reduction Procedure|style=plain}}".<!-- added "the", swapped order of names -->)<!-- [https://web.archive.org/web/20200815142344/https://www.chessprogramming.org/Paul_W._Abrahams] [https://web.archive.org/web/20200509033309/https://www.informit.com/authors/bio/33d9a1db-dae1-4ec3-bae5-406f84184012][https://web.archive.org/web/20200509034657/https://dl.acm.org/doi/pdf/10.1145/1141880.1380529] --></ref>
<ref name="Nordahl_2017">{{cite web |title=Welcome to the memorial page for John "Jack" G Nordahl June 14, 1933 ~ November 20, 2017 (age 84) |publisher=Jellison Funeral Home and Cremation Services |url=https://www.jellisonfuneralhome.com/obituary/JohnJack-Nordahl |access-date=2020-05-05 |url-status=live |archive-url=https://web.archive.org/web/20200505151004/https://www.jellisonfuneralhome.com/obituary/JohnJack-Nordahl |archive-date=2020-05-05}}</ref>
<ref name="Caldwell_1958">{{cite book |title=Switching Circuits and Logical Design |chapter=5.8. Operations Using Decimal Symbols |first=Samuel Hawks |last=Caldwell |author-link=Samuel Hawks Caldwell |version=5th printing September 1963 |date=1958-12-01 |orig-date=February 1958 |edition=1st |publisher=[[John Wiley & Sons Inc.]] |publication-place=New York, USA |location=Watertown, Massachusetts, USA |isbn=0-47112969-0 |lccn=58-7896 |pages=162–169 |quote-page=166 |quote=[...] It is a pleasure to record that this treatment is based on the work of two students during the period they were studying Switching Circuits at the Massachusetts Institute of Technology. They discussed the method independently and then collaborated in preparing a class memorandum: {{citeref|Abrahams|Nordahl|1955|P. W. Abraham and J. G. Nordahl|style=plain}} [...]}} (xviii+686 pages) (NB. For the first major treatise of the decimal method in this book, it is sometimes misleadingly known as "Caldwell's decimal tabulation".)</ref>
<ref name="Mullin_Kellner_1958">{{cite journal |title=A Residue Test for Boolean Functions |first1=Albert Alkins |last1=Mullin |author-link1=Albert Alkins Mullin |first2=Wayne G. |last2=Kellner |journal=Transactions of the Illinois State Academy of Science |volume=51 |number=3–4 |date=1958<!-- |orig-date=November 1955 According to Caldwell --> |publication-place=Springfield, Illinois, USA |location=University of Illinois, Urbana, USA and Electrical Engineering Department, [[Massachusetts Institute of Technology]], Massachusetts, USA |type=Teaching memorandum |s2cid=125171479 |pages=14–19 |url=https://ilacadofsci.com/wp-content/uploads/2016/03/051-16-print.pdf |access-date=2020-05-05 |url-status=live |archive-url=https://web.archive.org/web/20200505163915/https://ilacadofsci.com/wp-content/uploads/2016/03/051-16-print.pdf |archive-date=2020-05-05}} [https://ilacadofsci.com/archives/9279] (6 pages) (NB. In {{citeref|Caldwell|1958|his book|style=plain}}, Caldwell dates this to November 1955 as a teaching memorandum. Since Mullin dates their work to 1958 in {{citeref|Mullin|1960|another work|style=plain}} and Abrahams/Nordahl's {{citeref|Abrahams|Nordahl|1955|class memorandum|style=plain}} is also dated November 1955, this could be a copy error.)</ref>
<ref name="Mullin_1959">{{cite journal |title=Two Applications of Elementary Number Theory |first=Albert Alkins |last=Mullin |author-link=Albert Alkins Mullin |journal=Transactions of the Illinois State Academy of Science |volume=52 |number=3–4 |date=1960-03-15 |orig-date=1959-09-19 |location=University of Illinois, Urbana, USA |publication-place=Springfield, Illinois, USA |editor-first1=Harvey I. |editor-last1=Fisher |editor-first2=George E. |editor-last2=Ekblaw |editor-first3=F. O. |editor-last3=Green |editor-first4=Reece |editor-last4=Jones |editor-first5=Francis |editor-last5=Kruidenier |editor-first6=John |editor-last6=McGregor |editor-first7=Paul |editor-last7=Silva |editor-first8=Milton |editor-last8=Thompson |pages=102–103 |url=https://ilacadofsci.com/wp-content/uploads/2016/03/052-15-print.pdf |access-date=2020-05-05 |url-status=live |archive-url=https://web.archive.org/web/20200505143916/https://ilacadofsci.com/wp-content/uploads/2016/03/052-15-print.pdf |archive-date=2020-05-05}} [https://ilacadofsci.com/archives/9203][https://archive.org/details/transactionsofil5219unse][https://archive.org/stream/transactionsofil5219unse/transactionsofil5219unse_djvu.txt] (2 pages)</ref>
<ref name="McCluskey_1960">{{cite journal |title=Albert A. Mullin and Wayne G. Kellner. A residue test for Boolean functions. Transactions of the Illinois State Academy of Science, vol. 51 nos. 3 and 4, (1958), pp. 14–19. |type=Review |last=McCluskey |first=Edward Joseph Jr.|author-link=Edward Joseph McCluskey, Jr. |journal=[[The Journal of Symbolic Logic]] |volume=25 |issue=2 |date=June 1960 |doi=10.2307/2964263 |page=185 |jstor=2964263 |s2cid=123530443 |quote-page=185 |quote=[...] The results of this paper are presented in the more readily available {{citeref|Caldwell|1958|book|style=plain}} by S. H. Caldwell [...<!-- XXIII 433 -->]. In this book, the author gives credit to {{citeref|Mullin|Kellner|1958|Mullin and Kellner|style=plain}} for development of the manipulations with the decimal numbers.}} (1 page)</ref>
<ref name="Kämmerer_1969">{{cite book |title=Digitale Automaten – Theorie, Struktur, Technik, Programmieren |language=de |chapter=I.12. Theorie: Minimierung Boolescher Funktionen |first=Wilhelm |last=Kämmerer |author-link=:de:Wilhelm Kämmerer |editor-first1=Hans |editor-last1=Frühauf |editor-link1=:de:Hans Frühauf |editor-first2=Wilhelm |editor-last2=Kämmerer |editor-first3=Kurz |editor-last3=Schröder |editor-first4=Helmut |editor-last4=Winkler |edition=1 |date=May 1969 |publisher=[[Akademie-Verlag GmbH]] |publication-place=Berlin, Germany |location=Jena, Germany |volume=5 |id=License no. 202-100/416/69. Order no. 4666 ES 20 K 3. |series=Elektronisches Rechnen und Regeln |pages=98, 103–104 |url=https://books.google.com/books?id=jkcgAQAAIAAJ&q=P.+W.+Abraham+I.+G.+Nordahl |quote-page=98 |quote=[...] 1955 wurde das Verfahren auf die bequemere dezimale Schreibweise umgestellt ({{citeref|Abrahams|Nordahl|1955|P. W. Abraham und I. G. Nordahl|style=plain}} in [<nowiki/>{{citeref|Caldwell|1958|Caldwell|style=plain}}<nowiki/>]). [...]}} (NB. A second edition 1973 exists as well.<!-- where the relevant quote is located on page 99 rather than 98 -->)</ref>
<ref name="McColl_1878">{{cite journal |first=Hugh |last=McColl |author-link=Hugh McColl (mathematician) |date=1878-11-14 |title=The Calculus of Equivalent Statements (Third Paper) |journal=[[Proceedings of the London Mathematical Society]] |volume=s1-10<!-- or 10? --> |issue=1 |doi=10.1112/plms/s1-10.1.16 |pages=16–28 |url=https://academic.oup.com/plms/article-abstract/s1-10/1/16/1503062|url-access=subscription }}</ref>
<ref name="Blake_1932">{{cite journal |first=Archie |last=Blake |title=Canonical expressions in Boolean algebra |series=Abstracts of Papers |journal=[[Bulletin of the American Mathematical Society]] |date=November 1932 |page=805}}</ref>
<ref name="Blake_1937">{{cite book |last=Blake |first=Archie |date=1938 |orig-date=1937 |title=Canonical Expressions in Boolean Algebra |type=Dissertation |publisher=[[University of Chicago Libraries]] |location=Chicago, Illinois, USA |edition=Lithographed |page=36 |url=https://books.google.com/books?id=gqRYAAAAMAAJ |quote-page=36 |quote=[...] this method was known to [[Charles Sanders Peirce|Peirce]] and his students [...] It is mentioned at several places in Studies in Logic, by members of the [[Johns Hopkins University]], 1883 [...]}} (ii+60 pages)</ref>
<ref name="Blake_1938">{{cite journal |first=Archie |last=Blake |title=Corrections to ''Canonical Expressions in Boolean Algebra'' |journal=[[The Journal of Symbolic Logic]] |issn=0022-4812 |publisher=[[Association for Symbolic Logic]] |volume=3 |issue=2 |date=June 1938 |doi=10.2307/2267595 |jstor=2267595 |url=https://projecteuclid.org/euclid.jsl/1183385465 |pages=112–113|s2cid=5810863 |url-access=subscription }}</ref>
<ref name="Samson_1954">{{cite book |last1=Samson |first1=Edward Walter |last2=Mills |first2=Burton E. |date=April 1954 |title=Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions |publisher=[[Air Force Cambridge Research Center]] |id=Technical Report AFCRC TR 54-21 |location=Bedford, Massachusetts, USA}}</ref>
<ref name="Nelson_1955">{{cite journal |last=Nelson |first=Raymond J. |date=June 1955 |title=Simplest Normal Truth Functions |journal=[[The Journal of Symbolic Logic]] |publisher=[[Association for Symbolic Logic]] |volume=20 |issue=2 |doi=10.2307/2266893 |jstor=2266893 |pages=105–108|s2cid=32920372 }} (4 pages)</ref>
<ref name="Ladd_1883">{{cite book |last=Ladd |first=Christine |author-link=Christine Ladd |date=1883 |chapter=On the algebra of logic |editor-first=Charles Sanders |editor-last=Peirce |editor-link=Charles Sanders Peirce |title=Studies in Logic |location=Boston, USA |publisher=[[Little, Brown & Company]] |pages=17–71 |quote-page=23 |quote=[...] If the reduction [of an expression to simplest form] is not evident, it may be facilitated by taking the negative of the expression, reducing it, and then restoring it to the positive form. [...]}}</ref>
<ref name="Fielder_1966">{{cite journal |title=Classroom Reduction of Boolean Functions |first=Daniel C. |last=Fielder |journal=[[IEEE Transactions on Education]] |publisher=[[IEEE]] |volume=9 |issue=4 |date=December 1966 |issn=0018-9359 |eissn=1557-9638 |doi=10.1109/TE.1966.4321989 |bibcode=1966ITEdu...9..202F |pages=202–205}}</ref>
<ref name="Brown_2010">{{cite journal |title=McColl and Minimization |journal=History and Philosophy of Logic |volume=31 |number=4 |pages=337–348 |publisher=[[Taylor & Francis]] |issn=1464-5149 |date=November 2010 |orig-date=2010-10-27 |doi=10.1080/01445340.2010.517387 |first=Frank Markham |last=Brown<!-- |author-link=Frank Markham Brown --> |s2cid=216590641 |url=https://www.researchgate.net/publication/233139704 |access-date=2020-04-15 |url-status=live |archive-url=https://web.archive.org/web/20200415201838/https://www.researchgate.net/publication/233139704_McColl_and_Minimization |archive-date=2020-04-15}}</ref>
<ref name="Majumder_2015">{{cite conference |title=Investigation on Quine McCluskey Method: A Decimal Manipulation Based Novel Approach for the Minimization of Boolean Function |first1=Alak |last1=Majumder |first2=Barnali |last2=Chowdhury |first3=Abir J. |last3=Mondal |first4=Kunj |last4=Jain |location=Department of Electronics & Communication, Engineering National Institute of Technology, Arunachal Pradesh Yupia, India |date=2015-01-30 |orig-date=2015-01-09 |type=Conference paper |conference=2015 International Conference on Electronic Design, Computer Networks & Automated Verification (EDCAV), Shillong, India  |doi=10.1109/EDCAV.2015.7060531 |pages=18–22 |url=https://www.researchgate.net/publication/301408055 |access-date=2020-05-08 |url-status=live |archive-url=https://web.archive.org/web/20200508200648/https://www.researchgate.net/publication/301408055_Investigation_on_Quine_McCluskey_method_A_decimal_manipulation_based_novel_approach_for_the_minimization_of_Boolean_function
 |archive-date=2020-05-08}} [https://www.researchgate.net/profile/Alak_Majumder2/publication/301408055_Investigation_on_Quine_McCluskey_method_A_decimal_manipulation_based_novel_approach_for_the_minimization_of_Boolean_function/links/5948a1bba6fdcc70635a3706/Investigation-on-Quine-McCluskey-method-A-decimal-manipulation-based-novel-approach-for-the-minimization-of-Boolean-function.pdf] (NB. This work does not cite the prior art on decimal methods.) (5 pages)</ref>
<ref name="Holdsworth_2002">{{cite book |title=Digital Logic Design |chapter=3.17 Decimal approach to Quine–McCluskey simplification of Boolean algebra |first1=Brian |last1=Holdsworth |first2=Clive |last2=Woods |edition=4 |date=2002 |publisher=[[Newnes Books]] / [[Elsevier Science]] |isbn=((0-7506-4588-2))<!-- this ISBN is faulty, but actually printed in the book --> |pages=65–67 |chapter-url=https://books.google.com/books?id=o7enSwSVvgYC&pg=PA65 |url=https://books.google.com/books?id=o7enSwSVvgYC |access-date=2020-04-19}} (519 pages) [https://web.archive.org/web/20200419213939/http://s2.bitdownload.ir/Ebook/Electronics/Holdsworth%20-%20Digital%20Logic%20Design%204e%20HQ%20(Newnes,%202002).pdf]</ref>
<ref name="ChandraMarkowsky_1978">{{cite journal |title=On the number of prime implicants |first1=Ashok K. |last1=Chandra  |first2=George |last2=Markowsky |journal=Discrete Mathematics |volume=24 |number=1 |date=1978 |pages=7–11 |doi=10.1016/0012-365X(78)90168-1 |doi-access=free }}</ref>
}}

== Further reading==
* {{cite book |title=A new approach to the design of switching circuits |author-first=Herbert Allen |author-last=Curtis |chapter=Chapter 2.3. McCluskey's Method |publisher=[[D. van Nostrand Company, Inc.]] |date=1962 |location=Princeton, New Jersey, USA |edition=1 |series=The Bell Laboratories Series |s2cid=57068910 |oclc=1036797958 |isbn=0-44201794-4 |id={{ISBN|978-0-44201794-1}}. ark:/13960/t56d6st0q <!-- |ia=newapproachtodes00curt --> |pages=90–160}} (viii+635 pages) (NB. This book was reprinted by Chin Jih in 1969.)
* {{cite journal |first=Olivier |last=Coudert |title=Two-level logic minimization: an overview |journal=Integration, the VLSI Journal |issn=0167-9260 |volume=17-2 |date=October 1994 |issue=2 |pages=97–140 |doi=10.1016/0167-9260(94)00007-7 |url=https://oliviercoudert.files.wordpress.com/2020/11/int94.pdf |access-date=2020-05-10 |url-status=live |archive-url=https://web.archive.org/web/20200510214647/http://www.ocoudert.com/papers/pdf/int94.pdf |archive-date=2020-05-10}} (47 pages)
* {{cite arXiv |title=Modified Quine-McCluskey Method |first1=Vitthal |last1=Jadhav |first2=Amar |last2=Buchade |date=2012-03-08  |class=cs.OH |eprint=1203.2289}} (4 pages)
* {{cite web |title=All about Quine-McClusky |first=Jack |last=Crenshaw |date=2004-08-19 |website=embedded.com |url=http://www.embedded.com/electronics-blogs/programmer-s-toolbox/4025004/All-about-Quine-McClusky |access-date=2020-05-10 |url-status=live |archive-url=https://web.archive.org/web/20200510215306/https://www.embedded.com/all-about-quine-mcclusky/ |archive-date=2020-05-10}}
* {{cite journal |last1=Tomaszewski |first1=Sebastian P. |last2=Celik |first2=Ilgaz U. |last3=Antoniou |first3=George E. |title=WWW-based Boolean function minimization |journal=[[International Journal of Applied Mathematics and Computer Science]] |volume=13 |issue=4 |date=December 2003 |orig-date=2003-03-05, 2002-04-09 |pages=577–584 |url=http://matwbn.icm.edu.pl/ksiazki/amc/amc13/amc13414.pdf |access-date=2020-05-10 |url-status=live |archive-url=https://web.archive.org/web/20200510214937/http://matwbn.icm.edu.pl/ksiazki/amc/amc13/amc13414.pdf |archive-date=2020-05-10}} [https://www.researchgate.net/publication/228862329_WWW-based_Boolean_function_minimization][https://archive.today/20180115131301/http://matwbn.icm.edu.pl/ksiazki/amc/amc13/amc13414.pdf] (7 pages)
* {{cite journal |first=Adrian |last=Duşa |date=2008-10-01 |orig-date=September 2007<!--|website=www.compasss.org Working Papers --> |title=A mathematical approach to the boolean minimization problem |journal=[[Quality & Quantity]] |volume=44 |pages=99–113 |doi=10.1007/s11135-008-9183-x |s2cid=123042755 |id=Article number: 99 (2010)}} [https://web.archive.org/web/20120313031147/http://www.compasss.org/files/WPfiles/Dusa2007.pdf] (22 pages)
* {{cite web |title=Enhancing Quine-McCluskey |first=Adrian |last=Duşa |location=[[University of Bucharest]] |date=2007 |url=http://www.compasss.org/wpseries/Dusa2007b.pdf |access-date=2020-05-12 |url-status=live |archive-url=https://web.archive.org/web/20200512134710/http://www.compasss.org/wpseries/Dusa2007b.pdf |archive-date=2020-05-12}} (16 pages) (NB.<!-- A series of two articles describing the algorithm(s) implemented in R. The R implementation is exhaustive and it offers complete and exact solutions. It processes up to 20 input variables. --> 

==External links==
* [http://sites.google.com/site/simpogical/download Tutorial] Tutorial on Quine-McCluskey and Petrick's method.
* For a fully worked out example visit: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm

{{DEFAULTSORT:Quine-Mccluskey Algorithm}}
[[Category:Boolean algebra]]
[[Category:Willard Van Orman Quine]]