第2章邏輯代數(shù)

第2章邏輯代數(shù)基礎(chǔ)基本概念基本定理和規(guī)則邏輯函數(shù)表達(dá)式的形式與變換邏輯函數(shù)化簡2/6/20231邏輯代數(shù)是數(shù)子系統(tǒng)邏輯設(shè)計的理論基礎(chǔ)和重要數(shù)學(xué)工具1847年,英國數(shù)學(xué)家喬治·布爾(G.Boole)提出了用數(shù)學(xué)分析方法表示命題陳述的邏輯結(jié)構(gòu)，并將形式邏輯歸結(jié)為一種代數(shù)，從而誕生了著名的“布爾代數(shù)”1938年，克勞德·向農(nóng)(C.E.Shannon)將布爾代數(shù)應(yīng)用于電話繼電器的開關(guān)電路，提出了“開關(guān)代數(shù)”隨著電子技術(shù)的發(fā)展，集成電路邏輯門已經(jīng)取代了機(jī)械觸點(diǎn)開關(guān)，故人們更習(xí)慣于把開關(guān)代數(shù)叫做邏輯代數(shù)2/6/202322.1邏輯代數(shù)的基本概念2.1.1邏輯變量及基本邏輯運(yùn)算2.1.2邏輯函數(shù)及邏輯函數(shù)間的相等2.1.3邏輯函數(shù)的表示法2/6/20233邏輯代數(shù)的五個公理公理1交換律：A+B=B+AA?B=B?A公理2結(jié)合律：(A+B)+C=A+(B+C)(A?B)?C=A?(B?C)公理3分配律：A+(B?C)=(A+B)?(A+C)A

?(B+C)=A?B+A?C公理40-1律：A+0=AA+1=1A?0=0A?1=1公理5互補(bǔ)律：A+A=1A?A=02/6/202342.1.1邏輯變量及基本邏輯運(yùn)算邏輯變量的取值只能是0和1，用來表示數(shù)字系統(tǒng)中開關(guān)的接通與斷開、電壓的高和低、信號的有和無、晶體管的導(dǎo)通與截止等兩種穩(wěn)定的物理狀態(tài)。因此，邏輯變量取值無大小、無正負(fù)之分基本的邏輯運(yùn)算有“與”、“或”、“非”三種2/6/202351.邏輯“或”運(yùn)算邏輯或運(yùn)算

0+0=00+1=11+0=11+1=1邏輯“或”運(yùn)算又稱為“邏輯加”，用符號“+”或“?”表示。邏輯“或”的表達(dá)式：F=A+B二進(jìn)制加法運(yùn)算

0+0=00+1=11+0=11+1=10AB+U邏輯“或”電路F2/6/202362.邏輯“與”運(yùn)算邏輯與運(yùn)算

00=001=010=011=1邏輯“與”運(yùn)算又稱為“邏輯乘”，用符號“?”或“?”表示。邏輯“與”表達(dá)式：F=A?B二進(jìn)制乘法運(yùn)算

00=001=010=011=1AB+U邏輯“與”電路F2/6/202373.邏輯“非”運(yùn)算邏輯“非”運(yùn)算用符號“—”表示。邏輯“非”表達(dá)式為：A+U邏輯“非”電路F邏輯“非”運(yùn)算表AF01102/6/20238

邏輯函數(shù)與代數(shù)中的函數(shù)極為相似。但同時具有以下兩個特點(diǎn)：1.邏輯變量和邏輯函數(shù)的取值只能是“0”和“1”2.邏輯函數(shù)和邏輯變量之間的關(guān)系是由“與”、“或”、“非”三種基本運(yùn)算決定

