卡諾圖
| 卡諾圖 |
|
中文名: 卡諾圖 外文名: Karnaugh map 本 質: 邏輯函數 表現形式: 圖形 化簡最多變量: 6 發明人: 莫里斯·卡諾Maurice Karnaugh |
卡諾圖是邏輯函數的一種圖形表示。一個邏輯函數的卡諾圖就是將此函數的最小項表達式中的各最小項相應地填入一個方格圖內，此方格圖稱為卡諾圖。 卡諾圖的構造特點使卡諾圖具有一個重要性質：可以從圖形上直觀地找出相鄰最小項。兩個相鄰最小項可以合併為一個與項並消去一個變量。[1]
目錄
概述
卡諾圖是邏輯函數的一種圖形表示。卡諾圖是一種平面方格圖，每個小方格代表邏輯函數的一個最小項，故又稱為最小項方格圖。方格圖中相鄰兩個方格的兩組變量取值相比，只有一個變量的取值發生變化，按照這一原則得出的方格圖（全部方格構成正方形或長方形）就稱為卡諾方格圖，簡稱卡諾圖。
結構特點
卡諾圖中最小項的排列方案不是唯一的，變量的坐標值0表示相應變量的反變量，1表示相應變量的原變量，變量的取值變化規律按「循環碼」變化。各小方格依變量順序取坐標值，所得二進制數對應的十進制數即相應最小項的下標i。 在五變量卡諾圖中，為了方便省略了符號「m」，直接標出m的下標i 。 歸納起來，卡諾圖在構造上具有以下兩個特點： ☆ n個變量的卡諾圖由2^n個小方格組成，每個小方格代表一個最小項； ☆ 卡諾圖上處在相鄰、相對、相重位置的小方格所代表的最小項為相鄰最小項。 可以從圖形上直觀地找出相鄰最小項。兩個相鄰最小項可以合併為一個與項並消去一個變量。
歷史
組合電路邏輯關係的圖形表示法可以追溯到英國邏輯學家約翰·維恩（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）在數字邏輯、故障診斷等許多領域中應用廣泛。
性質
卡諾圖的構造特點使卡諾圖具有一個重要性質：可以從圖形上直觀地找出相鄰最小項合併。合併的理論依據是並項定理AB+AB反=A。例如， 根據定理AB+AB反=A和相鄰最小項的定義，兩個相鄰最小項可以合併為一個與項並消去一個互反變量。例如，4變量最小項ABCD和ABC反D相鄰，可以合併為ABD；A反BCD和A反BC反D相鄰，可以合併為A反BD；而與項A反BD和ABD又為相鄰與項，故按同樣道理可進一步將兩個相鄰與項合併為BD。 用卡諾圖化簡邏輯函數的基本原理就是把上述邏輯依據和圖形特徵結合起來，通過把卡諾圖上表徵相鄰最小項的相鄰小方格「圈」在一起進行合併，達到用一個簡單「與」項代替若干最小項的目的。 通常把用來包圍那些能由一個簡單「與」項代替的若干最小項的「圈」稱為卡諾圈。
函數
邏輯函數未用最小項表示照樣可以化簡。如果F採用與—或表達式，在填入卡諾圖過程中就能把函數展開成最小項。 具有無關項的化簡 無關項又叫任意項，是一種最小項，其值可以取0或1。利用無關項這一特點，可以使函數簡化。 用卡諾圖化簡邏輯函數的步驟 如果表達式為最小項表達式，則可直接填入卡諾圖 如果表達式不是最小項表達式，但是是「與—或表達式」，可將其先化成最小項表達式，再填入卡諾圖。也可直接填入。 合併相鄰的最小項，即根據下述原則畫圈 儘量畫大圈，但每個圈內只能含有2n（n=0,1,2,3……）個相鄰項。要特別注意對邊相鄰性和四角相鄰性。 圈的個數儘量少。 卡諾圖中所有取值為1的方格均要被圈過，即不能漏下取值為1的最小項。 在新畫的包圍圈中至少要含有1個末被圈過的1方格，否則該包圍圈是多餘的。 寫出化簡後的表達式。每一個圈寫一個最簡與項，規則是，取值始終為1的變量用原變量表示，取值出現過0的變量用反變量表示，將這些變量相與。然後將所有與項進行邏輯加，即得最簡與—或表達式。 在進行化簡時，如果用圖中真值為0的項更方便，可以用他們來處理，方法和真值取1時一樣，只是結果要再做一次求反。
變量
表示各最小項的2^n（n-變量數）個小格，排列呈矩形。小格按「循環碼」 排列，保證最小項間「幾何相鄰」與「邏輯相鄰性」的統一。（幾何相鄰有「內相鄰」 「外相鄰」和「中心對稱」）
變量填入
把函數包含的所有最小項，以「1」填入變量卡諾圖對應編號的小格內。
化簡函數
1．幾個定義 蘊涵項：在函數的「與-或」表達式中,每個「與」項被稱為該函數的蘊涵項(Implicant)。 顯然，在函數卡諾圖中，任何一個1方格所對應的最小項或者卡諾圈中的2m個1方格所對應的「與」項都是函數的蘊涵項。 質蘊涵項：若函數的一個蘊涵項不是該函數中其他蘊涵項的子集，則此蘊涵項稱為質蘊涵項(Prime Implicant)，簡稱為質項。 顯然，在函數卡諾圖中，按照最小項合併規律，如果某個卡諾圈不可能被其他更大的卡諾圈包含，那麼，該卡諾圈所對應的「與」項為質蘊涵項。 必要質蘊涵項：若函數的一個質蘊涵項包含有不被函數的其他任何質蘊涵項所包含的最小項，則此質蘊涵項被稱為必要質蘊涵項(Essential Prime Implicant)，簡稱為必要質項。 在函數卡諾圖中，若某個卡諾圈包含了不可能被任何其他卡諾圈包含的1方格，那麼，該卡諾圈所對應的「與」項為必要質蘊涵項。 2．求函數最簡「與-或」表達式 （1）一般步驟： 第一步：作出函數的卡諾圖。 第二步：在卡諾圖上圈出函數的全部質蘊涵項。按照卡諾圖上最小項的合併規律，對函數F卡諾圖中的1方格畫卡諾圈。為了圈出全部質蘊涵項，畫卡諾圈時在滿足合併規律的前提下應儘可能大，若卡諾圈不可能被更大的卡諾圈包圍，則對應的「與」項為質蘊涵項。 第三步：從全部質蘊涵項中找出所有必要質蘊涵項。在卡諾圖上只被一個卡諾圈包圍的最小項被稱為必要最小項，包含必要最小項的質蘊涵項即必要質蘊涵項。為了保證所得結果無一遺漏地覆蓋函數的所有最小項，函數表達式中必須包含所有必要質蘊涵項。 第四步：求出函數的最簡質蘊涵項集。若函數的所有必要質蘊涵項尚不能覆蓋卡諾圖上的所有1方格，則從剩餘質蘊涵項中找出最簡的所需質蘊涵項，使它和必要質蘊涵項一起構成函數的最小覆蓋。 歸納起來，卡諾圖化簡的原則是： ☆ 在覆蓋函數中的所有最小項的前提下，卡諾圈的個數達到最少。 ☆ 在滿足合併規律的前提下卡諾圈應儘可能大。 ☆ 根據合併的需要，每個最小項可以被多個卡諾圈包圍。 3.求函數的最簡「或-與」表達式 當需要求一個函數的最簡「或-與」表達式時，可採用「兩次取反法」。 具體如下： ☆ 先求出函數F的反函數F的最簡「與-或」表達（合併卡諾圖上的0方格）； ☆ 然後對F的最簡「與-或」表達式取反，從而得到函數F的最簡「或-與」表達式。 卡諾圖化簡邏輯函數具有方便、直觀、容易掌握等優點。但依然帶有試湊性。尤其當變量個數大於6時，畫圖以及對圖形的識別都變得相當複雜。
表示
1．給定邏輯函數為標準「與-或」表達式 當邏輯函數為標準「與-或」表達式時，只需在卡諾圖上找出和表達式中最小項對應的小方格填上1，其餘小方格填上0，即可得到該函數的卡諾圖。 2．邏輯函數為一般「與-或」表達式 當邏輯函數為一般「與-或」表達式時，可根據「與」的公共性和「或」的疊加性作出相應卡諾圖。 填寫該函數卡諾圖時，只需在4變量卡諾圖上依次找出和「與項」AB、CD、A·BC對應的小方格填上1，便可得到該函數的卡諾圖。 當邏輯函數表達式為其他形式時，可將其變換成上述形式後再作卡諾圖。 為了敘述的方便，通常將卡諾圖上填1的小方格稱為1方格，填0的小方格稱為0方格。0方格有時用空格表示。
合併規律
卡諾圖的一個重要特徵是：從圖形上直觀、清晰地反映了最小項的相鄰關係。四個小方格組成一個大方格、或組成一行（列）、或處於相鄰兩行（列）的兩端、或處於四角時，所的表的最小項可以合併，合併後可消去兩個變量。八個小方格組成一個大方格、或組成相鄰的兩行（列）、或處於兩個邊行（列）時，所代表的最小項可以合併，合併後可消去三個變量。至此，以3、4變量卡諾圖為例，討論了2，4，8個最小項的合併方法。依此類推，不難得出n個變量卡諾圖中最小項的合併規律。 歸納起來，n個變量卡諾圖中最小項的合併規律如下： （1）卡諾圈中小方格的個數必須為2^m個，m為小於或等於n的整數。 （2）卡諾圈中的2^m個小方格有一定的排列規律，具體地說，它們含有m個不同變量，(n-m)個相同變量。 （3）卡諾圈中的2^m個小方格對應的最小項可用(n-m)個變量的「與」項表示，該「與」項由這些最小項中的相同變量構成。 （4）當m=n時，卡諾圈包圍了整個卡諾圖，可用1表示，即n個變量的全部最小項之和為1。