邏輯函數(shù)的卡諾圖化簡法

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

1.最小項(xiàng)的基本概念

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

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

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

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

3.最小項(xiàng)的編號

　　最小項(xiàng)通常用m_i表示，下標(biāo)i即最小項(xiàng)編號 ，用十進(jìn)制數(shù)表示。以ABC為例，因?yàn)樗?11相對應(yīng)，所以就稱ABC是和變量取值011相對應(yīng)的最小項(xiàng)，而011相當(dāng)于十進(jìn)制中的3，所以把ABC記為m₃按此原則，3個(gè)變量的最小項(xiàng)

二、邏輯函數(shù)的最小項(xiàng)表達(dá)式

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

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

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

三、用卡諾圖表示邏輯函數(shù)

1.卡諾圖的引出

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

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

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

綜上所述，可歸納“折疊展開”的法則如下：
　　①新增加的方格按展開方向應(yīng)標(biāo)以新變量。
　?、谛碌姆礁駜?nèi)最小項(xiàng)編號應(yīng)為展開前對應(yīng)方格編號加2^n-1。
　　按照同樣的方法，可從折疊的２變量卡諾圖展開獲得３變量卡諾圖。３變量邏輯函數(shù)L(B, C, D)應(yīng)有８個(gè)最小項(xiàng)，可用８個(gè)相鄰的方格來表示。新增加的 ４個(gè)方格按展開方向應(yīng)標(biāo)以新增加的變量B（以區(qū)別于原來的變量C、D）。而且，新增加的方格內(nèi)最小項(xiàng)的編號為展開前對應(yīng)方格編號加2^n-1=2^3-1=4，這樣即可獲得３變量卡諾圖如下：

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

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

　　將上圖中的數(shù)碼編號與最小項(xiàng)的編號——對應(yīng)，可以得到下面這種形式的卡諾圖。

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

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

3.已知邏輯函數(shù)畫卡諾圖

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

例：畫出
的卡諾圖
解：
　　（1）利用摩根定律，可以將上式化簡為：

　?。?）因上式中最小項(xiàng)之和為Ｌ，故對Ｌ中的各最小項(xiàng)，在卡諾圖相應(yīng)方格內(nèi)應(yīng)填入０，其余填入１，即得下圖所示的卡諾圖。

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

1.化簡的依據(jù)

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

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

2.化簡的步驟

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

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

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

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

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

　　（2）畫包圍圈合并最小項(xiàng)，得簡化的與一或表達(dá)式。

　　（3） 求與非一與非表達(dá)式。

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

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

例：化簡下列邏輯函數(shù)

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

　?。?）用包圍１的方法化簡，如下圖所示，得

　　所以有：

　?。?）用包圍０的方法化簡，如圖所示，

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