基本邏輯電路的化簡方法

1、第二章 邏輯代數(shù)基礎(chǔ)2.1 邏輯代數(shù)運算提綱：n 邏輯變量與邏輯函數(shù)，n 邏輯代數(shù)運算，n 邏輯代數(shù)的公理和基本公式，n 邏輯代數(shù)的基本定理（三個），n 邏輯代數(shù)的常用公式。2.1.1 邏輯變量與邏輯函數(shù)采用邏輯變量表示數(shù)字邏輯的狀態(tài)，邏輯變量的輸入輸出之間構(gòu)成函數(shù)關(guān)系。邏輯常量：邏輯變量只有兩種可能的取值：“真”或“假”，習(xí)慣上，把“真”記為“1”，“假”記為“0”，這里“1”和“0”不表示數(shù)量的大小，表示完全對立的兩種狀態(tài)。2.1.2 邏輯代數(shù)運算基本邏輯運算與、或、非；復(fù)合邏輯運算。描述方法：邏輯表達式、真值表、邏輯符號（電路圖） 。定義：真值表描述各個變量取值組合和函數(shù)取值之間的對應(yīng)關(guān)

2、系。邏輯電平正邏輯與負邏輯。2.1.3 邏輯代數(shù)的公理和基本公式2.1.3.1 邏輯代數(shù)公理有關(guān)邏輯常量的基本邏輯運算規(guī)則，以及邏輯變量的取值。(1) 常量的“非”邏輯運算(24) 常量的與、或邏輯運算(5) 邏輯狀態(tài)只有”0”和”1”兩種取值2.1.3.2 邏輯代數(shù)的基本公式（基本定律）所謂“公式”，即“定律”，如表2. 1：表2. 1 邏輯代數(shù)的公式（基本公式部分）組名稱對偶的公式對備注101律變量與常量2重疊律同一個變量3互補律原變量與反變量之間的關(guān)系4還原律5交換律6結(jié)合律7分配律8反演律DeMorgan公式2.1.3.3 邏輯代數(shù)的三個基本定理所謂“定理”，即代數(shù)運算規(guī)則?；镜娜齻€

3、定理：n 代入定理在任何一個包含邏輯變量A的邏輯等式中，若以另外的邏輯式代入式中的所有A的位置，則等式依然成立。，n 反演定理，n 對偶定理。2.1.3.3.1 反演定理所謂“反演定理”，得到邏輯函數(shù)的“反”的定理。定義（反演定理）：將函數(shù)Y式中的所有n （基本運算符號）“與”換成“或”，“或”換成“與”；n （邏輯常量）“0”換成“1”，“1”換成“0”；n 原變量換成反變量，反變量換成原變量；注意：l 變換時要保持原式中邏輯運算的優(yōu)先順序；l 不屬于單個變量上的反號應(yīng)保持不變；則，所得到的表達式是的表達式。例2.1: 已知，求。解：（利用反演定理）例2.2: 已知，求。解：（利用反演定理）

4、例2.3: （反演律和反演定理），已知Y=A(B+C)+CD，求。解：（方法一、用反演定理）解：（方法二、反復(fù)用反演律）注意：對等式兩端根據(jù)反演定理進行操作是整體性的 “原子操作”，不允許在進行操作的同時，對局部的邏輯項進行所謂的“代入”、“反演律”等操作。2.1.3.3.2 對偶定理定義（對偶定理）：若兩個邏輯式相等，則它們的對偶式也相等。定義（對偶式）：將邏輯式中的n （基本運算符號）“與”換成“或”，“或”換成“與”；n （邏輯常量）“0”換成“1”，“1”換成“0”；n 變量保持不變；n 注意：原表達式中的運算優(yōu)先順序保持不變。2.1.4 邏輯代數(shù)常用公式如表2. 2：表2. 2 邏輯

