學(xué)習(xí)使用卡諾圖

卡 諾 圖 （Kamaug hM ap )是將所有命題的真假組合以二維表的形式表示的圖。

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

卡諾圖中最小項(xiàng)的排列方案不是唯一的，變量的坐標(biāo)值0表示相應(yīng)變量的反變量，1表示相應(yīng)變量的原變量。各小方格依變量順序取坐標(biāo)值，所得二進(jìn)制數(shù)對(duì)應(yīng)的十進(jìn)制數(shù)即相應(yīng)最小項(xiàng)的下標(biāo)i。

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

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

☆ n個(gè)變量的卡諾圖由2^n個(gè)小方格組成，每個(gè)小方格代表一個(gè)最小項(xiàng);

☆ 卡諾圖上處在相鄰、相對(duì)、相重位置的小方格所代表的最小項(xiàng)為相鄰最小項(xiàng)。

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

化簡(jiǎn)函數(shù)

---

1.幾個(gè)定義

蘊(yùn)涵項(xiàng):在函數(shù)的"與-或"表達(dá)式中,每個(gè)"與"項(xiàng)被稱為該函數(shù)的蘊(yùn)涵項(xiàng)(Implicant)。

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

質(zhì)蘊(yùn)涵項(xiàng):若函數(shù)的一個(gè)蘊(yùn)涵項(xiàng)不是該函數(shù)中其他蘊(yùn)涵項(xiàng)的子集，則此蘊(yùn)涵項(xiàng)稱為質(zhì)蘊(yùn)涵項(xiàng)(Prime Implicant)，簡(jiǎn)稱為質(zhì)項(xiàng)。

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

必要質(zhì)蘊(yùn)涵項(xiàng):若函數(shù)的一個(gè)質(zhì)蘊(yùn)涵項(xiàng)包含有不被函數(shù)的其他任何質(zhì)蘊(yùn)涵項(xiàng)所包含的最小項(xiàng)，則此質(zhì)蘊(yùn)涵項(xiàng)被稱為必要質(zhì)蘊(yùn)涵項(xiàng)(Essential Prime Implicant)，簡(jiǎn)稱為必要質(zhì)項(xiàng)。
在函數(shù)卡諾圖中，若某個(gè)卡諾圈包含了不可能被任何其他卡諾圈包含的1方格，那么，該卡諾圈所對(duì)應(yīng)的"與"項(xiàng)為必要質(zhì)蘊(yùn)涵項(xiàng)。

2.求函數(shù)最簡(jiǎn)"與-或"表達(dá)式

(1)一般步驟:

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

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

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

第四步:求出函數(shù)的最簡(jiǎn)質(zhì)蘊(yùn)涵項(xiàng)集。若函數(shù)的所有必要質(zhì)蘊(yùn)涵項(xiàng)尚不能覆蓋卡諾圖上的所有1方格，則從剩余質(zhì)蘊(yùn)涵項(xiàng)中找出最簡(jiǎn)的所需質(zhì)蘊(yùn)涵項(xiàng)，使它和必要質(zhì)蘊(yùn)涵項(xiàng)一起構(gòu)成函數(shù)的最小覆蓋。
歸納起來(lái)，卡諾圖化簡(jiǎn)的原則是:

☆ 在覆蓋函數(shù)中的所有最小項(xiàng)的前提下，卡諾圈的個(gè)數(shù)達(dá)到最少。
☆ 在滿足合并規(guī)律的前提下卡諾圈應(yīng)盡可能大。
☆ 根據(jù)合并的需要，每個(gè)最小項(xiàng)可以被多個(gè)卡諾圈包圍。

3.求函數(shù)的最簡(jiǎn)"或-與"表達(dá)式

當(dāng)需要求一個(gè)函數(shù)的最簡(jiǎn)"或-與"表達(dá)式時(shí)，可采用"兩次取反法"。
具體如下:

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

☆ 然后對(duì)F的最簡(jiǎn)"與-或"表達(dá)式取反，從而得到函數(shù)F的最簡(jiǎn)"或-與"表達(dá)式。

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

表示

---

1.給定邏輯函數(shù)為標(biāo)準(zhǔn)"與-或"表達(dá)式
當(dāng)邏輯函數(shù)為標(biāo)準(zhǔn)"與-或"表達(dá)式時(shí)，只需在卡諾圖上找出和表達(dá)式中最小項(xiàng)對(duì)應(yīng)的小方格填上1，其余小方格填上0，即可得到該函數(shù)的卡諾圖。
2.邏輯函數(shù)為一般"與-或"表達(dá)式
當(dāng)邏輯函數(shù)為一般"與-或"表達(dá)式時(shí)，可根據(jù)"與"的公共性和"或"的疊加性作出相應(yīng)卡諾圖。
填寫該函數(shù)卡諾圖時(shí)，只需在4變量卡諾圖上依次找出和"與項(xiàng)"AB、CD、A·BC對(duì)應(yīng)的小方格填上1，便可得到該函數(shù)的卡諾圖。
當(dāng)邏輯函數(shù)表達(dá)式為其他形式時(shí)，可將其變換成上述形式后再作卡諾圖。
為了敘述的方便，通常將卡諾圖上填1的小方格稱為1方格，填0的小方格稱為0方格。0方格有時(shí)用空格表示。

合并規(guī)律

---

1.卡諾圖的一個(gè)重要特征是，它從圖形上直觀、清晰地反映了最小項(xiàng)的相鄰關(guān)系。
2.四個(gè)小方格組成一個(gè)大方格、或組成一行(列)、或處于相鄰兩行(列)的兩端、或處于四角時(shí)，所的表的最小項(xiàng)可以合并，合并后可消去兩個(gè)變量。
3.八個(gè)小方格組成一個(gè)大方格、或組成相鄰的兩行(列)、或處于兩個(gè)邊行(列)時(shí)，所代表的最小項(xiàng)可以合并，合并后可消去三個(gè)變量。
至此，以3、4變量卡諾圖為例，討論了2，4，8個(gè)最小項(xiàng)的合并方法。依此類推，不難得出n個(gè)變量卡諾圖中最小項(xiàng)的合并規(guī)律。
歸納起來(lái)，n個(gè)變量卡諾圖中最小項(xiàng)的合并規(guī)律如下:
(1)卡諾圈中小方格的個(gè)數(shù)必須為2^m個(gè)，m為小于或等于n的整數(shù)。
(2)卡諾圈中的2^m個(gè)小方格有一定的排列規(guī)律，具體地說(shuō)，它們含有m個(gè)不同變量，(n-m)個(gè)相同變量。
(3)卡諾圈中的2^m個(gè)小方格對(duì)應(yīng)的最小項(xiàng)可用(n-m)個(gè)變量的"與"項(xiàng)表示，該"與"項(xiàng)由這些最小項(xiàng)中的相同變量構(gòu)成。
(4)當(dāng)m=n時(shí)，卡諾圈包圍了整個(gè)卡諾圖，可用1表示，即n個(gè)變量的全部最小項(xiàng)之和為1。