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

1、數(shù)字電子技術(shù)課程研討卡諾圖化簡邏輯函數(shù)的方法和理論依據(jù)摘要：從最小項(xiàng)的定義和性質(zhì)入手，簡述卡諾圖化簡邏輯函數(shù)的理論依據(jù)以及化簡是否達(dá)到最簡形式的判定標(biāo)準(zhǔn)。通過舉例來解釋利用卡諾圖化簡少變量邏輯函數(shù)的一般方法，以及卡諾圖在數(shù)字電子技術(shù)中其他應(yīng)用。另外介紹一種多變量邏輯函數(shù)的卡諾圖解法。關(guān)鍵詞：卡諾圖；最小項(xiàng)；邏輯函數(shù)化簡；多變量0 引言在邏輯電路的分析和設(shè)計(jì)中，經(jīng)常會(huì)遇到邏輯函數(shù)的化簡問題。如果利用常規(guī)的公式法化簡，除需要掌握大量的基本公式外，還需要能夠靈活、交替地運(yùn)用各種方法，方可求得最簡結(jié)果，而且有時(shí)不易判斷是否已簡化到最簡形式，技巧性較強(qiáng)，對使用者的要求較高。當(dāng)所需化簡的邏輯函數(shù)輸入變量較

2、少時(shí)（一般不大于4個(gè)），利用科諾圖化簡法可以更簡單、直接的得到邏輯函數(shù)的最簡表達(dá)式。因此邏輯函數(shù)的卡諾圖化簡法在實(shí)際分析、設(shè)計(jì)電路時(shí)有很廣泛的應(yīng)用。1 最小項(xiàng)定義及其性質(zhì)1.1最小項(xiàng)的定義設(shè)有n個(gè)邏輯變量，由它們組成具有n個(gè)變量的“與”項(xiàng)中，每個(gè)變量以原變量或者反變量的形式出現(xiàn)一次且僅出現(xiàn)一次，則稱這個(gè)與項(xiàng)為最小項(xiàng)。對于n個(gè)變量來說，可有2n個(gè)最小項(xiàng)。任何一個(gè)邏輯函數(shù)均可表示成惟一的一組最小項(xiàng)之和，稱它為標(biāo)準(zhǔn)的與或表達(dá)式，也稱為最小項(xiàng)表達(dá)式。對于任意一個(gè)最小項(xiàng)，只有一組變量取值使它的值為1，而變量的其他取值都使該最小項(xiàng)為0。事實(shí)上，真值表的每一行對應(yīng)著一個(gè)最小項(xiàng)。表（1）中列出了最小項(xiàng)取值為1

3、時(shí)，各輸入變量的取值。我們約定：將最小項(xiàng)為l時(shí)各輸入變量的取值視為二進(jìn)制，其對應(yīng)的十進(jìn)制i作為最小項(xiàng)的編號(hào)，并把該最小項(xiàng)記作mi。如A、B、C三個(gè)變量有2n =8個(gè)最小項(xiàng)，如表（1）所示。圖（1）最小項(xiàng)最小項(xiàng)為1時(shí)變量的值i的值miABCABC0000m0ABC0011m1ABC0102m2ABC0113m3ABC1004m4ABC1015m5ABC1106m6ABC1117m71.2最小項(xiàng)的性質(zhì)最小項(xiàng)具有以下三個(gè)性質(zhì)：(1)全體最小項(xiàng)之和為1；(2)任意兩個(gè)最小項(xiàng)之積為0；(3)若兩個(gè)最小項(xiàng)之間只有一個(gè)變量不同，即在一個(gè)最小項(xiàng)中是原變量，在另一個(gè)最小項(xiàng)中是反變量，其余各變量均相同，則稱這兩個(gè)

4、最小項(xiàng)是相鄰項(xiàng)。兩個(gè)相鄰的最小項(xiàng)之和可以合并成一個(gè)與項(xiàng)，并消去一個(gè)因子。這一性質(zhì)很重要，這正是用卡諾圖化簡邏輯函數(shù)的邏輯依據(jù)。如：ABC+ABC=（A+A）BC=BC。2 卡諾圖2.1 卡諾圖把真值表中的最小項(xiàng)重新排列，把它們排列成矩陣形式，并且使矩陣的橫方向和縱方向的布爾變量按格雷碼的順序排列，這樣構(gòu)成的圖形就是卡諾圖?？ㄖZ圖是邏輯函數(shù)的一種圖形表示。將一個(gè)邏輯函數(shù)的最小項(xiàng)表達(dá)式中的各最小項(xiàng)相應(yīng)地填入一個(gè)方格圖內(nèi)，此方格圖即為卡諾圖。卡諾圖是一種平面方格圖，每個(gè)小方格代表一個(gè)最小項(xiàng)，故又稱為最小項(xiàng)方格圖?？ㄖZ圖的實(shí)質(zhì)就是真值表的圖形化，使得最小項(xiàng)排列得更緊湊，更便于化簡?？ㄖZ圖中最小項(xiàng)的排列

