奎因-麦克拉斯基算法

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

方法涉及两步：

1. 找到这个函数的所有素蕴涵项。
2. 使用这些素蕴涵项（prime implicant）来找到这个函数的本质量蕴涵项（essential prime implicant），对覆盖这个函数是必须的其他素蕴涵项也同样要使用。

复杂度

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

例子

最小化一个任意的函数：

${\displaystyle f(A,B,C,D)=\sum m(4,8,10,11,12,15)+d(9,14).\,}$

	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

你能轻易的形成这个表的规范的积之和表达式，简单的通过总和这个函数求值为一的那些极小项(除掉那些不关心项)：

${\displaystyle f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'CD'+AB'CD+ABC'D'+ABCD\,}$

第一步找到素蕴涵项

当然，这的确不是最小化的。为了优化，所有求值为一的极小项都首先放到极小项表中，不关心项也可以加入这个表中与极小项组合：

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	-

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

${\displaystyle f_{A,B,C,D}=BC'D'+AB'+AC\,}$

${\displaystyle f_{A,B,C,D}=BC'D'+AD'+AC\,}$

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

${\displaystyle f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+ABCD'+ABCD\,}$

参见

• 逻辑综合
• 布尔代数
• 规范形式 (布尔代数)
• 威拉德·冯·奥曼·蒯因
• 图灵归约
• 交互式证明系统
• 随机预言机

外部链接

• 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 （页面存档备份，存于互联网档案馆）