Editing Quine–McCluskey algorithm (section)

{{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.