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

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

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

m0

m1

m2

m3

m4

m5

m6

m7

m12

m13

m14

m15

m8

m9

m10

m11ABCD四變量K圖第十頁，共五十四頁，2022年，8月28日四、邏輯函數(shù)的卡諾圖表示

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

00011110011111第十一頁，共五十四頁，2022年，8月28日例：將F(A、B、C、D)用卡諾圖表示解：0100011110001110CDABAB111111BCD11

ACD

ABC11AC1111m14,m15兩次填10000圖形法化簡函數(shù)第十二頁，共五十四頁，2022年，8月28日例：圖中給出輸入變量A、B、C的真值表，填寫函數(shù)的卡諾圖ABCF000

0

0

1

01001110010111011100111000ABC0100011110

1

110

0

0

0

0

010111001110第十三頁，共五十四頁，2022年，8月28日例：圖中給出輸入變量A、B、C的真值表，填寫函數(shù)的卡諾圖ABCF000

0

0

1

01001110010111011100111000ABC0100011110

1

110

0

0

0

0ABABCF=ABC+AB得：第十四頁，共五十四頁，2022年，8月28日K圖的特點

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

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

m0

m1

m2

m3

m4

m5

m6

m7

m12

m13

m14

m15

m8

m9

m10

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

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

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

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

解：③寫出最簡或與式。④畫出邏輯電路圖第三十五頁，共五十四頁，2022年，8月28日【例】

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

【例】化簡以下邏輯函數(shù)。第四十四頁，共五十四頁，2022年，8月28日例：已知函數(shù)：

求其最簡與或式0100011110001110CDAB解：填函數(shù)的卡諾圖111111100000化簡不考慮約束條件時：考慮約束條件時：0100011110001110CDAB111111100000第四十五頁，共五十四頁，2022年，8月28日

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

的最簡或與式