邏輯函數的卡諾圖化簡(jiǎn)法

一、最小項的定義及其性質(zhì)

1.最小項的基本概念

　　由A、B、C三個(gè)邏輯變量構成的許多乘積項中有八個(gè)被稱(chēng)為A、B、C的最小項的乘積項，它們的特點(diǎn)是
　　1. 每項都只有三個(gè)因子
　　2. 每個(gè)變量都是它的一個(gè)因子
　　3. 每一變量或以原變量(Ａ、Ｂ、Ｃ)的形式出現，或以反（非）變量(Ａ、Ｂ、Ｃ)的形式出現，各出現一次
　　一般情況下，對ｎ個(gè)變量來(lái)說(shuō)，最小項共有2ⁿ個(gè)，如n＝3時(shí)，最小項有2³＝8個(gè)

2.最小項的性質(zhì)

　　為了分析最小項的性質(zhì)，以下列出３個(gè)變量的所有最小項的真值表。

由此可見(jiàn)，最小項具有下列性質(zhì)：
　?。?）對于任意一個(gè)最小項，只有一組變量取值使得它的值為1，而在變量取其他各組值時(shí)，這個(gè)最小項的值都是0。
　?。?）不同的最小項，使它的值為1的那一組變量取值也不同。
　?。?）對于變量的任一組取值，任意兩個(gè)最小項的乘積為0。
　?。?）對于變量的任一組取值，全體最小項之和為1。

3.最小項的編號

　　最小項通常用m_i表示，下標i即最小項編號 ，用十進(jìn)制數表示。以ABC為例，因為它和011相對應，所以就稱(chēng)ABC是和變量取值011相對應的最小項，而011相當于十進(jìn)制中的3，所以把ABC記為m₃按此原則，3個(gè)變量的最小項

二、邏輯函數的最小項表達式

　　利用邏輯代數的基本公式，可以把任一個(gè)邏輯函數化成一種典型的表達式，這種典型的表達式是一組最小項之和，稱(chēng)為最小項表達式
。下面舉例說(shuō)明把邏輯表達式展開(kāi)為最小項表達式的方法。例如，要將化成最小項表達式,這時(shí)可利用的基本運算關(guān)系,將邏輯函數中的每一項都化成包含所有變量A、B、C的項，然后再用最小項下標編號來(lái)代表最小項，即

　　又如，要將 化成最小項表達式，可經(jīng)下列幾步：
　?。?）多次利用摩根定律去掉非號 ，直至最后得到一個(gè)只在單個(gè)變量上有非號的表達式；
　?。?）利用分配律除去括號，直至得到一個(gè)與或表達式；

　?。?）在以上第5個(gè)等式中，有一項AB不是最小項（缺少變量C），可用乘此項，正如第6個(gè)等式所示。
　　由此可見(jiàn)，任一個(gè)邏輯函數都可化成為唯一的最小項表達式。

三、用卡諾圖表示邏輯函數

1.卡諾圖的引出

　　一個(gè)邏輯函數的卡諾圖就是將此函數的最小項表達式中的各最小項相應地填入一個(gè)特定的方格圖內，此方格圖稱(chēng)為卡諾圖。
　　卡諾圖是邏輯函數的一種圖形表示。
　　下面從討論一變量卡諾圖開(kāi)始，逐步過(guò)渡到多變量卡諾圖。
　　大家知道，n個(gè)變量的邏輯函數有2ⁿ個(gè)最小項 ，因此一個(gè)變量的邏輯函數有兩個(gè)最小項。
　　比如有一個(gè)變量Ｄ，其邏輯函數Ｌ的最小項表達式為：

　　其中Ｄ和是兩個(gè)最小項，分別記為m₁和m₀，即m₀=D，m₁=D。這兩個(gè)最小項可用兩個(gè)相鄰的方格來(lái)表示，如下圖所示。方格上的Ｄ和分別表示原變量和非變量。為了簡(jiǎn)明起見(jiàn)，非變量可以不標出，只標出原變量Ｄ。但是還可以進(jìn)一步簡(jiǎn)化，也就是將m₀，m₁只用其下標編號來(lái)表示。

