第一章開關(guān)理論(PPT)

1、1.4 布爾代數(shù)布爾代數(shù)1.4.1 布爾代數(shù)的基本定律布爾代數(shù)的基本定律 公理、定律與常用公式公理、定律與常用公式公理公理交換律交換律結(jié)合律結(jié)合律分配律分配律0-1律律重疊律重疊律互補(bǔ)律互補(bǔ)律非非律非非律摩根律摩根律0 0 = 00 1 =1 0 =0 1 1 = 10 + 0 = 00 + 1 =1 + 0 =1 1 + 1 = 1A B = B A A + B = B + A (A B ) C = A (B C) (A+ B )+ C = A+ (B+ C) 自等律自等律A ( B + C ) = A B+ A C A + B C =( A + B) (A+ C )A 0=0 A+ 1=1

2、A 1=A A+ 0=AA A=0 A+A=1A A=A A+ A=AA B= A+B A+ B=AB A= A吸收律吸收律消因律消因律包含律包含律合并律合并律A B+ A B =A (A+ B) (A+ B) =A A+A B=A A (A+B)=AA+ A B =A+B A (A+ B) =A B AB+ A C +BC= AB+ A C(A+B)( A+ C )(B+C)= (A+B)(A +C)函數(shù)證明函數(shù)證明 方法方法1利用真值表利用真值表例：用真值表證明摩根定律例：用真值表證明摩根定律A BA BAB A+ BA BA+B000110111110111010001000 A B=

3、A+B A+ B=ABBCCAABB)C(1AC)AB(1CAAB等式右邊等式右邊 由此可以看出：與或表達(dá)式中，兩個(gè)乘積項(xiàng)分由此可以看出：與或表達(dá)式中，兩個(gè)乘積項(xiàng)分別包含別包含同一因子同一因子的的原原變量和變量和反反變量，而兩項(xiàng)的剩余變量，而兩項(xiàng)的剩余因子包含在第三個(gè)乘積項(xiàng)中，則第三項(xiàng)是多余的。因子包含在第三個(gè)乘積項(xiàng)中，則第三項(xiàng)是多余的。CAABBCDECAAB公式可推廣：公式可推廣：例：證明包含律例：證明包含律CAABBCCAAB成立。成立。BC)AA(CAAB利用基本定律利用基本定律函數(shù)證明函數(shù)證明 方法方法2ABACABCABC1.4.2 布爾代數(shù)的三個(gè)基本規(guī)則布爾代數(shù)的三個(gè)基本規(guī)則 代

4、入規(guī)則代入規(guī)則：任何一個(gè)含有某變量的等式，如果任何一個(gè)含有某變量的等式，如果等等式式中所有出現(xiàn)此中所有出現(xiàn)此變量變量的位置均代之以的位置均代之以一個(gè)一個(gè)邏輯函數(shù)式邏輯函數(shù)式，則此等式依然成立，則此等式依然成立例：例： A B= A+BBCBC替代替代B B得得ABCBCACBA由此摩根定律能推廣到由此摩根定律能推廣到n n個(gè)變量：個(gè)變量：n 21n 21n 21n 21AAAAAAAAAA A A利用摩根定律（1 1）代入規(guī)則）代入規(guī)則（2 2）反演規(guī)則）反演規(guī)則 反演規(guī)則反演規(guī)則：對(duì)于任意一個(gè)邏輯函數(shù)式對(duì)于任意一個(gè)邏輯函數(shù)式F F，做如下處理：，做如下處理： 若把式中的運(yùn)算符若把式中的運(yùn)算符

5、“. .”換成換成“+ +”, “”, “+ +” ” 換成換成“. .”;”; 常量常量“0 0”換成換成“1 1”，“1 1”換成換成“0 0”； 原原變量換成變量換成反反變量，變量，反反變量換成變量換成原原變量變量那么得到的那么得到的新函數(shù)式新函數(shù)式稱為原函數(shù)式稱為原函數(shù)式F F的的反函數(shù)式反函數(shù)式。注意：注意： 保持原函數(shù)的運(yùn)算次序保持原函數(shù)的運(yùn)算次序-先與后或，必要時(shí)適當(dāng)?shù)丶尤肜ㄌ?hào)。先與后或，必要時(shí)適當(dāng)?shù)丶尤肜ㄌ?hào)。 不屬于單個(gè)變量上的非號(hào)有兩種處理方法：不屬于單個(gè)變量上的非號(hào)有兩種處理方法： 非號(hào)保留，而非號(hào)下面的函數(shù)式按反演規(guī)則變換；非號(hào)保留，而非號(hào)下面的函數(shù)式按反演規(guī)則變換； 將

