布爾代數(shù)及邏輯函數(shù)化簡

布爾代數(shù)及邏輯函數(shù)化簡第1頁，共54頁，2023年，2月20日，星期四但是在變量多了之后，邏輯相鄰項(xiàng)會比較難找，而卡諾圖正好解決了這個(gè)問題：利用圖形法找出相鄰關(guān)系，即在圖形上相鄰的項(xiàng)也就是邏輯相鄰項(xiàng)。二、邏輯函數(shù)的標(biāo)準(zhǔn)式1、最小項(xiàng)對于一個(gè)給定變量數(shù)目的邏輯函數(shù)，所有變量參加相“與”的項(xiàng)叫做最小項(xiàng)。每個(gè)變量只能以原變量和反變量的形式出現(xiàn)一次一變量最小項(xiàng)：第2頁，共54頁，2023年，2月20日，星期四一變量最小項(xiàng)：二變量最小項(xiàng)：個(gè)個(gè)22N變量最小項(xiàng)：個(gè)2N2、最小項(xiàng)標(biāo)準(zhǔn)式全是由最小項(xiàng)組成的與或式。F=ABC+ABC+ABC+ABCF=ABC+BC+AC標(biāo)準(zhǔn)式一般式未必全部最小項(xiàng)第3頁，共54頁，2023年，2月20日，星期四最小項(xiàng)具有唯一性，而一般式具有多樣性。3、一般式轉(zhuǎn)換為標(biāo)準(zhǔn)式（1）代數(shù)法（拆項(xiàng)）第4頁，共54頁，2023年，2月20日，星期四（2）真值表法（拆項(xiàng)）ABCABCBCACF00010010010000010000001101011000011101000011000111110101第5頁，共54頁，2023年，2月20日，星期四4、最小項(xiàng)表示方法當(dāng)變量為0時(shí)，以反變量的形式出現(xiàn)當(dāng)變量為1時(shí)，以原變量的形式出現(xiàn)第6頁，共54頁，2023年，2月20日，星期四5、最小項(xiàng)性質(zhì)：②任意兩個(gè)不同的最小項(xiàng)的邏輯乘恒為0，即③n變量的每一個(gè)最小項(xiàng)有n個(gè)相鄰項(xiàng)。例如，三變量的某一最小項(xiàng)有三個(gè)相鄰項(xiàng)：。這種相鄰關(guān)系對于邏輯函數(shù)化簡十分重要。①n變量的全部最小項(xiàng)的邏輯和恒為1，即第7頁，共54頁，2023年，2月20日，星期四三、卡諾圖結(jié)構(gòu)（K圖）圖中的一小格對應(yīng)真值表中的一行，即對應(yīng)一個(gè)最小項(xiàng)，又稱真值圖AB00011011

m0

m1

m2

m3AABBABBAABABAB1010

m0

m1

m2

m3

miABC01000111100001111000011110

m0

m1

m2

m3

m4

m5

m6

m7

m0

m1

m2

m3

m4

m5

m6

m7

m12

m13

m14

m15

m8

m9

m10

m11ABCD二變量K圖三變量K圖四變量K圖第8頁，共54頁，2023年，2月20日，星期四K圖具有如下特點(diǎn)：①

n變量的卡諾圖有2n個(gè)方格，對應(yīng)表示2n個(gè)最小項(xiàng)。每當(dāng)變量數(shù)增加一個(gè)，卡諾圖的方格數(shù)就擴(kuò)大一倍。②卡諾圖中任何幾何位置相鄰的兩個(gè)最小項(xiàng)，在邏輯上都是相鄰的。由于變量取值的順序按格雷碼排列，保證了各相鄰行(列)之間只有一個(gè)變量取值不同，從而保證畫出來的最小項(xiàng)方格圖具有這一重要特點(diǎn)。所謂幾何相鄰，一是相接，即緊挨著；二是相對，即任意一行或一列的兩頭；三是相重，即對折起來位置重合。所謂邏輯相鄰，是指除了一個(gè)變量不同外其余變量都相同的兩個(gè)與項(xiàng)。第9頁，共54頁，2023年，2月20日，星期四0001111000011110

