第二章 邏輯代數(shù)基礎(chǔ)

1、第二章 邏輯代數(shù)基礎(chǔ),學(xué)習(xí)要求：掌握邏輯代數(shù)的基本概念，學(xué)會用邏輯函描述邏輯問題的基本方法。掌握邏輯代數(shù)的公理、基本定理和重要規(guī)則；學(xué)會用代數(shù)法化簡邏輯函數(shù)； 熟練掌握用卡諾圖化簡邏輯函數(shù)。,2.1 邏輯代數(shù)的基本概念,邏輯代數(shù)是一個由邏輯變量集K，常量0和1以及“與”、“或”、“非”3種基本運算構(gòu)成的一個封閉的代數(shù)系統(tǒng)，記為L={K, +, ?, -, 0, 1}。它是一個二值代數(shù)系統(tǒng)。常量0和1表示真和假，無大小之分。

2、該系統(tǒng)滿足下列公理：,公理1交換律 A+B=B+A, A ? B=B ? A,公理2結(jié)合律 (A+B)+C=A+(B+C), (A ? B) ? C=A ? (B ? C),公理3分配律 A+ ( B ? C ) =(A+B) ? (B+C), A? ( B+C ) =A ? B+A ? C,公理40－1律 A+ 0 =A, A ? 1=A

3、 A+1=1, A ? 0=0，,2.1.1 邏輯變量及基本邏輯運算,邏輯變量：僅取值0或取值1的變量。這里0和1無大小之分，實際上代表著矛盾的雙方或事件的真假，例如開關(guān)的接通與斷開，電壓的高和底，信號的有和無，電燈的亮和滅等等。 只要是兩種穩(wěn)定的物理狀態(tài)，都可以用0和1這兩種不同的邏輯值來表征。,一、"或"運算,如果決定某一事件發(fā)生的多個條件，只要有一個或一個以上

4、的條件成立，事件便可發(fā)生，這種因果關(guān)系稱之為"或"邏輯。在邏輯代數(shù)中，"或"邏輯關(guān)系用"或"運算描述。"或"運算又稱邏輯加，其運算符為"+"或" ? "，兩個變量的"或"運算可表示為:F=A+B 或者 F=A?B,讀作"F等于A或B",其中A、B是參加運算的兩個邏輯變量，F(xiàn)

5、為運算結(jié)果。意思是：只要A、B中有一個為1，則F為1；僅當(dāng)A、B均為0時，F(xiàn)才為0。,"或"運算表,由“或”運算的運算表可知“或”運算的法則為：,0+0=01+0=10+1=11+1=1,實現(xiàn)"或"運算的邏輯電路稱為"或"門。,二、"與"運算,如果決定某一事件的發(fā)生的多個條件必須同時具備，事件才能發(fā)生，這種因果關(guān)系稱為"與"邏輯。

6、邏輯代數(shù)中"與"邏輯關(guān)系用"與"運算描述。"與"運算又稱邏輯乘，其運算符為"?"或"?"。兩變量的"與"運算可表示為F＝A ? B 或者 F=A?B讀作"F等于A與B"，意思是若A ? B 均為1，則F為1；否則F為0。,"與"運算表,由“與”運算的運算表可知“與”

7、運算法則為：,0 ? 0 = 01 ? 0 = 00 ? 1 = 01 ? 1 = 1,實現(xiàn)“與”運算的邏輯電路稱為“與”門。,三、"非"運算,如果某一事件的發(fā)生取決于條件的否定，則這種因果關(guān)系稱為"非"邏輯。"非"邏輯用"非"運算描述。"非"運算又稱求反運算，運算符為"－"或"¬"

8、. "非"運算可表示為,讀作"F等于A非"，意思是若A＝0，則F為1；反之，若A=1, 則F為0。,“非"運算表,由“非”運算的運算表可知“非”運算法則為：,實現(xiàn)“非”運算的邏輯電路稱為“非”門。,2.1.2 邏輯函數(shù),一、邏輯函數(shù)的定義,設(shè)某一電路的輸入邏輯變量為A1, A2, …, An , 輸出邏輯變量為F。如果當(dāng)A1, A2 , …, An 的值確定后，F(xiàn)的值就唯一地被定下

9、來，則F稱為A1, A2, …, An , 的邏輯函數(shù)，記為F=f (A1, A2, …, An),邏輯電路的功能可由相應(yīng)邏輯函數(shù)完全描述。,與普通函數(shù)概念相比邏輯函數(shù)有如下特點： 1）邏輯變量與邏輯函數(shù)的取值只有0和1； 2）邏輯函數(shù)與邏輯變量的關(guān)系由“或”、 “與”、“非”運算決定。,二、邏輯函數(shù)的相等,設(shè)有兩個邏輯函數(shù),F1=f1 (A1, A2, …, An)F2=f2

