數(shù)字邏輯 第二章

1、2021-7-2712021-7-272n邏輯代數(shù)的基本概念n邏輯代數(shù)的公理、定理及規(guī)則n邏輯函數(shù)表達(dá)式的形式與轉(zhuǎn)換n邏輯函數(shù)的化簡本章的組成2021-7-273n邏輯變量n邏輯運(yùn)算n邏輯函數(shù)2.1 邏輯代數(shù)的基本概念2021-7-274n邏輯命題n在陳述句中凡是可以判斷“真”、“假”的句子稱為“邏輯命題”n邏輯變量n邏輯命題可以用變量來表示，這種變量稱為“邏輯變量”n邏輯代數(shù)系統(tǒng)是一種二值代數(shù)系統(tǒng)n任何邏輯變量的取值只有“1”或“0”兩種，即表示“真”或“假”、“是”或“非”、“有”或“無”等兩種對(duì)立的狀態(tài)，不具有“量”的概念；n在數(shù)字系統(tǒng)中表現(xiàn)為開關(guān)的接通與斷開、晶體管的導(dǎo)通與截止、電壓的

2、高與低、信號(hào)的有與無等兩種穩(wěn)定的物理狀態(tài)邏輯變量2021-7-275n邏輯變量x、y、z具有如下關(guān)系n自反性：x=xn對(duì)稱性：若x=y，則y=xn傳遞性：若x=y，且y=z，則x=z邏輯變量2021-7-276n三種基本邏輯運(yùn)算n“或”運(yùn)算 ORn“與”運(yùn)算 ANDn“非”運(yùn)算 NOT邏輯運(yùn)算2021-7-277n亦稱邏輯加、邏輯和，Logic Addition、Logic Sumn運(yùn)算符號(hào)：n“或”邏輯：在數(shù)理邏輯中，當(dāng)決定事件發(fā)生的各種條件中，只要有一個(gè)或一個(gè)以上條件成立，該事件便發(fā)生。n表示形式：F=A+B F=ABn真值表（truth table）n運(yùn)算法則：0+0=0 0+1=1 1

3、+0=1 1+1=1邏輯運(yùn)算之“或”運(yùn)算 OR真值表ABF0000111011112021-7-278n亦稱邏輯乘、邏輯積，Logic Multiplication、Logic Productn運(yùn)算符號(hào)：n“與”邏輯：在數(shù)理邏輯中，當(dāng)決定事件發(fā)生的各種條件中，只有全部條件同時(shí)具備時(shí)，該事件才發(fā)生。n表示形式：F=AB F=ABn真值表（truth table）n運(yùn)算法則：00=0 01=0 10=0 11=1邏輯運(yùn)算之“與”運(yùn)算 AND真值表ABF0000101001112021-7-279n亦稱反運(yùn)算、邏輯非，Inversion、Logic Negationn運(yùn)算符號(hào)：n“非”邏輯：是邏輯代

4、數(shù)所特有的一種形式。在數(shù)理邏輯中，事件的發(fā)生取決于條件的否定。n表示形式：F= A F= An真值表（truth table）n運(yùn)算法則：0 =1 1 =0邏輯運(yùn)算之“非”運(yùn)算 NOT真值表AF01102021-7-2710n定義：設(shè)有n個(gè)邏輯變量A1,A2, An，則 代表A1,A2, An構(gòu)成的邏輯函數(shù)， 的值取決于A1,A2, An的取值。n特點(diǎn)n邏輯變量和邏輯函數(shù)的取值只有“0”和“1”兩種n邏輯函數(shù)中各變量之間的運(yùn)算關(guān)系只能是“與”、“或”、“非”三種基本邏輯運(yùn)算n邏輯函數(shù)的相等n設(shè)有兩個(gè)邏輯函數(shù)： 若對(duì)應(yīng)與邏輯變量A1,A2, An的任何一組取值，F(xiàn)1和F2的值都相同，則稱函數(shù)F1