5、代數(shù)的公式（常用公式部分）組杜撰的名稱對偶的公式對備注和注記標記9吸收法A+AB=A兩個乘積項相或，其中一項以另一項作為因子，則該項是多余的。吸收冗余項10消元法消除冗余因子11推廣的消元/吸收法反用消元法，再用吸收法12推廣的消元/吸收法13另一種形式的吸收法14另一種形式的消元法說明：（常用公式的語言敘述）n “吸收法”兩個與項（“乘積項”）相或（“加”），如果其中一項中以另一項為因子，則該項為冗余項；n “消元（因子）法”兩個與項相或，如果其中一項取反后為另一項的因子，則該因子是多余的；n 推廣的消元/吸收法三個與項相或，其中兩個乘積項分別包含原變量與反變量作為因子，并且它們的其余部分作

6、為因子組成第三個乘積項（或作為第三個乘積項的部分因子），則第三個乘積項是多余的。2.1.4.1 案例研究邏輯代數(shù)常用公式的證明證明的手段 回顧：基本公式的證明采用：n 公理和運算法則，n 真值表。對于較復(fù)雜的公式，用真值表手工證明較為繁瑣，故采用“公式法”（公理、法則、定理、基本公式、常用公式），另不多于5個變量的邏輯表達式，也可以用特種的真值表“鄰接真值表”即“卡諾圖”表示。：n 公理和運算法則，n 定理代入、反演、對偶，n 基本公式和常用公式。例如：公式(9)“吸收法”A+AB=A(1+B)=AB，分配律、01律例如：公式(10) 證法一采用：反用或?qū)εc的分配律例如：公式(10) 證法二的

7、對偶式由：，AB的對偶式A+B，則根據(jù)對偶定理：成立。例如：公式(11)-(代入定理意義下的吸收律) = 2.1.5 異或代數(shù)n 三種基本邏輯運算“與”、“或”、“非”（復(fù)合使用）可以表示出任何邏輯問題；n 基本的復(fù)合邏輯“與非”、“或非”、“與或非”，用其中的任何一種就能描述任何邏輯問題；n 異或代數(shù)“異或”（exclusive-OR）和“同或”(coincidence-OR)邏輯，雖然僅用它們不能描述所有的邏輯問題，但是它們是兩種重要的復(fù)合邏輯。2.1.5.1 “異或”和“同或”的性質(zhì)異或（同或）代數(shù)的基本公式：(1) 交換律(2) 結(jié)合律(3) “分配律”n “與”對“異或”的分配律：n

8、 “或”對“同或”的分配律：A+BC=(A+B)(B+C)(4) 反演律=ABAB (取反) =(5) 調(diào)換律（因果互換關(guān)系）兩個邏輯變量（可以推廣到多個，并且可以是常量）異或（同或）運算得到的輸出結(jié)果，以另一個邏輯變量表示（即：“果”），構(gòu)成邏輯等式，該邏輯變量與異或（同或）運算中的任意邏輯變量的位置相調(diào)換，得到的邏輯等式仍成立。例如：奇校驗的編碼端，校驗比特為C，C=bn-1bn-2b11奇校驗的校驗端，如果校驗成功，應(yīng)有1= bn-1bn-2b1C(6) 移非律（特例：“消非律”）(7) 換門律=ABB=不用死記，異或（同或）運算的定義決定，也可使用01律證明。(8) 01律0A=A，1

9、A=（模2加1相當(dāng)于求反）1A=A，0A=(9) 奇偶律對于異或：AA=0AAA=A對于同或AA=1AAA=A(10) 異或邏輯和同或邏輯的關(guān)系多個邏輯變量進行異或（同或）運算的邏輯表達式，如果將異或（同或）運算符轉(zhuǎn)換為同或（異或）運算符，則：n 奇數(shù)個邏輯變量，運算符和互換時，邏輯關(guān)系不變；n 偶數(shù)個邏輯變量，運算符和互換時，變換后的結(jié)果取反。2.2 邏輯函數(shù)的表示方法及其標準形式2.2.1 邏輯函數(shù)的表示方法n 邏輯表達式n 真值表n 卡諾圖（鄰接真值表）n 邏輯圖n 波形圖*表示方法之間的轉(zhuǎn)換（如：圖2. 1） 2009年9月18日，授課至2.2.1。圖2. 1 邏輯函數(shù)表達方法之間的轉(zhuǎn)

