數(shù)字電子技術(shù)基礎(chǔ)第2章

1、第第2章章 邏輯代數(shù)基礎(chǔ)邏輯代數(shù)基礎(chǔ) 2.1 邏輯代數(shù)的三種基本運(yùn)算邏輯代數(shù)的三種基本運(yùn)算 2.2 邏輯代數(shù)的基本定律和規(guī)則邏輯代數(shù)的基本定律和規(guī)則 2.3 復(fù)合邏輯復(fù)合邏輯 2.4 邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式 2.5 邏輯函數(shù)的代數(shù)化簡(jiǎn)法邏輯函數(shù)的代數(shù)化簡(jiǎn)法2.6 邏輯函數(shù)的卡諾圖化簡(jiǎn)邏輯函數(shù)的卡諾圖化簡(jiǎn)2.7 非完全描述邏輯函數(shù)的化簡(jiǎn)非完全描述邏輯函數(shù)的化簡(jiǎn) 2.1 邏輯代數(shù)的三種基本運(yùn)算邏輯代數(shù)的三種基本運(yùn)算 2.1.1 邏輯變量與邏輯函數(shù)邏輯變量與邏輯函數(shù) 邏輯是指事物因果之間所遵循的規(guī)律。為了避免用冗繁的文字來(lái)描述邏輯問(wèn)題，邏輯代數(shù)采用邏輯變量和一套運(yùn)算符組成邏輯函

2、數(shù)表達(dá)式來(lái)描述事物的因果關(guān)系。 邏輯代數(shù)中的變量稱(chēng)為邏輯變量，一般用大寫(xiě)字母A、B、 C、表示，邏輯變量的取值只有兩種，即邏輯0和邏輯1。 0和1稱(chēng)為邏輯常量。但必須指出，這里的邏輯0和1本身并沒(méi)有數(shù)值意義，它們并不代表數(shù)量的大小，而僅僅是作為一種符號(hào)，代表事物矛盾雙方的兩種狀態(tài)。 邏輯函數(shù)與普通代數(shù)中的函數(shù)相似，它是隨自變量的變化而變化的因變量。因此，如果用自變量和因變量分別表示某一事件發(fā)生的條件和結(jié)果，那么該事件的因果關(guān)系就可以用邏輯函數(shù)來(lái)描述。 數(shù)字電路的輸入、輸出量一般用高、低電平來(lái)表示，高、低電平也可以用二值邏輯1和0來(lái)表示。同時(shí)數(shù)字電路的輸出與輸入之間的關(guān)系是一種因果關(guān)系， 因此它