5、和F2相等，記作F1=F2n如果F1和F2有相同的真值表，則F1=F2n如果F1=F2，則它們的真值表一定相同邏輯函數(shù)nAAAf,21nAAAfF,1121nAAAfF,2221nAAAf,212021-7-2711n邏輯代數(shù)的公理和基本定理n邏輯代數(shù)的重要規(guī)則n復(fù)合邏輯2.2 邏輯代數(shù)的公理、定理及規(guī)則2021-7-2712n公理系統(tǒng)n公理1，交換律：A+B=B+A AB=BAn公理2，結(jié)合律：(A+B)+C= A+(B+C)n公理3，分配律：A+(BC)=(A+B)(A+C) A(B+C)=AB+ACn公理4，0-1律：A+0=A A1=A A+1=1 A0=0n公理5，互補(bǔ)律：A+A=1

6、 AA=0n公理系統(tǒng)滿足：n一致性：公理系統(tǒng)內(nèi)各條公理之間不應(yīng)當(dāng)出現(xiàn)矛盾n獨(dú)立性：公理系統(tǒng)內(nèi)任何一條公理都不能由另一條公理來證明n完備性：所有定理都可以由公理系統(tǒng)推導(dǎo)出來邏輯代數(shù)的公理和基本定理2021-7-2713n基本定理n定理1：0+0=0 1+0=1 0+1=1 1+1=1 00=0 10=0 01=0 11=1 推論：1=0 0=1n定理2，重迭律： A+A=A AA=An定理3，吸收律：A+AB=A A(A+B)=An定理4，廣義吸收律： A+AB=A+B A(A+B)=ABn定理5，對(duì)合律：A=An定理6，反演律，狄摩根定理：A+B=AB AB=A+Bn定理7，吸收律：AB+AB

7、=A (A+B)(A+B)=An定理8，包含律，多余項(xiàng)定理：AB+ AC+BC= AB+ AC(A+B)(A+C)(B+C)=(A+B)(A+C)邏輯代數(shù)的公理和基本定理2021-7-2714n代入規(guī)則n任何一個(gè)含有變量A的等式，如果將所有出現(xiàn)A的位置都代之以同一個(gè)邏輯函數(shù)F，則等式仍然成立。邏輯代數(shù)的重要規(guī)則2021-7-2715n反演規(guī)則（香農(nóng)定理）n設(shè)F為一個(gè)邏輯函數(shù)表達(dá)式，如果將F中所有的“”變?yōu)椤?”、“+”變?yōu)椤啊薄ⅰ?”變?yōu)椤?”、“1”變?yōu)椤?”、原變量變?yōu)榉醋兞?A變?yōu)锳)、反變量變?yōu)樵兞?A變?yōu)锳)，則所得到的新的邏輯函數(shù)表達(dá)式就是原函數(shù)F的反函數(shù)F。n若 ，則n n注意

8、：使用反演規(guī)則時(shí)，應(yīng)保持原函數(shù)表達(dá)式中運(yùn)算符號(hào)的優(yōu)先順序不變，且兩個(gè)以上變量的公用“非”號(hào)保持不變。（優(yōu)先順序：“非”、“與”、“或”）邏輯代數(shù)的重要規(guī)則1 , 0,21nAAAfF0, 1 ,21nAAAfFFF 2021-7-2716n對(duì)偶規(guī)則n對(duì)偶式：設(shè)F為一個(gè)邏輯函數(shù)表達(dá)式，如果將F中所有的“”變?yōu)椤?”、“+”變?yōu)椤啊?、?”變?yōu)椤?”、“1”變?yōu)椤?”，而邏輯變量保持不變，則所得到的新的邏輯函數(shù)表達(dá)式稱為函數(shù)F的對(duì)偶式，記作F。（必須保持原函數(shù)的運(yùn)算順序不變）n若 ，則nF和F互為對(duì)偶式，即(F)=Fn對(duì)偶規(guī)則：若兩個(gè)邏輯函數(shù)表達(dá)式F和G相等，則它們的對(duì)偶式F和G也相等。n若F=G

