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

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

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

m0

m1

m2

m3

m4

m5

m6

m7

m12

m13

m14

m15

m8

m9

m10

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

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

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

ACD

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

0

0

1

01001110010111011100111000ABC0100011110

1

110

0

0

0

0

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

0

0

1

01001110010111011100111000ABC0100011110

1

110

0

0

0

0ABABCF=ABC+AB得：第十四頁(yè)，共五十四頁(yè)，2022年，8月28日K圖的特點(diǎn)

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

k圖中行、列兩組變量取值按循環(huán)碼規(guī)律排列，使變量各最小項(xiàng)之間具有邏輯相鄰性。上下左右?guī)缀蜗噜彽姆礁駜?nèi)，只有一個(gè)因子不同有三種幾何相鄰：鄰接、相對(duì)（行列兩端）和對(duì)稱（圖中以0、1分割線為對(duì)稱軸）方格均屬相鄰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卡諾圖化簡(jiǎn)函數(shù)規(guī)則：幾何相鄰的2i（i=1、2、3…n）個(gè)小格可合并在一起構(gòu)成正方形或矩形圈，消去i個(gè)變量，而用含（n-i）個(gè)變量的積項(xiàng)標(biāo)注該圈。第十五頁(yè)，共五十四頁(yè)，2022年，8月28日第十六頁(yè)，共五十四頁(yè)，2022年，8月28日卡諾圖化簡(jiǎn)的依據(jù)

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

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

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

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

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

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

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

的最簡(jiǎn)或與式