卡諾圖是邏輯函數(shù)的一種圖形表示。一個邏輯函數(shù)的卡諾圖就是將此函數(shù)的最小項表達(dá)式中的各最小項相應(yīng)地填入一個方格圖內(nèi)，此方格圖稱為卡諾圖。

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

卡諾圖是邏輯函數(shù)的一種圖形表示?？ㄖZ圖是一種平面方格圖，每個小方格代表邏輯函數(shù)的一個最小項，故又稱為最小項方格圖。方格圖中相鄰兩個方格的兩組變量取值相比，只有一個變量的取值發(fā)生變化，按照這一原則得出的方格圖(全部方格構(gòu)成正方形或長方形)就稱為卡諾方格圖，簡稱卡諾圖。 [1]

結(jié)構(gòu)特點(diǎn)

卡諾圖中最小項的排列方案不是唯一的，變量的坐標(biāo)值0表示相應(yīng)變量的反變量，1表示相應(yīng)變量的原變量，變量的取值變化規(guī)律按“循環(huán)碼”變化 [1] 。各小方格依變量順序取坐標(biāo)值，所得二進(jìn)制數(shù)對應(yīng)的十進(jìn)制數(shù)即相應(yīng)最小項的下標(biāo)i。

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

卡諾圖(18張)

歸納起來，卡諾圖在構(gòu)造上具有以下兩個特點(diǎn)：

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

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

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

一、卡諾圖概念

卡諾圖是邏輯函數(shù)的一種圖形表示。一個邏輯函數(shù)的卡諾圖就是將此函數(shù)的最小項表達(dá)式中的各最小項相應(yīng)地填入一個方格圖內(nèi)，此方格圖稱為卡諾圖?？ㄖZ圖的構(gòu)造特點(diǎn)使卡諾圖具有一個重要性質(zhì)：可以從圖形上直觀地找出相鄰最小項。兩個相鄰最小項可以合并為一個與項并消去一個變量。

二、卡諾圖結(jié)構(gòu)特點(diǎn)

卡諾圖中最小項的排列方案不是唯一的，變量的坐標(biāo)值0表示相應(yīng)變量的反變量，1表示相應(yīng)變量的原變量，變量的取值變化規(guī)律按“循環(huán)碼”變化[1]。各小方格依變量順序取坐標(biāo)值，所得二進(jìn)制數(shù)對應(yīng)的十進(jìn)制數(shù)即相應(yīng)最小項的下標(biāo)i。

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

歸納起來，卡諾圖在構(gòu)造上具有以下兩個特點(diǎn)：

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

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

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

三、卡諾圖的性質(zhì)

卡諾圖的構(gòu)造特點(diǎn)使卡諾圖具有一個重要性質(zhì)：可以從圖形上直觀地找出相鄰最小項合并。合并的理論依據(jù)是并項定理AB+AB=A。例如，

根據(jù)定理AB+AB=A和相鄰最小項的定義，兩個相鄰最小項可以合并為一個與項并消去一個變量。例如，4變量最小項ABCD和ABCD相鄰，可以合并為ABD;ABCD和ABCD相鄰，可以合并為ABD;而與項ABD和ABD又為相鄰與項，故按同樣道理可進(jìn)一步將兩個相鄰與項合并為BD。

用卡諾圖化簡邏輯函數(shù)的基本原理就是把上述邏輯依據(jù)和圖形特征結(jié)合起來，通過把卡諾圖上表征相鄰最小項的相鄰小方格“圈”在一起進(jìn)行合并，達(dá)到用一個簡單“與”項代替若干最小項的目的。

通常把用來包圍那些能由一個簡單“與”項代替的若干最小項的“圈”稱為卡諾圈。

邏輯函數(shù)在卡諾圖上的表示

1.給定邏輯函數(shù)為標(biāo)準(zhǔn)“與-或”表達(dá)式

當(dāng)邏輯函數(shù)為標(biāo)準(zhǔn)“與-或”表達(dá)式時，只需在卡諾圖上找出和表達(dá)式中最小項對應(yīng)的小方格填上1，其余小方格填上0，即可得到該函數(shù)的卡諾圖。

例如，3變量函數(shù)F(A，B，C)=∑m(1，2，3，7)的卡諾圖如圖2.6所示。

圖2.6函數(shù)F(A，B，C)=∑m(1，2，3，7)的卡諾圖

2.邏輯函數(shù)為一般“與-或”表達(dá)式

當(dāng)邏輯函數(shù)為一般“與-或”表達(dá)式時，可根據(jù)“與”的公共性和“或”的疊加性作出相應(yīng)卡諾圖。

例如，4變量函數(shù)F(A，B，C，D)=AB+CD+A·BC的卡諾圖如圖2.7所示。

圖2.7函數(shù)F(A，B，C，D)=AB+CD+A·BC的卡諾圖

