卡諾圖的構(gòu)成及其簡法
加入技術(shù)交流群
一 卡諾圖的構(gòu)成
卡諾圖是一種平面方格圖，每個小方格代表一個最小項，故又稱為最小項方格圖。
1．結(jié)構(gòu)特點
卡諾圖中最小項的排列方案不是唯一的，圖2．5(a)、(b)、(c)、(d)分別為2變量、3變量、4變量、5變量卡諾圖的一種排列方案。圖中，變量的坐標(biāo)值0表示相應(yīng)變量的反變量，1表示相應(yīng)變量的原變量。各小方格依變量順序取坐標(biāo)值，所得二進(jìn)制數(shù)對應(yīng)的十進(jìn)制數(shù)即相應(yīng)最小項的下標(biāo)i。
在五變量卡諾圖中，為了方便省略了符號“m”，直接標(biāo)出m的下標(biāo)i 。
從圖2.5所示的各卡諾圖可以看出，卡諾圖上變量的排列規(guī)律使最小項的相鄰關(guān)系能在圖形上清晰地反映出來。具體地說，在n個變量的卡諾圖中，能從圖形上直觀、方便地找到每個最小項的n個相鄰最小項。以四變量卡諾圖為例，圖中每個最小項應(yīng)有4個相鄰最小項，如m5的4個相鄰最小項分別是m1，m4，m7，m13，這4個最小項對應(yīng)的小方格與m5對應(yīng)的小方格分別相連，也就是說在幾何位置上是相鄰的，這種相鄰稱為幾何相鄰。而m2則不完全相同，它的4個相鄰最小項除了與之幾何相鄰的m3和m6之外，另外兩個是處在“相對”位置的m0(同一列的兩端)和m10(同一行的兩端)。這種相鄰似乎不太直觀，但只要把這個圖的上、下邊緣連接，卷成圓筒狀，便可看出m0和m2在幾何位置上是相鄰的。同樣，把圖的左、右邊緣連接，便可使m2和m10相鄰。通常把這種相鄰稱為相對相鄰。除此之外，還有“相重”位置的最小項相鄰，如五變量卡諾圖中的m3，除了幾何相鄰的m1，m2，m7和相對相鄰的m11外，還與m19相鄰。對于這種情形，可以把卡諾圖左邊的矩形重疊到右邊矩形之上來看，凡上下重疊的最小項相鄰，這種相鄰稱為重疊相鄰。??
歸納起來，卡諾圖在構(gòu)造上具有以下兩個特點：
☆ n個變量的卡諾圖由2n個小方格組成，每個小方格代表一個最小項；
☆ 卡諾圖上處在相鄰、相對、相重位置的小方格所代表的最小項為相鄰最小項。
二 卡諾圖的性質(zhì)
卡諾圖的構(gòu)造特點使卡諾圖具有一個重要性質(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方格有時用空格表示。
四 卡諾圖上最小項的合并規(guī)律
卡諾圖的一個重要特征是，它從圖形上直觀、清晰地反映了最小項的相鄰關(guān)系。當(dāng)一個函數(shù)用卡諾圖表示后，究竟哪些最小項可以合并呢？下面以2、3、4變量卡諾圖為例予以說明。
1．兩個小方格相鄰, 或處于某行(列)兩端時，所代表的最小項可以合并，合并后可消去一個變量。
例如，圖2.8給出了2、3、4變量卡諾圖上兩個相鄰最小項合并的典型情況的。
圖2．8 兩個相鄰最小項合并的情況
2．四個小方格組成一個大方格、或組成一行（列）、或處于相鄰兩行（列）的兩端、或處于四角時，所的表的最小項可以合并，合并后可消去兩個變量。
例如，圖2.9給出了3、4變量卡諾圖上四個相鄰最小項合并的典型情況的。
圖2．9 四個相鄰最小項合并的情況
3．八個小方格組成一個大方格、或組成相鄰的兩行（列）、或處于兩個邊行（列）時，所代表的最小項可以合并，合并后可消去三個變量。
例如，圖2．10給出了3、4變量卡諾圖上八個相鄰最小項合并的典型情況的。
圖2．10 八個相鄰最小項合并的情況
至此，以3、4變量卡諾圖為例，討論了2，4，8個最小項的合并方法。依此類推，不難得出n個變量卡諾圖中最小項的合并規(guī)律。
歸納起來，n個變量卡諾圖中最小項的合并規(guī)律如下：
（1）卡諾圈中小方格的個數(shù)必須為2m個，m為小于或等于n的整數(shù)。
（2）卡諾圈中的2m個小方格有一定的排列規(guī)律，具體地說，它們含有m個不同變量，(n-m)個相同變量。
（3）卡諾圈中的2m個小方格對應(yīng)的最小項可用(n-m)個變量的“與”項表示，該“與”項由這些最小項中的相同變量構(gòu)成。
（4）當(dāng)m=n時，卡諾圈包圍了整個卡諾圖，可用1表示，即n個變量的全部最小項之和為1。
五、卡諾圖化簡邏輯函數(shù)
1．幾個定義
蘊涵項：在函數(shù)的“與-或”表達(dá)式中,每個“與”項被稱為該函數(shù)的蘊涵項(Implicant)。
顯然，在函數(shù)卡諾圖中，任何一個1方格所對應(yīng)的最小項或者卡諾圈中的2m個1方格所對應(yīng)的“與”項都是函數(shù)的蘊涵項。
質(zhì)蘊涵項：若函數(shù)的一個蘊涵項不是該函數(shù)中其他蘊涵項的子集，則此蘊涵項稱為質(zhì)蘊涵項(Prime Implicant)，簡稱為質(zhì)項。
顯然，在函數(shù)卡諾圖中，按照最小項合并規(guī)律，如果某個卡諾圈不可能被其他更大的卡諾圈包含，那么，該卡諾圈所對應(yīng)的“與”項為質(zhì)蘊涵項。
必要質(zhì)蘊涵項：若函數(shù)的一個質(zhì)蘊涵項包含有不被函數(shù)的其他任何質(zhì)蘊涵項所包含的最小項，則此質(zhì)蘊涵項被稱為必要質(zhì)蘊涵項(Essential Prime Implicant)，簡稱為必要質(zhì)項。
在函數(shù)卡諾圖中，若某個卡諾圈包含了不可能被任何其他卡諾圈包含的1方格，那么，該卡諾圈所對應(yīng)的“與”項為必要質(zhì)蘊涵項。
2．求函數(shù)最簡“與-或”表達(dá)式
（1）一般步驟：
第一步：作出函數(shù)的卡諾圖。
第二步：在卡諾圖上圈出函數(shù)的全部質(zhì)蘊涵項。按照卡諾圖上最小項的合并規(guī)律，對函數(shù)F卡諾圖中的1方格畫卡諾圈。為了圈出全部質(zhì)蘊涵項，畫卡諾圈時在滿足合并規(guī)律的前題下應(yīng)盡可能大，若卡諾圈不可能被更大的卡諾圈包圍，則對應(yīng)的“與”項為質(zhì)蘊涵項。
第三步：從全部質(zhì)蘊涵項中找出所有必要質(zhì)蘊涵項。在卡諾圖上只被一個卡諾圈包圍的最小項被稱為必要最小項，包含必要最小項的質(zhì)蘊涵項即必要質(zhì)蘊涵項。為了保證所得結(jié)果無一遺漏地覆蓋函數(shù)的所有最小項，函數(shù)表達(dá)式中必須包含所有必要質(zhì)蘊涵項。
第四步：求出函數(shù)的最簡質(zhì)蘊涵項集。若函數(shù)的所有必要質(zhì)蘊涵項尚不能覆蓋卡諾圖上的所有1方格，則從剩余質(zhì)蘊涵項中找出最簡的所需質(zhì)蘊涵項，使它和必要質(zhì)蘊涵項一起構(gòu)成函數(shù)的最小覆蓋。
歸納起來，卡諾圖化簡的原則是：
☆ 在覆蓋函數(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所示。
圖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)點。但依然帶有試湊性。尤其當(dāng)變量個數(shù)大于6時，畫圖以及對圖形的識別都變得相當(dāng)復(fù)雜。
為了克服它的不足，引入了另一種化簡方法--列表化簡法。
卡諾圖是一種平面方格圖，每個小方格代表一個最小項，故又稱為最小項方格圖。
1．結(jié)構(gòu)特點
卡諾圖中最小項的排列方案不是唯一的，圖2．5(a)、(b)、(c)、(d)分別為2變量、3變量、4變量、5變量卡諾圖的一種排列方案。圖中，變量的坐標(biāo)值0表示相應(yīng)變量的反變量，1表示相應(yīng)變量的原變量。各小方格依變量順序取坐標(biāo)值，所得二進(jìn)制數(shù)對應(yīng)的十進(jìn)制數(shù)即相應(yīng)最小項的下標(biāo)i。
在五變量卡諾圖中，為了方便省略了符號“m”，直接標(biāo)出m的下標(biāo)i 。
從圖2.5所示的各卡諾圖可以看出，卡諾圖上變量的排列規(guī)律使最小項的相鄰關(guān)系能在圖形上清晰地反映出來。具體地說，在n個變量的卡諾圖中，能從圖形上直觀、方便地找到每個最小項的n個相鄰最小項。以四變量卡諾圖為例，圖中每個最小項應(yīng)有4個相鄰最小項，如m5的4個相鄰最小項分別是m1，m4，m7，m13，這4個最小項對應(yīng)的小方格與m5對應(yīng)的小方格分別相連，也就是說在幾何位置上是相鄰的，這種相鄰稱為幾何相鄰。而m2則不完全相同，它的4個相鄰最小項除了與之幾何相鄰的m3和m6之外，另外兩個是處在“相對”位置的m0(同一列的兩端)和m10(同一行的兩端)。這種相鄰似乎不太直觀，但只要把這個圖的上、下邊緣連接，卷成圓筒狀，便可看出m0和m2在幾何位置上是相鄰的。同樣，把圖的左、右邊緣連接，便可使m2和m10相鄰。通常把這種相鄰稱為相對相鄰。除此之外，還有“相重”位置的最小項相鄰，如五變量卡諾圖中的m3，除了幾何相鄰的m1，m2，m7和相對相鄰的m11外，還與m19相鄰。對于這種情形，可以把卡諾圖左邊的矩形重疊到右邊矩形之上來看，凡上下重疊的最小項相鄰，這種相鄰稱為重疊相鄰。??
歸納起來，卡諾圖在構(gòu)造上具有以下兩個特點：
☆ n個變量的卡諾圖由2n個小方格組成，每個小方格代表一個最小項；
☆ 卡諾圖上處在相鄰、相對、相重位置的小方格所代表的最小項為相鄰最小項。
二 卡諾圖的性質(zhì)
卡諾圖的構(gòu)造特點使卡諾圖具有一個重要性質(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方格有時用空格表示。
四 卡諾圖上最小項的合并規(guī)律
卡諾圖的一個重要特征是，它從圖形上直觀、清晰地反映了最小項的相鄰關(guān)系。當(dāng)一個函數(shù)用卡諾圖表示后，究竟哪些最小項可以合并呢？下面以2、3、4變量卡諾圖為例予以說明。
1．兩個小方格相鄰, 或處于某行(列)兩端時，所代表的最小項可以合并，合并后可消去一個變量。
例如，圖2.8給出了2、3、4變量卡諾圖上兩個相鄰最小項合并的典型情況的。
圖2．8 兩個相鄰最小項合并的情況
2．四個小方格組成一個大方格、或組成一行（列）、或處于相鄰兩行（列）的兩端、或處于四角時，所的表的最小項可以合并，合并后可消去兩個變量。
例如，圖2.9給出了3、4變量卡諾圖上四個相鄰最小項合并的典型情況的。
圖2．9 四個相鄰最小項合并的情況
3．八個小方格組成一個大方格、或組成相鄰的兩行（列）、或處于兩個邊行（列）時，所代表的最小項可以合并，合并后可消去三個變量。
例如，圖2．10給出了3、4變量卡諾圖上八個相鄰最小項合并的典型情況的。
圖2．10 八個相鄰最小項合并的情況
至此，以3、4變量卡諾圖為例，討論了2，4，8個最小項的合并方法。依此類推，不難得出n個變量卡諾圖中最小項的合并規(guī)律。
歸納起來，n個變量卡諾圖中最小項的合并規(guī)律如下：
（1）卡諾圈中小方格的個數(shù)必須為2m個，m為小于或等于n的整數(shù)。
（2）卡諾圈中的2m個小方格有一定的排列規(guī)律，具體地說，它們含有m個不同變量，(n-m)個相同變量。
（3）卡諾圈中的2m個小方格對應(yīng)的最小項可用(n-m)個變量的“與”項表示，該“與”項由這些最小項中的相同變量構(gòu)成。
（4）當(dāng)m=n時，卡諾圈包圍了整個卡諾圖，可用1表示，即n個變量的全部最小項之和為1。
五、卡諾圖化簡邏輯函數(shù)
1．幾個定義
蘊涵項：在函數(shù)的“與-或”表達(dá)式中,每個“與”項被稱為該函數(shù)的蘊涵項(Implicant)。
顯然，在函數(shù)卡諾圖中，任何一個1方格所對應(yīng)的最小項或者卡諾圈中的2m個1方格所對應(yīng)的“與”項都是函數(shù)的蘊涵項。
質(zhì)蘊涵項：若函數(shù)的一個蘊涵項不是該函數(shù)中其他蘊涵項的子集，則此蘊涵項稱為質(zhì)蘊涵項(Prime Implicant)，簡稱為質(zhì)項。
顯然，在函數(shù)卡諾圖中，按照最小項合并規(guī)律，如果某個卡諾圈不可能被其他更大的卡諾圈包含，那么，該卡諾圈所對應(yīng)的“與”項為質(zhì)蘊涵項。
必要質(zhì)蘊涵項：若函數(shù)的一個質(zhì)蘊涵項包含有不被函數(shù)的其他任何質(zhì)蘊涵項所包含的最小項，則此質(zhì)蘊涵項被稱為必要質(zhì)蘊涵項(Essential Prime Implicant)，簡稱為必要質(zhì)項。
在函數(shù)卡諾圖中，若某個卡諾圈包含了不可能被任何其他卡諾圈包含的1方格，那么，該卡諾圈所對應(yīng)的“與”項為必要質(zhì)蘊涵項。
2．求函數(shù)最簡“與-或”表達(dá)式
（1）一般步驟：
第一步：作出函數(shù)的卡諾圖。
第二步：在卡諾圖上圈出函數(shù)的全部質(zhì)蘊涵項。按照卡諾圖上最小項的合并規(guī)律，對函數(shù)F卡諾圖中的1方格畫卡諾圈。為了圈出全部質(zhì)蘊涵項，畫卡諾圈時在滿足合并規(guī)律的前題下應(yīng)盡可能大，若卡諾圈不可能被更大的卡諾圈包圍，則對應(yīng)的“與”項為質(zhì)蘊涵項。
第三步：從全部質(zhì)蘊涵項中找出所有必要質(zhì)蘊涵項。在卡諾圖上只被一個卡諾圈包圍的最小項被稱為必要最小項，包含必要最小項的質(zhì)蘊涵項即必要質(zhì)蘊涵項。為了保證所得結(jié)果無一遺漏地覆蓋函數(shù)的所有最小項，函數(shù)表達(dá)式中必須包含所有必要質(zhì)蘊涵項。
第四步：求出函數(shù)的最簡質(zhì)蘊涵項集。若函數(shù)的所有必要質(zhì)蘊涵項尚不能覆蓋卡諾圖上的所有1方格，則從剩余質(zhì)蘊涵項中找出最簡的所需質(zhì)蘊涵項，使它和必要質(zhì)蘊涵項一起構(gòu)成函數(shù)的最小覆蓋。
歸納起來，卡諾圖化簡的原則是：
☆ 在覆蓋函數(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所示。
圖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)點。但依然帶有試湊性。尤其當(dāng)變量個數(shù)大于6時，畫圖以及對圖形的識別都變得相當(dāng)復(fù)雜。
為了克服它的不足，引入了另一種化簡方法--列表化簡法。
評論