10、 (A1, A2, …, An),若對應(yīng)于A1, A2, …, An的任何一組取值, F1 和F2的值都相同, 則稱函數(shù)F1和函數(shù)F2相等, 記作F1= F2,亦稱函數(shù)F1與F2等價。,2.1.3 邏輯函數(shù)的表示法,一、邏輯表達式,由邏輯變量、常量和邏輯運算符構(gòu)成的合法表達式。,進行"非"運算可不加括號, 如,"與"運算符一般可省略, A?B可寫成AB.,可根據(jù)先"與"后&q

11、uot;或"的順序去括號, 如：(AB)＋(CD)＝AB＋CD,例：,,邏輯表達式書寫省略規(guī)則：,二、真值表,真值表是一種由邏輯變量的所有可能取值組合及其對應(yīng)的邏輯函數(shù)值所構(gòu)成的表格.,三、卡諾圖,卡諾圖是一種用圖形描述邏輯函數(shù)的方法。,2.2 邏輯代數(shù)的基本定理和規(guī)則,2.2.1 基本定理,定理10＋0＝01＋0＝1 0＋1＝1 1＋1＝1 0 ? 0

12、＝0 1 ? 0 ＝0 0 ? 1 ＝01 ? 1 ＝1,定理2(重疊律)A＋A＝AA ? A ＝A,定理3(吸收律)A＋A ? B＝A A ?( A +B)＝A,2.2.2 邏輯代數(shù)的重要規(guī)則,一、代入規(guī)則,任何一個含有變量A的邏輯等式，如果將所有出現(xiàn)A的位置都代之以同一個邏輯函數(shù)F，則等式仍然成立。,二、反演規(guī)則,如果將邏輯函數(shù)F中所有的"

13、? "變成"+", "+"變成" ? ", "0"變成"1", "1"變成"0", 原變量變成反變量，反變量變成原變量，所得到的新函數(shù)是原函數(shù)的反函數(shù),使用反演規(guī)則時, 應(yīng)注意保持原函式中運算符號的優(yōu)先順序不變。,例如：已知,三、對偶規(guī)則,如果將邏輯函數(shù)F中所有的" ? &quo

14、t;變成"+", "+"變成" ? ", "0"變成"1", "1"變成"0", 則所得到的新邏輯函數(shù)F的對偶式F'。如果F'是F的對偶式，則F也是F' 的對偶式，即F與F'互為對偶式。,求某一函數(shù)F的對偶式時，同樣要注意保持原函數(shù)的運算順序不變。,對偶規(guī)則：若兩個邏

15、輯函數(shù)F的G相等，則其對偶式F' 和G' 也相等。,2.3 邏輯函數(shù)表達式的形式與變換,2.3.1 邏輯函數(shù)表達式的基本形式,兩種基本形式："積之和"表達式與"和之積"表達式.,2.3.2 邏輯函數(shù)表達式的標準形式,一、最小項,如果一個具有n個變量的函數(shù)的"積"項包含全部n個變量, 每個變量都以原變量或反變量形式出現(xiàn), 且僅出現(xiàn)一次，則這個"積&

16、quot;項被稱為最小項。假如一個函數(shù)完全由最小項所組成, 那么該函數(shù)表達式稱為標準"積之和"表達式, 即"最小項之和".,三變量函數(shù)的最小項：,=m2+ m3+ m6+ m7,注意：變量的順序.,即n個變量的所有最小項之和恒等于1。,所以,=? m(2, 3, 6, 7),最小項的性質(zhì)：,1）當(dāng)函數(shù)以最小項之和形式表示時，可很容易列出函數(shù)及反函數(shù)的真值表（在真值表中，函數(shù)所包含的最小項填“1

17、”） 。,3）n變量的最小項有n個相鄰項。,相鄰項：只有一個變量不同（以相反的形式出現(xiàn)）。,一對相鄰項可以消去一個變量。,二、最大項,如果一個具有n個變量的函數(shù)的"和"項包含全部n個變量，每個變量都以原變量或反變量形式出現(xiàn)，且僅出現(xiàn)一次，則這個"和"項稱為最大項。假如一個函數(shù)完全由最大項組成，那么這個函數(shù)表達式稱為標準"和之積"表達式。,三變量函數(shù)的最大項：,注意：變量順序.,