10、換2.2.2 邏輯函數(shù)的兩種標準形式n 標準“與或”表達式（最小項之和）n 標準“或與”表達式（最大項之積）2.2.2.1 最小項定義（最小項）：在含有n個變量的邏輯函數(shù)中，n 包含全部n個變量的乘積項（與項），n 其中每個變量必須而且只能以原變量或反變量的形式出現(xiàn)一次。最小項也被稱為“標準乘積項”。最小項的編碼使最小項為1的邏輯變量的取值，即：將變量的由高到低排列，原變量對應(yīng)“1”，反變量對應(yīng)“0”，最小項以變量所對應(yīng)的自然二進制數(shù)編碼，記為：“mi”。最小項的性質(zhì)：n 每個最小項與變量的一組取值相對應(yīng)，只有該組取值才能使其為“1”；n 全體最小項之和恒為“1”；n 任意兩個不同的最小項的乘

11、積恒為“0”。2.2.2.2 標準與或表達式定義（標準與或表達式）：每個與項都是最小項的與或表達式。也被稱為“最小項之和表達式”。從真值表，以及一般與或表達式，轉(zhuǎn)換成標準“與或”表達式的方法如圖2. 2。圖2. 2 從真值表和一般與或表達式轉(zhuǎn)換為標準與或表達式對于任意一個邏輯函數(shù)，它的標準與或表達式（不考慮與項的順序）是唯一的。說明：熟練后，從一般“與或”表達式轉(zhuǎn)換為標準“與或”表達式，可由最小項的編碼規(guī)則得到。例如：2.2.2.3 最大項定義（最大項）：在一個有n個變量的邏輯函數(shù)中，n 包含全部n個變量的和項（或項），n 其中每個變量必須并且只能以原變量或反變量的形式出現(xiàn)一次。最大項的編碼與

12、邏輯變量取值的對應(yīng)關(guān)系使最大項為0的邏輯變量的取值，即：對于或項， 原變量對應(yīng)取值為“0”，反變量對應(yīng)取值為“1”。最大項的性質(zhì)：n 每個最大項與變量的一組取值相對應(yīng)，只有該組取值才能使其為“0”；n 全體最大項之積恒為“0”，即：；n 任意兩個不同的最大項之和恒為“1”，即：，；n 最大項和最小項之間的關(guān)系：。2.2.2.4 標準或與表達式定義（標準或與表達式）：每個或項都是最大項的“或與”表達式被稱為標準“或與”表達式，也被稱為最大項之積表達式。2.2.2.4.1 從真值表求標準或與表達式步驟（求標準或與表達式）：1) 在真值表中找出使邏輯函數(shù)Y為0的行，2) 對于Y=0的行，由變量的取值

13、“0”、“1”對應(yīng)最大項“原”、“反”變量的關(guān)系，寫出邏輯變量表達得標準或與表達式， 3) 確定最大項的編號n 方法一、由最大項定義，根據(jù)最大項編號與變量取值的對應(yīng)關(guān)系，n 方法二、真值表中Y=0的行對應(yīng)的是，利用關(guān)系，對應(yīng)得到最大項Mi的編號，。說明：真值表中變量取值組合隱含著與最小項的對應(yīng)關(guān)系，得到最大項的編號只不過根據(jù)的對應(yīng)關(guān)系。說明：也可以先根據(jù)的對應(yīng)關(guān)系，確定所含最大項的編號，再根據(jù)最大項編號和變量取值的對應(yīng)關(guān)系，寫出以邏輯變量表達的最大項之積表達式。2.2.2.4.2 從一般邏輯表達式得到標準或與表達式圖2. 3 從一般邏輯表達式得到標準或與表達式2.2.2.5 標準與或表達式/標

14、準或與表達式的轉(zhuǎn)化如果函數(shù)的標準與或表達式為：，則函數(shù)的標準或與表達式則為：。推導(dǎo)：，由最小項的性質(zhì)，則：1=由DeMorgan公式，可由標準與或表達式，求標準或與表達式。2.3 邏輯函數(shù)的化簡n 邏輯函數(shù)的最簡形式n 公式法化簡邏輯函數(shù)n 卡諾圖法化簡邏輯函數(shù)l 卡諾圖l 卡諾圖化簡法化簡為最簡與或表達式l 用卡諾圖化簡法 求 最簡或與表達式l 具有無關(guān)項的邏輯函數(shù)的化簡n 邏輯函數(shù)形式的轉(zhuǎn)換2.3.1 邏輯函數(shù)的最簡形式與或表達式是最常用的表達式，由它容易推導(dǎo)出其它表達形式。判別條件與或表達式為最簡的條件：n 乘積項（與項）的數(shù)目最少，（首要條件）n 每個乘積項中的因子（邏輯變量）最少。2