m0

m1

m2

m3

m4

m5

m6

m7

m12

m13

m14

m15

m8

m9

m10

m11ABCD四變量K圖第10頁，共54頁，2023年，2月20日，星期四四、邏輯函數(shù)的卡諾圖表示

1、先化為最小項(xiàng)表達(dá)式，并在相應(yīng)的方格內(nèi)填1，其余填0.2、直接將一般式畫在圖上。ABC

00011110011111第11頁，共54頁，2023年，2月20日，星期四例：將F(A、B、C、D)用卡諾圖表示解：0100011110001110CDABAB111111BCD11

ACD

ABC11AC1111m14,m15兩次填10000圖形法化簡函數(shù)第12頁，共54頁，2023年，2月20日，星期四例：圖中給出輸入變量A、B、C的真值表，填寫函數(shù)的卡諾圖ABCF000

0

0

1

01001110010111011100111000ABC0100011110

1

110

0

0

0

0

010111001110第13頁，共54頁，2023年，2月20日，星期四例：圖中給出輸入變量A、B、C的真值表，填寫函數(shù)的卡諾圖ABCF000

0

0

1

01001110010111011100111000ABC0100011110

1

110

0

0

0

0ABABCF=ABC+AB得：第14頁，共54頁，2023年，2月20日，星期四K圖的特點(diǎn)

k圖為方形圖。n個(gè)變量的函數(shù)--k圖有2n個(gè)小方格，分別對應(yīng)2n個(gè)最小項(xiàng)；

k圖中行、列兩組變量取值按循環(huán)碼規(guī)律排列，使變量各最小項(xiàng)之間具有邏輯相鄰性。上下左右?guī)缀蜗噜彽姆礁駜?nèi)，只有一個(gè)因子不同有三種幾何相鄰：鄰接、相對（行列兩端）和對稱（圖中以0、1分割線為對稱軸）方格均屬相鄰0001111000011110

m0

m1

m2

m3

m4

m5

m6

m7

m12

m13

m14

m15

m8

m9

m10

m11ABCD四變量K圖兩個(gè)相鄰格圈在一起，結(jié)果消去一個(gè)變量ABD

ADA1四個(gè)相鄰格圈在一起，結(jié)果消去兩個(gè)變量八個(gè)相鄰格圈在一起，結(jié)果消去三個(gè)變量十六個(gè)相鄰格圈在一起，結(jié)果mi=1卡諾圖化簡函數(shù)規(guī)則：幾何相鄰的2i（i=1、2、3…n）個(gè)小格可合并在一起構(gòu)成正方形或矩形圈，消去i個(gè)變量，而用含（n-i）個(gè)變量的積項(xiàng)標(biāo)注該圈。第15頁，共54頁，2023年，2月20日，星期四第16頁，共54頁，2023年，2月20日，星期四卡諾圖化簡的依據(jù)

相鄰項(xiàng)相加時(shí)，反復(fù)應(yīng)用，公式，函數(shù)表達(dá)式的項(xiàng)數(shù)和每項(xiàng)所含的因子數(shù)就會減小.第17頁，共54頁，2023年，2月20日，星期四多余圈—不允許出現(xiàn)，否則不是最簡形式第18頁，共54頁，2023年，2月20日，星期四五、與或表達(dá)式的簡化步驟先將函數(shù)填入相應(yīng)的卡諾圖中，存在的最小項(xiàng)對應(yīng)的方格填1，其它填0。合并：按作圈原則將圖上填1的方格圈起來，要求圈的數(shù)量少、范圍大，圈可重復(fù)包圍但每個(gè)圈內(nèi)必須有新的最小項(xiàng)。每個(gè)圈寫出一個(gè)乘積項(xiàng)。最后將全部積項(xiàng)邏輯加即得最簡與或表達(dá)式畫出邏輯電路圖第19頁，共54頁，2023年，2月20日，星期四【例】求F=m(1,3,4,5,10,11,12,13)的最簡與或式。解：①畫出F的K圖∑②畫K圈。第20頁，共54頁，2023年，2月20日，星期四③寫出最簡式。④畫出邏輯電路圖。第21頁，共54頁，2023年，2月20日，星期四【例】求的最簡與或式。解：①畫出F的K圖。給出的F為一般與或式，將每個(gè)與項(xiàng)所覆蓋的最小項(xiàng)都填1，K圖如圖所示。第22頁，共54頁，2023年，2月20日，星期四②畫K圈化簡函數(shù)。③寫出最簡與或式。按圖(b)圈法：該例說明，邏輯函數(shù)的最簡式不是惟一的。本例有兩種圈法，都可以得到最簡式。按圖(a)圈法：第23頁，共54頁，2023年，2月20日，星期四六、其他邏輯形式化簡