3、可以用邏輯函數(shù)來(lái)描述，并稱(chēng)為邏輯電路。對(duì)于任何一個(gè)電路，若輸入邏輯變量A、 B、 C、 的取值確定后，其輸出邏輯變量F的值也被惟一地確定了，則可以稱(chēng)F是A、 B、 C、 的邏輯函數(shù)， 并記為 ),( CBAfF2.1.2 三種基本運(yùn)算三種基本運(yùn)算 1. 與運(yùn)算與運(yùn)算(邏輯乘邏輯乘) 與運(yùn)算(邏輯乘)表示這樣一種邏輯關(guān)系：只有當(dāng)決定一事件結(jié)果的所有條件同時(shí)具備時(shí)，結(jié)果才能發(fā)生。例如在圖2-1所示的串聯(lián)開(kāi)關(guān)電路中，只有在開(kāi)關(guān)A和B都閉合的條件下，燈F才亮，這種燈亮與開(kāi)關(guān)閉合的關(guān)系就稱(chēng)為與邏輯。 如果設(shè)開(kāi)關(guān)A、B閉合為1，斷開(kāi)為0，設(shè)燈F亮為1，滅為0， 則F與A、B的與邏輯關(guān)系可以用表2-1所示的

4、真值表來(lái)描述 所謂真值表，就是將自變量的各種可能的取值組合與其因變量的值一一列出來(lái)的表格形式。 圖 2 -1 與邏輯實(shí)例 AFBE表 2-1 與邏輯運(yùn)算真值表 A BF0 00 11 01 10001與邏輯可以用邏輯表達(dá)式表示為F=AB 在邏輯代數(shù)中，將與邏輯稱(chēng)為與運(yùn)算或邏輯乘。符號(hào)“”表示邏輯乘，在不致混淆的情況下，常省去符號(hào)“”。在有些文獻(xiàn)中，也采用、 及&等符號(hào)來(lái)表示邏輯乘。 實(shí)現(xiàn)與邏輯的單元電路稱(chēng)為與門(mén)，其邏輯符號(hào)如圖2-2所示，其中圖(a)為我國(guó)常用的傳統(tǒng)符號(hào)，圖(b)為國(guó)外流行的符號(hào)，圖(c)為國(guó)標(biāo)符號(hào)(見(jiàn)附錄一)。圖2-3是一個(gè)2 輸入的二極管與門(mén)電路。圖中輸入端A、B的電位可以

5、取兩種值：高電位+3V或低電位0V。設(shè)二極管為理想開(kāi)關(guān)，并規(guī)定高電位為邏輯1，低電位為邏輯0，那么F與A、B之間邏輯關(guān)系的真值表與表2-1相同， 因而實(shí)現(xiàn)了F=AB的功能。 圖 2-2 與門(mén)的邏輯符號(hào) 圖 2-3 二極管與門(mén) FAB(a)(b)&FAB(c)FABUCC(+5V)R3.9kABFV1V22. 或運(yùn)算或運(yùn)算(邏輯加邏輯加) 圖 2-4 或邏輯實(shí)例 FABE表 2-2 或邏輯運(yùn)算真值表 A BF0 00 11 01 10111或邏輯可以用邏輯表達(dá)式表示為F=A+B 或邏輯也稱(chēng)為或運(yùn)算或邏輯加。符號(hào)“+”表示邏輯加。有些文獻(xiàn)中也采用、等符號(hào)來(lái)表示邏輯加。 實(shí)現(xiàn)或邏輯的單元電路稱(chēng)為或門(mén)

6、，其邏輯符號(hào)如圖2-5所示，其中圖(a)為我國(guó)常用的傳統(tǒng)符號(hào)，圖(b)為國(guó)外流行的符號(hào)， 圖(c)為國(guó)標(biāo)符號(hào)(見(jiàn)附錄一)。 圖2-6是一個(gè) 2 輸入的二極管或門(mén)電路。圖中輸入端A、 B的電位可以取兩種值： 高電位+3V或低電位0 V。 設(shè)二極管為理想開(kāi)關(guān)，并規(guī)定高電位為邏輯1，低電位為邏輯0，則F與A、B之間邏輯關(guān)系的真值表與表2-2相同， 因此實(shí)現(xiàn)了F=A+B的功能。 圖 2-5 或門(mén)的邏輯符號(hào) 圖 2-6 二極管或門(mén) FAB(a)(b)FAB(c)1FABR3.9kBAFV2V1 3. 非運(yùn)算非運(yùn)算(邏輯反邏輯反) 非運(yùn)算(邏輯反)是邏輯的否定：當(dāng)條件具備時(shí)，結(jié)果不會(huì)發(fā)生；而條件不具備時(shí)，

7、結(jié)果一定會(huì)發(fā)生。例如，在圖2-7所示的開(kāi)關(guān)電路中，只有當(dāng)開(kāi)關(guān)A斷開(kāi)時(shí)，燈F才亮，當(dāng)開(kāi)關(guān)A閉合時(shí)，燈F反而熄滅。燈F的狀態(tài)總是與開(kāi)關(guān)A的狀態(tài)相反。這種結(jié)果總是同條件相反的邏輯關(guān)系稱(chēng)為非邏輯。非邏輯的真值表如表2-3所示，其邏輯表達(dá)式為 AF 通常稱(chēng)A為原變量，A為反變量。 圖 2-7 非邏輯實(shí)例 AF0110表 2-3 非邏輯運(yùn)算真值表 FARE圖 2-8 非門(mén)邏輯符號(hào) FA(a)FA(b)1FA(c) 圖 2-9 三極管非 RVRCF(UI)UCC(+5v)A(UO)2.2 邏輯代數(shù)的基本定律和規(guī)則邏輯代數(shù)的基本定律和規(guī)則 2.2.1 基本定律基本定律 1. 變量和常量的關(guān)系式 邏輯變量的取值

8、只有0和1，根據(jù)三種基本運(yùn)算的定義，可推得以下關(guān)系式。 0-1律： A0 =0 A+1 =1自等律：A1=A A+0=A重疊律：AA=A A+A=A互補(bǔ)律：AA=0 A+A=1 2. 與普通代數(shù)相似的定律與普通代數(shù)相似的定律交換律 AB=BA A+B=B+A結(jié)合律 (AB)C=A(BC) (A+B)+C=A+(B+C)分配律 A(B+C)=AB+AC A+BC=(A+B)(A+C) 以上定律可以用真值表證明，也可以用公式證明。例如， 證明加對(duì)乘的分配律A+BC=(A+B)(A+C)。 證： (A+B)(A+C) =AA+AB+AC+BC =A+AB+AC+BC =A(1+B+C)+BC=A+B

9、C因此有 A+BC=(A+B)(A+C) 3. 邏輯代數(shù)中的特殊定律邏輯代數(shù)中的特殊定律反演律(De Morgan定律)： BABABABA還原律： AA表 2-4 反演律證明 AB0 00 11 01 11110111010001000ABBABABA 2.2.2 三個(gè)重要規(guī)則三個(gè)重要規(guī)則 1. 代入規(guī)則代入規(guī)則 任何一個(gè)邏輯等式，如果將等式兩邊所出現(xiàn)的某一變量都代之以同一邏輯函數(shù)，則等式仍然成立，這個(gè)規(guī)則稱(chēng)為代入規(guī)則。 由于邏輯函數(shù)與邏輯變量一樣，只有0、1兩種取值， 所以代入規(guī)則的正確性不難理解。運(yùn)用代入規(guī)則可以擴(kuò)大基本定律的運(yùn)用范圍。 例如，已知A+B=AB(反演律)，若用F=B+C代

10、替等式中的B，則可以得到適用于多變量的反演律， 即 CBACBACBA 2. 反演規(guī)則反演規(guī)則 對(duì)于任意一個(gè)邏輯函數(shù)式F，如果將其表達(dá)式中所有的算符“”換成“+”， “+”換成“”，常量“0”換成“1”，“1”換成“0”，原變量換成反變量，反變量換成原變量，則所得到的結(jié)果就是 。 稱(chēng)為原函數(shù)F的反函數(shù)，或稱(chēng)為補(bǔ)函數(shù)。 反演規(guī)則是反演律的推廣，運(yùn)用它可以簡(jiǎn)便地求出一個(gè)函數(shù)的反函數(shù)。 例如： FF,ACDCABF);()(CADCBAF若 則 ,EDCBAF。EDCBAF若 則 運(yùn)用反演規(guī)則時(shí)應(yīng)注意兩點(diǎn)： 不能破壞原式的運(yùn)算順序先算括號(hào)里的，然后按“先與后或”的原則運(yùn)算。 不屬于單變量上的非號(hào)應(yīng)保

11、留不變。 3. 對(duì)偶規(guī)則對(duì)偶規(guī)則 對(duì)于任何一個(gè)邏輯函數(shù)，如果將其表達(dá)式F中所有的算符“”換成“+”, “+”換成“”，常量“0”換成“1”，“1”換成“0”， 而變量保持不變，則得出的邏輯函數(shù)式就是F的對(duì)偶式，記為F(或F*)。 例如： AFAFCBAFCBAFCABAFCABAF,;,);1()(),0(則若則若則若以上各例中F是F的對(duì)偶式。不難證明F也是F對(duì)偶式。 即F與F互為對(duì)偶式。 任何邏輯函數(shù)式都存在著對(duì)偶式。 若原等式成立， 則對(duì)偶式也一定成立。即，如果F=G,則F=G。這種邏輯推理叫做對(duì)偶原理，或?qū)ε家?guī)則。 必須注意，由原式求對(duì)偶式時(shí)，運(yùn)算的優(yōu)先順序不能改變， 且式中的非號(hào)也保持