15、.3.2 公式法化簡邏輯函數(shù)化簡為最簡與或式。公式法化簡沒有固定的方法，這些方法歸納起來大致可以包括“并項、吸收、消因子、消項、配項”（這些名稱是杜撰的，切不可生搬硬套，掌握基本思想即可），化簡的方法不是唯一的。2.3.2.1 并項法利用互補律，將兩項合為一項，合并時消去一個邏輯變量（一個原變量，一個反變量）例如：2.3.2.2 吸收法利用公式A+AB=A，吸收掉冗余的乘積項。例如：2.3.2.3 消因子法利用公式，消去多余的因子。例如：2.3.2.4 消項法利用常用公式和，消去多余的乘積項例如：例如：2.3.2.5 配項法根據(jù)基本公式A+A=A，在式中重復(fù)某項，再化簡；或者根據(jù)基本公式，在式

16、中某項乘以，再化簡。例如：本例只是演示，實際上如果先對后兩項并項，然后消因子，更加簡單。2.3.3 卡諾圖法化簡邏輯函數(shù)2.3.3.1 卡諾圖卡諾圖是由美國工程師維奇（Veitch）和卡諾（Karnaugh M）于1953年分別從不同角度提出的。定義（卡諾圖，最小項卡諾圖）將n個變量的所有最小項（miniterm）分別以一個個方格的形式表示，并使具有邏輯相鄰性的最小項在幾何上也“相鄰”地排列，所得的圖形被稱為最小項卡諾圖 卡諾圖構(gòu)成的解說：卡諾圖以二維圖形的方式來表示邏輯變量的取值。(1)縱橫兩側(cè)分別標注邏輯變量（與項）的取值，取值以格雷循環(huán)碼的順序排列，對于給定的取值，縱橫相交對應(yīng)一個小方格

17、，這個小方格對應(yīng)一個最小項（即：使最小項為1的邏輯變量取值）；(2)對于最小項中的因子，取值為“1”對應(yīng)邏輯變量的原變量；取值為“0”對應(yīng)邏輯變量的反變量；(3)縱橫取值所組成的二進制數(shù)值（自然二進制數(shù)）就是最小項的序號?？ㄖZ圖也是一種特殊的真值表鄰接真值表：n 幾何相鄰（在幾何位置上，應(yīng)將卡諾圖看成上下/左右、四角閉合的圖形）的小方格具有邏輯相鄰性。（便于用互補律以作圖的方式化簡）定義（最小項的邏輯相鄰性）兩個最小項只有一個邏輯變量的取值不同。2.3.3.1.1 卡諾圖的構(gòu)成與特點例如：（四變量卡諾圖，如圖2. 4）圖2. 4 四變量卡諾圖例如：（五變量卡諾圖，如圖2. 5）圖2. 5 五變

18、量卡諾圖此時，僅用幾何圖形在二維空間的相鄰性來表達邏輯相鄰性已經(jīng)不夠了，在五變量卡諾圖中，（兩個44卡諾圖的）分界線為軸的軸對稱的小方格也具有邏輯相鄰性?？ㄖZ圖的特點：n 卡諾圖中的小方格數(shù)等于最小項總數(shù)，若邏輯變量的數(shù)目為n，則小方格數(shù)為2n個l 縱橫兩側(cè)標注是邏輯變量的取值組合，“0”和“1”表示使方格對應(yīng)的最小項為1的變量取值；同時，l 取值組合“0”、“1”的自然二進制數(shù)值就是最小項的編號。n 任何一個n變量 由卡諾圖的能力，n5。的邏輯函數(shù)均可以由n變量最小項卡諾圖表示l 邏輯函數(shù)等于卡諾圖中填入“1”的小格（即：“1格”）所對應(yīng)的最小項之和。n 卡諾圖是“鄰接真值表”，l 變量的取