9、，則F=G邏輯代數(shù)的重要規(guī)則1 , 0,21nAAAfF0, 1 ,21nAAAfF2021-7-2717n與非邏輯(NAND)：“與”和“非”的復(fù)合邏輯n表達(dá)式形式：n功能：只當(dāng)所有變量的取值全為1時(shí)，F(xiàn)=0，否則，F(xiàn)=1。n或非邏輯(NOR)：“或”和“非”的復(fù)合邏輯n表達(dá)式形式：n功能：只當(dāng)所有變量的取值全為0時(shí)，F(xiàn)=1，否則，F(xiàn)=0。n與或非邏輯： “與”、“或”和“非”的復(fù)合邏輯n表達(dá)式形式：復(fù)合邏輯CBAFCBAFEFCDABF2021-7-2718n異或邏輯(XOR)n表達(dá)式形式：n功能：當(dāng)兩個(gè)變量的取值相異時(shí)，F(xiàn)=1，否則，F(xiàn)=0。n當(dāng)多個(gè)(3個(gè))變量時(shí)，當(dāng)有奇數(shù)個(gè)變量取值為1

10、時(shí)，F(xiàn)=1，否則，F(xiàn)=0。n奇偶律： 求補(bǔ)律：n同或邏輯(XNOR)n表達(dá)式形式：F=A Bn功能：當(dāng)兩個(gè)變量的取值相同時(shí)，F(xiàn)=1，否則，F(xiàn)=0。n奇偶律： A A=1 A 1=A 求補(bǔ)律： A A=0 A 0=A復(fù)合邏輯BAFA0A0AAA1A1AA2021-7-2719n異或邏輯與同或邏輯的關(guān)系n對(duì)于二變量有如下關(guān)系： A B A Bn對(duì)于多變量(3個(gè))有如下關(guān)系：n偶數(shù)個(gè)變量時(shí)具有互補(bǔ)關(guān)系 如： A B C Dn奇數(shù)個(gè)變量時(shí)具有相等關(guān)系 如： A B C復(fù)合邏輯BABADCBACBA2021-7-2720n邏輯函數(shù)的表示法n邏輯函數(shù)表達(dá)式的基本形式n邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式n邏輯函數(shù)表達(dá)

11、式的轉(zhuǎn)換2.3 邏輯函數(shù)表達(dá)式的形式與轉(zhuǎn)換2021-7-2721n邏輯表達(dá)式n真值表n卡諾圖邏輯函數(shù)的表示法2021-7-2722n邏輯表達(dá)式是由邏輯變量、常量和運(yùn)算符所構(gòu)成的式子n書寫時(shí)可簡化n“非”運(yùn)算可不加括號(hào)n“與”運(yùn)算符常可省略n如果有括號(hào)，則可按先“非”后“與”再“或”的規(guī)則省去括號(hào)，如邏輯表達(dá)式CBBACBBA2021-7-2723n對(duì)一函數(shù)求出所有輸入變量取值下的函數(shù)值，并用表格形式記錄下來，這種表格稱為真值表，亦稱全值表。n真值表由兩部分組成n左邊一欄列出變量的所有取值組合，n個(gè)邏輯變量則有2n種可能的取值組合n右邊一欄為相應(yīng)變量取值組合下的邏輯函數(shù)值真值表2021-7-27

12、24n是由表示邏輯變量的所有可能組合的小方格所構(gòu)成的一幅或多幅方格子平面圖。將在第四節(jié)中詳述?？ㄖZ圖2021-7-2725n一個(gè)邏輯命題可以用多種形式的邏輯函數(shù)來描述，每一種函數(shù)式對(duì)應(yīng)著一種邏輯電路。n邏輯函數(shù)表達(dá)式種最基本的兩種形式是“與或”式和“或與”式n“與或”式(Sum of Product)：即“積之和”表達(dá)式，是指一個(gè)函數(shù)表達(dá)式中包含著若干個(gè)“積”項(xiàng)，每個(gè)“積”項(xiàng)中可以有一個(gè)或多個(gè)以原變量或反變量形式出現(xiàn)的字母，所有這些“積”項(xiàng)的“和”就表示了一個(gè)函數(shù)。n“或與”式(Product of Sum)：即“和之積”表達(dá)式，是指一個(gè)函數(shù)表達(dá)式中包含著若干個(gè)“和”項(xiàng)，每個(gè)“和”項(xiàng)中有若干個(gè)

