《卡諾圖化簡(jiǎn)法》PPT課件

1、2003-10-4數(shù)字電子技術(shù)基礎(chǔ)課程教學(xué)輔助系統(tǒng)是助教型多媒體課件，供教師上課使用。本課件是模擬課件的姐妹篇，目前正在聯(lián)系出版，考慮版權(quán)問(wèn)題，網(wǎng)上只給出了一小部分課程內(nèi)容。供評(píng)審專家審閱。用鼠標(biāo)點(diǎn)擊左下方或右下方的播放按鍵，即可播放。按盤上的“”鍵，前進(jìn)；按“”鍵后退；按“Esc”鍵，再用鼠標(biāo)點(diǎn)擊屏幕右上角的“”，可退出。在播動(dòng)畫(huà)時(shí)，如提示有病毒，可按“確定”鍵播放。1.4 卡諾圖化簡(jiǎn)法卡諾圖化簡(jiǎn)法1.4.1 卡諾圖卡諾圖 1.3.2 邏輯函數(shù)如何填入卡諾圖邏輯函數(shù)如何填入卡諾圖1.3.3 卡諾圖化簡(jiǎn)步驟卡諾圖化簡(jiǎn)步驟mi1.4 卡諾圖化簡(jiǎn)法1.4.1 1.4.1 卡諾圖卡諾圖 1.4.1.

2、1 1.4.1.1 卡諾圖的構(gòu)成卡諾圖的構(gòu)成 卡諾圖是最小項(xiàng)按一定規(guī)律陳列的方格圖，每一個(gè)最小項(xiàng)占有一個(gè)小方格。由于最小項(xiàng)的數(shù)目與變量數(shù)有關(guān)，設(shè)變量數(shù)為n，那么最小項(xiàng)的數(shù)目為2n 。二個(gè)變量的卡諾圖見(jiàn)以下圖所示。圖中第一行表示 ，第二行表示A；第一列表示 ，第二列表示B。這樣四個(gè)小方格就由四個(gè)最小項(xiàng)分別對(duì)號(hào)占有，行和列的符號(hào)相交就以最小項(xiàng)的與邏輯方式記入該方格中。ABABABA BA BA BA B( )a11000 00 11 01 1( )bAB0123mi 掌握卡諾圖的構(gòu)成特點(diǎn)，就可以從印在表格旁邊的AB、CD的“0、“1值直接寫(xiě)出最小項(xiàng)的文字符號(hào)內(nèi)容。例如在四變量卡諾圖中，第四行第二列

3、相交的小方格。000111100132675412131514891110A BCD000111100000010011001000001001101110101000110111111110110001010111011001 表格第四行的“AB標(biāo)為“10，應(yīng)記為 ，第二列的“CD標(biāo)為“01，記為 ，所以該小格為 。BADCDCBA10000111( )b10BCA00000110011010001111110101326754( )aAABCBCBCBCABC AAABCBCBCABC A BC A BC A BC這是三變量卡諾圖mi1.4.1.2 鄰接與化簡(jiǎn)的關(guān)系 卡諾圖為什么可以用來(lái)化