12、不變。 觀察前面邏輯代數(shù)基本定律和公式，不難看出它們都是成對(duì)出現(xiàn)的， 而且都是互為對(duì)偶的對(duì)偶式。 例如，已知乘對(duì)加的分配律成立，即A(B+C)=AB+AC，根據(jù)對(duì)偶規(guī)則有，A+BC=(A+B)(A+C)，即加對(duì)乘的分配律也成立。 2.2.3 若干常用公式若干常用公式 1. 合并律合并律 ABAAB 在邏輯代數(shù)中，如果兩個(gè)乘積項(xiàng)分別包含了互補(bǔ)的兩個(gè)因子(如B和B)， 而其它因子都相同，那么這兩個(gè)乘積項(xiàng)稱(chēng)為相鄰項(xiàng)。 合并律說(shuō)明，兩個(gè)相鄰項(xiàng)可以合并為一項(xiàng)， 消去互補(bǔ)量。 2. 吸收律吸收律 A+AB=A 證： A+AB=A(1+B)=A1=A 該公式說(shuō)明，在一個(gè)與或表達(dá)式中，如果某一乘積項(xiàng)的部分因子

13、(如AB項(xiàng)中的A)恰好等于另一乘積項(xiàng)(如A)的全部， 則該乘積項(xiàng)(AB)是多余的。 BABABAAABAABABAA)(1)( 證： 該公式說(shuō)明，在一個(gè)與或表達(dá)式中，如果一個(gè)乘積項(xiàng)(如A)取反后是另一個(gè)乘積項(xiàng)(如 的因子，則此因子 是多余的。 BAACAABBCAABCCAABBCAACAABBCCAABCAABBCCAAB)( 證： 推論： CAABBCDCAAB證：AB+AC=AB+ABC+AC+ABC=AB+AC+BC（A+A） =AB+AC+BC證：AB+AC+BCD=AB+AC+BC+BCD =AB+AC+BC（1+D）=AB+AC 該公式及推論說(shuō)明，在一個(gè)與或表達(dá)式中，如果兩個(gè)乘積

14、項(xiàng)中的部分因子互補(bǔ)(如AB項(xiàng)和AC項(xiàng)中的A和A)，而這兩個(gè)乘積項(xiàng)中的其余因子(如B和C)都是第三個(gè)乘積項(xiàng)中的因子， 則這個(gè)第三項(xiàng)是多余的。 2.3 復(fù)復(fù) 合合 邏邏 輯輯 2.3.1 復(fù)合邏輯運(yùn)算和復(fù)合門(mén)復(fù)合邏輯運(yùn)算和復(fù)合門(mén) 1. 與非、與非、 或非、或非、 與或非邏輯運(yùn)算與或非邏輯運(yùn)算與非邏輯運(yùn)算是與運(yùn)算和非運(yùn)算的組合， 即 BAF或非邏輯運(yùn)算是或運(yùn)算和非運(yùn)算的組合， 即 BAF 與或非邏輯運(yùn)算是與、或、非三種運(yùn)算的組合，即 CDABF圖圖 2-10 與非門(mén)、與非門(mén)、 或非門(mén)和與或非門(mén)的邏輯符或非門(mén)和與或非門(mén)的邏輯符號(hào)號(hào) (a) 與非門(mén)；與非門(mén)； (b) 或非門(mén)；或非門(mén)； (c) 與或非門(mén)與

15、或非門(mén) FFBFA(a)FA&ABBFBFA(b)FAABB1FBADCABCDFBADC1&(c) 2. 異或和同或邏輯運(yùn)算異或和同或邏輯運(yùn)算 異或邏輯的含義是：當(dāng)兩個(gè)輸入變量相異時(shí)，輸出為1； 相同時(shí)輸出為0。 是異或運(yùn)算的符號(hào)。 異或運(yùn)算也稱(chēng)模2加運(yùn)算。 異或邏輯的真值表如表2-5所示， 其邏輯表達(dá)式為 BABABAFA BF0 00 11 01 10110表表 2-5 異或邏輯真值表異或邏輯真值表 圖 2-11 異或門(mén)和同或門(mén)的邏輯符號(hào)(a) 異或門(mén)； (b) 同或門(mén) FBFA(a)FAABB 1FBFA(b)FAABB 同或邏輯與異或邏輯相反，它表示當(dāng)兩個(gè)輸入變量相同時(shí)輸出為1；相異

16、時(shí)輸出為0。 是同或運(yùn)算的符號(hào)。 同或邏輯的真值表如表2-6所示，其邏輯表達(dá)式為 ABBABAFA BF0 00 11 01 11001表 2-6 同或邏輯真值表 由定義和真值表可見(jiàn)，異或邏輯與同或邏輯互為反函數(shù)，即 BABABABA, 不僅如此，它們還互為對(duì)偶式。如果 ，G=A B， 不難證明F=G, G=F。 因此可以將“ ”作為“ ”的對(duì)偶符號(hào)，反之亦然。由以上分析可以看出， 兩變量的異或函數(shù)和同或函數(shù)既互補(bǔ)又對(duì)偶，這是一對(duì)特殊函數(shù)。 BAF表 2-7 常用異或和同或運(yùn)算公式 此外， AAAAA0(A的個(gè)數(shù)為偶數(shù)) (A的個(gè)數(shù)為奇數(shù)) 對(duì)于一個(gè)代數(shù)系統(tǒng)， 若僅用它所定義的一組運(yùn)算符號(hào)就能

17、解決所有的運(yùn)算問(wèn)題， 則稱(chēng)這一組符號(hào)是一個(gè)完備的集合， 簡(jiǎn)稱(chēng)完備集。 在邏輯代數(shù)中， 與、 或、 非是三種最基本的運(yùn)算，n變量的所有邏輯函數(shù)都可以用n個(gè)變量及一組邏輯運(yùn)算符“、 +、 -”來(lái)構(gòu)成， 因此稱(chēng)“、 +、 -”運(yùn)算符是一組完備集。 2.3.2 邏輯運(yùn)算符的完備性邏輯運(yùn)算符的完備性 但是“與、 或、 非”并不是最好的完備集， 因?yàn)樗鼘?shí)現(xiàn)一個(gè)函數(shù)要使用三種不同規(guī)格的邏輯門(mén)。 實(shí)際上從反演律可以看出， 有了“與”和“非”可得出“或”， 有了“或”和“非”可得出“與”， 因此“與非”、 “或非”、 “與或非”運(yùn)算中的任何一種都能單獨(dú)實(shí)現(xiàn)“與、 或、 非”運(yùn)算， 這三種復(fù)合運(yùn)算每種都是完備集，