19、值按照格雷循環(huán)碼排列，因此l 卡諾圖的邏輯相鄰性 與 幾何位置相鄰性是一致的；l 注意，在幾何位置上，應(yīng)將卡諾圖看成上下/左右，四角閉合的圖形。（五變量包括分界軸對稱）2.3.3.1.2 根據(jù)邏輯函數(shù)填寫卡諾圖n 步驟一（得到標準與或表達式）、若已知邏輯函數(shù)的表達式，可首先把函數(shù)寫成最小項之和的形式（標準與或表達式）；然后，n 步驟二（填寫卡諾圖）、在卡諾圖上與這些最小項對應(yīng)的位置上填入1，在其余位置上填入0，這樣就可以得到該邏輯函數(shù)的卡諾圖。例2.5: （根據(jù)邏輯函數(shù)填寫卡諾圖）解: （步驟1-1）反復(fù)使用反演律，脫去“非”號，直到最后只有單變量上有非號；（步驟1-2）用乘對加的分配律，脫去

20、括號，直到最后得到一個“與或”表達式；（步驟1-3）在“與或”表達式中，若一個乘積項缺少某變量因子，則利用互補律配項，并用所配的項去乘該項；如缺少兩個以上的項，則要反復(fù)用互補律配項，直到得到最小項之和的表達式（還要刪除重復(fù)的最小項）。（步驟2-1）邏輯變量按照位置計數(shù)法排列，以自然二進制數(shù)對應(yīng)最小項的編號；（步驟2-2）最小項為1的取值組合，會使邏輯函數(shù)為1，所以在存在的最小項的對應(yīng)方格中標注“1”（其余方格填“0”）。說明：熟練后，可以根據(jù)與或表達式“看圖說話”地直接填寫卡諾圖，不僅效率高，而且不容易出錯。例2.6: （根據(jù)邏輯函數(shù)填寫卡諾圖）解 2009年9月22日，授課至2.3.3.1.

21、2。: 2.3.3.1.3 由卡諾圖得到標準或與表達式根據(jù)卡諾圖既可寫出標準“與或”表達式，也可寫出標準“或與”表達式（參見2.3.3）。2.3.3.2 卡諾圖化簡法卡諾圖化簡邏輯函數(shù)的依據(jù)：由于卡諾圖上幾何位置的相鄰性與邏輯相鄰性是一致的，因而從卡諾圖上能直觀地找出具有相鄰性的最小項，并根據(jù)互補律將其合并化簡。n 幾何相鄰的兩個方格（包括 上下閉合、左右閉合、軸對稱）所代表的最小項只有一個變量不同；n 根據(jù)互補律，當(dāng)方格為1（“1”格），且兩個“1”格相鄰時，對應(yīng)的最小項就可以加以合并，消去一對原變量與反變量，合并后只剩公共因子。n 多于多個相鄰的方格，反復(fù)利用合并法則，保留相同變量，消除相

22、反變量。問題：n 如何“直觀地”找到可以合并的最小項？n 如何選擇可以合并的最小項，以達到最簡？2.3.3.2.1 最小項卡諾圖邏輯化簡規(guī)則問題1、如何“直觀地”找到可以合并的最小項？ 理論：合并化簡的理論支持（互補律）。技巧：圈定卡諾圈的技巧。規(guī)則1：卡諾圖中兩個相鄰的“1格”的最小項可以合并成一個與項，并消去一個變量。例如： Y= 化簡為： 化簡為： 化簡為：規(guī)則2：卡諾圖中四個相鄰“1格”的最小項可以合并成一個與項，并消去兩個變量。規(guī)則3：卡諾圖中八個相鄰的“1”格的最小項可以合并成一個與項，并消去三個變量。2.3.3.2.2 用最小項卡諾圖化簡法求最簡與或表達式步驟：(1) 建立邏輯函