2.1.2邏輯函數(shù)及邏輯函數(shù)表示2/6/20239邏輯函數(shù)的三種表示法一、邏輯表達(dá)式由邏輯變量和“與”、“或”、“非”三種基本運(yùn)算構(gòu)成的式子邏輯表達(dá)式的運(yùn)算特點(diǎn)：1.運(yùn)算順序：括號先內(nèi)后外，先“與”后“或”2.邏輯運(yùn)算中可使用公理1-5如F=(A+B)(A+C)=A+BC（公理3）2/6/202310邏輯函數(shù)的三種表示法二、真值表將輸入變量的所有取值與函數(shù)的對應(yīng)關(guān)系用表格方式表示出來如函數(shù)真值表如右所示ABCF00000011010001111001101111001110真值表是邏輯分析的重要工具2/6/202311邏輯函數(shù)的三種表示法三、卡諾圖法邏輯變量的所有取值小方格構(gòu)成的圖，即邏輯函數(shù)的圖形表示方法?？ㄖZ圖是邏輯化簡的重要工具00011101ABC0001111001ABCF000000110100011110011011110011102/6/2023122.2邏輯代數(shù)的基本定理和規(guī)則2.2.1邏輯代數(shù)的基本定理2.2.2邏輯代數(shù)的三個規(guī)則2.2.3復(fù)合邏輯2/6/2023132.2.1邏輯代數(shù)的基本定理T1定理10+0=0 1+0=10+1=1 1+1=10·0=0 1·0=00·1=0 1·1=1T2定理2（冪等性）※

A+A=AAA=A2/6/202314T3定理3（吸收率）(1)A+AB=A(2)A(A+B)=A吸收率的用途：去掉布爾表達(dá)式中額外的元素。舉例：

2.2.1邏輯代數(shù)的基本定理2/6/202315T4定理4(1)A+B=A+B(2)A

(+B)=AB證明：定理4應(yīng)用舉例----消去多余變量

2.2.1邏輯代數(shù)的基本定理2/6/2023162.2.1邏輯代數(shù)的基本定理T5定理5（自反率）：

T6定理6

（求反率）(1)(2)摩根定律：

(1)(2)摩根定理的使用：求邏輯表達(dá)式的補(bǔ)2/6/202317摩根定理舉例（表達(dá)式化簡）例：2/6/202318T7定理7(1)(2)舉例：T8定理8※※（1）（2）若某變量以原變量和反變量的形式出現(xiàn)在“與或”表達(dá)式的某兩個“與”項中，則該兩項的其余因子組成的第三個“與”項為冗余項。2.2.1邏輯代數(shù)的基本定理2/6/202319定理8的證明AB+AC+BC=AB+AC+BC(A+A)=AB+AC+ABC+ABC=(AB+ABC)+(AC+ABC)=AB(1+C)+AC(1+B)=AB+AC2/6/202320定理2、3、4、6、7、8中，每個定理中的兩個表達(dá)式互為“準(zhǔn)對偶式”。如定理7

如定理8基本定理和規(guī)則分析2/6/202321

定理8舉例T8定理8（1）（2）若某變量以原變量和反變量的形式出現(xiàn)在“與或”表達(dá)式的某兩個“與”項中，則該兩項的其余因子組成的第三個“與”項為冗余項。例：化簡表達(dá)式冗余項冗余項2/6/202322代入規(guī)則：任何一個含有A的邏輯等式，如果將所有出現(xiàn)A的位置都代之同一個邏輯函數(shù)F，則等式仍然成立。例：

A(B+C)=AB+AC,若C用C+D代替，則該邏輯等式仍然成立，即：

A(B+(C+D))=AB+A(C+D)意義：利用代入規(guī)則可以將邏輯代數(shù)公理、定理中的變量用任意的函數(shù)代替，從而推導(dǎo)出更多的等式。2.2.2邏輯代數(shù)的三個規(guī)則

---

代入規(guī)則

2/6/202323反演規(guī)則：如果將邏輯函數(shù)表達(dá)式F中的“?”變成“+”，“+”變成“?”，“0”變成“1”，“1”變成“0”，原變量變成反變量，反變量變成原變量，并保持原函數(shù)的運(yùn)算順序不變，則所得到的新函數(shù)為原函數(shù)F的反函數(shù)

。例：2.2.2邏輯代數(shù)的三個規(guī)則

---

反演規(guī)則