填寫該函數(shù)卡諾圖時，只需在4變量卡諾圖上依次找出和“與項”AB、CD、A·BC對應(yīng)的小方格填上1，便可得到該函數(shù)的卡諾圖。

當(dāng)邏輯函數(shù)表達(dá)式為其他形式時，可將其變換成上述形式后再作卡諾圖。

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

四、卡諾圖化簡邏輯函數(shù)

1.幾個定義

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

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

質(zhì)蘊(yùn)涵項：若函數(shù)的一個蘊(yùn)涵項不是該函數(shù)中其他蘊(yùn)涵項的子集，則此蘊(yùn)涵項稱為質(zhì)蘊(yùn)涵項(PrimeImplicant)，簡稱為質(zhì)項。

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

必要質(zhì)蘊(yùn)涵項：若函數(shù)的一個質(zhì)蘊(yùn)涵項包含有不被函數(shù)的其他任何質(zhì)蘊(yùn)涵項所包含的最小項，則此質(zhì)蘊(yùn)涵項被稱為必要質(zhì)蘊(yùn)涵項(EssenTIalPrimeImplicant)，簡稱為必要質(zhì)項。

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

2.求函數(shù)最簡“與-或”表達(dá)式

(1)一般步驟：

第一步：作出函數(shù)的卡諾圖。

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

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

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

(2)舉例

例1用卡諾圖化簡邏輯函數(shù)F(A，B，C，D)=∑m(0，3，5，6，7，10，11，13，15)。

解根據(jù)卡諾圖化簡的步驟，該題化簡過程如下：

該題中，5個必要質(zhì)蘊(yùn)涵項已將函數(shù)的全部最小項覆蓋，故將各卡諾圈對應(yīng)的與項相或即可得到函數(shù)F的最簡“與-或”表達(dá)式為

F(A，B，C，D)=A·B·C·D+ABC+ABC+BD+CD

例2用卡諾圖化簡邏輯函數(shù)F(A，B，C，D)=∑m(2，3，6，7，8，10，12)。

解根據(jù)卡諾圖化簡的步驟，該題化簡過程如下：

由圖可知，該函數(shù)包含兩個必要質(zhì)蘊(yùn)涵項，即AC和AC·D。在選取必要質(zhì)蘊(yùn)涵項之后，尚有最小項m10未被覆蓋。為了覆蓋最小項m10，可選質(zhì)蘊(yùn)涵項BCD或者AB·D，由于這兩個質(zhì)蘊(yùn)涵項均由3個變量組成，故可任選其中之一作為所需質(zhì)蘊(yùn)涵項，即F的最簡質(zhì)蘊(yùn)涵項集可為

{AC，AC·D，BCD}或者{AC，AC·D，AB·D}

因而，可求得函數(shù)F的最簡“與-或”表達(dá)式為

F(A，B，C，D)=AC+AC·D+BCD或者F(A，B，C，D)=AC+AC·D+AB·D

這里，函數(shù)F的最簡“與-或”式有兩個，其復(fù)雜程度相同。由此可見，一個函數(shù)的最簡“與-或”表達(dá)式不一定是唯一的!

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

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

☆在滿足合并規(guī)律的前題下卡諾圈應(yīng)盡可能大。

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

3.求函數(shù)的最簡“或-與”表達(dá)式

當(dāng)需要求一個函數(shù)的最簡“或-與”表達(dá)式時，可采用“兩次取反法”。

具體如下：

☆先求出函數(shù)F的反函數(shù)F的最簡“與-或”表達(dá)(合并卡諾圖上的0方格);

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

例如，用卡諾圖求邏輯函數(shù)F(A，B，C，D)=∑m(3，4，6，7，11，12，13，14，15)的最簡“或-與”表達(dá)式。

解首先畫出函數(shù)F的卡諾圖如圖2.13所示。

圖中，F(xiàn)的0方格即反函數(shù)F的1方格，它們代表F的各個最小項，將全部0方格合并就可得到反函數(shù)F的最簡“與-或”表達(dá)式

F(A，B，C，D)=AB+CD+BD

再對上述函數(shù)式兩邊取反，即可求得函數(shù)的最簡“或-與”表達(dá)式

卡諾圖化簡邏輯函數(shù)具有方便、直觀、容易掌握等優(yōu)點(diǎn)。但依然帶有試湊性。尤其當(dāng)變量個數(shù)大于6時，畫圖以及對圖形的識別都變得相當(dāng)復(fù)雜。

卡諾圖化簡邏輯函數(shù)具有方便、直觀、容易掌握等優(yōu)點(diǎn)。但依然帶有試湊性。尤其當(dāng)變量個數(shù)大于6時，畫圖以及對圖形的識別都變得相當(dāng)復(fù)雜。

為了克服它的不足，引入了另一種化簡方法--列表化簡法。