6、非號(hào)去掉，而非號(hào)下的函數(shù)式保留不變。將非號(hào)去掉，而非號(hào)下的函數(shù)式保留不變。例：例：F(AF(A、B B、C)C)CBAB )C A(BA 其反函數(shù)為其反函數(shù)為)CBA(BCA)BA(F或或)CBA(B)CA()BA(F 對(duì)偶式對(duì)偶式：對(duì)于任意一個(gè)邏輯函數(shù)，做如下處理：對(duì)于任意一個(gè)邏輯函數(shù)，做如下處理：1 1）若把式中的運(yùn)算符）若把式中的運(yùn)算符“. .”換成換成“+ +”，“+ +”換成換成“. .”；2 2）常量）常量“0 0”換成換成“1 1”，“1 1”換成換成“0 0”。得到新函數(shù)式為原函數(shù)式得到新函數(shù)式為原函數(shù)式F F的對(duì)偶式的對(duì)偶式FF，也稱對(duì)偶函數(shù)。，也稱對(duì)偶函數(shù)。 對(duì)偶規(guī)則：對(duì)偶

7、規(guī)則：如果兩個(gè)函數(shù)式相等，則它們對(duì)應(yīng)的對(duì)偶式也相如果兩個(gè)函數(shù)式相等，則它們對(duì)應(yīng)的對(duì)偶式也相等。即等。即 若若 F F1 1 = F = F2 2 則則F F1 1= F= F2 2。使公式的。使公式的數(shù)目增加一倍。數(shù)目增加一倍。 求對(duì)偶式時(shí)求對(duì)偶式時(shí)運(yùn)算順序不變運(yùn)算順序不變，且它只，且它只變變換換運(yùn)算符運(yùn)算符和常量和常量，其，其變量變量是是不變不變的。的。注意：注意： 函數(shù)式中有函數(shù)式中有“ ”和和“”運(yùn)算符，求反函數(shù)運(yùn)算符，求反函數(shù)及對(duì)偶函數(shù)時(shí)，要將運(yùn)算符及對(duì)偶函數(shù)時(shí)，要將運(yùn)算符“ ”換成換成“”， “”換成換成“ ”。 例：例：B1CAABF 其對(duì)偶式：其對(duì)偶式：)B 0() CA ()B