2/6/202324對偶規(guī)則：將一個邏輯函數(shù)表達(dá)式F中所有的

和

+互換，0和1互換，并保持原函數(shù)中的運(yùn)算順序不變，則所得到的新的邏輯表達(dá)式稱為函數(shù)F的對偶式，并記作F?

。例：

2.2.2邏輯代數(shù)的三個規(guī)則

---

對偶規(guī)則

)(

))()(())()((

)()0(

)1)(()1)((

)0(EDCCAABFDECCABAFDECCABAFEDCCAABFCBBAFCBBAFCBBAFCBBAF+++=+++=+++=+++=++=++=++=++=2/6/202325

用邏輯代數(shù)的定理證明下列表達(dá)式（1）（2）

證明:(1)左邊=(2)右邊=2/6/2023262.2.3復(fù)合邏輯之與非邏輯

（1）與非邏輯：由與、非兩種邏輯復(fù)合形成的，可用邏輯函數(shù)表示為：&ABFABF2輸入“與非門”ABF001011011102/6/202327（2）或非邏輯：由或、非兩種邏輯復(fù)合而成的，可用邏輯函數(shù)表示為： ≥1ABFABF2輸入“或非門”ABF001010001102.2.3復(fù)合邏輯之或非邏輯

2/6/202328（3）與或非邏輯：由與、或、非三種邏輯復(fù)合形成的，可用邏輯函數(shù)表示為：&ABFABF&CDCD≥1與或非門2.2.3復(fù)合邏輯之與或非邏輯

2/6/202329（4）異或邏輯：是一種兩變量邏輯關(guān)系，當(dāng)這兩個變量邏輯值相異時，其邏輯函數(shù)值為真。可用邏輯函數(shù)表示為：=1ABFABF2輸入“異或門”)ABF000011011102.2.3復(fù)合邏輯之異或邏輯

2/6/202330（5）同或邏輯：也是一種兩變量邏輯關(guān)系，當(dāng)這兩變量邏輯值相同時，其邏輯函數(shù)值為真?？捎眠壿嫼瘮?shù)表示為： =ABFABF2輸入“同或門”)ABF001010001112.2.3復(fù)合邏輯之同或邏輯

2/6/2023312.3邏輯函數(shù)表達(dá)式的形式和變換2.3.1邏輯函數(shù)的基本形式2.3.2邏輯函數(shù)的標(biāo)準(zhǔn)形式2.3.3邏輯函數(shù)表達(dá)式的轉(zhuǎn)換2/6/2023322.3.1邏輯函數(shù)表達(dá)式的基本形式1.積之和(Sumofproduct,SOP，“與-或”式)

