Quine-McCluskey算法

维基百科，自由的百科全书

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

方法涉及两步:

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

目录 1 复杂性 2 例子 3 参见 4 外部链接

[编辑] 复杂性

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

[编辑] 例子

最小化一个任意的函数:

f(A, B, C, D) = Σ(4, 8, 9, 10, 11, 12, 14, 15)

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

你能轻易的形成这个表的规范的积之和表达式，简单的通过总和这个函数求值为一的那些极小项:

f_A,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD

当然，这的确不是最小化的。为了优化，所有求值为一的极小项都首先放到极小项表中:

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

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

1的数目       极小项    0-立方   | 大小为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     |----------------------
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	9	10	11	12	14	15
m(4,12)*	X					X
m(8,9,10,11)*		X	X	X	X
m(8,10,12,14)		X		X		X	X
m(10,11,14,15)*				X	X		X	X

这里的每个本质素蕴涵项都标记了星号。如果一个一个素蕴涵项是本质的，则同希望的一样，它必须包含在最小化的布尔等式中。在这种情况下，这些 EPI(本质素蕴涵项)含盖了所有的极小项，所以组合后的极小项被总结为等式:

f_A,B,C,D = BC'D' + AB' + AC

最终的等式函数上等价于最初的(冗长)等式:

f_A,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD

[编辑] 参见

• 布尔代数
• 规范形式 (布尔代数)
• 威拉德·冯·奥曼·蒯因

[编辑] 外部链接

• [1]
• [2]
• Python 实现: [3]