1、與非邏輯步驟利用卡諾圖法求出最簡與或式兩次取反，摩根定律畫出邏輯電路圖第24頁，共54頁，2023年，2月20日，星期四例：將與或結(jié)果用與非門實(shí)現(xiàn)。邏輯電路圖：&&&&BCABCABDF第25頁，共54頁，2023年，2月20日，星期四例：將F(A、B、C、D)化為最簡與非式解：0100011110001110CDAB111111111111ACADBCBDABC化簡得：最簡與非式為：第26頁，共54頁，2023年，2月20日，星期四2、或與邏輯步驟在卡諾圖上求反函數(shù)得出原函數(shù)，摩根定律畫出邏輯電路圖和與或式相反第27頁，共54頁，2023年，2月20日，星期四例：將化簡為最簡或與式。（1）在卡諾圖上求反函數(shù)1111111110000000(2)原函數(shù)第28頁，共54頁，2023年，2月20日，星期四關(guān)于最大項(xiàng)最大項(xiàng)：n個(gè)變量的最大項(xiàng)是n個(gè)變量的“或項(xiàng)”，其中每個(gè)變量必須而且只能以原變量或反變量的形式出現(xiàn)一次兩變量A,B的最大項(xiàng)三變量A,B,C的最大項(xiàng)n個(gè)變量有2n個(gè)最大項(xiàng)第29頁，共54頁，2023年，2月20日，星期四M7M611111076最大項(xiàng)二進(jìn)制數(shù)十進(jìn)制數(shù)編號最大項(xiàng)的編號：通常用Mi表示最大項(xiàng)，M表示最大項(xiàng),下標(biāo)i為最大項(xiàng)編號。第30頁，共54頁，2023年，2月20日，星期四相同變量構(gòu)成的兩個(gè)不同最大項(xiàng)的和為1。即Mi+Mj=1(i≠j)全部最大項(xiàng)之積為0，即對于任意一個(gè)最大項(xiàng)，僅有一組變量取值使這個(gè)最大項(xiàng)值為0，并且，最大項(xiàng)不同，使其值為0的變量取值不同最大項(xiàng)的性質(zhì)：第31頁，共54頁，2023年，2月20日，星期四第32頁，共54頁，2023年，2月20日，星期四任何一個(gè)邏輯函數(shù)既可以等于其卡諾圖上填1的那些最小項(xiàng)之和，也可以等于其卡諾圖上填0的那些最大項(xiàng)之積，因此，如果要求出某函數(shù)的最簡或與式，可以在該函數(shù)的卡諾圖上合并那些填0的相鄰項(xiàng)。這種方法簡稱為圈0合并，其化簡步驟及化簡原則與圈1合并類同，只要按圈逐一寫出或項(xiàng)，然后將所得的或項(xiàng)相與即可。但需注意，或項(xiàng)由K圈對應(yīng)的沒有變化的那些變量組成，當(dāng)變量取值為0時(shí)寫原變量，取值為1時(shí)寫反變量。第33頁，共54頁，2023年，2月20日，星期四或與邏輯化簡方法2步驟畫出卡諾圖，圈0項(xiàng)得出最大項(xiàng)表達(dá)式畫出邏輯電路圖第34頁，共54頁，2023年，2月20日，星期四【例】求的最簡或與式。①畫出F的K圖②圈K圈。圈0合并，其規(guī)律與圈1相同，即K圈的數(shù)目應(yīng)最少，K圈所覆蓋的0格應(yīng)盡可能多。

