奎因－麥克拉斯基算法（Quine-McCluskey算法）是最小化布爾函式的一種方法。
基本介紹
- 中文名：奎因-麥克拉斯基算法
- 外文名：Quine-McCluskey算法
簡介,複雜度,例子,第一步找到素蘊涵項,第二步找到本質素蘊涵項,
簡介
方法涉及兩步：
- 找到這個函式的所有素蘊涵項。
- 使用這些素蘊涵項（prime implicant）來找到這個函式的本質素蘊涵項（essential prime implicant），對覆蓋這個函式是必須的其他素蘊涵項也同樣要使用。
複雜度
儘管在處理多於四個變數的時候比卡諾圖更加實用，奎因－麥克拉斯基算法也有使用限制，因為它解決的問題是NP-困難的：奎因－麥克拉斯基算法的運行時間隨輸入大小而呈指數增長。可以證明對於n個變數的函式，素蘊涵項的數目的上界是3/n。如果n= 32，則可能超過6.1 * 10，或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 | - |
這裡的每個本質素蘊涵項都標記了星號 - 第二個素蘊涵項能被第三個和第四個所覆蓋，而第三個素蘊涵能被第二個和第一個所覆蓋，因此都不是本質的。如果一個素蘊涵項是本質的，則同希望的一樣，它必須包含在最小化的布爾等式中。在某些情況下，本質素蘊涵形不能覆蓋所有的極小項，此時可採用額外的簡約過程。最簡單的“額外過程”是反覆試驗，而更系統的方式是Petrick方法。在當前這個例子中，本質素蘊涵項不能處理所有的極小項，你可以組合這兩個本質素蘊涵項與兩個非素蘊涵項中的一個而生成：
最終的等式在功能上等價於最初的（冗長）等式：