13、以原變量或反變量形式出現(xiàn)的字母，所有這些“和”項(xiàng)的“積”就表示了一個(gè)函數(shù)。邏輯函數(shù)表達(dá)式的基本形式2021-7-2726n其它形式的表達(dá)式：與非式、或非式、與或非式、與非-與式、或非-或式、或與非式等n轉(zhuǎn)換n對(duì)與或表達(dá)式二次求補(bǔ)可轉(zhuǎn)換為與非式、或與非式、或非-或式n對(duì)或與表達(dá)式二次求補(bǔ)可轉(zhuǎn)換為或非式、與或非式、與非-與式邏輯函數(shù)表達(dá)式的基本形式2021-7-2727n最小項(xiàng)表達(dá)式n最大項(xiàng)表達(dá)式n兩種標(biāo)準(zhǔn)形式的關(guān)系邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式2021-7-2728n最小項(xiàng)(Minterm)：一個(gè)具有n個(gè)變量的函數(shù)的“積”項(xiàng)如果包含全部的n個(gè)變量，每個(gè)變量都以原變量或反變量形式出現(xiàn)，且僅出現(xiàn)一次，則這

14、個(gè)“積”項(xiàng)稱為n個(gè)變量的最小項(xiàng)。n最小項(xiàng)表達(dá)式：由最小項(xiàng)之和所構(gòu)成的函數(shù)表達(dá)式，亦稱標(biāo)準(zhǔn)“積之和”表達(dá)式、標(biāo)準(zhǔn)與或式、邏輯函數(shù)的第一范式。n表示形式n最小項(xiàng)通常用mi表示n下標(biāo)i的確定規(guī)則：變量按一定次序排列，如果積項(xiàng)中的變量以原變量出現(xiàn)，則記以1；變量以反變量出現(xiàn)，則記以0。這樣構(gòu)成的二進(jìn)制數(shù)稱為轉(zhuǎn)換碼，其所對(duì)應(yīng)的十進(jìn)制數(shù)就是該最小項(xiàng)mi的下標(biāo)i的值。n最小項(xiàng)表達(dá)式的表示形式F(A,B,C)=ABC+ABC+ABC+ABC=m2+m3+m6+m7=m(2,3,6,7)最小項(xiàng)表達(dá)式2021-7-2729n最小項(xiàng)性質(zhì)n任意一個(gè)最小項(xiàng)只有一組與之相對(duì)應(yīng)的變量組合取值使其值為1。nn個(gè)變量的全體最小

15、項(xiàng)共有2n個(gè),而且它們之和為1，記為：n任意兩個(gè)最小項(xiàng)mi和mj(ij)之積為0，記為：mimj=0 (i j)nn變量的最小項(xiàng)有n個(gè)相鄰項(xiàng)(相鄰項(xiàng)：兩個(gè)最小項(xiàng)間只有一個(gè)變量不同)最小項(xiàng)表達(dá)式1201niim2021-7-2730n最大項(xiàng)(Maxterm)：一個(gè)具有n個(gè)變量的函數(shù)的“和”項(xiàng)如果包含全部的n個(gè)變量，每個(gè)變量都以原變量或反變量形式出現(xiàn)，且僅出現(xiàn)一次，則這個(gè)“和”項(xiàng)稱為n個(gè)變量的最大項(xiàng)。n最大項(xiàng)表達(dá)式：由最大項(xiàng)之積所構(gòu)成的函數(shù)表達(dá)式，亦稱標(biāo)準(zhǔn)“和之積”表達(dá)式、標(biāo)準(zhǔn)或與式、邏輯函數(shù)的第二范式。n表示形式n最大項(xiàng)通常用Mi表示n下標(biāo)i的確定規(guī)則：變量按一定次序排列，如果和項(xiàng)中的變量以原變