18、 而且實(shí)現(xiàn)函數(shù)只需要一種規(guī)格的邏輯門(mén)， 這就給設(shè)計(jì)工作帶來(lái)許多方便。 例如，任何一個(gè)邏輯函數(shù)式都可以通過(guò)邏輯變換寫(xiě)成以下五種形式： CABACABACAABCABACAABF)()()(與或式 或與式 與非與非式 或非或非式 與或非式 圖 2-12 邏輯函數(shù)的五種形式 &AB&C1(a)&B&AC&(c)AAF=AB+ACABC1(b)BA(d)A&1F=(A+B)(A+C)111ACA1&(e)BCAF=(A+B)+(A+C)F=AB+ACF=ABAC2.4 邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式 2.4.1 最小項(xiàng)和最小項(xiàng)表達(dá)式最小項(xiàng)和最小項(xiàng)表達(dá)式 1. 最小項(xiàng)最小項(xiàng) n個(gè)變量的最小

19、項(xiàng)是n個(gè)變量的“與項(xiàng)”，其中每個(gè)變量都以原變量或反變量的形式出現(xiàn)一次。 兩 個(gè) 變 量 A 、 B 可 以 構(gòu) 成 四 個(gè) 最 小 項(xiàng) ，三個(gè)變量A、B、C可以構(gòu)成八個(gè)最小項(xiàng) ，可見(jiàn)n個(gè)變量的最小項(xiàng)共有2n個(gè)。 ABCCABCBACBABCACBACBACBA、ABBABABA、表 2-8 三變量邏輯函數(shù)的最小項(xiàng) 最小項(xiàng)具有以下性質(zhì)： n變量的全部最小項(xiàng)的邏輯和恒為1，即 1120niim 任意兩個(gè)不同的最小項(xiàng)的邏輯乘恒為0， 即 )(0jimmji n變量的每一個(gè)最小項(xiàng)有n個(gè)相鄰項(xiàng)。例如，三變量的某一最小項(xiàng) 有三個(gè)相鄰項(xiàng)： 。這種相鄰關(guān)系對(duì)于邏輯函數(shù)化簡(jiǎn)十分重要。 CBACBABCACBA、

20、 2. 最小項(xiàng)表達(dá)式最小項(xiàng)表達(dá)式標(biāo)準(zhǔn)與或式標(biāo)準(zhǔn)與或式 如果在一個(gè)與或表達(dá)式中，所有與項(xiàng)均為最小項(xiàng)， 則稱(chēng)這種表達(dá)式為最小項(xiàng)表達(dá)式，或稱(chēng)為標(biāo)準(zhǔn)與或式、標(biāo)準(zhǔn)積之和式。 例如： CABCBACBACBAF),(是一個(gè)三變量的最小項(xiàng)表達(dá)式， 它也可以簡(jiǎn)寫(xiě)為 )6 , 5 , 4(),(645mmmmCBAF 任何一個(gè)邏輯函數(shù)都可以表示為最小項(xiàng)之和的形式： 只要將真值表中使函數(shù)值為1的各個(gè)最小項(xiàng)相或，便可得出該函數(shù)的最小項(xiàng)表達(dá)式。 由于任何一個(gè)函數(shù)的真值表是惟一的，因此其最小項(xiàng)表達(dá)式也是惟一的。 表 2-9 真值表 A B CF0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1

21、 101101011 從真值表可知，當(dāng)A、B、C取值分別為001、010、 100、111時(shí)，F(xiàn)為1，因此最小項(xiàng)表達(dá)式由這四種組合所對(duì)應(yīng)的最小項(xiàng)進(jìn)行相或構(gòu)成，即 )7 , 4 , 2 , 1 (mABCCBACBACBAF表 2-10 三變量邏輯函數(shù)的最大項(xiàng) 2.4.2 最大項(xiàng)和最大項(xiàng)表達(dá)式最大項(xiàng)和最大項(xiàng)表達(dá)式 1. 最大項(xiàng)最大項(xiàng) n個(gè)變量的最大項(xiàng)是n個(gè)變量的“或項(xiàng)”，其中每一個(gè)變量都以原變量或反變量的形式出現(xiàn)一次。 n個(gè)變量可以構(gòu)成2n個(gè)最大項(xiàng)。最大項(xiàng)用符號(hào)Mi表示(見(jiàn)表2-10)。與最小項(xiàng)恰好相反，對(duì)于任何一個(gè)最大項(xiàng)，只有一組變量取值使它為0，而變量的其余取值均使它為1。 例如，或項(xiàng) 僅和

22、變量取值101對(duì)應(yīng)，故用M5表示。 CBA最大項(xiàng)具有以下性質(zhì)： n變量的全部最大項(xiàng)的邏輯乘恒為0，即 1200niiM n變量的任意兩個(gè)不同的最大項(xiàng)的邏輯和必等于1，即 )( 1jiMMji n變量的每個(gè)最大項(xiàng)有n個(gè)相鄰項(xiàng)。例如，三變量的某一最大項(xiàng) 有三個(gè)相鄰項(xiàng)： )(CBA。、)()()(CBACBACBA2. 最小項(xiàng)與最大項(xiàng)之間的關(guān)系最小項(xiàng)與最大項(xiàng)之間的關(guān)系 變量數(shù)相同，編號(hào)相同的最小項(xiàng)和最大項(xiàng)之間存在互補(bǔ)關(guān)系，即 iiiimMMm,例如： 7777MCBACBACBAMmCBACBAM 3. 最大項(xiàng)表達(dá)式最大項(xiàng)表達(dá)式標(biāo)準(zhǔn)或與式標(biāo)準(zhǔn)或與式 在一個(gè)或與式中，如果所有的或項(xiàng)均為最大項(xiàng)，則稱(chēng)這種

23、表達(dá)式為最大項(xiàng)表達(dá)式，或稱(chēng)為標(biāo)準(zhǔn)或與式、標(biāo)準(zhǔn)和之積表達(dá)式。 如果一個(gè)邏輯函數(shù)的真值表已給出，要寫(xiě)出該函數(shù)的最大項(xiàng)表達(dá)式，可以先求出該函數(shù)的反函數(shù) ，并寫(xiě)出 的最小項(xiàng)表達(dá)式，然后將 再求反，利用mi和Mi的互補(bǔ)關(guān)系便得到最大項(xiàng)表達(dá)式。例如，已知表2-11的真值表，可得 FFF表 2-11 真值表 A B C F F0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 11 01 00 10 11 01 00 10 1)7 , 6 , 3 , 2()5 , 4 , 1 , 0(7632763276327632MmmmmmmmmmmmmFFmmmmFmF可見(jiàn)，最大項(xiàng)表達(dá)式是真

24、值表中使函數(shù)值為0的各個(gè)最大項(xiàng)相與。 得出結(jié)論：任何一個(gè)邏輯函數(shù)既可以用最小項(xiàng)表達(dá)式表示，也可以用最大項(xiàng)表達(dá)式表示。如果將一個(gè)n變量函數(shù)的最小項(xiàng)表達(dá)式改為最大項(xiàng)表達(dá)式時(shí)，其最大項(xiàng)的編號(hào)必定都不是最小項(xiàng)的編號(hào)， 而且這些最小項(xiàng)的個(gè)數(shù)和最大項(xiàng)的個(gè)數(shù)之和為2n。 2.5 邏輯函數(shù)的代數(shù)化簡(jiǎn)法邏輯函數(shù)的代數(shù)化簡(jiǎn)法 1. 并項(xiàng)法并項(xiàng)法 利用公式AB+AB=A將兩項(xiàng)合并成一項(xiàng)，并消去互補(bǔ)因子。如：AACCACBBCACBCBACBAABCCABCBAFDCADCABDCBAF)()( 2. 吸收法吸收法 利用吸收律 A+AB=A、 和 吸收(消去)多余的乘積項(xiàng)或多余的 因子。 如： BABAACAABBC

25、CAABDCACBAADEDCACBADCADEACBAFDCDAABCBDDACABCBDDCAABCBDDCDAABCFCBDACDCBACDCABAFCABCABABCBAABCBCAABF)()( 3. 配項(xiàng)法配項(xiàng)法 利用重疊律A+A=A、互補(bǔ)律A+ A = 1 和吸收律AB+AC+BC=AB+AC先配項(xiàng)或添加多余項(xiàng)，然后再逐步化簡(jiǎn)。如： DCBACDABCBACDABABCBACDBACBACCBDBDAACF)(添多余項(xiàng)AB) (去掉多余項(xiàng)AB) ABCBCAABBCAABCCBCBACBAABAABCCBCCBAABBCCBBAFCBBACACABCBABCACBACBACBAC

