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

1、第二章 邏輯代數(shù)基礎,學習要求：掌握邏輯代數(shù)的基本概念，學會用邏輯函描述邏輯問題的基本方法。掌握邏輯代數(shù)的公理、基本定理和重要規(guī)則；學會用代數(shù)法化簡邏輯函數(shù)； 熟練掌握用卡諾圖化簡邏輯函數(shù)。,2.1 邏輯代數(shù)的基本概念,邏輯代數(shù)是一個由邏輯變量集K，常量0和1以及“與”、“或”、“非”3種基本運算構成的一個封閉的代數(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結合律 (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無大小之分，實際上代表著矛盾的雙方或事件的真假，例如開關的接通與斷開，電壓的高和底，信號的有和無，電燈的亮和滅等等。 只要是兩種穩(wěn)定的物理狀態(tài)，都可以用0和1這兩種不同的邏輯值來表征。,一、"或"運算,如果決定某一事件發(fā)生的多個條件，只要有一個或一個以上

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

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

6、邏輯代數(shù)中"與"邏輯關系用"與"運算描述。"與"運算又稱邏輯乘，其運算符為"?"或"?"。兩變量的"與"運算可表示為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ā)生取決于條件的否定，則這種因果關系稱為"非"邏輯。"非"邏輯用"非"運算描述。"非"運算又稱求反運算，運算符為"－"或"¬"

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

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

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

11、uot;或"的順序去括號, 如：(AB)＋(CD)＝AB＋CD,例：,,邏輯表達式書寫省略規(guī)則：,二、真值表,真值表是一種由邏輯變量的所有可能取值組合及其對應的邏輯函數(shù)值所構成的表格.,三、卡諾圖,卡諾圖是一種用圖形描述邏輯函數(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ō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),最小項的性質：,1）當函數(shù)以最小項之和形式表示時，可很容易列出函數(shù)及反函數(shù)的真值表（在真值表中，函數(shù)所包含的最小項填“1

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

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

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

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

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

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

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

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

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

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

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

28、項"稱為函數(shù)的蘊涵項；,質蘊涵項：不被其它蘊涵項所包含的蘊涵項；,必要質蘊涵項：質蘊涵項中至少有一個最小項不被其它蘊涵項所包含。,用卡諾圖化簡邏輯函數(shù)的一般步驟為：,第一步：作出函數(shù)的卡諾圖；,第二步：在卡諾圖上圈出函數(shù)的全部質蘊涵項；,第三步：從全部質蘊涵項中找出所有必要質蘊涵項；,第四步：若全部必要質蘊涵項尚不能覆蓋所有的1 方格，則需從剩余質蘊涵項中找出最簡的所需質蘊涵項，使它和必要質蘊涵項一起構成函數(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ù)化簡中兩個實際問題的考慮,一、包含無關最小項的邏輯函數(shù)的化簡,無關最小項：一個邏輯函數(shù), 如果它的某些輸入取值組合因受特殊原因制約而不會再現(xiàn), 或者雖然每種輸入取值組合都可能出現(xiàn), 但此時函數(shù)取值為1還是為0無關緊要, 那么這些輸入取值組合所對應的最小項稱為無關最小項。,無關最小項可以隨意加到函數(shù)表達式中，或不加到函數(shù)表達式中，并不影響函數(shù)的實際邏輯功能。,例：給定某電路的邏輯函數(shù)真值表如下，求F的最

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