16、量出現(xiàn)，則記以0；變量以反變量出現(xiàn)，則記以1。這樣構(gòu)成的二進(jìn)制數(shù)的轉(zhuǎn)換碼所對(duì)應(yīng)的十進(jìn)制數(shù)就是該最大項(xiàng)Mi的下標(biāo)i的值。n最大項(xiàng)表達(dá)式的表示形式 F(A,B,C)=(A+B+C)(A+B+C)(A+B+C)(A+B+C) =M0M1M4M5 =M(0,1,4,5)最大項(xiàng)表達(dá)式2021-7-2731n最大項(xiàng)性質(zhì)n每個(gè)最大項(xiàng)只有一組輸入變量組合取值使其值為0。nn個(gè)變量的全部最大項(xiàng)共有2n個(gè)，而且它們之積為0，記為：n任意兩個(gè)最大項(xiàng)Mi和Mj(ij)之和為1，記為：Mi+Mj=1 (i j)nn變量的最大項(xiàng)有n個(gè)鄰項(xiàng)最大項(xiàng)表達(dá)式0M120nii2021-7-2732兩種標(biāo)準(zhǔn)形式的關(guān)系n最小項(xiàng)和最大項(xiàng)

17、是互補(bǔ)的關(guān)系：Mi=mi Mi=miMi+mi=1 Mimi=0n任一邏輯函數(shù)，都可以表示成“最小項(xiàng)之和”及“最大項(xiàng)之積”形式n方法：邏輯函數(shù)的一種標(biāo)準(zhǔn)形式轉(zhuǎn)換成另一種標(biāo)準(zhǔn)形式時(shí)，互換和符號(hào)，并在符號(hào)后列出原函數(shù)中缺少的那些數(shù)字2021-7-2733邏輯函數(shù)表達(dá)式的轉(zhuǎn)換n代數(shù)轉(zhuǎn)換法n真值表轉(zhuǎn)換法2021-7-2734代數(shù)轉(zhuǎn)換法n用代數(shù)轉(zhuǎn)換法將邏輯函數(shù)表達(dá)式轉(zhuǎn)換成“最小項(xiàng)之和”形式n第一步，將函數(shù)表達(dá)式轉(zhuǎn)換成一般“與-或”表達(dá)式n第二步，將函數(shù)表達(dá)式中的非最小項(xiàng)的“與”項(xiàng)都擴(kuò)展成最小項(xiàng)n用代數(shù)轉(zhuǎn)換法將邏輯函數(shù)表達(dá)式轉(zhuǎn)換成“最大項(xiàng)之和”形式n第一步，將函數(shù)表達(dá)式轉(zhuǎn)換成一般“或-與”表達(dá)式n第二步，

18、將函數(shù)表達(dá)式中的非最大項(xiàng)的“或”項(xiàng)都擴(kuò)展成最大項(xiàng)2021-7-2735真值表轉(zhuǎn)換法n化為“最小項(xiàng)之和”形式n假如在函數(shù)F的真值表中有n組變量的取值使函數(shù)F的值為1，那么函數(shù)F的“最小項(xiàng)之和”形式由這n組變量取值對(duì)應(yīng)的n個(gè)最小項(xiàng)組成n化為“最大項(xiàng)之積”形式n假如在函數(shù)F的真值表中有n組變量的取值使函數(shù)F的值為0，那么函數(shù)F的“最大項(xiàng)之積”形式由這n組變量取值對(duì)應(yīng)的n個(gè)最大項(xiàng)組成2021-7-27362.4 邏輯函數(shù)的化簡n化簡的目的n就是尋求一種最佳等效函數(shù)式，以便在用集成電路去實(shí)現(xiàn)此函數(shù)時(shí)，能獲得運(yùn)算速度快、可靠性高的電路，并且是所用集成電路塊數(shù)最少、輸入端數(shù)最少的電路。n化簡的方法主要有n代

19、數(shù)法n運(yùn)用邏輯代數(shù)的基本公式和法則對(duì)函數(shù)式進(jìn)行代數(shù)變換，消去多余項(xiàng)以獲得最簡函數(shù)式的方法，也稱公式化簡法。n圖解法卡諾圖化簡法n把真值表按坐標(biāo)架的形式加以變換，將相應(yīng)的n個(gè)變量(具有2n個(gè)最小項(xiàng))的邏輯函數(shù)連同它的系數(shù)一起列成一個(gè)表，這個(gè)表稱為卡諾圖。n列表法2021-7-2737代數(shù)化簡法n“與或”表達(dá)式的化簡n“或與”表達(dá)式的化簡2021-7-2738“與或”表達(dá)式的化簡n衡量最簡的與或式的兩個(gè)條件n表達(dá)式中的乘積項(xiàng)(與項(xiàng))個(gè)數(shù)最少n在滿足上述的條件下，每個(gè)乘積項(xiàng)中的變量個(gè)數(shù)最少n常用方法n并項(xiàng)法：利用吸收律AB+AB=A以消去一個(gè)或多個(gè)變量n吸收法：利用吸收律A+AB=A消去多余的項(xiàng)n消

