卡諾圖化簡邏輯函數

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

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

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

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

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

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

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

8、卡諾圖上合并的過程。因此根據卡諾圖化簡法的基本原理，我們可以得到化簡是否達到最簡形式的判定標準：是否選擇了盡可能少的方格群，且每個方格群是否盡可能的大。3 卡諾圖法化簡邏輯函數的一般步驟3.1 將邏輯函數化為最小項表達式當邏輯函數不是最小項表達式時，可以用配項法將邏輯函數化為最小項表達式。這樣才可以填入卡諾圖并用卡諾圖法化簡。例如：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 由最小項表達式畫出卡諾圖例如上面給出的F（A，B，C，D）= m（6，9，12，13，14，15）。根據此最小項表達式畫出對應的卡諾圖：AB圖（4）CD000111100000100100111100101001103.3 畫圈，合并相鄰的最小項相鄰最小項用矩形圈圈起來，稱為卡諾圈。畫卡諾圈所遵循的規(guī)則為：（1）必須包含所有的最小項；（2）按照從小到大順序，先圈孤立的“1”，即先圈孤立的最小項，再圈只能兩個組合的，再圈只能四個組合的，依此類推；每個卡諾圈內包含最小項的數目應是2的冪，2n個相鄰的最小項之和可以合并成一個“與”項，并消去i個因子。（3）圈的

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

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

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

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

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

15、化簡問題時，能充分的體現出其優(yōu)越性。但是在面對多變量邏輯函數化簡時就會力不從心。這里簡單介紹一個化簡5變量和6變量的卡諾圖化簡法。卡諾圖形式表示的4變量以上的邏輯函數，必須采取二維以上的表示方法，才可能保證全部僅有一個變量發(fā)生變化的方格幾何相鄰。N維卡諾圖可以用來描述具有2N個變量的邏輯函數。對于多變量的邏輯函數，可以采取多維表示法。例如5變量的邏輯函數采用三維卡諾圖，三維卡諾圖通常又展開為多個二維卡諾圖。以下列邏輯函數為例：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）將此邏輯函數拆分成A

16、=0和A=1兩組4變量邏輯函數的化簡。如下式：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 兩張圖化簡之后的邏輯函數分別為：FA=1（B，C，D，E）= DE + C FA=0（B，C，D，E）= DE + C + ABD則最終的化簡結果為兩次化簡的結果相或，即：F = FA=1 + FA=0 = DE + C + ABD這就是通過卡諾圖化簡5輸入變量邏輯函數的方法。如果是6輸入變量，則分為4幅卡諾圖。而當輸入變量繼續(xù)增加時，利用卡諾圖化簡邏輯函數的工作量會變得十分巨大，卡諾圖化簡法在此時也就失去了意義。所以我們更多的時候還是在輸入變量小于等于