18、與最小項類似，有,例如：,最大項的性質(zhì)：,1）當(dāng)函數(shù)以最大項之積形式表示時，可很容易列出函數(shù)及反函數(shù)的真值表（在真值表中，函數(shù)所包含的最大項填“0”）。,3）n變量的最大項有n個相鄰項。,相鄰項：只有一個變量不同（以相反的形式出現(xiàn)）。,一對相鄰項可以消去一個變量。,三、兩種標準形式的轉(zhuǎn)換：,以最小項之和的形式表示的函數(shù)可以轉(zhuǎn)換成最大項之積的形式，反之亦然。,=? m(2, 3, 6, 7),且有,即：最大項與最小項互補。,2.3.3

19、 邏輯函數(shù)表達式的轉(zhuǎn)換,任何一個邏輯函數(shù)，總可以將其 轉(zhuǎn)換成"最小項之和"及"最大項之積"的形式, 常用代數(shù)轉(zhuǎn)換法或真值表轉(zhuǎn)換法.,一、代數(shù)轉(zhuǎn)換法,用代數(shù)法求一個函數(shù)"最小項之和"的形式，一般分為兩步：,第一步：將函數(shù)表達式變換成一般的"與或"式.,,F(A,B,C) = m0+m1+m3+m6+m7,=Σm(0,1,3,6,7),類似地，用代數(shù)法求一個

20、函數(shù)"最大項之積"的形式，也可分為兩步：,第一步：將函數(shù)表達式轉(zhuǎn)換成一般"或與"式；,如果給出的函數(shù)已經(jīng)是"與或"式或者是"或與"式，則可直接進行第二步。,F(A,B,C) = M1 · M3 · M6 · M7,=ΠM(1,3,6,7),二、真值表轉(zhuǎn)換法,一個邏輯函數(shù)的真值表與它的最小項表達式和最大項表達式均存在一一對應(yīng)的關(guān)系

21、。函數(shù)F的最小項表達式由使F取值為1的全部最小項之和組成。函數(shù)F的最大項表達式由使F取值為0的全部最大項之積組成。,和"最大項之積"的形式。,解：,注意：任何一個邏輯函數(shù)的兩種標準形式唯一 .,2.4 邏輯函數(shù)的簡化,一般來說, 邏輯函數(shù)表達式越簡單, 設(shè)計出來的電路也就越簡單。把邏輯函數(shù)簡化成最簡形式稱為邏輯函數(shù)的最小化, 有三種常用的方法, 即代數(shù)化簡法、卡諾圖化簡法和列表化簡法。,2.4.1 代數(shù)化簡法,

22、該方法運用邏輯代數(shù)的公理、定理和規(guī)則對邏輯函數(shù)進行推導(dǎo)、變換而進行化簡，沒有固定的步驟可以遵循，主要取決于對公理、定理和規(guī)則的熟練掌握及靈活運用的程度。有時很難判定結(jié)果是否為最簡。,一、"與或"式的化簡,化簡應(yīng)滿足的兩個條件：,1） 表達式中"與項"的個數(shù)最少；,2） 在滿足1）的前提下, 每個"與項"中的變量個數(shù)最少。,,,,,,,,,,二、"或與"式的

23、化簡,化簡應(yīng)滿足的兩個條件：,1） 表達式中"或項"的個數(shù)最少；,2） 在滿足1）的前提下, 每個"或項"中的變量個數(shù)最少。,解：,= A(B+C),解：,,,,,,,2.4.2 卡諾圖化簡法,該方法簡單、直觀、容易掌握, 當(dāng)變量個數(shù)小于等于6時非常有效, 在邏輯設(shè)計中得到廣泛應(yīng)用。,一、卡諾圖的構(gòu)成,n個變量的卡諾圖是一種由2n個方格構(gòu)成的圖形, 每一個方格表示邏輯函數(shù)的一個最小項,

24、所有的最小項巧妙地排列成一種能清楚地反映它們相鄰關(guān)系的方格陣列。因為任意一個邏輯函數(shù)都 可表示成"最小項之和"的形式, 所以一個函數(shù)可用圖形中若干方格構(gòu)成的區(qū)域來表示。,二變量卡諾圖,三變量卡諾圖,四變量卡諾圖,定義：彼此只有一個變量不同，且這個不同變量互為反變量的兩個最小 項(或"與項")稱為相鄰最小項(或相鄰"與項").,相鄰最小項在卡諾圖中有三種特征，即幾何相鄰、相對相鄰

