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

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

1.最小項的基本概念

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

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

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

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

3.最小項的編號

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

二、邏輯函數(shù)的最小項表達式

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

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

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

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

1.卡諾圖的引出

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

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

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

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

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

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

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

2.卡諾圖的特點

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

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

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

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

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

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

1.化簡的依據(jù)

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

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

2.化簡的步驟

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

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

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

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

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

　　（2）畫包圍圈合并最小項，得簡化的與一或表達式。

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

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

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

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

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

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

　　所以有：

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

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