查看“︁奎因-麦克拉斯基算法”︁的源代码

{{NoteTA
|G1 = IT
|G2 = Math
}}
'''奎因－麦克拉斯基算法'''（'''Quine-McCluskey算法'''）是最小化[[布尔函数]]的一种方法。它在功能上等同于[[卡诺图]]，但是它具有文字表格的形式，因此它更适合用于[[电子设计自动化]][[算法]]的实现，并且它还给出了检查布尔函数是否达到了最小化形式的确定性方法。

方法涉及两步：
#找到这个函数的所有[[蕴涵项|素蕴涵项]]。
#使用这些素蕴涵项（prime implicant）来找到这个函数的本质素蕴涵项（essential prime implicant），对覆盖这个函数是必须的其他素蕴涵项也同样要使用。

== 复杂度 ==
尽管在处理多于四个变量的时候比卡诺图更加实用，奎因－麦克拉斯基算法也有使用限制，因为它解决的问题是[[NP-困难]]的：奎因－麦克拉斯基算法的[[运行时间]]随输入大小而呈[[指數函數|指数]]增长。可以证明对于''n''个变量的函数，素蕴涵项的数目的上界是3<sup>''n''</sup>/''n''。如果''n'' = 32，则可能超过6.1 * 10<sup>14</sup>，或617万亿个素蕴涵项。有大量变量的函数必须使用潜在的非最优的[[启发式]]方法来最小化。

== 例子 ==
最小化一个任意的函数：
:<math>f(A,B,C,D) =\sum m(4,8,10,11,12,15) + d(9,14).  \,</math>

{| 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
|}
你能轻易的形成这个表的规范的[[积之和]]表达式，简单的通过总和这个函数求值为一的那些[[极小项]](除掉那些[[不關心項]])：

:<math>f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD \,</math>

=== 第一步找到素蕴涵项 ===
当然，这的确不是最小化的。为了优化，所有求值为一的极小项都首先放到极小项表中，不關心項也可以加入這個表中與極小項組合：

{| class="wikitable"
|-
! 1的数目 !! 极小项 !! 二进制表示
|-
| rowspan="2" | 1 
| m4 || 0100
|-
| m8 || 1000
|-
| rowspan="3" | 2 
| m9 || 1001
|-
| m10 || 1010
|-
| m12 || 1100
|-
| rowspan="2" | 3
| m11 || 1011
|-
| m14 || 1110
|-
| rowspan="1" | 4
| m15 || 1111
|}

现在你可以开始把极小项同其他极小项组合在一起。如果两个项只有一个二进制位的数值不同，则可以这个位的数值可以替代为一个横杠，来指示这个数字无关紧要。不再组合的项标记上 "*"。

{| class="wikitable"
|-
! 1的数目 !! 极小项 !! 二进制表示 !! 大小为2的蕴涵项 !! 大小为4的蕴涵项
|-
| rowspan="4" | 1
| m4 || 0100 || m(4,12)  -100* || m(8,9,10,11) 10--*
|-
| m8 || 1000 || m(8,9) 100- || m(8,10,12,14)  1--0*
|-
| -- || -- || m(8,10)  10-0 || --
|-
| -- || -- || m(8,12)  1-00 || --
|-
| rowspan="4" | 2
| m9 || 1001
 || m(9,11)  10-1 || m(10,11,14,15)  1-1-*
|-
| m10 || 1010 || m(10,11)  101- || --
|-
| -- || -- || m(10,14)  1-10 || --
|-
| m12 || 1100 || m(12,14)  11-0 || --
|-
| rowspan="2" | 3
| m11 || 1011 || m(11,15)  1-11 || --
|-
| m14 || 1110 || m(14,15)  111- || --
|-
| rowspan="1" | 4
| m15 || 1111 || -- || --
|}

=== 第二步找到本质素蕴涵项 ===
没有项可以继续进一步这样组合，所以现在我们构造一个本质素蕴涵项表。纵向是刚才生成的素蕴涵项，横向是早先指定的极小项。

{| class="wikitable"
|                 || 4 || 8 || 10 || 11 || 12 || 15 ||      || => || A || B || C || D
|-
| m(4,12)*        || X ||   ||    ||    || X  ||    || -100 || => || - || 1 || 0 || 0
|-
| m(8,9,10,11)    ||   || X || X  || X  ||    ||    || 10-- || => || 1 || 0 || - || -
|-
| m(8,10,12,14)   ||   || X || X  ||    || X  ||    || 1--0 || => || 1 || - || - || 0
|-
| m(10,11,14,15)* ||   ||   || X  || X  ||    || X  || 1-1- || => || 1 || - || 1 || -
|} 