5、方案不是惟一的；變量的坐標(biāo)值0表示相應(yīng)變量的反變量，1表示相應(yīng)變量的原變量；各小方格依變量順序取坐標(biāo)值，所得二進(jìn)制數(shù)對應(yīng)的十進(jìn)制數(shù)即相應(yīng)最小項(xiàng)的下標(biāo)i。對應(yīng)于一組n個(gè)邏輯變量，則函數(shù)共有2n個(gè)最小項(xiàng)。如果把每個(gè)最小項(xiàng)用一個(gè)小方格表示，再將這些小方格以格雷碼順序排列，就可以構(gòu)成n個(gè)變量的卡諾圖。下面兩圖展示了3輸入變量和4輸入變量的卡諾圖表示：AB圖（2）CD000111100026411375圖（3）CD00011110000412801151391137151110261410AB2.2 卡諾圖的特點(diǎn)卡諾圖是邏輯函數(shù)的一種圖形表示，卡諾圖的圖形特征表現(xiàn)出了它的特點(diǎn)?？ㄖZ圖的特點(diǎn)主要有以下三點(diǎn)

6、：（1）卡諾圖中的每個(gè)小方格對應(yīng)一個(gè)最小項(xiàng)。（2）具有循環(huán)相鄰的特性，即卡諾圖中同一行里最左和最右端的小方格是相鄰的，同一列里最上和最下端的小方格也是相鄰的。（3）邏輯相鄰的最小項(xiàng)在幾何位置上也相鄰，這個(gè)特性是由于我們對變量的排布采用的是格雷碼。 每個(gè)2輸入變量的最小項(xiàng)有兩個(gè)最小項(xiàng)與它相鄰； 每個(gè)3輸入變量的最小項(xiàng)有三個(gè)最小項(xiàng)與它相鄰； 每個(gè)4輸入變量的最小項(xiàng)有四個(gè)最小項(xiàng)與它相鄰。2.3 卡諾圖化簡的基本原理用卡諾圖化簡邏輯函數(shù)的基本原理就是把“相鄰的最小項(xiàng)之和可以合并成一個(gè)與項(xiàng)，并消去因子”的邏輯依據(jù)和卡諾圖的圖形特征結(jié)合起來，通過把卡諾圖上表征相鄰最小項(xiàng)的相鄰小方格“圈”在一起進(jìn)行合并，達(dá)

7、到用一個(gè)簡單“與”項(xiàng)代替若干最小項(xiàng)的目的。2.4 卡諾圖化簡的性質(zhì)（1）卡諾圖上任何21標(biāo)1的相鄰最小項(xiàng)，可以合并為一個(gè)“與”項(xiàng)，并消去一個(gè)變量。（2）卡諾圖上任何22標(biāo)l的相鄰最小項(xiàng)，可以合并為一個(gè)“與”項(xiàng)，并消去二個(gè)變量。（3）卡諾圖上任何23標(biāo)1的相鄰最小項(xiàng)，可以合并為一個(gè)“與”項(xiàng)，并消去三個(gè)變量。可見，相鄰最小項(xiàng)的數(shù)目必須為2i個(gè)才能合并成一個(gè)“與”項(xiàng)，并消去ib變量。2.5 邏輯函數(shù)是否達(dá)到最簡表達(dá)式的判斷方法與-或式最簡的標(biāo)準(zhǔn)是：首先表達(dá)式中的與項(xiàng)最少，其次是與項(xiàng)中的變量最少，在卡諾圖上體現(xiàn)為：甩最少量的且盡可能大的圈覆蓋函數(shù)的全部最小項(xiàng)。函數(shù)化簡過程就是按最簡的標(biāo)準(zhǔn)將相鄰最小項(xiàng)在

8、卡諾圖上合并的過程。因此根據(jù)卡諾圖化簡法的基本原理，我們可以得到化簡是否達(dá)到最簡形式的判定標(biāo)準(zhǔn)：是否選擇了盡可能少的方格群，且每個(gè)方格群是否盡可能的大。3 卡諾圖法化簡邏輯函數(shù)的一般步驟3.1 將邏輯函數(shù)化為最小項(xiàng)表達(dá)式當(dāng)邏輯函數(shù)不是最小項(xiàng)表達(dá)式時(shí)，可以用配項(xiàng)法將邏輯函數(shù)化為最小項(xiàng)表達(dá)式。這樣才可以填入卡諾圖并用卡諾圖法化簡。例如：F（A，B，C，D）= AB+BCD+ACD+ABD = AB（C+C）（D+D）+ BCD（A+A）+ACD（B+B）+ABD（C+C） =ABCD+ ABCD+ ABCD+ ABCD+ ABCD+ ABCD+ ABCD+ ABCD+ ABCD+ ABCD= m（

