數(shù)字邏輯 第二章

2023/2/61第二章邏輯代數(shù)基礎(chǔ)2023/2/62邏輯代數(shù)的基本概念邏輯代數(shù)的公理、定理及規(guī)則邏輯函數(shù)表達(dá)式的形式與轉(zhuǎn)換邏輯函數(shù)的化簡(jiǎn)本章的組成2023/2/63邏輯變量邏輯運(yùn)算邏輯函數(shù)2.1邏輯代數(shù)的基本概念2023/2/64邏輯命題在陳述句中凡是可以判斷“真”、“假”的句子稱為“邏輯命題”邏輯變量邏輯命題可以用變量來表示，這種變量稱為“邏輯變量”邏輯代數(shù)系統(tǒng)是一種二值代數(shù)系統(tǒng)任何邏輯變量的取值只有“1”或“0”兩種，即表示“真”或“假”、“是”或“非”、“有”或“無”等兩種對(duì)立的狀態(tài)，不具有“量”的概念；在數(shù)字系統(tǒng)中表現(xiàn)為開關(guān)的接通與斷開、晶體管的導(dǎo)通與截止、電壓的高與低、信號(hào)的有與無等兩種穩(wěn)定的物理狀態(tài)邏輯變量2023/2/65邏輯變量x、y、z具有如下關(guān)系自反性：x=x對(duì)稱性：若x=y，則y=x傳遞性：若x=y，且y=z，則x=z邏輯變量2023/2/66三種基本邏輯運(yùn)算“或”運(yùn)算OR“與”運(yùn)算AND“非”運(yùn)算NOT邏輯運(yùn)算2023/2/67亦稱邏輯加、邏輯和，LogicAddition、LogicSum運(yùn)算符號(hào)：＋∨“或”邏輯：在數(shù)理邏輯中，當(dāng)決定事件發(fā)生的各種條件中，只要有一個(gè)或一個(gè)以上條件成立，該事件便發(fā)生。表示形式：F=A+BF=A∨B真值表（truthtable）運(yùn)算法則：0+0=00+1=11+0=11+1=1邏輯運(yùn)算之“或”運(yùn)算OR真值表ABF0000111011112023/2/68亦稱邏輯乘、邏輯積，LogicMultiplication、LogicProduct運(yùn)算符號(hào)：·∧“與”邏輯：在數(shù)理邏輯中，當(dāng)決定事件發(fā)生的各種條件中，只有全部條件同時(shí)具備時(shí)，該事件才發(fā)生。表示形式：F=A·BF=A∧B真值表（truthtable）運(yùn)算法則：0·0=00·1=01·0=01·1=1邏輯運(yùn)算之“與”運(yùn)算AND真值表ABF0000101001112023/2/69亦稱反運(yùn)算、邏輯非，Inversion、LogicNegation運(yùn)算符號(hào)：“非”邏輯：是邏輯代數(shù)所特有的一種形式。在數(shù)理邏輯中，事件的發(fā)生取決于條件的否定。表示形式：F=AF=A真值表（truthtable）運(yùn)算法則：0=11=0邏輯運(yùn)算之“非”運(yùn)算NOT真值表AF01102023/2/610定義：設(shè)有n個(gè)邏輯變量A1,A2,……An，則代表A1,A2,……An構(gòu)成的邏輯函數(shù)，的值取決于A1,A2,……An的取值。特點(diǎn)邏輯變量和邏輯函數(shù)的取值只有“0”和“1”兩種邏輯函數(shù)中各變量之間的運(yùn)算關(guān)系只能是“與”、“或”、“非”三種基本邏輯運(yùn)算邏輯函數(shù)的相等設(shè)有兩個(gè)邏輯函數(shù)：若對(duì)應(yīng)與邏輯變量A1,A2,……An的任何一組取值，F(xiàn)1和F2的值都相同，則稱函數(shù)F1和F2相等，記作F1=F2如果F1和F2有相同的真值表，則F1=F2如果F1=F2，則它們的真值表一定相同邏輯函數(shù)2023/2/611邏輯代數(shù)的公理和基本定理邏輯代數(shù)的重要規(guī)則復(fù)合邏輯2.2邏輯代數(shù)的公理、定理及規(guī)則2023/2/612公理系統(tǒng)公理1，交換律：A+B=B+AA·B=B·A公理2，結(jié)合律：(A+B)+C=A+(B+C)公理3，分配律：A+(B·C)=(A+B)·(A+C)A·(B+C)=A·B+A·C公理4，0-1律：A+0=AA·1=AA+1=1A·0=0公理5，互補(bǔ)律：A+A=1A·A=0公理系統(tǒng)滿足：一致性：公理系統(tǒng)內(nèi)各條公理之間不應(yīng)當(dāng)出現(xiàn)矛盾獨(dú)立性：公理系統(tǒng)內(nèi)任何一條公理都不能由另一條公理來證明完備性：所有定理都可以由公理系統(tǒng)推導(dǎo)出來邏輯代數(shù)的公理和基本定理2023/2/613基本定理定理1：0+0=01+0=10+1=11+1=10·0=01·0=00·1=01·1=1