26、ABBCACBACBAF)()()()()(2.6 邏輯函數(shù)的卡諾圖化簡(jiǎn)邏輯函數(shù)的卡諾圖化簡(jiǎn) 2.6.1 卡諾圖的構(gòu)成卡諾圖的構(gòu)成 在邏輯函數(shù)的真值表中， 輸入變量的每一種組合都和一個(gè)最小項(xiàng)相對(duì)應(yīng)，這種真值表也稱(chēng)最小項(xiàng)真值表。卡諾圖就是根據(jù)最小項(xiàng)真值表按一定規(guī)則排列的方格圖。 表 2-12 三變量最小項(xiàng) 圖 2-14 四變量、五變量K圖 0ABCD00011110(a)141285139327151161410000111100ABCDE000(b)1412851393271511614100001111024252820162921172726312319302218001011010110

27、111101100A B CA B CA B CA B CA B CA B CA B CA B CABC0001111001(a)m0ABC0001111001(b)m1m2m6m4m3m7m50ABC0001111001(c)1264375圖 2-13 三變量K圖 由圖2-14可以看出，K圖具有如下特點(diǎn)： n變量的卡諾圖有2n個(gè)方格，對(duì)應(yīng)表示2n個(gè)最小項(xiàng)。每當(dāng)變量數(shù)增加一個(gè)，卡諾圖的方格數(shù)就擴(kuò)大一倍。 卡諾圖中任何幾何位置相鄰的兩個(gè)最小項(xiàng)，在邏輯上都是相鄰的。由于變量取值的順序按格雷碼排列，保證了各相鄰行(列)之間只有一個(gè)變量取值不同，從而保證畫(huà)出來(lái)的最小項(xiàng)方格圖具有這一重要特點(diǎn)。 所謂幾何

28、相鄰，一是相接，即緊挨著； 二是相對(duì)，即任意一行或一列的兩頭；三是相重， 即對(duì)折起來(lái)位置重合。 所謂邏輯相鄰，是指除了一個(gè)變量不同外其余變量都相同的兩個(gè)與項(xiàng)。 例如圖2-14(b)五變量K圖中，m5在幾何位置上與m4、m7、m1、m13、m21相鄰，因此 與 相鄰， 此外還與 和 分別相鄰， 即m5有五個(gè)相鄰項(xiàng)?？梢?jiàn)卡諾圖也反映了n變量的任何一個(gè)最小項(xiàng)有n個(gè)相鄰項(xiàng)這一特點(diǎn)。 卡諾圖的主要缺點(diǎn)是隨著輸入變量的增加圖形迅速?gòu)?fù)雜， 相鄰項(xiàng)不那么直觀，因此它只適于用來(lái)表示6個(gè)以下變量的邏輯函數(shù)。 EDCBAm 5EDCBAm 4EDBCAmEDCBAmCDEBAm1317、EDCBAm212.6.2