　　若變量的個(gè)數為兩個(gè)，則最小項個(gè)數為2²=4項，函數的最小項表達式為
　　由于有４個(gè)最小項，可用４個(gè)相鄰的方格來(lái)表示。這４個(gè)方格可以由折疊了的１變量卡諾圖展開(kāi)來(lái)獲得，如下圖所示，變量Ｄ標在圖的底下，標的規律符合展開(kāi)的規律，即中間兩格底下為Ｄ，兩邊的兩格底下為。而變量Ｃ可標在展開(kāi)后新的兩個(gè)方格的頂上,以保持左邊的第一格仍為m₀項，即維持展開(kāi)前兩方格最小項序號不改變。由圖中可看到一個(gè)規律：新的方格內最小項的編號比對應的原方格增加了2^n-1＝2^2-1＝2。按照這個(gè)規律折疊時(shí)，方格1后面為方格３,方格０后面為方格２，展開(kāi)后即得圖示的２變量卡諾圖。

綜上所述，可歸納“折疊展開(kāi)”的法則如下：
　?、傩略黾拥姆礁癜凑归_(kāi)方向應標以新變量。
　?、谛碌姆礁駜茸钚№椌幪枒獮檎归_(kāi)前對應方格編號加2^n-1。
　　按照同樣的方法，可從折疊的２變量卡諾圖展開(kāi)獲得３變量卡諾圖。３變量邏輯函數L(B, C, D)應有８個(gè)最小項，可用８個(gè)相鄰的方格來(lái)表示。新增加的 ４個(gè)方格按展開(kāi)方向應標以新增加的變量B（以區別于原來(lái)的變量C、D）。而且，新增加的方格內最小項的編號為展開(kāi)前對應方格編號加2^n-1=2^3-1=4，這樣即可獲得３變量卡諾圖如下：

　　同理，可得４變量卡諾圖，如下圖所示。

　　在使用時(shí)，只要熟悉了卡諾圖上各變量的取值情況（即方格外各變量A、B、C、D等取值的區域），就可直接填入對應的最小項。

　　將上圖中的數碼編號與最小項的編號——對應，可以得到下面這種形式的卡諾圖。

2.卡諾圖的特點(diǎn)

　　上面所得各種變量的卡諾圖，其共同特點(diǎn)是可以直接觀(guān)察相鄰項
。也就是說(shuō)，各小方格對應于各變量不同的組合，而且上下左右在幾何上相鄰的方格內只有一個(gè)因子有差別，這個(gè)重要特點(diǎn)成為卡諾圖化簡(jiǎn)邏輯函數的主要依據。在卡諾圖水平方向的同一行里，最左和最右端的方格也是符合上述相鄰規律的，例如，m₄和m₆的差別僅在C和。同樣，垂直方向同一列里最上端和最下端兩個(gè)方格也是相鄰的，這是因為都只有一個(gè)因子有差別。這個(gè)特點(diǎn)說(shuō)明卡諾圖呈現循環(huán)鄰接的特性。

3.已知邏輯函數畫(huà)卡諾圖

　　根據邏輯函數的最小項表達式和卡諾圖的一般形式，就可以得到相應的卡諾圖。
　例如，要畫(huà)出邏輯函數的卡諾圖時(shí)，可根據４變量卡諾圖，對上列邏輯函數最小項表達式中的各項，在卡諾圖相應方格內填入１，其余填入０，即可得到如下圖所示的Ｌ的卡諾圖。

例：畫(huà)出
的卡諾圖
解：
　?。?）利用摩根定律，可以將上式化簡(jiǎn)為：

　?。?）因上式中最小項之和為Ｌ，故對Ｌ中的各最小項，在卡諾圖相應方格內應填入０，其余填入１，即得下圖所示的卡諾圖。

四、用卡諾圖化簡(jiǎn)邏輯函數

1.化簡(jiǎn)的依據

　　我們知道，卡諾圖具有循環(huán)鄰接的特性，若圖中兩個(gè)相鄰的方格均為1，則這兩個(gè)相鄰最小項的和將消去一個(gè)變量。
　　比如４變量卡諾圖中的方格５和方格７，它們的邏輯加是，項消去了變量Ｃ，即消去了相鄰方格中不相同的那個(gè)因子。若卡諾圖中４個(gè)相鄰的方格為１，則這４個(gè)相鄰的最小項的和將消去兩個(gè)變量，如上述４變量卡諾圖中的方格２、３、７、６，它們的邏輯加是

