奎因-麥克拉斯基表法

---

---

本章將討論使用也稱為**奎因-麥克拉斯基方法**的表格方法化簡布林表示式。

奎因-麥克拉斯基方法在化簡超過六個變數的布林函式方面更有優勢。這種化簡技術克服了卡諾圖在處理超過六個變數時的問題。

奎因-麥克拉斯基方法的另一個主要優點是它同樣適用於手工計算和機器計算，因為它可以程式設計。

奎因-麥克拉斯基方法理論

奎因-麥克拉斯基方法是一種系統地化簡複雜布林表示式的技術。對於大量變數的布林表示式化簡，它成為了一種合適的方法。它也稱為表格方法。

這種最小化技術基於對所有相鄰項對重複使用組合定理（即，$\mathrm{XA \: + \: X\bar{A} \: = \: X}$，其中X是一組文字）。此過程給出了一組所有質蘊含項，從中我們可以選擇一個最小和。

奎因-麥克拉斯基方法步驟

下面解釋了使用奎因-麥克拉斯基方法化簡布林函式的分步過程：

**步驟1** - 列出給定布林表示式的所有最小項。

**步驟2** - 對最小項分組。在此步驟中，我們根據最小項二進位制形式中1的個數對所有最小項進行排列。例如，將所有沒有1的最小項放在一起，所有隻有一個1的最小項放在一起，依此類推。最小項中1的個數稱為最小項的指標。將這些分組的最小項寫在表的第1列中。

**步驟3** - 合併最小項。在此步驟中，將最低指標組的每個最小項與後續組中的每個最小項進行比較。只要可能，將相鄰組中僅相差一位的兩個最小項合併，並將不同的位替換為破折號（-）。這表示無關項。此外，在已與至少一個最小項合併的每個最小項前面放置一個勾號（✓）。重複此過程，直到完成所有可能的最小項組合。將所有組合的最小項寫在表的第2列中。

**步驟4** - 以相同的方式比較和合並上述步驟中生成的最小項。在此步驟中，我們將合併僅相差一位且破折號位於相同位置的兩個最小項。我們不能合併破折號位於不同位置的兩個最小項。

將新生成的項寫在第3列中，並在已在第2列中合併的每個項旁邊放置一個勾號（✓）。使用第3列、第4列等中的項繼續此過程，直到不再可能進行進一步的組合。最後，未組合的項稱為**質蘊含項**。

**步驟5** - 列出所有質蘊含項並建立質蘊含項表。如果有任何無關項，則它不應出現在質蘊含項表中。

**步驟6** - 選擇基本質蘊含項，即覆蓋至少一個不被任何其他質蘊含項覆蓋的最小項的質蘊含項。

**步驟7** - 合併基本質蘊含項以獲得最終簡化的表示式。

與奎因-麥克拉斯基方法相關的術語

在布林表示式最小化奎因-麥克拉斯基方法中，使用多個術語來傳達資訊。下面定義了與奎因-麥克拉斯基方法相關的一些關鍵術語：

**最小項** - 最小項是布林變數的組合，其中真值用1表示，假值用0表示。

**最大項** - 最大項是布林變數的組合，其中真值用0表示，假值用1表示。

**指標** - 最小項中1的個數稱為其指標。

**質蘊含項** - 不能與任何其他最小項組合的最小項稱為質蘊含項。

**基本質蘊含項** - 覆蓋至少一個不被任何其他質蘊含項覆蓋的最小項的質蘊含項稱為基本質蘊含項。

**質蘊含項表** - 顯示布林表示式質蘊含項和最小項之間關係的圖形表示稱為質蘊含項表。

**無關項** - 無關項是可以忽略的位或變數，用於函式的最小化。在奎因-麥克拉斯基方法中，它用破折號（-）表示。

這些是一些使用奎因-麥克拉斯基方法的基本重要術語。

現在讓我們透過一個例子來了解奎因-麥克拉斯基方法在化簡布林函式中的應用。