2.和之積(Productofsum,POS，“或-與”式）2/6/2023332.3.2邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式邏輯函數(shù)的兩種基本表達(dá)式不唯一邏輯函數(shù)的標(biāo)準(zhǔn)表達(dá)式是唯一的標(biāo)準(zhǔn)表達(dá)式也有兩種形式：標(biāo)準(zhǔn)“與-或”式（最小項和形式）、標(biāo)準(zhǔn)“或-與”表達(dá)式（最大項積形式）2/6/2023341、最小項定義：如果一個函數(shù)有n個變量，如果一個積項中每個變量以補(bǔ)或非補(bǔ)的形式全部出現(xiàn)并且只出現(xiàn)一次，這個積項成為最小項。例:三個變量A、B和C可以構(gòu)成8個最小項：如果一個積之和（SOP,“與-或”表達(dá)式）中的每個積項都是最小項，則稱為邏輯函數(shù)的標(biāo)準(zhǔn)形式。2/6/202335最小項的性質(zhì)性質(zhì)1：任意一個最小項，其相應(yīng)變量有且只有一種取值使這個最小項的值為1，并且，最小項不同，使其值為1的變量取值不同。性質(zhì)2

：相同變量構(gòu)成的兩個不同最小項相“與”為0。性質(zhì)3：n個變量的全部最小項相“或”為1?？梢杂洖椋盒再|(zhì)4：n個變量構(gòu)成的最小項有n個相鄰最小項。2/6/202336最小項的列表表示最小項編碼編號在開關(guān)函數(shù)的最小項列表形式中，編碼是十分重要的。變量的順序2/6/202337邏輯函數(shù)最小項表示優(yōu)點(diǎn)：開關(guān)函數(shù)的最接近真值表的表示形式能很容易地判斷在一個輸入組合下，開關(guān)函數(shù)的值是否為1。不足：不是最簡單的函數(shù)形式相關(guān)的電路復(fù)雜結(jié)論：需要化簡2/6/2023382、最大項定義：如果一個函數(shù)有n個變量，如果在一個“或項”中每個變量以補(bǔ)或非補(bǔ)的形式出現(xiàn)并且只出現(xiàn)一次，這個“或項”成為最大項。如果一個函數(shù)用和之積（POS，“或-與”表達(dá)式）的形式表示，其中的“或項”都是最大項，則該函數(shù)的表達(dá)式稱為最大項標(biāo)準(zhǔn)式。例如三變量A,B,C有8個最大項為：

2/6/202339最大項的性質(zhì)性質(zhì)1：任意一個最大項，其相應(yīng)變量有且只有一種取值使這個最大項的值為0，并且，最大項不同，使其值為0的變量取值不同。性質(zhì)2：相同變量構(gòu)成的兩個不同最大項相“或”為1。性質(zhì)3：n個變量的全部最大項相“與”為0。可以記為：性質(zhì)4：n個變量構(gòu)成的最大項有n個相鄰最大項。2/6/202340最大項的列表表示最大項編碼編號和最小項范式同理，變量的順序也是重要的。0000011001012/6/202341邏輯函數(shù)的最大項表示優(yōu)點(diǎn)：和函數(shù)的真值表有直接的關(guān)系能很容易地判斷出對于一個輸入組合，函數(shù)的值是否為0不足：不是函數(shù)的最簡單形式相應(yīng)的電路比較復(fù)雜結(jié)論：需要化簡2/6/2023422.3.3邏輯函數(shù)表達(dá)式的轉(zhuǎn)換代數(shù)轉(zhuǎn)換法用邏輯代數(shù)的公理、定理和規(guī)則進(jìn)行邏輯變換，將函數(shù)表達(dá)式從一種形式轉(zhuǎn)換到另一種形式。真值表轉(zhuǎn)換法

以上兩種方法，可將一般函數(shù)表達(dá)式轉(zhuǎn)換成標(biāo)準(zhǔn)表達(dá)式2/6/2023431、代數(shù)轉(zhuǎn)換法用代數(shù)轉(zhuǎn)換法求一個函數(shù)的標(biāo)準(zhǔn)“與-或”表達(dá)式：

①將函數(shù)表達(dá)式變成基本“與-或”式；

②將所有的“與”項擴(kuò)展成最小項。用代數(shù)轉(zhuǎn)換法求一個函數(shù)的標(biāo)準(zhǔn)“或-與”表達(dá)式：

①將函數(shù)表達(dá)式變成一般的“或-與”式；

②將所有的“或”項擴(kuò)展成最大項。2/6/202344將函數(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)“與-或”式例2.1：將函數(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)“與-或”表達(dá)式。2/6/202345將函數(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)“或-與”式例2.2：將函數(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)“或-與”表達(dá)式。

2/6/2023462、真值表轉(zhuǎn)換法ABCF00000011010001111001101111001110例：將函數(shù)分別轉(zhuǎn)換成最小項、最大項表達(dá)式。

2/6/202347思考題邏輯函數(shù)f(A,B,C,D)=m(1,4,9,12)和函數(shù)g(A,B,C,D)=M(1,4,9,12)，試要求邏輯函數(shù)f(A,B,C,D)+g(A,B,C,D)=?2/6/2023482.4邏輯函數(shù)的化簡2.4.1代數(shù)化簡法2.4.2卡諾圖化簡法2.3.3列表化簡法*

化簡的目的：降低系統(tǒng)成本、減少復(fù)雜度、提高可靠性2/6/2023492.4.1代數(shù)化簡法代數(shù)化簡法

運(yùn)用邏輯代數(shù)的公理、定理和規(guī)則對邏輯函數(shù)進(jìn)行化簡的方法。這種方法主要取決于對邏輯代數(shù)中公理、定理和規(guī)則的熟練程度。最簡“與-或”表達(dá)式應(yīng)滿足兩個條件表達(dá)式中的與項個數(shù)最少；在滿足上述條件的前提下，每個與項中的變量個數(shù)最少“與-或”表達(dá)式化簡的常用方法并項法吸收法消去法配項法2/6/2023501、“與-或”表達(dá)式的化簡并項法利用定理7中的，將兩個“與”項合并成一個“與”項，合并后消去一個變量。例如：吸收法利用定理3中的，消去多余的項。例如：消去法利用定理4中的，消去多余變量。例如：2/6/202351配項法利用公理4和公理5中的

,先從函數(shù)式中適當(dāng)選擇某些與項并配上所缺的一個合適變量，然后再利用并項、吸收和消去等方法進(jìn)行化簡。例如：1、“與-或”表達(dá)式的化簡2/6/202352例2.5化簡下面邏輯函數(shù)解：2/6/202353例2.6化簡下面邏輯函數(shù)解：2/6/202354例2.7化簡下面邏輯函數(shù)解：2/6/202355最簡“或-與”表達(dá)式應(yīng)滿足的條件：

表達(dá)式中的“或”項個數(shù)最少在滿足上述條件的前提下，每個或項的變量個數(shù)最少。例2.8

用二次“對偶法”可對“或-與”表達(dá)式化簡2、“或-與”表達(dá)式的化簡2/6/202356例2.9

2、“或-與”表達(dá)式的化簡2/6/202357代數(shù)化簡法的評價不受變量個數(shù)多少的約束，如果對公理和定理熟練，化簡很方便化簡過程無規(guī)律可循，也沒有規(guī)定的步驟對最后結(jié)果很難判斷是否達(dá)到最簡2/6/2023582.4.2卡諾圖化簡法卡諾圖(Karnaughmap)的構(gòu)成邏輯函數(shù)在卡諾圖上的表示卡諾圖上最小項的合并規(guī)律卡諾圖化簡邏輯函數(shù)的步驟2/6/2023591、卡諾圖的構(gòu)成n個變量的卡諾圖，由2n個小方格構(gòu)成的二維圖形，每個小方格對應(yīng)一個最小項卡諾圖是真值表的圖形化形式卡諾圖中最小項的排列方案不唯一，但應(yīng)能清楚地反映最小項的相鄰關(guān)系2/6/20236061

2-4個變量的卡諾圖m0m2m1m3m00101ABm2m6m4m1m3m7m5ABC0001111001BBCAAm0m4m12m3m2m5m7m6m13m15m14m8m9m11m10m1ABCD0001111000011110ABCD注意以下三個問題：1、最小項的下標(biāo)；2、相鄰關(guān)系的識別（三種）；3、各變量在圖中的對應(yīng)范圍。認(rèn)識卡諾圖2/6/2023615個變量的卡諾圖m0m4m12m3m2m5m7m6m13m15m14m8m9m11m10m1ABCDE00000101101000011110BCDm16m20m28m19m18m21m23m22m29m31m30m24m25m27m26m17100101111110BCEA2/6/2023622、邏輯函數(shù)在卡諾圖上的表示標(biāo)準(zhǔn)表達(dá)式（正則表達(dá)式）：為了簡便可將最小項對應(yīng)小方格填上1，或?qū)⒆畲箜棇?yīng)小方格填上0基本表達(dá)式：根據(jù)“與”的公共性和“或”的疊加性，畫出相對應(yīng)的卡諾圖2/6/202363卡諾圖的畫法-例1f(A,B,C)=m(0,3,5)=M(1,2,4,6,7)10000101ABC0001111001f(A,B,C,D)=m(0,3,5,7,10,11,12,13,14,15)=M(1,2,4,6,8,9)