29、邏輯函數(shù)的卡諾圖表示法邏輯函數(shù)的卡諾圖表示法 1. 給出邏輯函數(shù)的最小項(xiàng)表達(dá)式給出邏輯函數(shù)的最小項(xiàng)表達(dá)式 只要將構(gòu)成邏輯函數(shù)的最小項(xiàng)在卡諾圖上相應(yīng)的方格中填1，其余的方格填0(或不填)，則可以得到該函數(shù)的卡諾圖。也就是說(shuō)，任何一個(gè)邏輯函數(shù)都等于其卡諾圖上填1的那些最小項(xiàng)之和。 例如，用卡諾圖表示函數(shù) 時(shí)，只需在三變量卡諾圖中將m0、m3、m4、m6處填1，其余填0(或不填)，如圖2-15(a)所示。 同理， 的卡諾圖如圖 2-15(b)所示。 )6 , 4 , 3 , 0(1mF)15,12,10, 9 , 7 , 4 , 2 , 0(2mF圖 2-15 F1、2的卡諾圖 1ABC000111

30、1001(a)0111ABCD00011110(b)011000101110001000111100100 2. 給出邏輯函數(shù)的一般與或式給出邏輯函數(shù)的一般與或式 將一般與或式中每個(gè)與項(xiàng)在卡諾圖上所覆蓋的最小項(xiàng)處都填1，其余的填0(或不填)，就可以得到該函數(shù)的卡諾圖。 例如，用卡諾圖表示函數(shù) 時(shí)， 先確定使每個(gè)與項(xiàng)為1的輸入變量取值， 然后在該輸入變量取值所對(duì)應(yīng)的方格內(nèi)填1。 ：當(dāng)ABCD=101(表示可以為0，也可以為1)時(shí)該與項(xiàng)為1，在卡諾圖上對(duì)應(yīng)兩個(gè)方格(m10、m11)處填1。 ADDCBACBAF3CBA ：當(dāng)ABCD=001時(shí)該與項(xiàng)為1，對(duì)應(yīng)兩個(gè)方格(m2、m3)處填1。 D：當(dāng)A

31、BCD=1時(shí)該與項(xiàng)為1，對(duì)應(yīng)八個(gè)方格(m1、m3、m5、m7、m9、m11、m13、m15)處填1。 AD：當(dāng)ABCD=11時(shí)該與項(xiàng)為1，對(duì)應(yīng)四個(gè)方格(m9、 m11、m13、m15)處填1。 某些最小項(xiàng)重復(fù)，只需填一次即可。CBA圖 2-16 F3的卡諾圖 ABCD00011110111111111100011110 3. 給出邏輯函數(shù)的最大項(xiàng)表達(dá)式給出邏輯函數(shù)的最大項(xiàng)表達(dá)式 只要將構(gòu)成邏輯函數(shù)的最大項(xiàng)在卡諾圖相應(yīng)的方格中填0，其余的方格填1即可。也就是說(shuō)，任何一個(gè)邏輯函數(shù)都等于其卡諾圖上填0的那些最大項(xiàng)之積。 例如，函數(shù) 的卡諾圖如圖2-17所示。 必須注意，在卡諾圖中最大項(xiàng)的編號(hào)與最小項(xiàng)

32、編號(hào)是一致的，但對(duì)應(yīng)輸入變量的取值是相反的。 )()()6 , 2 , 0(4CBACBACBAMF圖 2-17 F4的卡諾圖 0ABC00011110010011111 4. 給出邏輯函數(shù)的一般或與式給出邏輯函數(shù)的一般或與式 將一般或與式中每個(gè)或項(xiàng)在卡諾圖上所覆蓋的最大項(xiàng)處都填0，其余的填1即可。 例如，將函數(shù) 填入卡諾圖時(shí)，先確定使每個(gè)或項(xiàng)為0時(shí)輸入變量的取值，然后在該取值所對(duì)應(yīng)的方格內(nèi)填0。 )(5CBCAF: )(CA: )(CB 當(dāng)ABC=10時(shí)，該或項(xiàng)為0，對(duì)應(yīng)兩個(gè)方格(M4、M6)處填0。當(dāng)ABC=10時(shí)，該或項(xiàng)為0，對(duì)應(yīng)兩個(gè)方格(M2、M6)處填0。某些最大項(xiàng)重復(fù)，填一次即可。

33、F5的卡諾圖如圖2-18所示。 圖 2-18 F5的卡諾圖 1ABC000111100100011112.6.3 最小項(xiàng)合并規(guī)律最小項(xiàng)合并規(guī)律 在卡諾圖中，凡是幾何位置相鄰的最小項(xiàng)均可以合并。 兩個(gè)相鄰最小項(xiàng)合并為一項(xiàng)，消去一個(gè)互補(bǔ)變量。在卡諾圖上該合并圈稱(chēng)為單元圈，它所對(duì)應(yīng)的與項(xiàng)由圈內(nèi)沒(méi)有變化的那些變量組成，可以直接從卡諾圖中讀出。例如，圖2-19(a) 中m1、m3合并為 ，圖2-19(b)中m0、m4合并為 。 任何兩個(gè)相鄰的單元K圈也是相鄰項(xiàng)，仍然可以合并，消去互補(bǔ)變量。因此，如果K圈越大，消去的變量數(shù)就越多。 CACB 圖2-19(c)、 (d)表示四個(gè)相鄰最小項(xiàng)合并為一項(xiàng)，消去了兩

34、個(gè)變量，合并后積項(xiàng)由K圈對(duì)應(yīng)的沒(méi)有變化的那些變量組成。圖2-19(c)中m0、m1、m4、m5合并為 ，圖2-19(d)中m0、m2、m8、m10合并為 ，m5、m7、m13、m15合并為BD， m12、m13、m15、m14合并為AB。 圖2-19(e)表示八個(gè)相鄰最小項(xiàng)合并為一項(xiàng)，消去了三個(gè)變量，即DBCADmAm)15,13,11, 9 , 7 , 5 , 3 , 1 (,)15,14,13,12,11,10, 9 , 8( 綜上所述， 最小項(xiàng)合并有以下特點(diǎn)： 任何一個(gè)合并圈(即卡諾圈)所含的方格數(shù)為2i個(gè)。 必須按照相鄰規(guī)則畫(huà)卡諾圈，幾何位置相鄰包括三種情況：一是相接，即緊挨著的方格相

35、鄰；二是相對(duì)，即一行(或一列)的兩頭、兩邊、四角相鄰；三是相重，即以對(duì)稱(chēng)軸為中心對(duì)折起來(lái)重合的位置相鄰。 2m個(gè)方格合并，消去m個(gè)變量。合并圈越大，消去的變量數(shù)越多。 需要指出，上述最小項(xiàng)的合并規(guī)則，對(duì)最大項(xiàng)的合并同樣是適用的。只是因?yàn)樽畲箜?xiàng)是與函數(shù)的0值相對(duì)應(yīng)，在卡諾圖中則與0格對(duì)應(yīng)，因此，最大項(xiàng)的合并在卡諾圖中是相鄰的0格圈在一起。 圖 2-19 最小項(xiàng)合并規(guī)律 1ABC00011110011(b)ABC0001111001111ABCD0001111011100011110(c)(a)1ABCD0001111011111111100011110(d)ACACBCBDABCD0001111