解：③寫出最簡或與式。④畫出邏輯電路圖第35頁，共54頁，2023年，2月20日，星期四【例】

求的最簡或與式。解：①畫出F的K圖。本例給出的F為一般或與式，因此將每個(gè)或項(xiàng)所覆蓋的最大項(xiàng)都填0.②圈K圈化簡函數(shù)。③寫出最簡或與式。④畫出電路圖。第36頁，共54頁，2023年，2月20日，星期四3、或非邏輯步驟先求出或與式兩次取反，摩根定律畫出邏輯電路圖第37頁，共54頁，2023年，2月20日，星期四例：寫出最簡或非式。第38頁，共54頁，2023年，2月20日，星期四3、與或非邏輯步驟先求出與或式兩次摩根定律，不展開畫出邏輯電路圖先求出反函數(shù)得出原函數(shù)畫出邏輯電路圖方法1方法2多一個(gè)反相器第39頁，共54頁，2023年，2月20日，星期四七、非完全描述邏輯函數(shù)的化簡邏輯問題分為完全描述和非完全描述兩種。如果對于輸入變量的每一組取值，邏輯函數(shù)都有確定的值，則稱這類函數(shù)為完全描述邏輯函數(shù)。如果輸入變量的某些取值不允許出現(xiàn)，那么這類函數(shù)稱為非完全描述的邏輯函數(shù)，此時(shí)函數(shù)值可以為0，也可以為1(通常將函數(shù)值記為?或×)。第40頁，共54頁，2023年，2月20日，星期四非完全描述邏輯函數(shù)真值表ABCF000001010011100101110111010×0××1無關(guān)項(xiàng)第41頁，共54頁，2023年，2月20日，星期四無關(guān)項(xiàng)發(fā)生在以下兩種情況：①由于某種條件的限制(或約束)使得輸入變量的某些組合不可能出現(xiàn)，因而在這些取值下對應(yīng)的函數(shù)值是“無關(guān)”緊要的，它可以為1，也可以為0。②某些輸入變量取值所產(chǎn)生的輸出并不影響整個(gè)系統(tǒng)的功能，因此可以不必考慮其輸出是0還是1。非完全描述邏輯函數(shù)一般用以下方法表示：①在真值表或K圖中填?或×，表示函數(shù)值為0或1均可。②在邏輯表達(dá)式中用約束條件來表示。第42頁，共54頁，2023年，2月20日，星期四例如，十字路口的交通燈規(guī)定紅燈停，綠燈行，黃燈要注意(即黃燈一亮，未過停車線的車輛也須停車)。若以變量A、B、C分別表示紅、黃、綠燈的狀態(tài)，且以燈亮為1，燈滅為0，用F表示停車與否，且以停車為1，通行為0，則F是A、B、C的函數(shù)。如果規(guī)定不允許有兩個(gè)以上的燈同時(shí)亮，則A、B、C三個(gè)變量的取值組合只可能是000、001、010、100，而不應(yīng)出現(xiàn)011、101、110、111這四種情況，即A與B、A與C、B與C、A與B與C不可能同時(shí)為1，所以A、B、C是一組具有約束的變量，其相互約束關(guān)系可以表示為，AB=0、BC=0、AC=0、ABC=0，即AB+BC+AC+ABC=0，或?qū)懗?3,5,6,7)=0。式中的最小項(xiàng)就是我們所說的無關(guān)項(xiàng)。第43頁，共54頁，2023年，2月20日，星期四

【例】化簡以下邏輯函數(shù)。第44頁，共54頁，2023年，2月20日，星期四例：已知函數(shù)：

求其最簡與或式0100011110001110CDAB解：填函數(shù)的卡諾圖111111100000化簡不考慮約束條件時(shí)：考慮約束條件時(shí)：0100011110001110CDAB111111100000第45頁，共54頁，2023年，2月20日，星期四

【例】試化簡邏輯函數(shù)為最簡或與式，并用與或非門實(shí)現(xiàn)電路。解：③將函數(shù)F變換為最簡與或非式。②圈0求得F

的最簡或與式。①