推論：1=00=1定理2，重迭律：A+A=AA·A=A定理3，吸收律：A+A·B=AA·(A+B)=A定理4，廣義吸收律：A+A·B=A+BA·(A+B)=A·B定理5，對(duì)合律：A=A定理6，反演律，狄·摩根定理：A+B=A·BA·B=A+B定理7，吸收律：A·B+A·B=A(A+B)·(A+B)=A定理8，包含律，多余項(xiàng)定理：A·B+A·C+B·C=A·B+A·C(A+B)·(A+C)·(B+C)=(A+B)·(A+C)邏輯代數(shù)的公理和基本定理2023/2/614代入規(guī)則任何一個(gè)含有變量A的等式，如果將所有出現(xiàn)A的位置都代之以同一個(gè)邏輯函數(shù)F，則等式仍然成立。邏輯代數(shù)的重要規(guī)則2023/2/615反演規(guī)則（香農(nóng)定理）設(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。若，則

注意：使用反演規(guī)則時(shí)，應(yīng)保持原函數(shù)表達(dá)式中運(yùn)算符號(hào)的優(yōu)先順序不變，且兩個(gè)以上變量的公用“非”號(hào)保持不變。（優(yōu)先順序：“非”、“與”、“或”）邏輯代數(shù)的重要規(guī)則2023/2/616對(duì)偶規(guī)則對(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)算順序不變）若，則F和F’互為對(duì)偶式，即(F’)’=F對(duì)偶規(guī)則：若兩個(gè)邏輯函數(shù)表達(dá)式F和G相等，則它們的對(duì)偶式F’和G’也相等。若F=G，則F’=G’邏輯代數(shù)的重要規(guī)則2023/2/617與非邏輯(NAND)：“與”和“非”的復(fù)合邏輯表達(dá)式形式：功能：只當(dāng)所有變量的取值全為1時(shí)，F(xiàn)=0，否則，F(xiàn)=1。或非邏輯(NOR)：“或”和“非”的復(fù)合邏輯表達(dá)式形式：功能：只當(dāng)所有變量的取值全為0時(shí)，F(xiàn)=1，否則，F(xiàn)=0。與或非邏輯：“與”、“或”和“非”的復(fù)合邏輯表達(dá)式形式：復(fù)合邏輯2023/2/618異或邏輯(XOR)表達(dá)式形式：功能：當(dāng)兩個(gè)變量的取值相異時(shí)，F(xiàn)=1，否則，F(xiàn)=0。當(dāng)多個(gè)(≥3個(gè))變量時(shí)，當(dāng)有奇數(shù)個(gè)變量取值為1時(shí)，F(xiàn)=1，否則，F(xiàn)=0。奇偶律：求補(bǔ)律：同或邏輯(XNOR)表達(dá)式形式：F=A⊙B功能：當(dāng)兩個(gè)變量的取值相同時(shí)，F(xiàn)=1，否則，F(xiàn)=0。奇偶律：A⊙A=1A⊙1=A

求補(bǔ)律：A⊙A=0A⊙0=A復(fù)合邏輯2023/2/619異或邏輯與同或邏輯的關(guān)系對(duì)于二變量有如下關(guān)系：

A⊙BA⊙B對(duì)于多變量(≥3個(gè))有如下關(guān)系：偶數(shù)個(gè)變量時(shí)具有互補(bǔ)關(guān)系如：A⊙B⊙C⊙D奇數(shù)個(gè)變量時(shí)具有相等關(guān)系如：A⊙B⊙C復(fù)合邏輯2023/2/620邏輯函數(shù)的表示法邏輯函數(shù)表達(dá)式的基本形式邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式邏輯函數(shù)表達(dá)式的轉(zhuǎn)換2.3邏輯函數(shù)表達(dá)式的形式與轉(zhuǎn)換2023/2/621邏輯表達(dá)式真值表卡諾圖邏輯函數(shù)的表示法2023/2/622邏輯表達(dá)式是由邏輯變量、常量和運(yùn)算符所構(gòu)成的式子書寫時(shí)可簡(jiǎn)化“非”運(yùn)算可不加括號(hào)“與”運(yùn)算符?？墒÷匀绻欣ㄌ?hào)，則可按先“非”后“與”再“或”的規(guī)則省去括號(hào)，如邏輯表達(dá)式2023/2/623對(duì)一函數(shù)求出所有輸入變量取值下的函數(shù)值，并用表格形式記錄下來，這種表格稱為真值表，亦稱全值表。真值表由兩部分組成左邊一欄列出變量的所有取值組合，n個(gè)邏輯變量則有2n種可能的取值組合右邊一欄為相應(yīng)變量取值組合下的邏輯函數(shù)值真值表2023/2/624是由表示邏輯變量的所有可能組合的小方格所構(gòu)成的一幅或多幅方格子平面圖。將在第四節(jié)中詳述?？ㄖZ圖2023/2/625一個(gè)邏輯命題可以用多種形式的邏輯函數(shù)來描述，每一種函數(shù)式對(duì)應(yīng)著一種邏輯電路。邏輯函數(shù)表達(dá)式種最基本的兩種形式是“與或”式和“或與”式“與或”式(SumofProduct)：即“積之和”表達(dá)式，是指一個(gè)函數(shù)表達(dá)式中包含著若干個(gè)“積”項(xiàng)，每個(gè)“積”項(xiàng)中可以有一個(gè)或多個(gè)以原變量或反變量形式出現(xiàn)的字母，所有這些“積”項(xiàng)的“和”就表示了一個(gè)函數(shù)?！盎蚺c”式(ProductofSum)：即“和之積”表達(dá)式，是指一個(gè)函數(shù)表達(dá)式中包含著若干個(gè)“和”項(xiàng)，每個(gè)“和”項(xiàng)中有若干個(gè)以原變量或反變量形式出現(xiàn)的字母，所有這些“和”項(xiàng)的“積”就表示了一個(gè)函數(shù)。邏輯函數(shù)表達(dá)式的基本形式2023/2/626其它形式的表達(dá)式：與非式、或非式、與或非式、與非-與式、或非-或式、或與非式等轉(zhuǎn)換對(duì)與或表達(dá)式二次求補(bǔ)可轉(zhuǎn)換為與非式、或與非式、或非-或式對(duì)或與表達(dá)式二次求補(bǔ)可轉(zhuǎn)換為或非式、與或非式、與非-與式邏輯函數(shù)表達(dá)式的基本形式2023/2/627最小項(xiàng)表達(dá)式最大項(xiàng)表達(dá)式兩種標(biāo)準(zhǔn)形式的關(guān)系邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式2023/2/628最小項(xiàng)(Minterm)：一個(gè)具有n個(gè)變量的函數(shù)的“積”項(xiàng)如果包含全部的n個(gè)變量，每個(gè)變量都以原變量或反變量形式出現(xiàn)，且僅出現(xiàn)一次，則這個(gè)“積”項(xiàng)稱為n個(gè)變量的最小項(xiàng)。最小項(xiàng)表達(dá)式：由最小項(xiàng)之和所構(gòu)成的函數(shù)表達(dá)式，亦稱標(biāo)準(zhǔn)“積之和”表達(dá)式、標(biāo)準(zhǔn)與或式、邏輯函數(shù)的第一范式。表示形式最小項(xiàng)通常用mi表示下標(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的值。最小項(xiàng)表達(dá)式的表示形式F(A,B,C)=ABC+ABC+ABC+ABC=m2+m3+m6+m7=∑m(2,3,6,7)最小項(xiàng)表達(dá)式2023/2/629最小項(xiàng)性質(zhì)任意一個(gè)最小項(xiàng)只有一組與之相對(duì)應(yīng)的變量組合取值使其值為1。n個(gè)變量的全體最小項(xiàng)共有2n個(gè),而且它們之和為1，記為：任意兩個(gè)最小項(xiàng)mi和mj(i≠j)之積為0，記為：mi·mj=0(i≠j)n變量的最小項(xiàng)有n個(gè)相鄰項(xiàng)(相鄰項(xiàng)：兩個(gè)最小項(xiàng)間只有一個(gè)變量不同)最小項(xiàng)表達(dá)式2023/2/630最大項(xiàng)(Maxterm)：一個(gè)具有n個(gè)變量的函數(shù)的“和”項(xiàng)如果包含全部的n個(gè)變量，每個(gè)變量都以原變量或反變量形式出現(xiàn)，且僅出現(xiàn)一次，則這個(gè)“和”項(xiàng)稱為n個(gè)變量的最大項(xiàng)。最大項(xiàng)表達(dá)式：由最大項(xiàng)之積所構(gòu)成的函數(shù)表達(dá)式，亦稱標(biāo)準(zhǔn)“和之積”表達(dá)式、標(biāo)準(zhǔn)或與式、邏輯函數(shù)的第二范式。表示形式最大項(xiàng)通常用Mi表示下標(biāo)i的確定規(guī)則：變量按一定次序排列，如果和項(xiàng)中的變量以原變量出現(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的值。最大項(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á)式2023/2/631最大項(xiàng)性質(zhì)每個(gè)最大項(xiàng)只有一組輸入變量組合取值使其值為0。n個(gè)變量的全部最大項(xiàng)共有2n個(gè)，而且它們之積為0，記為：任意兩個(gè)最大項(xiàng)Mi和Mj(i≠j)之和為1，記為：Mi+Mj=1(i≠j)n變量的最大項(xiàng)有n個(gè)鄰項(xiàng)最大項(xiàng)表達(dá)式2023/2/632兩種標(biāo)準(zhǔn)形式的關(guān)系最小項(xiàng)和最大項(xiàng)是互補(bǔ)的關(guān)系：Mi=miMi=miMi+mi=1Mi·mi=0任一邏輯函數(shù)，都可以表示成“最小項(xiàng)之和”及“最大項(xiàng)之積”形式方法：邏輯函數(shù)的一種標(biāo)準(zhǔn)形式轉(zhuǎn)換成另一種標(biāo)準(zhǔn)形式時(shí)，互換∑和∏符號(hào)，并在符號(hào)后列出原函數(shù)中缺少的那些數(shù)字2023/2/633邏輯函數(shù)表達(dá)式的轉(zhuǎn)換代數(shù)轉(zhuǎn)換法真值表轉(zhuǎn)換法2023/2/634代數(shù)轉(zhuǎn)換法用代數(shù)轉(zhuǎn)換法將邏輯函數(shù)表達(dá)式轉(zhuǎn)換成“最小項(xiàng)之和”形式第一步，將函數(shù)表達(dá)式轉(zhuǎn)換成一般“與-或”表達(dá)式第二步，將函數(shù)表達(dá)式中的非最小項(xiàng)的“與”項(xiàng)都擴(kuò)展成最小項(xiàng)用代數(shù)轉(zhuǎn)換法將邏輯函數(shù)表達(dá)式轉(zhuǎn)換成“最大項(xiàng)之和”形式第一步，將函數(shù)表達(dá)式轉(zhuǎn)換成一般“或-與”表達(dá)式第二步，將函數(shù)表達(dá)式中的非最大項(xiàng)的“或”項(xiàng)都擴(kuò)展成最大項(xiàng)2023/2/635真值表轉(zhuǎn)換法化為“最小項(xiàng)之和”形式假如在函數(shù)F的真值表中有n組變量的取值使函數(shù)F的值為1，那么函數(shù)F的“最小項(xiàng)之和”形式由這n組變量取值對(duì)應(yīng)的n個(gè)最小項(xiàng)組成化為“最大項(xiàng)之積”形式假如在函數(shù)F的真值表中有n組變量的取值使函數(shù)F的值為0，那么函數(shù)F的“最大項(xiàng)之積”形式由這n組變量取值對(duì)應(yīng)的n個(gè)最大項(xiàng)組成2023/2/6362.4邏輯函數(shù)的化簡(jiǎn)化簡(jiǎn)的目的就是尋求一種最佳等效函數(shù)式，以便在用集成電路去實(shí)現(xiàn)此函數(shù)時(shí)，能獲得運(yùn)算速度快、可靠性高的電路，并且是所用集成電路塊數(shù)最少、輸入端數(shù)最少的電路?；?jiǎn)的方法主要有代數(shù)法運(yùn)用邏輯代數(shù)的基本公式和法則對(duì)函數(shù)式進(jìn)行代數(shù)變換，消去多余項(xiàng)以獲得最簡(jiǎn)函數(shù)式的方法，也稱公式化簡(jiǎn)法。圖解法——卡諾圖化簡(jiǎn)法把真值表按坐標(biāo)架的形式加以變換，將相應(yīng)的n個(gè)變量(具有2n個(gè)最小項(xiàng))的邏輯函數(shù)連同它的系數(shù)一起列成一個(gè)表，這個(gè)表稱為卡諾圖。列表法2023/2/637代數(shù)化簡(jiǎn)法“與或”表達(dá)式的化簡(jiǎn)“或與”表達(dá)式的化簡(jiǎn)2023/2/638“與或”表達(dá)式的化簡(jiǎn)衡量最簡(jiǎn)的與或式的兩個(gè)條件表達(dá)式中的乘積項(xiàng)(與項(xiàng))個(gè)數(shù)最少在滿足上述的條件下，每個(gè)乘積項(xiàng)中的變量個(gè)數(shù)最少常用方法并項(xiàng)法：利用吸收律AB+AB=A以消去一個(gè)或多個(gè)變量吸收法：利用吸收律A+AB=A消去多余的項(xiàng)消去法：利用廣義吸收律A+AB=A+B消去多余的變量配項(xiàng)法：利用公理A·1=A及A+A=1進(jìn)行化簡(jiǎn)2023/2/639“或與”表達(dá)式的化簡(jiǎn)衡量最簡(jiǎn)的或與式的兩個(gè)條件表達(dá)式中的或項(xiàng)個(gè)數(shù)最少在滿足上述的條件下，每個(gè)或項(xiàng)中的變量個(gè)數(shù)最少常用方法直接化簡(jiǎn)法直接用定理、公式進(jìn)行化簡(jiǎn)二次對(duì)偶法若原函數(shù)F是“或與”表達(dá)式，則它的對(duì)偶式F’必然是“與或”表達(dá)式，對(duì)F’使用公式等進(jìn)行化簡(jiǎn)，化簡(jiǎn)后再求F’的對(duì)偶式(F’)’，即得F的最簡(jiǎn)“或與”表達(dá)式2023/2/640卡諾圖化簡(jiǎn)法卡諾圖的構(gòu)成邏輯函數(shù)在卡諾圖上的表示卡諾圖上最小項(xiàng)的合并用卡諾圖化簡(jiǎn)邏輯函數(shù)2023/2/641卡諾圖的構(gòu)成卡諾圖是真值表的二維形式?？ㄖZ圖的單元格采用以下的排列方式：相鄰單元格的真值表輸入只有一位不同。AB010m0m21m1m3AB010ABAB1ABABBBAAAA二變量2023/2/642卡諾圖的構(gòu)成ABCD0001111000m0m4m12m801m1m5m13m911m3m7m15m1110m2m6m14m10ABC000111100m0m2m6m41m1m3m7m5三變量四變量2023/2/643卡諾圖的構(gòu)成構(gòu)成的特點(diǎn)n變量的卡諾圖包含有2n個(gè)小方塊，每個(gè)小方格對(duì)應(yīng)真值表中的一行。整個(gè)卡諾圖總是被每個(gè)變量分成兩半：原變量和反變量各占一半。任一變量的原變量和反變量所占區(qū)域，總是被其它變量分成兩半。在垂直方向、水平方向上相鄰的小方格所對(duì)應(yīng)的最小項(xiàng)，僅有一個(gè)變量狀態(tài)不同。除掉某個(gè)小方格外的整個(gè)卡諾圖區(qū)域?qū)?yīng)一個(gè)最大項(xiàng)，該最大項(xiàng)的下標(biāo)值就是被除掉的小方格中最小項(xiàng)的下標(biāo)值。2023/2/644卡諾圖的構(gòu)成方格的相鄰幾何相鄰：在同一幅卡諾圖中，有一條公共邊界的方格。相重相鄰：在相鄰的兩幅卡諾圖中，處于相同位置的兩個(gè)方格。在n變量的卡諾圖中，每個(gè)方格(最小項(xiàng))有n個(gè)相鄰方格(相鄰最小項(xiàng))。2023/2/645邏輯函數(shù)在卡諾圖上的表示若邏輯函數(shù)是“最小項(xiàng)之和”形式，則在卡諾圖中與所有最小項(xiàng)對(duì)應(yīng)的小方格填“1”，其余的填“0”。若邏輯函數(shù)是“與或”表達(dá)式，可先將函數(shù)展開成“最小項(xiàng)之和”形式。（或者將各與項(xiàng)分別表示在卡諾圖上，然后疊加起來）若邏輯函數(shù)是“最大項(xiàng)之積”形式，則式中最大項(xiàng)下標(biāo)值對(duì)應(yīng)的方格填“0”，其余的填“1”。2023/2/646卡諾圖上最小項(xiàng)的合并相鄰最小項(xiàng)(相鄰方