36、011111111111100011110(e)ABDABD2.6.4 用卡諾圖化簡(jiǎn)邏輯函數(shù)用卡諾圖化簡(jiǎn)邏輯函數(shù) 1. 求最簡(jiǎn)與或式求最簡(jiǎn)與或式 在卡諾圖上以最少的卡諾圈數(shù)和盡可能大的卡諾圈覆蓋所有填1的方格， 即滿(mǎn)足最小覆蓋，就可以求得邏輯函數(shù)的最簡(jiǎn)與或式。 化簡(jiǎn)的一般步驟是： 畫(huà)出邏輯函數(shù)的K圖。 先從只有一種圈法的最小項(xiàng)開(kāi)始圈起，K圈的數(shù)目應(yīng)最少(與項(xiàng)的項(xiàng)數(shù)最少)，K圈應(yīng)盡量大(對(duì)應(yīng)與項(xiàng)中變量數(shù)最少)。 將每個(gè)K圈寫(xiě)成相應(yīng)的與項(xiàng)， 并將它們相或， 便得到最簡(jiǎn)與或式。 圈圈時(shí)應(yīng)注意，根據(jù)重疊律(A+A=A)，任何一個(gè)1格可以多次被圈用，但如果在某個(gè)K圈中所有的1格均已被別的K圈圈過(guò)，則該圈

37、為多余圈。為了避免出現(xiàn)多余圈， 應(yīng)保證每個(gè)K圈內(nèi)至少有一個(gè)1格只被圈一次。 【例 2-1】 求F= m(1, 3, 4, 5, 10, 11, 12, 13)的最簡(jiǎn)與或式。 解：解： 畫(huà)出F的K圖(見(jiàn)圖2-20)。 圖 2-20 例2-1的卡諾圖 ABCD000111101111111100011110 畫(huà)K圈。按照最小項(xiàng)合并規(guī)律，將可以合并的最小項(xiàng)分別圈起來(lái)。 根據(jù)化簡(jiǎn)原則，應(yīng)選擇最少的K圈和盡可能大的K圈覆蓋所有的1格。首先選擇只有一種圈法的BC，剩下四個(gè)1格(m1、m3、m10、m11)用兩個(gè)K圈 覆蓋。 可見(jiàn)一共只要用三個(gè)K圈即可覆蓋全部1格。 寫(xiě)出最簡(jiǎn)式。 CBADBA、CBADBA

38、CBF【例例 2-2】 求 ABCDCABDCBDBACDBF的最簡(jiǎn)與或式。 解：解： 畫(huà)出F的K圖。給出的F為一般與或式，將每個(gè)與項(xiàng)所覆蓋的最小項(xiàng)都填1，K圖如圖2-21所示。 圖 2-21 例2-2的卡諾圖 ABCD0001111011111111100011110(a)ABCD0001111011111111100011110(b) 畫(huà)K圈化簡(jiǎn)函數(shù)。 寫(xiě)出最簡(jiǎn)與或式。 本例有兩種圈法， 都可以得到最簡(jiǎn)式。 按圖2-21(a)圈法： ABDDCBDCACBF按圖2-21(b)圈法： ACDCABDBACBF該例說(shuō)明，邏輯函數(shù)的最簡(jiǎn)式不是惟一的。 【例 2-3】求 的最簡(jiǎn)與或式。 解：解：