　　消去了變量Ｂ和Ｄ，即消去相鄰４個(gè)方格中不相同的那兩個(gè)因子
，這樣反復應用的關(guān)系，就可使邏輯表達式得到簡(jiǎn)化。這就是利用卡諾圖法化簡(jiǎn)邏輯函數的某本原理。

2.化簡(jiǎn)的步驟

用卡諾圖化簡(jiǎn)邏輯函數的步驟如下：
　?。?）將邏輯函數寫(xiě)成最小項表達式。
　?。?）按最小項表達式填卡諾圖 ，凡式中包含了的最小項，其對應方格填1，其余方格填0。
　?。?）合并最小項，即將相鄰的1方格圈成一組（包圍圈），每一組含2ⁿ個(gè)方格，對應每個(gè)包圍圈寫(xiě)成一個(gè)新的乘積項。
　?。?）將所有包圍圈對應的乘積項相加。
　　有時(shí)也可以由真值表直接填卡諾圖，以上的（1）、（2）兩步就合為一步。

畫(huà)包圍圈時(shí)應遵循以下原則：
　?。?）包圍圈內的方格數必定是2ⁿ個(gè)，n等于0、1、2、3、…。
　?。?）相鄰方格包括上下底相鄰，左右邊相鄰和四角相鄰。
　?。?）同一方格可以被不同的包圍圈重復包圍 ，但新增包圍圈中一定要有新的方格，否則該包圍圈為多余。
　?。?）包圍圈內的方格數要盡可能多，包圍圈的數目要盡可能少。

　　化簡(jiǎn)后，一個(gè)包圍圈對應一個(gè)與項（乘積項），包圍圈越大，所得乘積項中的變量越少。實(shí)際上，如果做到了使每個(gè)包圍圈盡可能大
，結果包圍圈個(gè)數也就會(huì )少，使得消失的乘積項個(gè)數也越多，就可以獲得最簡(jiǎn)的邏輯函數表達式。下面通過(guò)舉列來(lái)熟悉用卡諾圖化簡(jiǎn)邏輯函數的方法。

　　例: 一個(gè)邏輯電路的輸入是４個(gè)邏輯變量Ａ、Ｂ、Ｃ、Ｄ ，它的真值表如下，用卡諾圖法求化簡(jiǎn)的與一或表達式及與非一與非表達式。

解：
　?。?）由真值表畫(huà)出卡諾圖，如下圖所示。

　?。?）畫(huà)包圍圈合并最小項，得簡(jiǎn)化的與一或表達式。

　?。?） 求與非一與非表達式。

　　二次求非然后利用摩根定律得

　　利用卡諾圖表示邏輯函數式時(shí)，如果卡諾圖中各小方格被１占去了大部分，雖然可用包圍１的方法進(jìn)行化簡(jiǎn)，但由于要重復利用１項
，往往顯得零亂而易出錯。這時(shí)采用包圍０的方法化簡(jiǎn)更為簡(jiǎn)單。即求出非函數再對求非，其結果相同，下面舉例說(shuō)明。

例：化簡(jiǎn)下列邏輯函數

解：
　?。?）由Ｌ畫(huà)出卡諾圖，如圖所示。

　?。?）用包圍１的方法化簡(jiǎn)，如下圖所示，得

　　所以有：

　?。?）用包圍０的方法化簡(jiǎn)，如圖所示，

　　根據圖得到：，兩邊去反后可得：
　　兩種方法得到的結果是相同的。
　　實(shí)際中經(jīng)常會(huì )遇到這樣的問(wèn)題，在真值表內對應于變量的某些取值下，函數的值可以是任意的，或者這些變量的取值根本不會(huì )出現，這些變量取值所對應的最小項稱(chēng)為無(wú)關(guān)項或任意項。
　　無(wú)關(guān)項的意義在于，它的值可以?。盎蛉。?，具體取什么值，可以根據使函數盡量得到簡(jiǎn)化而定。