基於奎因-麥克拉斯基方法的示例

使用奎因-麥克拉斯基技術化簡以下布林函式。

$$\mathrm{f(A, B,C,D) \: = \: \sum \: m(0,1,5,7,10,14)}$$

解答

下面解釋了使用奎因-麥克拉斯基方法化簡給定布林函式的過程。

**步驟1** - 按1的個數升序對給定的最小項分組，並將它們的二進位制形式寫在第1列中。

**步驟2** - 比較和合並第1列的最小項。

我們可以看到，在兩個相鄰組之間，第2列中沒有項可以與任何其他項合併。因此，它們都是質蘊含項。

**步驟3** - 建立質蘊含項表。

從質蘊含項表中可以看到，最小項m10和m14僅被S覆蓋。因此，S是基本質蘊含項。還可以觀察到，函式的其餘最小項被P和R的最小質蘊含項集覆蓋。

因此，最小表示式將是：

$$\mathrm{f_{min} \: = \: P \: + \: R \: + \: S \: = \: (000 \: − \: ) \: + \: (01 \: − \: 1) \: + \:(1 \: − \: 10)}$$

$$\mathrm{\Rightarrow f_{min} \: = \: \overline{ABC} \: + \: \overline{A}BD \: + \: AC\overline{D}}$$

這是給定布林函式的最小布爾表示式，可以使用與門、或門和非門實現。

奎因-麥克拉斯基方法的優點

奎因-麥克拉斯基方法比其他最小化技術（如卡諾圖）具有 several advantages。奎因-麥克拉斯基方法的一些主要優點如下：

• 奎因-麥克拉斯基方法提供了一個系統的最小化過程，以找到複雜布林表示式的最小版本。
• 它可以應用於具有大量變數的布林函式，而卡諾圖技術在這種情況下變得不切實際。
• 它適用於手工計算和計算機計算。
• 奎因-麥克拉斯基方法基於系統的演算法，有助於減少人為錯誤。
• 它也可以應用於具有“無關項”（don't care conditions）的布林函式，即不完整的布林函式。

奎因-麥克拉斯基方法的缺點

然而，奎因-麥克拉斯基方法是一種強大的簡化技術，用於最小化布林函式，比其他最小化技術具有 several advantages。

但是，它也有一些缺點，其中一些列在下面：

• 奎因-麥克拉斯基方法的主要缺點是計算複雜度。這是因為我們必須檢查所有可能的最小項組合。
• 雖然對於大量變數，奎因-麥克拉斯基方法比卡諾圖更好，但對於非常大量的變數（通常超過7個變數），它也變得不切實際。
• 奎因-麥克拉斯基方法涉及大量的 manual computation，這使得它既繁瑣又容易出錯。
• 奎因-麥克拉斯基方法對於某些型別的布林函式效率不高。
• 由於奎因-麥克拉斯基方法採用演算法方法而不是圖形方法進行最小化，這使得它不那麼直觀。

奎因-麥克拉斯基方法的應用

奎因-麥克拉斯基方法是布林代數中最有效的最小化技術之一。它提供了一種系統的方法來最小化具有大量變數的複雜布林函式。奎因-麥克拉斯基方法的一些主要應用如下：

• 奎因-麥克拉斯基方法用於設計和最佳化數位電路和系統。它有助於減少數位電路中使用的邏輯閘數量。
• 它也用於計算機程式設計中最佳化條件邏輯，以提高效率和速度。
• 在數字訊號處理中，奎因-麥克拉斯基方法用於簡化布林表示式，以開發高效的處理演算法。
• 奎因-麥克拉斯基方法用於設計高效的狀態機。

結論

總之，奎因-麥克拉斯基方法是一種系統且演算法化的簡化複雜布林表示式的方法。對於具有大量變數的布林函式，它是一種有效的最小化技術。

奎因-麥克拉斯基方法的最大優點是它支援手工計算和機器計算，即它是可程式設計的。然而，這種方法涉及相對複雜的計算，這使得它很繁瑣。