20、去法：利用廣義吸收律A+AB=A+B消去多余的變量n配項(xiàng)法：利用公理A1=A及A+A=1進(jìn)行化簡2021-7-2739“或與”表達(dá)式的化簡n衡量最簡的或與式的兩個(gè)條件n表達(dá)式中的或項(xiàng)個(gè)數(shù)最少n在滿足上述的條件下，每個(gè)或項(xiàng)中的變量個(gè)數(shù)最少n常用方法n直接化簡法n直接用定理、公式進(jìn)行化簡n二次對(duì)偶法n若原函數(shù)F是“或與”表達(dá)式，則它的對(duì)偶式F必然是“與或”表達(dá)式，對(duì)F使用公式等進(jìn)行化簡，化簡后再求F的對(duì)偶式(F)，即得F的最簡“或與”表達(dá)式2021-7-2740卡諾圖化簡法n卡諾圖的構(gòu)成n邏輯函數(shù)在卡諾圖上的表示n卡諾圖上最小項(xiàng)的合并n用卡諾圖化簡邏輯函數(shù)2021-7-2741卡諾圖的構(gòu)成n卡諾圖

21、是真值表的二維形式。n卡諾圖的單元格采用以下的排列方式：相鄰單元格的真值表輸入只有一位不同。AB010m0m21m1m3AB010ABAB1ABABBBAAAA二變量2021-7-2742卡諾圖的構(gòu)成ABCD0001111000m0m4m12m801m1m5m13m911m3m7m15m1110m2m6m14m10ABC000111100m0m2m6m41m1m3m7m5三變量四變量2021-7-2743卡諾圖的構(gòu)成n構(gòu)成的特點(diǎn)nn變量的卡諾圖包含有2n個(gè)小方塊，每個(gè)小方格對(duì)應(yīng)真值表中的一行。n整個(gè)卡諾圖總是被每個(gè)變量分成兩半：原變量和反變量各占一半。任一變量的原變量和反變量所占區(qū)域，總是被其

22、它變量分成兩半。n在垂直方向、水平方向上相鄰的小方格所對(duì)應(yīng)的最小項(xiàng)，僅有一個(gè)變量狀態(tài)不同。n除掉某個(gè)小方格外的整個(gè)卡諾圖區(qū)域?qū)?yīng)一個(gè)最大項(xiàng)，該最大項(xiàng)的下標(biāo)值就是被除掉的小方格中最小項(xiàng)的下標(biāo)值。2021-7-2744卡諾圖的構(gòu)成n方格的相鄰n幾何相鄰：在同一幅卡諾圖中，有一條公共邊界的方格。n相重相鄰：在相鄰的兩幅卡諾圖中，處于相同位置的兩個(gè)方格。n在n變量的卡諾圖中，每個(gè)方格(最小項(xiàng))有n個(gè)相鄰方格(相鄰最小項(xiàng))。2021-7-2745邏輯函數(shù)在卡諾圖上的表示n若邏輯函數(shù)是“最小項(xiàng)之和”形式，則在卡諾圖中與所有最小項(xiàng)對(duì)應(yīng)的小方格填“1”，其余的填“0”。n若邏輯函數(shù)是“與或”表達(dá)式，可先將函數(shù)展開成“最小項(xiàng)之和”形式。（或者將各與項(xiàng)分別表示在卡諾圖上，然后疊加起來）n若邏輯函數(shù)是“最大項(xiàng)之積”形式，則式中最大項(xiàng)下標(biāo)值對(duì)應(yīng)的方格填“0”，其余的填“1”。2021-7-2746卡諾圖上最小項(xiàng)的合并n相鄰最小項(xiàng)(相鄰方格)可以合并成一個(gè)較大的區(qū)域。n卡諾圈：表示相鄰小方格合并結(jié)果的圈。n以“1”卡諾圈為例：n卡諾圈中的“1”方