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

1、1.4 布爾代數(shù)布爾代數(shù)1.4.1 布爾代數(shù)的基本定律布爾代數(shù)的基本定律 公理、定律與常用公式公理、定律與常用公式公理公理交換律交換律結(jié)合律結(jié)合律分配律分配律0-1律律重疊律重疊律互補律互補律非非律非非律摩根律摩根律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等式右邊等式右邊 由此可以看出：與或表達式中，兩個乘積項分由此可以看出：與或表達式中，兩個乘積項分別包含別包含同一因子同一因子的的原原變量和變量和反反變量，而兩項的剩余變量，而兩項的剩余因子包含在第三個乘積項中，則第三項是多余的。因子包含在第三個乘積項中，則第三項是多余的。CAABBCDECAAB公式可推廣：公式可推廣：例：證明包含律例：證明包含律CAABBCCAAB成立。成立。BC)AA(CAAB利用基本定律利用基本定律函數(shù)證明函數(shù)證明 方法方法2ABACABCABC1.4.2 布爾代數(shù)的三個基本規(guī)則布爾代數(shù)的三個基本規(guī)則 代

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

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

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

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

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

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

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

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

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

13、量必須而且只能以原變（每個變量必須而且只能以原變量或反變量的形式出現(xiàn)一次）。量或反變量的形式出現(xiàn)一次）。（1） 最小項的概念最小項的概念最小項最小項二進制數(shù)二進制數(shù)十進制數(shù)十進制數(shù)編號編號最小項編號最小項編號i是指各輸入是指各輸入變量取值看成二進制數(shù)變量取值看成二進制數(shù)對應的十進制數(shù)對應的十進制數(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三變量的最小項三變量的最小項 （2）最小項）最小項 的性質(zhì)：的性質(zhì)： 任意任意兩個不同兩個不同最小項的最小項的乘積乘積為為0， 即即 mi mj=0 (ij)。 全部全部最小項之最小項之和和為為1，即，即120ii1mn 任意一組變量取值，任意一組變量取值，只有一個只有一個最小最小 項項 的值為的值為1，其它最小項的值均為，其它最小項的值均為0。 標準積之和標準積之和( 最小項）表達式最小項）表達式式中的每一個乘式中的每一個乘積項均為最小項積項均為最小項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的標準積之的標準積之和表達式和表達式解：解：F(AF(A、B B、C C、D)D)CB ABACB ABACB A)CC(BACB ACBABCA123mmm)3 2 1 (m、利用反演律利用反演律利用互補律，補利用互補律，補上所缺變量上所缺變量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ù)的標準積之和表達式已知函數(shù)的真值表，寫出該函數(shù)的標準積之和表達式 從真值表找出從真值表找出F為為1的對應最小項的對應最小項解解: 然后將這些項邏輯加然后將這些項邏輯加F(AF(A、B B、C)C)ABCCABCBABCA7653mmmm)7 6 5 3(m、（3）邏輯函數(shù)的標準形式邏輯函數(shù)的標準形式1.5.2 卡諾圖的結(jié)構(gòu)特點卡諾圖的結(jié)構(gòu)特點（一）（一） 1 1、2 2、3 3變量卡諾圖變量卡諾圖排列原則排列原則：任何兩個上下或左右相鄰的小方格對應的兩個任何兩個上下或左右相鄰的小方格對應的兩個 最小項中，有且僅有一個變量發(fā)生變化。最小項中，有且僅有一個變量發(fā)生變化。 （二）（二） 4 4變

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

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

19、、2、3n）個小格）個小格可合可合并在一起構(gòu)成正方形或矩形圈，消去并在一起構(gòu)成正方形或矩形圈，消去i個變量，而個變量，而用含用含（n - i）個變量的積項標注該圈個變量的積項標注該圈。例：圖中給出輸入變量例：圖中給出輸入變量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ù)表達式填卡諾圖根據(jù)函數(shù)表達式填卡諾圖(3) 用卡諾圖化簡邏輯函數(shù)的步驟用卡諾圖化簡邏輯函數(shù)的步驟 與或表達式的簡化與或表達式的簡化步步驟驟(1) 把邏輯函數(shù)變換為最小項表達式；把邏輯函數(shù)變換為最小項表達式；(2) 用卡諾圖表示邏輯函數(shù)：最小項表達式中用卡諾圖表示邏輯函數(shù)：最小項表達式中 各最小項對應的各小方格填入各最小項對應的各小方格填入“1”，其余的，其余的 填填 “0”或不填；或不填；(3) 合并相鄰合并相鄰“1”方格；方格

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

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