邏輯函數的卡諾圖化簡法

由前面的學習得知，利用代數法可以使邏輯函數變成較簡單的形式。但要求熟練掌握邏輯代數的基本定律，而且需要一些技巧，特別是經化簡後得到的邏輯表達式是否是最簡式較難確定。運用卡諾圖法可以較簡便的方法得到最簡表達式。但首先需要了解最小項的概念。

一、最小項的定義及其性質

1.最小項的基本概念

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

2.最小項的性質

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

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

3.最小項的編號

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

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

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

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

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

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

1.卡諾圖的引出

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

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

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

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

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

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

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

2.卡諾圖的特點

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

3.已知邏輯函數畫卡諾圖

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

　

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

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

四、用卡諾圖化簡邏輯函數

1.化簡的依據

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

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

2.化簡的步驟

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

畫包圍圈時應遵循以下原則：
　　（1）包圍圈內的方格數必定是2ⁿ個，n等於0、1、2、3、…。
　　（2）相鄰方格包括上下底相鄰，左右邊相鄰和四角相鄰。
　　（3）同一方格可以被不同的包圍圈重複包圍 ，但新增包圍圈中一定要有新的方格，否則該包圍圈為多餘。
　　（4）包圍圈內的方格數要儘可能多，包圍圈的數目要儘可能少。

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

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

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

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

　　（3） 求與非一與非表達式。

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

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

例：化簡下列邏輯函數

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

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

　　所以有：

　　（3）用包圍０的方法化簡，如圖所示，

　　根據圖得到：，兩邊去反後可得：
　　兩種方法得到的結果是相同的。
　　實際中經常會遇到這樣的問題，在真值表內對應於變量的某些取值下，函數的值可以是任意的，或者這些變量的取值根本不會出現，這些變量取值所對應的最小項稱為無關項或任意項。
　　無關項的意義在於，它的值可以取０或取１，具體取什麼值，可以根據使函數儘量得到簡化而定。