25、和重疊相鄰。,卡諾圖在構(gòu)造上具有以下兩個特點：,1）n個變量的卡諾圖由2n個小方格組成, 每個小方格代表一個最小項。,2）卡諾圖上處在相鄰、相對、相重位置的小方格所代表的最小項為相鄰最小項。,二、邏輯函數(shù)的卡諾圖表示,將邏輯函數(shù)所對應(yīng)的最小項在卡諾圖的相應(yīng)方格中標以1，剩余方格標以0或不標。,1、"與或"式的卡諾圖表示.,直接將表達式的"與項"或"最小項"所對應(yīng)的方格標以1.,

26、2、其它形式函數(shù)的卡諾圖表示要轉(zhuǎn)換成"與或"式再在卡諾圖上表示。,三、卡諾圖的性質(zhì),在卡諾圖上把相鄰最小項所對應(yīng)的小方格"圈"在一起可進行合并，以達到用一個簡單"與項"代替若干最小項的目的。這樣的"圈"稱為"卡諾圈"。,二變量卡諾圖的典型合并情況,AB,三變量卡諾圖的典型合并情況,,四變量卡諾圖的典型合并情況,一個卡諾圈中的小方格滿足以下

27、規(guī)律：,1）卡諾圈中的小方格的數(shù)目為2m, m為整數(shù)且m?n;,3） 2m個小方格可用(n-m)個變量的"與項"表示, 該"與項"由這些最小項中的相同變量構(gòu)成。,2） 2m個小方格含有m個不同變量和(n-m)個相同變量;,4）當(dāng)m=n時,卡諾圈包圍整個卡諾圖,可用1表示，即n個變量的全部最小項之和為1。,四、卡諾圖化簡邏輯函數(shù)的步驟：,蘊涵項："與或"式中的每一個"與

28、項"稱為函數(shù)的蘊涵項；,質(zhì)蘊涵項：不被其它蘊涵項所包含的蘊涵項；,必要質(zhì)蘊涵項：質(zhì)蘊涵項中至少有一個最小項不被其它蘊涵項所包含。,用卡諾圖化簡邏輯函數(shù)的一般步驟為：,第一步：作出函數(shù)的卡諾圖；,第二步：在卡諾圖上圈出函數(shù)的全部質(zhì)蘊涵項；,第三步：從全部質(zhì)蘊涵項中找出所有必要質(zhì)蘊涵項；,第四步：若全部必要質(zhì)蘊涵項尚不能覆蓋所有的1 方格，則需從剩余質(zhì)蘊涵項中找出最簡的所需質(zhì)蘊涵項，使它和必要質(zhì)蘊涵項一起構(gòu)成函數(shù)的最小覆蓋。,例：

29、用卡諾圖化簡邏輯涵數(shù) F(A, B, C, D)=?m(0, 3, 5, 6, 7, 10, 11, 13, 15),解：,例：用卡諾圖化簡邏輯函數(shù) F(A, B, C, D)=?m(2, 3, 6, 7, 8,10, 12),解：,例：用卡諾圖把邏輯函數(shù) F(A, B, C, D)=? M( 3, 4, 6, 7, 11, 12, 13, 14,15)化簡成最簡"或與"

30、表達式。,1,2.4.4 邏輯函數(shù)化簡中兩個實際問題的考慮,一、包含無關(guān)最小項的邏輯函數(shù)的化簡,無關(guān)最小項：一個邏輯函數(shù), 如果它的某些輸入取值組合因受特殊原因制約而不會再現(xiàn), 或者雖然每種輸入取值組合都可能出現(xiàn), 但此時函數(shù)取值為1還是為0無關(guān)緊要, 那么這些輸入取值組合所對應(yīng)的最小項稱為無關(guān)最小項。,無關(guān)最小項可以隨意加到函數(shù)表達式中，或不加到函數(shù)表達式中，并不影響函數(shù)的實際邏輯功能。,例：給定某電路的邏輯函數(shù)真值表如下，求F的最

31、簡"與或"式。,解：,1)不考慮無關(guān)最小項：,2)考慮無關(guān)最小項：,二、多輸出邏輯函數(shù)的化簡.,對于多輸出邏輯函數(shù)，如果孤立地將單個輸出一一化簡，然后直接拼在一起，通常并不能保證整個電路最簡，因為各個輸出函數(shù)之間往往存在可供共享的部分。,多輸出邏輯函數(shù)化簡的標準：,2） 在滿足上述條件的前提下，各不同"與項"中所含的變量總數(shù)最少。,1） 所有邏輯表達式包含的不同"與項"總數(shù)