9、6，9，12，13，14，15）3.2 由最小項(xiàng)表達(dá)式畫出卡諾圖例如上面給出的F（A，B，C，D）= m（6，9，12，13，14，15）。根據(jù)此最小項(xiàng)表達(dá)式畫出對應(yīng)的卡諾圖：AB圖（4）CD000111100000100100111100101001103.3 畫圈，合并相鄰的最小項(xiàng)相鄰最小項(xiàng)用矩形圈圈起來，稱為卡諾圈。畫卡諾圈所遵循的規(guī)則為：（1）必須包含所有的最小項(xiàng)；（2）按照從小到大順序，先圈孤立的“1”，即先圈孤立的最小項(xiàng)，再圈只能兩個(gè)組合的，再圈只能四個(gè)組合的，依此類推；每個(gè)卡諾圈內(nèi)包含最小項(xiàng)的數(shù)目應(yīng)是2的冪，2n個(gè)相鄰的最小項(xiàng)之和可以合并成一個(gè)“與”項(xiàng)，并消去i個(gè)因子。（3）圈的

10、圈數(shù)要盡可能少(與項(xiàng)總數(shù)要少)；（4）圈要盡可能大(與項(xiàng)含的因子最少)，不論是否與其他圈相重，也要盡可能地畫大，相重是指同一塊區(qū)域可以重復(fù)圈多次，但每個(gè)圈至少要包含一個(gè)尚未被圈過的1。 按照上面規(guī)則，圈出上面給出的卡諾圖中可以合并的最小項(xiàng)。如下圖所示：AB圖（5）CD000111100000100100111100101001103.4 由卡諾圖寫出最簡與-或表達(dá)式在圈出的合并項(xiàng)所處位置上，若某變量的取值有0也有1，則該變量被消去，否則該變量被保留，并按0為反變量，1為原變量的原則寫成一個(gè)“與”項(xiàng)。也就是根據(jù)卡諾圖的性質(zhì)合并相鄰最小項(xiàng)，并消去變量。有幾個(gè)卡諾圈就有幾個(gè)“與”項(xiàng)，而后把這些“與”

11、項(xiàng)“或”起來，就得到給定邏輯函數(shù)的最簡“與-或”表達(dá)式了。因此，上圖合并最小項(xiàng)之后的最簡表達(dá)式為：F（A，B，C，D）= BCD + ACD + AB3.5 無關(guān)項(xiàng)的處理當(dāng)我們在設(shè)計(jì)邏輯電路時(shí)，經(jīng)常會(huì)遇到邏輯函數(shù)的某些變量的值可以是任意的，或者這些變量的取值根本不會(huì)出現(xiàn)，這些變量所對應(yīng)的最小項(xiàng)稱為無關(guān)項(xiàng)或任意項(xiàng)。既然無關(guān)項(xiàng)的值可以是任意的，或者說這個(gè)變量取何值對電路的設(shè)計(jì)沒有影響，所以在化簡邏輯函數(shù)時(shí)，它們的值既可以取0也可以取1。具體取什么值，要根據(jù)具體的情況而定，目的是盡量能使函數(shù)得到最大程度的簡化。4 卡諾圖的其他應(yīng)用4.1 卡諾圖在消除競爭-冒險(xiǎn)現(xiàn)象時(shí)的應(yīng)用競爭-冒險(xiǎn)是組合邏輯電路中經(jīng)

12、常發(fā)生的一種現(xiàn)象，需要采取恰當(dāng)?shù)拇胧┘右韵?。例如在電路中除采取引入封鎖脈沖、引人選通脈沖、接人濾波電容等。此外還可以采取修改邏輯設(shè)計(jì)的方法，實(shí)際上是增加函數(shù)的冗余項(xiàng)。即利用卡諾圖化簡邏輯函數(shù)時(shí)，考慮到消除競爭-冒險(xiǎn)，適當(dāng)增加冗余項(xiàng)，就可以使邏輯電路達(dá)到消除競爭-冒險(xiǎn)的效果。例如：邏輯函數(shù)的卡諾圖如下。AB圖（6）CD00011110000010011110110111100100如果按上面的方式畫圈，雖然滿足卡諾圖化簡邏輯函數(shù)的基本規(guī)則，但是由于八個(gè)最小項(xiàng)組成的四個(gè)圈彼此相切不相交，這樣根據(jù)化簡后的邏輯函數(shù)組成的邏輯電路極易出現(xiàn)競爭-冒險(xiǎn)現(xiàn)象。為了避免這種情況，我們在畫圈時(shí)把中間的四個(gè)最小項(xiàng)

