[科普中国]-奎因-麦克拉斯基算法

奎因－麦克拉斯基算法（Quine-McCluskey算法）是最小化布尔函数的一种方法。

简介它在功能上等同于卡诺图，但是它具有文字表格的形式，因此它更适合用于电子设计自动化算法的实现，并且它还给出了检查布尔函数是否达到了最小化形式的确定性方法。

方法涉及两步：

找到这个函数的所有素蕴涵项。

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

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

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

|| ||

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

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

|| ||

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

|| ||

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

|| ||

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

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

本词条内容贡献者为:

杨明 - 副教授 - 西南大学