1011011011100110ABCD00011110000111102/6/20236465

卡諾圖的畫法-例20011101011100100ABCD0001111000011110ABCD2/6/2023653、卡諾圖上最小項合并規(guī)律卡諾圖的重要特征：直觀且清淅地反映了最小項的相鄰（相鄰、相對、相重）關(guān)系卡諾圖的合并原理：用一個簡單的與項替代（被卡諾圈所包圍的）若干個相鄰最小項。以達(dá)到邏輯函數(shù)化簡之目的2/6/202366情況1：兩個相鄰最小項10010110ABC00011110010011001010000110ABCD0001111000011110BCBCACDABCABC兩個相鄰最小項合并后，可減少一個變量2/6/202367情況2：四個相鄰最小項01100110ABC00011110011010100011110110ABCD0001111000011110BACABBD四個相鄰最小項合并后，可減少兩個變量2/6/202368情況3：八個相鄰最小項0011101111111110ABCD000111100001111011111111ABC00011110011CA八個相鄰最小項合并后，可減少三個變量2/6/202369卡諾圖的合并規(guī)律總結(jié)n個變量卡諾圖中最小項的合并規(guī)律：

1、卡諾圈中小方格的個數(shù)必須為個，m為小于等于n的正整數(shù)。2、卡諾圈中的個小方格對應(yīng)的最小項可用（n-m)個變量的“與”表示。3、當(dāng)m=n時，卡諾圈包圍了整個卡諾圖，可用1表示，即n個變量的全部最小項之和為1。在復(fù)蓋函數(shù)中的所有最小項的全體下，卡諾圈的個數(shù)達(dá)到最少，每個卡諾圈達(dá)到最大。2/6/2023704、卡諾圖化簡邏輯函數(shù)的步驟作出邏輯函數(shù)的卡諾圖在卡諾圖上圈出函數(shù)的全部質(zhì)項從全部質(zhì)蘊(yùn)含項中找出所有的必要質(zhì)項必要質(zhì)項構(gòu)成函數(shù)的最小覆蓋2/6/202371蘊(yùn)涵項：在與-或表達(dá)式中，每個“與”項被稱為該函數(shù)的蘊(yùn)涵項（一個卡諾圈）質(zhì)蘊(yùn)涵項：若函數(shù)的一個蘊(yùn)涵項不是該函數(shù)中其他蘊(yùn)涵項的子集，則此蘊(yùn)涵項被稱為質(zhì)蘊(yùn)涵項（一個最大的卡諾圈）