8、A(F（3 3）對(duì)偶規(guī)則）對(duì)偶規(guī)則 五種常用表達(dá)式五種常用表達(dá)式F(AF(A、B B、C)C)CAAB“與與或或”式式)BA)(CA(“或或與與”式式CAAB“與非與非與非與非”式式 BACA“或非或非或非或非”式式BACA“與與或或非非”式式基本形式基本形式 表達(dá)式形式轉(zhuǎn)換表達(dá)式形式轉(zhuǎn)換CA AB F CAABCAAB利用非非律利用非非律利用摩根律利用摩根律1.4.3 利用布爾代數(shù)化簡(jiǎn)邏輯函數(shù)利用布爾代數(shù)化簡(jiǎn)邏輯函數(shù)補(bǔ)充：邏輯函數(shù)的五種常用表達(dá)式及其轉(zhuǎn)換補(bǔ)充：邏輯函數(shù)的五種常用表達(dá)式及其轉(zhuǎn)換函數(shù)的簡(jiǎn)化依據(jù)函數(shù)的簡(jiǎn)化依據(jù) 邏輯電路所用邏輯門的數(shù)量少；邏輯電路所用邏輯門的數(shù)量少； 每個(gè)邏輯門的輸

9、入端個(gè)數(shù)少；每個(gè)邏輯門的輸入端個(gè)數(shù)少； 邏輯電路構(gòu)成級(jí)數(shù)少；邏輯電路構(gòu)成級(jí)數(shù)少； 邏輯電路保證能可靠地工作。邏輯電路保證能可靠地工作。降低成本降低成本提高電路的工作提高電路的工作速度和可靠性速度和可靠性(1) 要求乘積項(xiàng)的數(shù)目最少要求乘積項(xiàng)的數(shù)目最少;(2) 滿足滿足(1)的條件下，每個(gè)乘積項(xiàng)中變量個(gè)數(shù)也最少。的條件下，每個(gè)乘積項(xiàng)中變量個(gè)數(shù)也最少。 總之總之：最簡(jiǎn)式的標(biāo)準(zhǔn)最簡(jiǎn)式的標(biāo)準(zhǔn) 首先是式中首先是式中乘積項(xiàng)最少；乘積項(xiàng)最少； 乘積項(xiàng)中含的變量少。乘積項(xiàng)中含的變量少。 與或表達(dá)式的化簡(jiǎn)與或表達(dá)式的化簡(jiǎn)主要化簡(jiǎn)方法主要化簡(jiǎn)方法方法：方法： 并項(xiàng)：并項(xiàng)： 利用利用ABAAB將兩項(xiàng)并為一項(xiàng)，將兩項(xiàng)

10、并為一項(xiàng)，且消去一個(gè)變量且消去一個(gè)變量B 吸收：吸收： 利用利用A + AB = A消去多余的項(xiàng)消去多余的項(xiàng)AB 配項(xiàng)：利用配項(xiàng)：利用CAABBCCAAB和互補(bǔ)律、和互補(bǔ)律、重疊律先增添項(xiàng)，再消去多余項(xiàng)重疊律先增添項(xiàng)，再消去多余項(xiàng)BC 消去：利用消去：利用BABAA消去多余因子消去多余因子 ACBDBDAACF例：例：簡(jiǎn)化函數(shù)：簡(jiǎn)化函數(shù)：解：解：CBDBDAACF利用摩根律利用摩根律)BA(DCBACABDCBAC配項(xiàng)加配項(xiàng)加ABABABDABCBAC消因律消因律DABCBAC消項(xiàng)消項(xiàng)ABABDCBAC 或與表達(dá)式的簡(jiǎn)化或與表達(dá)式的簡(jiǎn)化F（或與式）（或與式）求對(duì)偶式求對(duì)偶式 F （與或式）（與

11、或式）簡(jiǎn)化簡(jiǎn)化 F （最簡(jiǎn)與或式）（最簡(jiǎn)與或式）求對(duì)偶式求對(duì)偶式 F（最簡(jiǎn)最簡(jiǎn)或與式）或與式）例：例：試簡(jiǎn)化函數(shù)試簡(jiǎn)化函數(shù)解：解：)()(CBCABBCACACBABCACABFCACBABCACABF)(BCACABACACABAC 結(jié)合律結(jié)合律消因律消因律分配律分配律互補(bǔ)律互補(bǔ)律結(jié)合、互補(bǔ)律結(jié)合、互補(bǔ)律本小節(jié)主要講解布爾代數(shù)的定律與規(guī)則，本小節(jié)主要講解布爾代數(shù)的定律與規(guī)則，并利用這些定律和規(guī)則化簡(jiǎn)邏輯函數(shù)。并利用這些定律和規(guī)則化簡(jiǎn)邏輯函數(shù)。 本小節(jié)要求熟記布爾代數(shù)的定律與規(guī)則，本小節(jié)要求熟記布爾代數(shù)的定律與規(guī)則，掌握利用這些定律和規(guī)則化簡(jiǎn)邏輯函數(shù)。掌握利用這些定律和規(guī)則化簡(jiǎn)邏輯函數(shù)。 小結(jié)

12、小結(jié) 作業(yè)作業(yè)P3031T6、T7 、T81.5 卡諾圖卡諾圖1.5.1 邏輯函數(shù)的最小項(xiàng)表達(dá)式邏輯函數(shù)的最小項(xiàng)表達(dá)式最小項(xiàng)：最小項(xiàng)：n n個(gè)變量有個(gè)變量有2 2n n個(gè)最小項(xiàng)，記作個(gè)最小項(xiàng)，記作m mi i。例如：例如：3 3個(gè)變量有個(gè)變量有2 23 3（8 8）個(gè)最小項(xiàng)。個(gè)最小項(xiàng)。CBACBAm m0 0m m1 100000101CBABCACBACBACABABC m m2 2m m3 3m m4 4m m5 5m m6 6m m7 7010011100101110111234567n n個(gè)變量的邏輯函數(shù)中，包括個(gè)變量的邏輯函數(shù)中，包括全部全部n n個(gè)變量個(gè)變量的的乘積項(xiàng)乘積項(xiàng)（每個(gè)變

13、量必須而且只能以原變（每個(gè)變量必須而且只能以原變量或反變量的形式出現(xiàn)一次）。量或反變量的形式出現(xiàn)一次）。（1） 最小項(xiàng)的概念最小項(xiàng)的概念最小項(xiàng)最小項(xiàng)二進(jìn)制數(shù)二進(jìn)制數(shù)十進(jìn)制數(shù)十進(jìn)制數(shù)編號(hào)編號(hào)最小項(xiàng)編號(hào)最小項(xiàng)編號(hào)i是指各輸入是指各輸入變量取值看成二進(jìn)制數(shù)變量取值看成二進(jìn)制數(shù)對(duì)應(yīng)的十進(jìn)制數(shù)對(duì)應(yīng)的十進(jìn)制數(shù)0 0 1A B CA B C0 0 0m m0 0CBAm m1 1m m2 2m m3 3m m4 4m m5 5m m6 6m m7 7CBACBABCACBACBACABABC 1 -n20iimF1000000001000000110 1 00 1 11 0 01 0 11 1 01 1 1

14、000000000000100000010000001000000100000010000001111111三變量的最小項(xiàng)三變量的最小項(xiàng) （2）最小項(xiàng)）最小項(xiàng) 的性質(zhì)：的性質(zhì)： 任意任意兩個(gè)不同兩個(gè)不同最小項(xiàng)的最小項(xiàng)的乘積乘積為為0， 即即 mi mj=0 (ij)。 全部全部最小項(xiàng)之最小項(xiàng)之和和為為1，即，即120ii1mn 任意一組變量取值，任意一組變量取值，只有一個(gè)只有一個(gè)最小最小 項(xiàng)項(xiàng) 的值為的值為1，其它最小項(xiàng)的值均為，其它最小項(xiàng)的值均為0。 標(biāo)準(zhǔn)積之和標(biāo)準(zhǔn)積之和( 最小項(xiàng)）表達(dá)式最小項(xiàng)）表達(dá)式式中的每一個(gè)乘式中的每一個(gè)乘積項(xiàng)均為最小項(xiàng)積項(xiàng)均為最小項(xiàng)F(AF(A、B B、C C、D)

15、D)D C BADCBADC B AD C B A8510mmmm)8 5 1 0(m、例：例：求函數(shù)求函數(shù)F(AF(A、B B、C C、D)D)CB ABA的標(biāo)準(zhǔn)積之的標(biāo)準(zhǔn)積之和表達(dá)式和表達(dá)式解：解：F(AF(A、B B、C C、D)D)CB ABACB ABACB A)CC(BACB ACBABCA123mmm)3 2 1 (m、利用反演律利用反演律利用互補(bǔ)律，補(bǔ)利用互補(bǔ)律，補(bǔ)上所缺變量上所缺變量C A B C A B C0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1mi01234567FMi0123456700010111例：例：已知函數(shù)的真值表，寫出該

16、函數(shù)的標(biāo)準(zhǔn)積之和表達(dá)式已知函數(shù)的真值表，寫出該函數(shù)的標(biāo)準(zhǔn)積之和表達(dá)式 從真值表找出從真值表找出F為為1的對(duì)應(yīng)最小項(xiàng)的對(duì)應(yīng)最小項(xiàng)解解: 然后將這些項(xiàng)邏輯加然后將這些項(xiàng)邏輯加F(AF(A、B B、C)C)ABCCABCBABCA7653mmmm)7 6 5 3(m、（3）邏輯函數(shù)的標(biāo)準(zhǔn)形式邏輯函數(shù)的標(biāo)準(zhǔn)形式1.5.2 卡諾圖的結(jié)構(gòu)特點(diǎn)卡諾圖的結(jié)構(gòu)特點(diǎn)（一）（一） 1 1、2 2、3 3變量卡諾圖變量卡諾圖排列原則排列原則：任何兩個(gè)上下或左右相鄰的小方格對(duì)應(yīng)的兩個(gè)任何兩個(gè)上下或左右相鄰的小方格對(duì)應(yīng)的兩個(gè) 最小項(xiàng)中，有且僅有一個(gè)變量發(fā)生變化。最小項(xiàng)中，有且僅有一個(gè)變量發(fā)生變化。 （二）（二） 4 4變

17、量卡諾圖變量卡諾圖卡卡諾諾圖圖的的特特點(diǎn)點(diǎn)1.5.3 用卡諾圖化簡(jiǎn)函數(shù)用卡諾圖化簡(jiǎn)函數(shù) k k圖為方形圖。圖為方形圖。n n個(gè)變量的函數(shù)個(gè)變量的函數(shù)-k-k圖有圖有2 2n n個(gè)小方個(gè)小方格，分別對(duì)應(yīng)格，分別對(duì)應(yīng)2 2n n個(gè)最小項(xiàng)個(gè)最小項(xiàng)； k k圖中行、列兩組變量取值按循環(huán)碼規(guī)律排列，圖中行、列兩組變量取值按循環(huán)碼規(guī)律排列，使變量各最小項(xiàng)之間具有使變量各最小項(xiàng)之間具有邏輯相鄰性邏輯相鄰性。上下左右?guī)缀蜗噜彽姆礁裆舷伦笥規(guī)缀蜗噜彽姆礁駜?nèi)，只有一個(gè)因子不同內(nèi)，只有一個(gè)因子不同 有三種幾何相鄰：有三種幾何相鄰：鄰接、相對(duì)（行列兩端）和對(duì)鄰接、相對(duì)（行列兩端）和對(duì)稱稱（圖中以（圖中以0 0、1 1

18、分割線為對(duì)稱軸）方格均屬相鄰分割線為對(duì)稱軸）方格均屬相鄰0001111000011110 m0 m1 m2 m3 m4 m5 m6 m7 m12 m13 m14 m15 m8 m9 m10 m11ABCD四四變變量量卡卡諾諾圖圖兩個(gè)相鄰格圈在一起，兩個(gè)相鄰格圈在一起，結(jié)果消去一個(gè)變量結(jié)果消去一個(gè)變量ABD ADA1四個(gè)相鄰格圈在一起，四個(gè)相鄰格圈在一起，結(jié)果消去兩個(gè)變量結(jié)果消去兩個(gè)變量八個(gè)相鄰格圈在一起，八個(gè)相鄰格圈在一起，結(jié)果消去三個(gè)變量結(jié)果消去三個(gè)變量十六個(gè)相鄰格圈在十六個(gè)相鄰格圈在一起，結(jié)果一起，結(jié)果 mi=1卡諾圖化簡(jiǎn)函數(shù)規(guī)則：卡諾圖化簡(jiǎn)函數(shù)規(guī)則： 幾何相鄰的幾何相鄰的2i（i = 1

19、、2、3n）個(gè)小格）個(gè)小格可合可合并在一起構(gòu)成正方形或矩形圈，消去并在一起構(gòu)成正方形或矩形圈，消去i個(gè)變量，而個(gè)變量，而用含用含（n - i）個(gè)變量的積項(xiàng)標(biāo)注該圈個(gè)變量的積項(xiàng)標(biāo)注該圈。例：圖中給出輸入變量例：圖中給出輸入變量A、B、C的真值表，填寫函數(shù)的的真值表，填寫函數(shù)的 卡諾圖?？ㄖZ圖。ABCF000 0 0 1 01001110010111011100111000ABC0100011110 1 110 0 0 0 0 010111001110(1) 根據(jù)真值表填卡諾圖根據(jù)真值表填卡諾圖例：例：將將F(AF(A、B B、C C、D)D)ACBCADCBABDCA的卡諾圖填寫出來。的卡諾圖填

20、寫出來。解：解：0100011110001110CDABAB111111B CD11 ACD ABC11AC1111m14,m15兩次填兩次填10000(2) 根據(jù)函數(shù)表達(dá)式填卡諾圖根據(jù)函數(shù)表達(dá)式填卡諾圖(3) 用卡諾圖化簡(jiǎn)邏輯函數(shù)的步驟用卡諾圖化簡(jiǎn)邏輯函數(shù)的步驟 與或表達(dá)式的簡(jiǎn)化與或表達(dá)式的簡(jiǎn)化步步驟驟(1) 把邏輯函數(shù)變換為最小項(xiàng)表達(dá)式；把邏輯函數(shù)變換為最小項(xiàng)表達(dá)式；(2) 用卡諾圖表示邏輯函數(shù)：最小項(xiàng)表達(dá)式中用卡諾圖表示邏輯函數(shù)：最小項(xiàng)表達(dá)式中 各最小項(xiàng)對(duì)應(yīng)的各小方格填入各最小項(xiàng)對(duì)應(yīng)的各小方格填入“1”，其余的，其余的 填填 “0”或不填；或不填；(3) 合并相鄰合并相鄰“1”方格；方格

21、；(4) 將每個(gè)包圍圈所表示的乘積項(xiàng)邏輯加，可將每個(gè)包圍圈所表示的乘積項(xiàng)邏輯加，可 得與或表達(dá)式。得與或表達(dá)式。(4) 畫圈的要領(lǐng)畫圈的要領(lǐng)(1) (1) 包圍圈越大越好；包圍圈越大越好；(2) (2) 包圍圈個(gè)數(shù)越少越好；包圍圈個(gè)數(shù)越少越好；(3) (3) 同一個(gè)同一個(gè)“1”1”方格可以被圈多次；方格可以被圈多次；(4) (4) 每個(gè)包圍圈要有新成分；每個(gè)包圍圈要有新成分；(5) (5) 畫包圍圈時(shí)，先圈大，后圈?。划嫲鼑r(shí)，先圈大，后圈??；(6) (6) 不要遺漏任何不要遺漏任何“1”1”方格。方格?？傇瓌t：總原則：在覆蓋所有最小項(xiàng)的前提下，卡諾圈在覆蓋所有最小項(xiàng)的前提下，卡諾圈 的個(gè)數(shù)

22、達(dá)到最少，每個(gè)卡諾圈最大。的個(gè)數(shù)達(dá)到最少，每個(gè)卡諾圈最大。例例1：直接給出函數(shù)的真值表，求函數(shù)的最簡(jiǎn)與或式。：直接給出函數(shù)的真值表，求函數(shù)的最簡(jiǎn)與或式。見例見例1例例2：直接給出函數(shù)的：直接給出函數(shù)的復(fù)雜的運(yùn)算式復(fù)雜的運(yùn)算式。見例見例2(5) 卡諾圖化簡(jiǎn)函數(shù)舉例卡諾圖化簡(jiǎn)函數(shù)舉例 含有含有無關(guān)項(xiàng)無關(guān)項(xiàng)的函數(shù)的化簡(jiǎn)的函數(shù)的化簡(jiǎn) 填函數(shù)的卡諾圖時(shí)只在無關(guān)項(xiàng)對(duì)應(yīng)的格內(nèi)填函數(shù)的卡諾圖時(shí)只在無關(guān)項(xiàng)對(duì)應(yīng)的格內(nèi)填任意符號(hào)填任意符號(hào)“”、“d或或“”。無關(guān)項(xiàng)無關(guān)項(xiàng)對(duì)于變量的對(duì)于變量的某些取值組合某些取值組合，所對(duì)應(yīng)的，所對(duì)應(yīng)的函數(shù)值函數(shù)值是不確定的是不確定的。通常。通常約束項(xiàng)和任意項(xiàng)約束項(xiàng)和任意項(xiàng)在邏輯函在邏輯函數(shù)中統(tǒng)稱為數(shù)中統(tǒng)稱為無關(guān)項(xiàng)無關(guān)項(xiàng)。 化簡(jiǎn)時(shí)可根據(jù)需要視為化簡(jiǎn)時(shí)可根據(jù)需要視為“1”也可視為也可視為“0”，