奎因-麦克拉斯基算法

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

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

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

 例子 
最小化一个任意的函数：

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

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

 1的数目  极小项  二进制表示 1  m4  0100 m8  1000 2  m9  1001 m10  1010 m12  1100 3 m11  1011 m14  1110 4 m15  1111

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

 1的数目  极小项  二进制表示  大小为2的蕴涵项  大小为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  -- 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  -- 3 m11  1011  m(11,15)  1-11  -- m14  1110  m(14,15)  111-  -- 4 m15  1111  --  --

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

                  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  - 

这里的每个本质素蕴涵项都标记了星号 - 第二个素蕴涵项能被第三个和第四个所覆盖，而第三个素蕴涵能被第二个和第一个所覆盖，因此都不是本质的。如果一个素蕴涵项是本质的，则同希望的一样，它必须包含在最小化的布尔等式中。在某些情况下，本质素蕴涵形不能覆盖所有的极小项，此时可采用额外的简约过程。最简单的“额外过程”是反复试验，而更系统的方式是。在当前这个例子中，本质素蕴涵项不能处理所有的极小项，你可以组合这两个本质素蕴涵项與两个非素蕴涵项中的一个而生成：

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

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

 外部链接 

Web-Based Quine-McCluskey Algorithm，an open source implementation written in PHP.（PHP Class）
Java-Applet Applet to minimize a boolean function based on QuineMcCluskey Algorithm. (German page)
 Karma 3 , 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.
 Lecture on the Quine–McCluskey algorithm
 A. Costa BFunc ，QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)
 Java applet to display all the generated primes.
 Python Implementation 
 Quinessence ，an open source implementation written in Free Pascal.
 A literate program written in Java implementing the Quine-McCluskey algorithm 。
 minBool a Matlab implementation.
 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: first article and second article。
 The R implementation is exhaustive and it offers complete and exact solutions. It processes up to 20 input variables.
 a Java program to display the boolean expresssion ..... by Manoranjan Sahu
 an applet for a step by step analyze of the QMC- algorithm by Christian Roth 
 SourceForge.net C++ program implementing the algorithm. 
 Perl Module 

Category:布尔代数
Category:算法