4、簡(jiǎn)？這與最小項(xiàng)的陳列滿足鄰接關(guān)系有關(guān)。由于在最小項(xiàng)相加時(shí)，相鄰兩項(xiàng)就可以提出項(xiàng)，從而消去一個(gè)變量。以四變量為例，m12與m13相鄰接，那么m12+m13為：CABDDCABDCABDCAB)(000111100132675412131514891110A BCD000111100000010011001000001001101110101000110111111110110001010111011001 卡諾圖的是按鄰接規(guī)律構(gòu)建的，在幾何位置上相鄰的小格是鄰接的。同時(shí)，第一行和第四行也是鄰接的；第一列和第四列也是鄰接的；四個(gè)角也是鄰接的。所以，在卡諾圖中只需將有關(guān)的最小項(xiàng)重新陳列、組合，就也能

5、夠消去一些變量，使邏輯函數(shù)得到化簡(jiǎn)。ABCBCDABDmi1.4.2 1.4.2 邏輯函數(shù)如何填入卡諾圖邏輯函數(shù)如何填入卡諾圖 1.4.2.1 1.4.2.1 與項(xiàng)如何填入卡諾圖與項(xiàng)如何填入卡諾圖 例如，將邏輯式填入卡諾圖。它為一個(gè)三變量的邏輯式，結(jié)果見(jiàn)以下圖。CABCBACBAP),(10ABC0010000100011110001100CBA11 1101CAB1. 與項(xiàng)是最小項(xiàng)的方式 與項(xiàng)是最小項(xiàng)時(shí)，按最小項(xiàng)編號(hào)的位置直接填入。mi與項(xiàng)不是最小項(xiàng)的方式，按鄰接關(guān)系直接填入卡諾圖。例如與項(xiàng)不是最小項(xiàng)的方式，按鄰接關(guān)系直接填入卡諾圖。例如2. 與項(xiàng)不是最小項(xiàng)的方式ABDCDADCBAP),(

6、先填 ,CDA這是CD;這是 A , 所以 處于第一第二行和第三列的交點(diǎn)上二行一列。CDA再填 ,ABD這是AB ，這是D 。00011110ABCD0001111011110011 所以 處于第一第二行和第三列的交點(diǎn)上二行一列。CDA 所以ABD處于第三行和第二、第三列的交點(diǎn)上一行二列。113715111300mi00011110ABCD00011110例：將邏輯式P= + 填入卡諾圖CBDB先填 ，CB這是B，這是 ；C11111100CB 這一與項(xiàng)處于第二、第三行和第一、第二列的交點(diǎn)處二行二列。DB再填 ，B這是 ，D這是 。0000DB 這一與項(xiàng)處于第一、第四行和第一、第四列的交點(diǎn)處二

7、行二列。1111mi例：將邏輯式 填入卡諾圖DABCBPAB00011110CD000111101111CBBC11ABDABD填CB填DABmi 000111101ABCD00011110111000111101ABCD000111101111111例：將邏輯式 填入卡諾圖CABPABD 由上述各例題可以看出，與項(xiàng)中變量數(shù)越少，在卡諾圖中占的小格越多； 最小項(xiàng)在卡諾圖中占1個(gè)小格；與最小項(xiàng)相比，少一個(gè)變量占二個(gè)小格；少二個(gè)變量占四個(gè)小格；少三個(gè)變量占八個(gè)小格，。mi 卡諾圖中的與項(xiàng)對(duì)應(yīng)的小格，只能一個(gè)一組；二個(gè)一組；四個(gè)一組；八個(gè)一組，即按2i 的規(guī)律組成矩形帶。i為短少的變量數(shù)。以四變量為

8、例，與項(xiàng)只需一個(gè)變量，即缺3個(gè)變量，應(yīng)占23個(gè)小格，且組成一個(gè)矩形帶；與項(xiàng)只需二個(gè)變量，即缺2個(gè)變量，應(yīng)占22個(gè)小格，且組成一個(gè)矩形帶；與項(xiàng)只需三個(gè)變量，即缺1個(gè)變量，應(yīng)占21個(gè)小格，且組成一個(gè)矩形帶。 我們的義務(wù)是化簡(jiǎn)邏輯函數(shù)，將與或型邏輯函數(shù)填入卡諾圖后，這樣原來(lái)的邏輯函數(shù)就以最小項(xiàng)的容顏出如今卡諾圖中。然后，經(jīng)過(guò)重新組合，將具有“1的小格按照 2i 的規(guī)律盡能夠大地圈成矩形帶。這樣新得到的邏輯函數(shù)能夠會(huì)更簡(jiǎn)單一些。 下面我們來(lái)討論如何用卡諾圖進(jìn)展化簡(jiǎn)。也就是如何重新組合帶有“1的小格，如何盡能夠大地圈成矩形帶，以得到最簡(jiǎn)與或邏輯式。mi1.4.3 1.4.3 卡諾圖化簡(jiǎn)步驟卡諾圖化簡(jiǎn)步驟

9、 1.4.3.1 如何使與項(xiàng)最簡(jiǎn) 由前面的討論可知，卡諾圖中的矩形帶包括的小格越多，對(duì)應(yīng)的與項(xiàng)的變量數(shù)就越少。所以一個(gè)需求化簡(jiǎn)的邏輯函數(shù)，填入卡諾圖后，經(jīng)過(guò)重新組合，圈出的矩形帶應(yīng)越大越好。CACBAP 該邏輯式能否最簡(jiǎn)？顯然不是最簡(jiǎn)方式，由于CBCACBAABACCACBAP)()(000111101ABCD0001111011111 顯然 對(duì)應(yīng)下面四個(gè)小格； 對(duì)應(yīng)上面四個(gè)小格，中間二個(gè)小格被覆蓋，屬于公共享有。 CACB所以，為使與項(xiàng)最簡(jiǎn)，圈矩形帶時(shí)，小格可以公用，相互覆蓋。 例如左圖假設(shè)把上面兩個(gè)小方格圈在一同有 ，下面四個(gè)小方格圈在一同有 ，于是邏輯式為：CBACACBCAmi1.4.

10、3.2 關(guān)于覆蓋 000111101ABCD000111101111111 但是在小格覆蓋時(shí)，需求留意，每一個(gè)矩形帶中至少要 有一個(gè)小格是獨(dú)立的，即沒(méi)有被其他矩形帶所覆蓋。CBACDAABCDCABD 例如以下圖中，四個(gè)矩形帶對(duì)應(yīng)的與項(xiàng)分別是CBACDAABC 中間的四個(gè)小格圈成的矩形帶對(duì)應(yīng)的與項(xiàng)BD雖然最簡(jiǎn)， 但 BD 對(duì)應(yīng)的四個(gè)小格一一被其他四個(gè)矩形帶所覆蓋，所以就應(yīng)從最簡(jiǎn)與或式中取消，最簡(jiǎn)與或式為DCAABCCDACBAPDCAmi 總之，一個(gè)矩形帶中的一切小格最少要有一個(gè)未被覆蓋，這個(gè)矩形帶所代表的與項(xiàng)才是化簡(jiǎn)后的與或型邏輯式中不可短少的項(xiàng)。反之，一個(gè)矩形帶中的一切小格都被其它矩形帶所

11、覆蓋，那么這個(gè)矩形帶所代表的與項(xiàng)就不是獨(dú)立的，假設(shè)寫(xiě)入與或型邏輯式中就是多余的。 卡諾圖化簡(jiǎn)法的步驟如下： 1邏輯式填入卡諾圖，假設(shè)邏輯式不是與或型，先將邏輯式轉(zhuǎn)換為與或型。 2照最小的原那么，盡能夠?qū)⒕匦螏Υ笠恍?3選出至少有一個(gè)小格是獨(dú)立的矩形帶，寫(xiě)出它們所對(duì)應(yīng)的最簡(jiǎn)與項(xiàng)的邏輯和。 4如有脫漏，添上脫漏小格所對(duì)應(yīng)的一個(gè)最簡(jiǎn)與項(xiàng)，它們的邏輯和就是最簡(jiǎn)化的與或型邏輯式。動(dòng)畫(huà)1-1動(dòng)畫(huà)1-2mi例例: :化簡(jiǎn)化簡(jiǎn)DBADCAABCBAP00011110ABCD00011110111111111110111101001100000111101ABCD00011110111111111化簡(jiǎn)結(jié)果D

12、CADBACBAP00011110181917162021232230312928262725241000110001000000101011100110001010111111011100111001110101010001mi 000111100132675412131514891110A BCD000111100000010011001000001001101110101000110111111110110001010111011001EE最小項(xiàng)編號(hào)變量按EABCD順序0001111018191716202123223031292826272524100011000100000010101110011000101011111101110