卡諾圖簡介

　　卡諾圖是邏輯函數的一種圖形表示。一個邏輯函數的卡諾圖就是將此函數的最小項表達式中的各最小項相應地填入一個方格圖內，此方格圖稱為卡諾圖。

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

　　卡諾圖結構特點

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

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

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

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

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

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

　　卡諾圖化簡函數

　　1．幾個定義

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

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

　　質蘊涵項：若函數的一個蘊涵項不是該函數中其他蘊涵項的子集，則此蘊涵項稱為質蘊涵項（PrimeImplicant），簡稱為質項。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　具體如下：

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

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

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

　　卡諾圖化簡的步驟

　　⑴將邏輯函數變換為與-或式。

　　⑵畫出邏輯函數的卡諾圖。

　　⑶將2的n次方個為1的相鄰方格（相鄰項）分別畫包圍圈，每個包圍圈的公因子作為乘積項。

　　⑷將每個乘積項項相加，就得到最簡的與-或表達式。

　　二變量卡諾位置圖

　　卡諾圖化簡方法

　　一、邏輯函數的卡諾圖表示法

　　將n變量的全部最小項各用一個小方塊表示，并使具有邏輯相鄰性的最小項在幾何位置上也相鄰地排列起來，所得到的圖形稱為n變量最小項的卡諾圖。

　　為了保證圖中幾何位置相鄰地最小項在邏輯上也具有相鄰性，這些數碼不能按自然二進制數從小到大地順序排列，而必須按圖中的方式排列，以確保相鄰的兩個最小項僅有一個變量是不同的。

　　從卡諾圖上可以看到，處在任何一行或一列兩端的最小項也僅有一個變量不同，所以它們也具有邏輯相鄰性。因此，從幾何位置上應當將卡諾圖看成是上下、左右閉合的圖形。

　　任何一個邏輯函數都能表示為若干最小項之和的形式，自然也可以用卡諾圖來表示任意一個邏輯函數。具體做法是：首先將邏輯函數化為最小項之和的形式，然后在卡諾圖上標出與之相對應的最小項，在其余位置上標入0，就得到了表示該邏輯函數的卡諾圖。也就是說，任何一個邏輯函數都等于卡諾圖中填入1的那些最小項之和。

　　二、用卡諾圖化解邏輯函數

　　化簡時依據的基本原理就是具有相鄰性的最小項可以合并，并消去不同的因子。由于在卡諾圖上幾何位置相鄰與邏輯上的相鄰性是一致的，因而從卡諾圖上能直觀的找出那些具有相鄰性的最小項并將其合并化簡。

　　合并最小項的原則：若兩個最小項相鄰，則可以合并為一項并消去一對因子。若四個最小項相鄰并排列成一個矩形組，則可合并為一項并消去兩隊因子。若八個最小項相鄰并且排列成一個矩形組，則可以合并成一項并消去三對因子。合并后的結果中只剩下公共因子。

　　卡諾圖化簡法步驟

　　（一）將函數式化為最小項之和的形式；

　　（二）畫出表示該邏輯函數的卡諾圖；

　　（三）找出可以合并的最小項；

　　（四）畫出包圍圈并選取化簡后的乘積項。

　　在畫包圍圈時要注意：

　　（一）包圍圈越大越好；

　　（二）包圍圈的個數越少越好；

　　（三）同一個“1”方塊可以被圈多次；

　　（四）畫包圍圈時，可先圈大，再圈小；

　　（五）每個圈要有新的成分，如果某一圈中所有的“1”方塊均被別的包圍圈包圍，就可以舍掉這個包圍圈；

　　（六）不要遺漏任何方塊。

　　通常我們都是通過合并卡諾圖中的1來求得化簡結果得。但有時也可以通過合并卡諾圖中的0先求出‘Y的化簡結果，然后再將’Y求反而得到Y。