13、也用一個(gè)大圈圈起來。如下圖（7）所示。這樣雖然會(huì)增加一個(gè)冗余項(xiàng)BD，但是可以有效地消除邏輯電路中出現(xiàn)的競爭-冒險(xiǎn)現(xiàn)象。AB圖（7）CD00011110000010011110110111100100AB4.2 利用卡諾圖進(jìn)行邏輯函數(shù)運(yùn)算利用卡諾圖，可實(shí)現(xiàn)邏輯函數(shù)之間與、或、異或等邏輯運(yùn)算。下面以邏輯函數(shù)Y1和Y2為例加以說明：首先在一個(gè)卡諾圖中將邏輯函數(shù)Y1表示出來，再在另一個(gè)卡諾圖中將邏輯函數(shù)Y2表示出來。兩邏輯函數(shù)Y1和Y2進(jìn)行與運(yùn)算時(shí)，只需將兩個(gè)卡諾圖中對應(yīng)方格的最小項(xiàng)做與運(yùn)算，再用上面講到的方法對運(yùn)算后的卡諾圖化簡，所得既兩邏輯函數(shù)與運(yùn)算后的結(jié)果。同理，兩邏輯函數(shù)Y1和Y2進(jìn)行或或者異

14、或運(yùn)算時(shí)，只需將兩個(gè)卡諾圖中對應(yīng)方格的最小項(xiàng)做相同運(yùn)算，再用上面講到的方法對運(yùn)算后的卡諾圖化簡，所得既兩邏輯函數(shù)運(yùn)算后的結(jié)果。4.3 利用卡諾圖求反函數(shù)利用卡諾圖求反函數(shù)的方法與卡諾圖法化簡邏輯函數(shù)類似。不同的是求反函數(shù)時(shí)需要合并消去的是值為0的最小項(xiàng)。4.4 利用卡諾圖求最簡或與式 做出關(guān)于邏輯函數(shù)最大項(xiàng)的卡諾圖，利用圈0的方法，即與上文化簡邏輯函數(shù)時(shí)用的圈1法類似，只不過圈的是值為0的項(xiàng)。每一個(gè)圈寫成一個(gè)或項(xiàng)，再把所有的或項(xiàng)相與，即得化簡后的或與式。此外還可以用卡諾圖配合相應(yīng)的器件設(shè)計(jì)組合邏輯電路以及時(shí)序邏輯電路。5 多變量函數(shù)的卡諾圖化簡法前面已經(jīng)講到，卡諾圖在解決不大于4變量的邏輯函數(shù)

15、化簡問題時(shí)，能充分的體現(xiàn)出其優(yōu)越性。但是在面對多變量邏輯函數(shù)化簡時(shí)就會(huì)力不從心。這里簡單介紹一個(gè)化簡5變量和6變量的卡諾圖化簡法。卡諾圖形式表示的4變量以上的邏輯函數(shù)，必須采取二維以上的表示方法，才可能保證全部僅有一個(gè)變量發(fā)生變化的方格幾何相鄰。N維卡諾圖可以用來描述具有2N個(gè)變量的邏輯函數(shù)。對于多變量的邏輯函數(shù)，可以采取多維表示法。例如5變量的邏輯函數(shù)采用三維卡諾圖，三維卡諾圖通常又展開為多個(gè)二維卡諾圖。以下列邏輯函數(shù)為例：F(A，B，C，D，E)= （0，4，5，6，7，8，12，13，14，15，16，18，19，20，21，22，23，24，28，29，30，31）將此邏輯函數(shù)拆分成A

16、=0和A=1兩組4變量邏輯函數(shù)的化簡。如下式：FA=0（B，C，D，E）= （0，4，5，6，7，8，12，13，14，15）和 FA=1（B，C，D，E）= （16, 18, 19, 20, 21, 22, 23, 24, 28, 29, 30, 31）它們各自的卡諾圖如圖（8）和圖（9）所示：圖（8）BC00011110001000011111111111101000DE圖（9）BC00011110001011011111111111101000DE 兩張圖化簡之后的邏輯函數(shù)分別為：FA=1（B，C，D，E）= DE + C FA=0（B，C，D，E）= DE + C + ABD則最終的化簡結(jié)果為兩次化簡的結(jié)果相或，即：F = FA=1 + FA=0 = DE + C + ABD這就是通過卡諾圖化簡5輸入變量邏輯函數(shù)的方法。如果是6輸入變量，則分為4幅卡諾圖。而當(dāng)輸入變量繼續(xù)增加時(shí)，利用卡諾圖化簡邏輯函數(shù)的工作量會(huì)變得十分巨大，卡諾圖化簡法在此時(shí)也就失去了意義。所以我們更多的時(shí)候還是在輸入變量小于等于