卡諾圖

卡諾圖是邏輯函數的一種圖形表示。

卡諾圖中最小項的排列方案不是唯一的，變數的坐標值0表示相應變數的反變數，1表示相應變數的原變數，變數的取值變化規律按“循環碼”變化。各小方格依變數順序取坐標值，所得二進位數對應的十進位數即相應最小項的下標i。

在五變數卡諾圖中，為了方便省略了符號“m”，直接標出m的下標i 。

歸納起來，卡諾圖在構造上具有以下兩個特點：

☆ n個變數的卡諾圖由個小方格組成，每個小方格代表一個最小項；

☆ 卡諾圖上處在相鄰、相對、相重位置的小方格所代表的最小項為相鄰最小項。

可以從圖形上直觀地找出相鄰最小項。兩個相鄰最小項可以合併為一個與項並消去一個變數。

卡諾圖的構造特點使卡諾圖具有一個重要性質：可以從圖形上直觀地找出相鄰最小項，兩個相鄰最小項可以合併為一個與項並消去一個變數。

邏輯函數未用最小項表示照樣可以化簡。如果F採用與—或表達式，在填入卡諾圖過程中就能把函數展開成最小項。

具有無關項的化簡

無關項又叫任意項，是一種最小項，其值可以取0或1。利用無關項這一特點，可以使函數簡化。

用卡諾圖化簡邏輯函數的步驟

如果表達式為最小項表達式，則可直接填入卡諾圖

如果表達式不是最小項表達式，但是是“與—或表達式”，可將其先化成最小項表達式，再填入卡諾圖。也可直接填入。

合併相鄰的最小項，即根據下述原則畫圈

盡量畫大圈，但每個圈內只能含有個相鄰項。要特別注意對邊相鄰性和四角相鄰性。

圈的個數盡量少。

卡諾圖中所有取值為1的方格均要被圈過，即不能漏下取值為1的最小項。

在新畫的包圍圈中至少要含有1個末被圈過的1方格，否則該包圍圈是多餘的。

寫出化簡后的表達式。每一個圈寫一個最簡與項，規則是，取值始終為1的變數用原變數表示，取值出現過0的變數用反變數表示，將這些變數相與。然後將所有與項進行邏輯加，即得最簡與—或表達式。

在進行化簡時，如果用圖中真值為0的項更方便，可以用他們來處理，方法和真值取1時一樣，只是結果要再做一次求反。

把函數包含的所有最小項，以“1”填入變數卡諾圖對應編號的小格內。

1．給定邏輯函數為標準“與-或”表達式

當邏輯函數為標準“與-或”表達式時，只需在卡諾圖上找出和表達式中最小項對應的小方格填上1，其餘小方格填上0，即可得到該函數的卡諾圖。

2．邏輯函數為一般“與-或”表達式

當邏輯函數為一般“與-或”表達式時，可根據“與”的公共性和“或”的疊加性作出相應卡諾圖。

填寫該函數卡諾圖時，只需在4變數卡諾圖上依次找出和“與項”對應的小方格填上1，便可得到該函數的卡諾圖。

當邏輯函數表達式為其他形式時，可將其變換成上述形式后再作卡諾圖。

為了敘述的方便，通常將卡諾圖上填1的小方格稱為1方格，填0的小方格稱為0方格。0方格有時用空格表示。

卡諾圖的一個重要特徵是：從圖形上直觀、清晰地反映了最小項的相鄰關係。四個小方格組成一個大方格、或組成一行（列）、或處於相鄰兩行（列）的兩端、或處於四角時，所的表的最小項可以合併，合併后可消去兩個變數。八個小方格組成一個大方格、或組成相鄰的兩行（列）、或處於兩個邊行（列）時，所代表的最小項可以合併，合併后可消去三個變數。至此，以3、4變數卡諾圖為例，討論了2，4，8個最小項的合併方法。依此類推，不難得出n個變數卡諾圖中最小項的合併規律。

歸納起來，n個變數卡諾圖中最小項的合併規律如下：

（1）卡諾圈中小方格的個數必須為個，m為小於或等於n的整數。

（2）卡諾圈中的個小方格有一定的排列規律，具體地說，它們含有m個不同變數，個相同變數。

（3）卡諾圈中的個小方格對應的最小項可用個變數的“與”項表示，該“與”項由這些最小項中的相同變數構成。

（4）當時，卡諾圈包圍了整個卡諾圖，可用1表示，即n個變數的全部最小項之和為1。

組合電路邏輯關係的圖形表示法可以追溯到英國邏輯學家約翰·維恩（John Venn）1881年發明的在集合論中處理集合間邏輯關係的文氏圖（Venn diagram），赫爾姆·哈斯（Helmut Hasse）有效地利用Vogt在1895年用過的哈斯圖（Hasse diagram）來表示序理論中的有限偏序集，愛德華·維奇（Edward W. Veitch）在1952年將維恩圖中的圓形改畫成矩形而發明了維奇圖（Veitch diagram）。但這些圖都不如美國貝爾實驗室的電信工程師莫里斯·卡諾（Maurice Karnaugh）在1953年根據維奇圖改進的卡諾圖（Karnaugh map）或K圖（K-map）在數字邏輯、故障診斷等許多領域中應用廣泛。

