简介

方法

复杂性

实例(第一步找到素蕴涵项 第二步找到本质素蕴涵项)

简介

Quine-McCluskey 算法是最小化布尔函数的一种方法。它在功能上等同于卡诺图，但是它的表格形式使它更有效的用做计算机算法，并且它还给出了检查布尔函数是否达到了最小化形式的确定性方法。

方法

涉及两步：

找到这个函数的所有素蕴涵项（也叫质蕴涵项）。

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

复杂性

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

实例

最小化一个任意的函数：

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　m4　0100

m8　1000

2　m9　1001

m10　1010

m12　1100

3　m11　1011

m14　1110

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

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

2　m9　1001　m(8,12) 1-00　m(10,11,14,15) 1-1-*

m10　1010　--　--

m12　1100　m(9,11) 10-1　--

--　--　--　m(10,11) 101-　--

3　m11　1011　m(10,14) 1-10　--

m14　1110　m(12,14) 11-0　--

4　m15　1111　m(11,15) 1-11　--

　　m(14,15) 111-　

第二步找到本质素蕴涵项

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

　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方法。在当前这个例子中，本质素蕴涵项不能处理所有的极小项，你可以组合这两个本质素蕴涵项于两个非素蕴涵项中的一个而生成：