必要蘊(yùn)涵項：若函數(shù)的一個質(zhì)項包含有不被函數(shù)的其他任何質(zhì)項所包含的最小項，則此質(zhì)項被稱為必要質(zhì)項（不被兩個以上卡諾圈所包含的最小項）最小覆蓋是一個包含最少的質(zhì)項和最少的符號的覆蓋。2/6/202372蘊(yùn)涵項的概念最小項:

蘊(yùn)涵項：質(zhì)蘊(yùn)涵項:

必要質(zhì)蘊(yùn)含項：最小覆蓋：01101110ABC000111100101*1*01*11*0ABC00011110012/6/202373例2.10用卡諾圖化簡f(A,B,C,D)=m(0,3,5,6,7,10,11,13,15)

1001011111000110ABCD0001111000011110ABCDABCABCBDCD第一步：作出卡諾圖第二步：畫卡諾圈第三步：找出全部質(zhì)項2/6/202374例2.11用卡諾圖化簡邏輯函數(shù)ABCD000111100001111011111112/6/20237576

例2.12用卡諾圖化簡下面函數(shù)

f(A,B,C,D)=m(0,3,5,7,10,11,12,13,14,15)1011011011100110ABCD0001111000011110ABCDABDABC1011011011100110ABCD0001111000011110ABBDCDAC2/6/202376卡諾圖的作用邏輯函數(shù)化簡：求邏輯函數(shù)的最簡“與-或”表達(dá)式；也可求邏輯函數(shù)的最