这里的每个'''本质'''素蕴涵项都标记了星号 - 第二个素蕴涵项能被第三个和第四个所覆盖，而第三个素蕴涵能被第二个和第一个所覆盖，因此都不是本质的。如果一个素蕴涵项是本质的，则同希望的一样，它必须包含在最小化的布尔等式中。在某些情况下，本质素蕴涵形不能覆盖所有的极小项，此时可采用额外的简约过程。最简单的“额外过程”是反复试验，而更系统的方式是{{le|Petrick方法|Petrick's_method}}。在当前这个例子中，本质素蕴涵项不能处理所有的极小项，你可以组合这两个本质素蕴涵项與两个非素蕴涵项中的一个而生成：
:<math>f_{A,B,C,D} = BC'D' + AB' + AC \, </math>
:<math>f_{A,B,C,D} = BC'D' + AD' + AC \, </math>

最终的等式在功能上等价于最初的（冗长）等式：

<math>f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD \,</math>

== 参见 ==
* [[逻辑综合]]
* [[布尔代数]]
* [[规范形式 (布尔代数)]]
* [[威拉德·冯·奥曼·蒯因]]
* [[图灵归约]]
* [[交互式证明系统]]
* [[隨機預言機]]

== 外部链接 ==

*[https://web.archive.org/web/20080117073434/http://www.omnistream.co.uk/qm/ Web-Based Quine-McCluskey Algorithm]，an open source implementation written in PHP.（[http://www.phpclasses.org/quine_mccluskey PHP Class]）
*[https://web.archive.org/web/20080207022238/http://user.cs.tu-berlin.de/~lordmaik/projects/quinemccluskey/quinemccluskey/quineapplet.htm Java-Applet] Applet to minimize a boolean function based on QuineMcCluskey Algorithm. (German page)
* [http://www.inf.ufrgs.br/logics/ Karma 3] {{Wayback|url=http://www.inf.ufrgs.br/logics/ |date=20210109073843 }}, A set of logic synthesis tools including Karnaugh maps, Quine-McCluskey minimization, BDDs, probabilities, teaching module and more. Logic Circuits Synthesis Labs (LogiCS) - UFRGS, Brazil.
* [http://134.193.15.25/vu/course/cs281/lectures/simplification/quine-McCluskey.html Lecture on the Quine–McCluskey algorithm]{{Wayback|url=http://134.193.15.25/vu/course/cs281/lectures/simplification/quine-McCluskey.html |date=20070512195526 }}
* A. Costa [http://www.dei.isep.ipp.pt/~acc/bfunc/ BFunc] {{Wayback|url=http://www.dei.isep.ipp.pt/~acc/bfunc/ |date=20120712042144 }}，QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)
* [https://web.archive.org/web/20080130134530/http://www25.brinkster.com/denshade/QuineMcCluskey.html Java applet] to display all the generated primes.
* [[Python]] [http://cheeseshop.python.org/pypi/qm/0.1 Implementation] {{Wayback|url=http://cheeseshop.python.org/pypi/qm/0.1 |date=20071113151455 }}
* [http://sourceforge.net/projects/quinessence/ Quinessence] {{Wayback|url=http://sourceforge.net/projects/quinessence/ |date=20210108120732 }}，an open source implementation written in Free Pascal.
* [[Literate programming|A literate program]] written in Java [http://en.literateprograms.org/Quine-McCluskey_algorithm_%28Java%29 implementing the Quine-McCluskey algorithm] {{Wayback|url=http://en.literateprograms.org/Quine-McCluskey_algorithm_%28Java%29 |date=20190919110445 }}。
* [http://automatics.hit.bg/#minBool minBool]{{Wayback|url=http://automatics.hit.bg/#minBool |date=20090529082620 }} a [[Matlab]] implementation.
* [https://web.archive.org/web/20071216072432/http://cran.r-project.org/src/contrib/Descriptions/QCA.html QCA] an open source, R based implementation used in the social sciences, by Adrian Duşa
* A series of two articles describing the algorithm(s) implemented in R: [https://web.archive.org/web/20070823084159/http://www.compasss.org/Dusa2007.pdf first article] and [http://www.compasss.org/Dusa2007a.pdf second article]{{dead link|date=2017年12月 |bot=InternetArchiveBot |fix-attempted=yes }}。
* The R implementation is exhaustive and it offers complete and exact solutions. It processes up to 20 input variables.
* [https://web.archive.org/web/20091026213335/http://geocities.com/abeautifulmind1998/ a Java program to display the boolean expresssion ..... by Manoranjan Sahu]
* [http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/qmc/embed_qmc.html an applet for a step by step analyze of the QMC- algorithm by Christian Roth] {{Wayback|url=http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/qmc/embed_qmc.html |date=20210108013102 }}
* [http://sourceforge.net/projects/qmcs SourceForge.net C++ program implementing the algorithm.] {{Wayback|url=http://sourceforge.net/projects/qmcs |date=20210110024420 }}
* [http://search.cpan.org/~kulp/Algorithm-QuineMcCluskey-0.01/lib/Algorithm/QuineMcCluskey.pm Perl Module] {{Wayback|url=http://search.cpan.org/~kulp/Algorithm-QuineMcCluskey-0.01/lib/Algorithm/QuineMcCluskey.pm |date=20180520234231 }}

[[Category:布尔代数]]
[[Category:算法]]