由於卡諾圖兩個相鄰最小項中，只有一個變數取值不同，而其餘的取值都相同。所以，合併相鄰最小項，利用公式，可以消去一個或多個變數，從而使邏輯函數得到簡化。 （1）卡諾圖中最小項合併的規律合併相鄰最小項，可消去變數。合併兩個最小項，可消去一個變數；合併四個最小項，可消去兩個變數；合併八個最小項，可消去三個變數；合併2N個最小項，可消去N個變數。（2）利用卡諾圖化簡邏輯函數 A．基本步驟： ① 畫出邏輯函數的卡諾圖； ② 合併相鄰最小項（圈組）； ③ 從圈組寫出最簡與或表達式。關鍵是能否正確圈組。 B．正確圈組的原則 ① 必須按2、4、8、2N的規律來圈取值為1的相鄰最小項； ② 每個取值為1的相鄰最小項至少必須圈一次，但可以圈多次； ③ 圈的個數要最少（與項就少），並要儘可能大（消去的變數就越多）。 C．從圈組寫最簡與或表達式的方法： ① 將每個圈用一個與項表示圈內各最小項中互補的因子消去，相同的因子保留，相同取值為1用原變數，相同取值為0用反變數； ② 將各與項相或，便得到最簡與或表達式。圈組技巧(防止多圈組的方法)： ① 先圈孤立的1； ② 再圈只有一種圈法的1； ③ 最後圈大圈； ④檢查：每個圈中至少有一個1未被其它圈圈過。

表示各最小項的（n-變數數）個小格，排列呈矩形。

小格按“循環碼”排列，保證最小項間“幾何相鄰”與“邏輯相鄰性”的統一。（幾何相鄰有“內相鄰” “外相鄰”和“中心對稱”）

1．幾個定義

蘊涵項：在函數的“與-或”表達式中，每個“與”項被稱為該函數的蘊涵項(Implicant)。

顯然，在函數卡諾圖中，任何一個1方格所對應的最小項或者卡諾圈中的2m個1方格所對應的“與”項都是函數的蘊涵項。

質蘊涵項：若函數的一個蘊涵項不是該函數中其他蘊涵項的子集，則此蘊涵項稱為質蘊涵項(Prime Implicant)，簡稱為質項。

顯然，在函數卡諾圖中，按照最小項合併規律，如果某個卡諾圈不可能被其他更大的卡諾圈包含，那麼，該卡諾圈所對應的“與”項為質蘊涵項。

必要質蘊涵項：若函數的一個質蘊涵項包含有不被函數的其他任何質蘊涵項所包含的最小項，則此質蘊涵項被稱為必要質蘊涵項(Essential Prime Implicant)，簡稱為必要質項。

在函數卡諾圖中，若某個卡諾圈包含了不可能被任何其他卡諾圈包含的1方格，那麼，該卡諾圈所對應的“與”項為必要質蘊涵項。

2．求函數最簡“與-或”表達式

（1）一般步驟：第一步：作出函數的卡諾圖。

第二步：在卡諾圖上圈出函數的全部質蘊涵項。按照卡諾圖上最小項的合併規律，對函數F卡諾圖中的1方格畫卡諾圈。為了圈出全部質蘊涵項，畫卡諾圈時在滿足合併規律的前題下應儘可能大，若卡諾圈不可能被更大的卡諾圈包圍，則對應的“與”項為質蘊涵項。

第三步：從全部質蘊涵項中找出所有必要質蘊涵項。在卡諾圖上只被一個卡諾圈包圍的最小項被稱為必要最小項，包含必要最小項的質蘊涵項即必要質蘊涵項。為了保證所得結果無一遺漏地復蓋函數的所有最小項，函數表達式中必須包含所有必要質蘊涵項。

第四步：求出函數的最簡質蘊涵項集。若函數的所有必要質蘊涵項尚不能復蓋卡諾圖上的所有1方格，則從剩餘質蘊涵項中找出最簡的所需質蘊涵項，使它和必要質蘊涵項一起構成函數的最小復蓋。

歸納起來，卡諾圖化簡的原則是：

☆ 在復蓋函數中的所有最小項的前提下，卡諾圈的個數達到最少。

☆ 在滿足合併規律的前提下卡諾圈應儘可能大。

☆ 根據合併的需要，每個最小項可以被多個卡諾圈包圍。

3.求函數的最簡“或-與”表達式

當需要求一個函數的最簡“或-與”表達式時，可採用“兩次取反法”。

具體如下：

☆ 先求出函數F的反函數F的最簡“與-或”表達（合併卡諾圖上的0方格）；

☆ 然後對F的最簡“與-或”表達式取反，從而得到函數F的最簡“或-與”表達式。

卡諾圖化簡邏輯函數具有方便、直觀、容易掌握等優點。但依然帶有試湊性。尤其當變數個數大於6時，畫圖以及對圖形的識別都變得相當複雜。