39、畫(huà)F的K圖。 這是一個(gè)五變量邏輯函數(shù)，按五變量K圖中的編號(hào)填圖，得出F的K圖如圖2 - 22所示。 )31,29,27,25,24,23,22,21,20,16,15,13,11, 8 , 7 , 6 , 5 , 4 , 0(mF1ABCDE0001*11 1*11*1*100011110111111111 1*001011010110111101100圖 2-22 例2-3的卡諾圖 畫(huà)K圈化簡(jiǎn)函數(shù)。 先找只有一種圈法的最小項(xiàng)： 覆蓋；用余下覆蓋；：用覆蓋；：用覆蓋；，：用覆蓋；用、ABEmmEDCmmCEmmBDEmmCBmmm)31,29,27,25()24,16, 8 , 0()31,2

40、9,23,21,15,13, 7 , 5()3127,15,11()23,22,21,20, 7 , 6 , 5 , 4(:2581311226 寫(xiě)出最簡(jiǎn)式。 ABEEDCCEBDECBF 如何判斷得到的函數(shù)式是否為最簡(jiǎn)式呢? 下面從蘊(yùn)含項(xiàng)的概念討論最簡(jiǎn)式問(wèn)題： 蘊(yùn)含項(xiàng)(Implicant)。組成邏輯函數(shù)的每一個(gè)與項(xiàng)(積項(xiàng))稱(chēng)為該函數(shù)的蘊(yùn)含項(xiàng)。它可以是最小項(xiàng)，也可以是合并項(xiàng)。 本原蘊(yùn)含項(xiàng)(Prime Implicant)。如果邏輯函數(shù)的一個(gè)蘊(yùn)含項(xiàng)再也不能同該函數(shù)的其它蘊(yùn)含項(xiàng)合并組成變量數(shù)更少的蘊(yùn)含項(xiàng)，則稱(chēng)該蘊(yùn)含項(xiàng)為本原蘊(yùn)含項(xiàng)。實(shí)際上它對(duì)應(yīng)著卡諾圖中不能再擴(kuò)大的合并項(xiàng)， 即最大卡諾圈。 實(shí)質(zhì)本原

41、蘊(yùn)含項(xiàng)(Essential Prime Implicant)。不能被其它蘊(yùn)含項(xiàng)所包含的本原蘊(yùn)含項(xiàng)稱(chēng)為實(shí)質(zhì)本原蘊(yùn)含項(xiàng)。它對(duì)應(yīng)著卡諾圖中必不可少的最大卡諾圈，該圈至少包含了一個(gè)只有一種圈法的最小項(xiàng)。 例如，已知邏輯函數(shù)F1、F2的卡諾圖分別如圖2-23(a)、(b)所示，化簡(jiǎn)F1時(shí)只需用 3 個(gè)最大的K圈就可以覆蓋全部1格，如果用四個(gè)K圈肯定有一個(gè)多余圈。從圖2-23(a)中看出，合并項(xiàng)AC為多余項(xiàng)，因?yàn)樵撊χ忻總€(gè) 1 格被圈了兩次。因此可得出最簡(jiǎn)與或式為 CBDAABF1 化簡(jiǎn)圖2-23(b)的F2，只用六個(gè)最大的K圈覆蓋所有的 1 格，觀察每一個(gè)K圈都有一個(gè) 1 格只被圈過(guò)一次，因此這六個(gè)K圈

42、都必須存在，最簡(jiǎn)與或式為 CDBADCADCABACBDBF2圖 2-23 F1、F2的化簡(jiǎn)K圖 (a)ABCD00011110111111111100011110(b)1ABCD00011110111111111100011110 2. 求最簡(jiǎn)或與式求最簡(jiǎn)或與式 任何一個(gè)邏輯函數(shù)既可以等于其卡諾圖上填1的那些最小項(xiàng)之和，也可以等于其卡諾圖上填0的那些最大項(xiàng)之積， 因此，如果要求出某函數(shù)的最簡(jiǎn)或與式， 可以在該函數(shù)的卡諾圖上合并那些填0的相鄰項(xiàng)。這種方法簡(jiǎn)稱(chēng)為圈0合并， 其化簡(jiǎn)步驟及化簡(jiǎn)原則與圈1合并類(lèi)同，只要按圈逐一寫(xiě)出或項(xiàng)， 然后將所得的或項(xiàng)相與即可。但需注意，或項(xiàng)由K圈對(duì)應(yīng)的沒(méi)有變化的那

43、些變量組成，當(dāng)變量取值為0時(shí)寫(xiě)原變量， 取值為1時(shí)寫(xiě)反變量。 【例 2-4】 求 )13,11, 9 , 7 , 6 , 5 , 4 , 3 , 1 (mF的最簡(jiǎn)或與式。 解：解： 畫(huà)出F的K圖(見(jiàn)圖2-24)。 圈K圈。圈0合并，其規(guī)律與圈1相同，即K圈的數(shù)目應(yīng)最少，K圈所覆蓋的0格應(yīng)盡可能多。本例用三個(gè)K圈覆蓋所有0格。 寫(xiě)出最簡(jiǎn)或與式。 )()(CBADADBF圖 2-24 例2-4的卡諾圖 0ABCD0001111011001111010110000011110【例例 2-5】 求 CCABADCBAF)()(的最簡(jiǎn)或與式。 解：解： 畫(huà)出F的K圖。本例給出的F為一般或與式，因此將每個(gè)或項(xiàng)所覆蓋的最大項(xiàng)都填0，就可以得到F的K圖如圖2-25所示。 圈K圈化簡(jiǎn)函數(shù)。 寫(xiě)出最簡(jiǎn)或與式。 )(BADBACF 當(dāng)需要將邏輯函數(shù)化為最簡(jiǎn)與或非式時(shí)， 也可以采用合并0格的方式，即在卡諾圖上圈0格，先求出 的最簡(jiǎn)與或式， 然后根據(jù)F=F再求出F的最簡(jiǎn)與或非式。 F 圖 2-25 例2-5的卡諾圖ABCD0001111000000000000