23、數(shù)的卡諾圖；(2) 合并最小項； 關(guān)鍵在于：如何選擇可合并的最小項，以達到最簡（問題2）(3) 寫出 最簡與或表達式問題2：如何選擇可合并的最小項，以達到最簡？ 理論：找到實質(zhì)蘊涵項 所謂“最簡”：是指在卡諾圖中，構(gòu)成函數(shù)Y的一個最小閉覆蓋的全部實質(zhì)蘊涵項的集合。l 所謂“實質(zhì)”：蘊涵項中至少有一項之被合并過一次（即：沒有被其它卡諾圈圈?。?；l 由“實質(zhì)蘊涵”的原則，從本原蘊涵項中選擇實質(zhì)蘊涵項；l 定義（本原蘊涵項）：又叫作“素項”最大合并范圍的卡諾圈所圈定的合并項。完備的卡諾圖化簡步驟為：1) 建立邏輯函數(shù)的卡諾圖；2) 圈出所有的本源蘊涵項（素項）即：可合并的卡諾圈，且使圈“膨脹”到最大

24、；3) 確定實質(zhì)蘊涵項；4) 寫出函數(shù)的最簡邏輯表達式最小實質(zhì)素項集合。該原則對于 最小項卡諾圖 和 最大項卡諾圖 均使用，其中：與項 為 升蘊涵項，或項 為降蘊涵項。技巧：選擇卡諾圈的技巧：使得n 圈的個數(shù)盡可能少（首要目標），n 圈的面積盡可能大，n 每個圈中至少應(yīng)包含一個新的“1格”（最小項卡諾圖）。例2.7: (卡諾圖化簡求最簡與或表達式) Y(A,B,C,D)=m(1,2,4,9,10,11,13,15)例2.8: (例題并講解，什么是本源蘊涵項，如何從本源蘊涵項中選擇實質(zhì)蘊涵項)寫出最簡與或邏輯表達式技巧：圈的個數(shù)盡可能少（首要目標）例2.9: （例題并講解：本源蘊涵項）技巧：圈的

25、面積盡可能大例2.10: （例題并講解：實質(zhì)蘊涵項）技巧：每個圈至少應(yīng)包含一個新的“1格”卡諾圖化簡得到的最簡式不一定是唯一的。2.3.3.3 用卡諾圖化簡法求最簡或與表達式方法：n 方法一、合并反函數(shù)的最小項，n 方法二、合并原函數(shù)的最大項（最大項卡諾圖，由于最大項卡諾圖的編碼規(guī)則與習(xí)慣的正邏輯不同，故而容易出錯，主要選用方法一）。注意：反函數(shù)可以用真值表或者卡諾圖中Y=0對應(yīng)的最小項之和表示。方法一：1) 畫出邏輯函數(shù)Y的卡諾圖，2) 合并0方格（俗稱“0格”），求得反函數(shù)的最簡與或表達式，3) 對反函數(shù)的最簡“與或”式進行反演變換（DeMorgan公式），得到函數(shù)的最簡“或與”式。例2.

26、11: (卡諾圖化簡求最簡與或表達式)Y(A,B,C,D)=m(0, 1, 2, 5, 8, 9, 10)2.3.3.4 具有無關(guān)項邏輯函數(shù)的化簡無關(guān)項的概念無關(guān)項包括約束項和任意項，n 約束項：輸入邏輯變量的某些取值組合禁止出現(xiàn)（由外部的機制約束，以保證一定不會出現(xiàn)）；n 任意項：一些取值組合出現(xiàn)時，輸出邏輯值可以是任意的；這些取值組合對應(yīng)的最小項稱為約束項或任意項，統(tǒng)稱為“無關(guān)項”。在卡諾圖的方格中，常使用符號“”（或“”）表示無關(guān)項。無關(guān)項在化簡邏輯函數(shù)中的應(yīng)用：n 合理利用無關(guān)項，一般可以得到更加簡單的化簡結(jié)果，n 在卡諾圖中，無關(guān)項“”可以被作為“1”，也可以被作為“0”，n 目的：加入的無關(guān)項應(yīng)該與函數(shù)式盡可能多的最小項具有邏輯相鄰性。例2.10: （例題并講解：具有無關(guān)項的邏輯函數(shù)化簡）Y(A,B,C,D)=m(1, 3, 7, 11, 15)+ d(0, 2, 5)Y=問題：利用卡諾圖合并包含無關(guān)項的最小項，如何確定：n 卡諾圈包含無關(guān)項將無