1、2.1 邏輯代數(shù)中的幾個概念邏輯代數(shù)中的幾個概念2.2 邏輯代數(shù)的基本運算邏輯代數(shù)的基本運算2.3 邏輯代數(shù)的基本定理及規(guī)則邏輯代數(shù)的基本定理及規(guī)則2.4 邏輯函數(shù)的性質(zhì)邏輯函數(shù)的性質(zhì)2.5 邏輯函數(shù)的化簡邏輯函數(shù)的化簡第二章第二章 邏輯代數(shù)基礎(chǔ)邏輯代數(shù)基礎(chǔ)第二章第二章 邏輯代數(shù)基礎(chǔ)邏輯代數(shù)基礎(chǔ)Fundamentals of Boolean Algebar布爾代數(shù)布爾代數(shù) Boolean algebra： 用一種用一種數(shù)學運算數(shù)學運算的代數(shù)系統(tǒng)描述的代數(shù)系統(tǒng)描述人的人的邏輯思維規(guī)律和推理過程。邏輯思維規(guī)律和推理過程。1854年，由英國數(shù)學家年，由英國數(shù)學家George Boole在在他的一篇論

2、文他的一篇論文思維規(guī)律的研究思維規(guī)律的研究（A investigation of the laws of thought）中提出，建立了計算機的）中提出，建立了計算機的計算符號語言計算符號語言中進行中進行邏輯推理的基本邏輯推理的基本規(guī)律規(guī)律。邏輯代數(shù)邏輯代數(shù) Switching algebra： 在在1938年，由貝爾實驗室的研年，由貝爾實驗室的研究人員究人員Claude E.Shannon指出如何將布爾代數(shù)的一些基本前提和定理指出如何將布爾代數(shù)的一些基本前提和定理應(yīng)應(yīng)用于繼電器用于繼電器的分析與描述的分析與描述，稱為，稱為二值布爾代數(shù)二值布爾代數(shù)，或，或開關(guān)代數(shù)開關(guān)代數(shù)。繼電器是。繼電器是當

3、時最常用的數(shù)字邏輯元件，繼電器的接觸狀態(tài)（打開或閉合）用當時最常用的數(shù)字邏輯元件，繼電器的接觸狀態(tài)（打開或閉合）用0或或1表示。表示。邏輯代數(shù)是二值邏輯運算中的基本數(shù)學工具邏輯代數(shù)是二值邏輯運算中的基本數(shù)學工具邏輯代數(shù)廣泛應(yīng)用于數(shù)字系統(tǒng)的分析和設(shè)計邏輯代數(shù)廣泛應(yīng)用于數(shù)字系統(tǒng)的分析和設(shè)計在在現(xiàn)代邏輯分析技術(shù)現(xiàn)代邏輯分析技術(shù)中，邏輯值對應(yīng)于各種廣泛的物中，邏輯值對應(yīng)于各種廣泛的物理條件：電壓的高或低、燈光的明或暗、電容器的充電或理條件：電壓的高或低、燈光的明或暗、電容器的充電或放電、熔絲的斷開或接通，等等。下表給出了放電、熔絲的斷開或接通，等等。下表給出了不同的計算不同的計算機邏輯和存儲技術(shù)中表示

4、位值的物理狀態(tài)機邏輯和存儲技術(shù)中表示位值的物理狀態(tài)。表表 示示 位位 值值 的的 狀狀 態(tài)態(tài)技術(shù)技術(shù)01氣動邏輯氣動邏輯繼電器邏輯繼電器邏輯CMOS邏輯邏輯TTL邏輯邏輯光纖光纖動態(tài)存儲動態(tài)存儲非易失的可擦存儲器非易失的可擦存儲器雙極只讀存儲器雙極只讀存儲器磁泡存儲器磁泡存儲器磁帶存儲器磁帶存儲器聚合體存儲器聚合體存儲器只讀壓縮盤只讀壓縮盤可重寫壓縮盤可重寫壓縮盤低壓流動低壓流動電路斷開電路斷開01.5V00.8V暗暗電容放電電容放電電子捕獲電子捕獲熔絲燒斷熔絲燒斷無磁泡無磁泡磁通朝磁通朝“北北”分子處于狀態(tài)分子處于狀態(tài)A無凹陷無凹陷晶態(tài)染色晶態(tài)染色高壓流動高壓流動電路閉合電路閉合3.55.0

5、V2.05.0V亮亮電容充電電容充電電子釋放電子釋放熔絲完好熔絲完好有磁泡有磁泡磁通朝磁通朝“南南”分子處于狀態(tài)分子處于狀態(tài)B凹陷凹陷非晶態(tài)染色非晶態(tài)染色2.1 邏輯代數(shù)中的幾個概念邏輯代數(shù)中的幾個概念 1. 邏輯狀態(tài)邏輯狀態(tài) Logic State： 當事物的某些特性表現(xiàn)為兩種當事物的某些特性表現(xiàn)為兩種互不相容互不相容的狀態(tài)，即的狀態(tài)，即 某一時刻必出現(xiàn)且僅出現(xiàn)一種狀態(tài)某一時刻必出現(xiàn)且僅出現(xiàn)一種狀態(tài) 一種狀態(tài)是另一種狀態(tài)的反狀態(tài)一種狀態(tài)是另一種狀態(tài)的反狀態(tài) 則用符號則用符號0、1分別表示這兩種狀態(tài)，稱邏輯狀態(tài)。分別表示這兩種狀態(tài)，稱邏輯狀態(tài)。即：即：0 狀態(tài)狀態(tài) (0state) 和和 1

6、狀態(tài)狀態(tài) (1state) 一般，一般，0狀態(tài)狀態(tài)邏輯條件的假或無效，邏輯條件的假或無效， 1狀態(tài)狀態(tài)邏輯條件的真或有效。邏輯條件的真或有效。 (兩種狀態(tài)無大小之分兩種狀態(tài)無大小之分) 2. 邏輯變量邏輯變量 Logic Value ：用于表示事物的邏輯狀態(tài)隨邏輯條件的變化而變化，取值用于表示事物的邏輯狀態(tài)隨邏輯條件的變化而變化，取值“0” 或或“1” 。 邏輯常量邏輯常量 Logic Constant ：邏輯狀態(tài)保持不變，取值邏輯狀態(tài)保持不變，取值“0” 或或“1”。 3. 邏輯電平邏輯電平 Logic Voltage：在二值邏輯電路在二值邏輯電路(開關(guān)電路開關(guān)電路)中，將物理器件的物理量中

7、，將物理器件的物理量離散離散為兩種電平：為兩種電平：高電平高電平(用用H表示表示)、低電平低電平(用用L表示表示)抽象化的高、低電平抽象化的高、低電平忽略忽略其物理量值的實際含義，實際上其物理量值的實際含義，實際上它們是代表著它們是代表著一定范圍一定范圍的物理量。參見下頁。的物理量。參見下頁。在高、低電平之間有一邏輯不確定區(qū)，稱為在高、低電平之間有一邏輯不確定區(qū)，稱為“噪音區(qū)噪音區(qū)”。若電平穩(wěn)定于噪音區(qū)稱為邏輯模糊，這在邏輯電路中不允若電平穩(wěn)定于噪音區(qū)稱為邏輯模糊，這在邏輯電路中不允許。許。表表21不同工藝器件定義的邏輯電平不同工藝器件定義的邏輯電平 工藝工藝 邏輯電平（電源電壓為邏輯電平（電

8、源電壓為5V） L H TTL 00.40V 3.0 5.0V CMOS 0 0.80V 2.0 5.0V圖圖2-1 脈沖的邏輯電平表示脈沖的邏輯電平表示LHLH4. 邏輯約定邏輯約定 Logic Assumpsit： 規(guī)定規(guī)定 邏輯電平邏輯電平（表示物理器件的輸入、輸出物理量）（表示物理器件的輸入、輸出物理量） 與與 邏輯狀態(tài)邏輯狀態(tài)（表示物理器件的邏輯功能）（表示物理器件的邏輯功能） 之間的之間的 關(guān)系關(guān)系，即，即邏輯規(guī)定（約定）邏輯規(guī)定（約定）。 這一規(guī)定過程稱為這一規(guī)定過程稱為邏輯化過程邏輯化過程。 邏輯約定邏輯約定有兩種：有兩種：正邏輯正邏輯規(guī)定（約定）規(guī)定（約定） 和和 負邏輯負邏

9、輯規(guī)定（約定），如下：規(guī)定（約定），如下：正邏輯正邏輯規(guī)定（約定）規(guī)定（約定）負邏輯負邏輯規(guī)定（約定）規(guī)定（約定）01LH邏輯狀態(tài)邏輯狀態(tài)邏輯電平邏輯電平(a)(a)正邏輯規(guī)定（約定）正邏輯規(guī)定（約定）注：本書均采用正邏輯約定。H H電平電平L L電平電平1狀態(tài)0狀態(tài)10LH邏輯狀態(tài)邏輯狀態(tài)邏輯電平邏輯電平(b)(b)負邏輯規(guī)定（約定）負邏輯規(guī)定（約定）H H電平電平L L電平電平0狀態(tài)1狀態(tài) 邏輯電路邏輯電路Logic Circuit： 由實現(xiàn)邏輯變量之間邏輯關(guān)系的物理器件所構(gòu)成的由實現(xiàn)邏輯變量之間邏輯關(guān)系的物理器件所構(gòu)成的電路稱為邏輯電路，即二值邏輯電路。電路稱為邏輯電路，即二值邏輯電路。

10、5. 邏輯代數(shù)邏輯代數(shù) Logic Algebar ： 用代數(shù)形式表現(xiàn)邏輯變量之間的因果關(guān)系。用代數(shù)形式表現(xiàn)邏輯變量之間的因果關(guān)系。 用代數(shù)運算對這些邏輯變量進行邏輯推理。用代數(shù)運算對這些邏輯變量進行邏輯推理。 因此，邏輯代數(shù)是因此，邏輯代數(shù)是一個集合一個集合：邏輯：邏輯變量變量集、集、常量常量0和和1、 “與與”、“或或”和和“非非”三種邏輯三種邏輯運算運算。 運算順序是：運算順序是：“非非”最高，最高，“與與”次之，次之，“或或”最低。最低。6. 邏輯函數(shù)邏輯函數(shù) Logic Function： 輸入邏輯變量輸入邏輯變量 A1，A2， , An；輸出邏輯變量；輸出邏輯變量F；記為：記為：F

11、 = f (A1，A2， , An )，關(guān)系如下圖所示：，關(guān)系如下圖所示：F = f (A1, A2, , An)實現(xiàn)f (A1，A2， , An )的邏輯網(wǎng)絡(luò)A1A2 AnF6. 邏輯函數(shù)的表示法邏輯函數(shù)的表示法 Representation：主要有四種主要有四種 真值表真值表(窮舉法窮舉法) Truth TableA BF0 00 11 01 10001真值表例真值表例表達式例：表達式例：F = A B 邏輯表達式邏輯表達式 Algebraic Forms of Switching Functions 卡諾圖卡諾圖 Karnaugh MAP (文氏圖文氏圖 Venn Diagrams) 時

12、間圖時間圖 (信號波形圖信號波形圖 ) TimingVenn圖圖全集全集 為為 1引入變量引入變量B，將已有區(qū)域?qū)⒁延袇^(qū)域再分別一分再分別一分為二為二引入變量引入變量A，將，將 區(qū)域區(qū)域 一分為二一分為二2.2 邏輯代數(shù)的基本運算邏輯代數(shù)的基本運算“與與”運算運算(邏輯邏輯乘乘)Logic Multiplication“或或”運算運算(邏輯邏輯加加)Logic Addition“非非”運算運算(邏輯邏輯非非)Logic Negation運算運算結(jié)果結(jié)果邏輯邏輯積積 Logic Product邏輯邏輯和和 Logic Sum求求補補Complement示意示意電路電路真值真值表表FABFABFA

13、RA BF0 00 11 01 10001A BF0 00 11 01 10111AF0 1 10“與與”運算運算(邏輯邏輯乘乘)Logic Multiplication“或或”運算運算(邏輯邏輯加加)Logic Addition“非非”運算運算(邏輯邏輯非非)Logic Negation代數(shù)代數(shù)式式F = A B = A BF = ABF = A邏輯邏輯符號符號波形波形圖圖文氏文氏圖圖(F為為陰影陰影)&DABCFDABCF1DABCFFDABC1AFAFABFABFAFA2.3 邏輯代數(shù)的基本定理及規(guī)則邏輯代數(shù)的基本定理及規(guī)則基本運算：基本運算： 1 = 0 0 = 11 1 = 1 0

14、+ 0 = 00 1 = 1 0 = 0 1 + 0 = 0 + 1 = 10 0 = 0 1 + 1 = 1 (10)2.3.1 布爾代數(shù)的基本公理布爾代數(shù)的基本公理 Basic Postulates 公理是基本的假設(shè)，是客觀存在，無需證明。可以用公理是基本的假設(shè)，是客觀存在，無需證明。可以用真真值表驗證等式值表驗證等式成立，當然等式兩邊還具有相同的卡諾圖，體成立，當然等式兩邊還具有相同的卡諾圖，體現(xiàn)了表達式的多樣性。現(xiàn)了表達式的多樣性。 運算的優(yōu)先順序：括號，非，與，或運算的優(yōu)先順序：括號，非，與，或。01 律律 0 and 1 elements for and operators A +

15、 0 = A A 1 = A A + 1 = 1 A 0 = 0 用用VENN圖驗證圖驗證Commutativity of the and operations交換律交換律 A B = B A A B = B A結(jié)合律結(jié)合律 A(BC) = (AB)C A ( B C ) = ( A B ) C Distributivity of the and operations分配律分配律 AB C = (AB)(AC) A (BC) = A BA C用真值表證明用真值表證明A B C（A+B)(A+C) B C A+BCA+B A+C0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0

16、1 1 1 0 1 1 10001000100011111001111110101111100011111可以用同樣的方法證明可以用同樣的方法證明 A (B+C) = A B+ A C 成立。成立。由此證明由此證明 A+BC = (A+B)(A+C) 成立成立。例：證明例：證明 分配律分配律 AB C = (AB)(AC) 成立。成立。 用真值表證明，如下用真值表證明，如下：重疊律重疊律 Idempotency A + A = A A A = A 上述三條基本公理可以用上述三條基本公理可以用Venn圖驗證。如下所示：圖驗證。如下所示：問題：問題：若若 A + B = 1 ，則，則 A 與與 B

17、 互補嗎？互補嗎？ 若若 A B = 0 ，則，則 A 與與 B 互補嗎？互補嗎？互補律互補律 Complement A + A = 1 A A = 0全集全集 = 1引入變量引入變量A，將全集分為兩個互補相容，將全集分為兩個互補相容的部分：的部分： A 區(qū)域區(qū)域 和和 A 區(qū)域區(qū)域AVenn圖圖A對合律對合律 involution A = A2.3.2 邏輯代數(shù)的基本定理邏輯代數(shù)的基本定理 Fundamental Theorems右邊右邊 = A + 1 B （01律）律） = A +（ A + A ) B （互補律）（互補律） = A + AB + A B （分配律）（分配律） = A +

18、 AB （吸收律）（吸收律） = A + B例例 ：證明：證明 A + A B = A + B ，可以用，可以用公理公理來來證明證明。吸收律吸收律 AbsorptionA + A B = A + B A ( A + B ) = A BA B + A B = A ( A + B )( A+B ) = AA + AB = A A ( A + B ) = A = 左邊左邊 證明成立證明成立A + B = A B A B = A + B反演律反演律 DeMorgans Theorem (摩根定理摩根定理) = A + 1 （互補律）（互補律） = 1 （01律）律）例例 ：證明：證明 A B = A

19、+ B 成立，可以用函數(shù)的互補性來證明成立，可以用函數(shù)的互補性來證明設(shè)：設(shè)：X = A B Y = A + B X + Y = AB + A + B = A + B + B （吸收律）（吸收律）又又 X Y = AB（ A + B） = A B A + AB B (分配律）分配律） = 0 A + 0 B (互補律）互補律） = 0 + 0 (01律）律） = 0 (基本運算）基本運算） X 與與 Y 互補，互補，X = Y，Y = X 。證明摩根定理成立。證明摩根定理成立。A1 + A2 + + An = A1 A2 An A1 A2 An = A1 + A2 + + An 摩根定理的作用摩

20、根定理的作用：進行函數(shù)化簡和邏輯變換。：進行函數(shù)化簡和邏輯變換。N變量的摩根定理：變量的摩根定理：（此定理證明見代入規(guī)則。）（此定理證明見代入規(guī)則。） = 右邊 證明成立 A B + AC + BC = AB + AC (A + B) (A + C) (B + C) = (A + B) (A + C) 例 ：證明 A B + AC + BC = AB + AC左邊 = A B + AC + BC 1 （01律） = AB + AC + ABC + ABC （分配律） = AB + ABC + AC + ACB （交換律） = AB（1+C） + AC（1+B） （分配律） = AB 1 + A

21、C 1 （ 01律） = AB + AC （ 01律）包含包含律律 Consensus (也稱多余項定理也稱多余項定理) = A B + AC + BC（ A + A ) （互補律）1. 代入規(guī)則：代入規(guī)則：又又 邏輯函數(shù)邏輯函數(shù) h 取值取值也是也是僅有僅有 0 或或 1已知已知 f ( x1 , x2 , , xi , , xn ) = g ( x1 , x2 , , xi , , xn ) 有任意函數(shù)有任意函數(shù) h ，令：，令： xi = h則則 f ( x1 , x2 , , h , , xn ) = g ( x1 , x2 , ,h , , xn ) 依然成立。依然成立。證明：證明：

22、 xi 取值取值(只有只有) 0 或或 1，使等式成立，使等式成立 代入規(guī)則成立。代入規(guī)則成立。2.3.4 邏輯代數(shù)的基本規(guī)則邏輯代數(shù)的基本規(guī)則 Basic FormulasA1 + A2 + + An = A1 A2 An 令令 X = A2 + Y 代入代入 A1 + X = A1 X (摩根定理摩根定理)令令 Y = A3 + Z 代入代入則則 A1 + A2 + A3 + Z = A1 A 2 (A3 + Z) 依次類推，則推出依次類推，則推出N變量的摩根定理。變量的摩根定理。證明證明N變量的摩根定理：變量的摩根定理： 則則 A1 + A2 + Y = A1 ( A 2 + Y ) =

23、 A1 A2 Y (摩根定理摩根定理)= A1 A2 A3 Z (摩根定理摩根定理)用代入規(guī)則證明N變量的摩根定理，如下：這是反演律和代入規(guī)則的推廣使用，是對互補函數(shù)的完善說明。這是反演律和代入規(guī)則的推廣使用，是對互補函數(shù)的完善說明。已知原函數(shù)已知原函數(shù) f ( x1 , x2 , , xn, 0 , 1, +, ) 則反函數(shù)則反函數(shù) f ( x1 , x2 , , xn , 0 , 1, +, ) = f ( x1 , x2 , , xn , 1 , 0, , + ) 注意：注意：必須保持原有的運算次序（必要時加各種括號來標必須保持原有的運算次序（必要時加各種括號來標 識運算次序）。識運算次

24、序）。2. 反演規(guī)則反演規(guī)則(香農(nóng)定理香農(nóng)定理) Shannons expansion theorem例例： F = A B + (CD + E) G 則反函數(shù)則反函數(shù) F = A + B (C+D) E+ G 反函數(shù)同樣也可用反演律（摩根定律）來獲得。反函數(shù)同樣也可用反演律（摩根定律）來獲得。例例： F = A B + (CD + E) G = A + B (C+D) E+ G F = A B + (CD + E) G = A + B + (CD + E) G = A + B (CD + E) G = A + B (CD + E) + G = A + B CD E + G 又例：又例： F

25、= A (AC + B + CD) E + G ( C + AE) F = ? 已知原函數(shù)已知原函數(shù) f ( x1 , x2 , , xn, 0 , 1, +, )則對偶函數(shù)則對偶函數(shù) f ( x1 , x2 , , xn , 0 , 1, +, ) = f ( x1 , x2 , , xn , 1 , 0, , + ) 結(jié)論：結(jié)論：1. （f ) = f3. 對偶規(guī)則對偶規(guī)則 Dual expansion theorem借助于借助于對偶規(guī)則，對偶規(guī)則，可以減少記憶公式的數(shù)目可以減少記憶公式的數(shù)目(見公式見公式) 。2. 若若 f1 = f2 則則 f1 = f2 2.4 邏輯函數(shù)的性質(zhì)邏輯函

26、數(shù)的性質(zhì) 2.4.1 復(fù)合邏輯復(fù)合邏輯與與、或或、非非三種基本邏輯運算組合起來可以實現(xiàn)任何邏三種基本邏輯運算組合起來可以實現(xiàn)任何邏輯函數(shù)。輯函數(shù)。與門、或門、非門三種基本邏輯運算與門、或門、非門三種基本邏輯運算(門門)組合起來可以組合起來可以構(gòu)成實現(xiàn)任何邏輯功能的邏輯電路，稱此三門構(gòu)成了一構(gòu)成實現(xiàn)任何邏輯功能的邏輯電路，稱此三門構(gòu)成了一個個邏輯完備組邏輯完備組若實現(xiàn)一個較復(fù)雜的邏輯功能，尤其在大規(guī)模集成電路若實現(xiàn)一個較復(fù)雜的邏輯功能，尤其在大規(guī)模集成電路快速發(fā)展的今天，必須增加門電路的功能，以簡化電路。快速發(fā)展的今天，必須增加門電路的功能，以簡化電路。1. 與非邏輯與非邏輯(NAND) 邏輯表

27、達式為: F = A B CA B CF0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111111110&FA B CFB CA與非與非邏輯真值表 與非門與非門的邏輯符號可以用與非門實現(xiàn)三種基本運算： 與運算與運算 F1 = AB&AF3B& 或運算或運算 F3= AA BB = A B = A B&AF1B& 非運算非運算 F2 = AA = A&F2A2. 或非邏輯或非邏輯(NOR) 邏輯表達式為: F = A B CA B CF0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 110000000或非或非邏輯真值表 或非門或非門的

28、邏輯符號11FA B CFBCA可以用或非門實現(xiàn)三種基本運算： 或運算或運算 F2 = AB1F3A非運算非運算 F3 =AA = AAF1B111 與運算與運算 F1 = AA BB = AB = ABAF2B113. 與或非邏輯與或非邏輯(AOI) 邏輯表達式為: F = AB CD EF與或非與或非門的邏輯符號11FAB CD E F&FBCAFDE4. 異或邏輯異或邏輯(XOR) 邏輯表達式為: F = A B = A B A B異或異或邏輯真值表 異或異或門門的邏輯符號A BF0 00 11 01 101101 1FA BFBAFA B5. 同或邏輯同或邏輯 邏輯表達式為: F =

29、A B = A B A B同或同或邏輯真值表 同或同或門門的邏輯符號A BF0 00 11 01 110011 1FA BFBAFA B異或運算與同或運算的關(guān)系異或運算與同或運算的關(guān)系1. A B = A B A B = A B 2. (A B) = A B (A B) = A B 3. A B C = A B C例：證明例：證明 A B = A B A B = A B A B = ( A B )( A B) = A B A B = A B 證明證明 (A B) = (A B A B) = ( A B )( A B ) = A B A B = A B證明證明 A B C = A ( B C )

30、 A ( B C ) = A ( B C ) A ( B C ) = A ( B C BC ) A ( B C BC ) = A B C A B C A B C A B C 由上式可知，任意個變量的異或運算，只要輸入為由上式可知，任意個變量的異或運算，只要輸入為 1 的的個數(shù)是奇數(shù)時，輸出必為個數(shù)是奇數(shù)時，輸出必為1，即為，即為奇校驗邏輯奇校驗邏輯。證明證明 A B C = A ( B C ) A ( B C ) = A ( B C ) A ( B C ) = A ( B C BC ) A ( B C BC ) = A B C A B C A B C A B C 所以：當所以：當變量為變量為2

31、時，時，同或運算同或運算與與異或運算異或運算的之間具有的之間具有互補互補關(guān)系；關(guān)系； 當當變量為變量為3時，時，同或運算同或運算與與異或運算異或運算的之間具有的之間具有相等相等關(guān)系。關(guān)系。由代入規(guī)則可以證明：由代入規(guī)則可以證明：當當變量為偶數(shù)變量為偶數(shù)時，時，同或運算同或運算與與異或運算異或運算之間具有之間具有互補互補關(guān)系關(guān)系；當當變量為奇數(shù)變量為奇數(shù)時，時，同或運算同或運算與與異或運算異或運算之間具有之間具有相等關(guān)系相等關(guān)系。即：即：A1 A2 A3 An = A1 A2 A3 An n 為偶數(shù)為偶數(shù)A1 A2 A3 An = A1 A2 A3 An n 為奇數(shù)為奇數(shù)異或運算和同或運算的基本

32、代數(shù)性質(zhì)異或運算和同或運算的基本代數(shù)性質(zhì)01律律 (a) A 0 =A A 1 =A (b) A 0 =A A 1 =A交換律交換律 (a) A B =B A (b) A B =B A分配律分配律 (a) A(B C) =AB AC (b) A(B C) =(AB) (AC)結(jié)合律結(jié)合律 (a) A (B C) = (A B) C (b) A (B C) =(A B ) C調(diào)換律調(diào)換律 (a)若若 A B = C 則則 A C = B ， C B = A (b) 若若A B = C 則則 A C = B ， C B = A 依照邏輯運算的規(guī)則，一個邏輯命題可以用多種依照邏輯運算的規(guī)則，一個邏輯

33、命題可以用多種形式的邏輯函數(shù)來描述，而這些邏輯函數(shù)的真值表形式的邏輯函數(shù)來描述，而這些邏輯函數(shù)的真值表都是相同的。如：都是相同的。如： F = A B2.4.2 邏輯函數(shù)的基本表達式邏輯函數(shù)的基本表達式 Algebraic Forms of Switching Functions = A B AB 與非式與非式= ( AB ) ( AB ) 或非式或非式= A B A B 與或非式與或非式= = ( AB )( AB ) 或與式或與式 POS= A B A B 與或式與或式 SOPF2.4.3 邏輯函數(shù)的標準形式邏輯函數(shù)的標準形式 Canonical Forms of Switching Fu

34、nctions 一個邏輯命題的三種表示法：一個邏輯命題的三種表示法：真值表真值表 表達式表達式 卡諾圖卡諾圖三者之間的關(guān)系：三者之間的關(guān)系：真值表是邏輯函數(shù)最基本的表達方式，具有唯一性；真值表是邏輯函數(shù)最基本的表達方式，具有唯一性；由真值表可以導出邏輯表達式和卡諾圖；由真值表可以導出邏輯表達式和卡諾圖；由真值表導出邏輯表達式的兩種標準形式：由真值表導出邏輯表達式的兩種標準形式： 最小項之和最小項之和 The canonical SOP(the Sum Of Products) 最大項之積最大項之積 The canonical POS(Product Of Sums)1. 最小項最小項 mint

35、erm設(shè)有設(shè)有 n 個變量，它們組成的個變量，它們組成的與項與項中每個變量或以原變中每個變量或以原變量或以反變量形式出現(xiàn)一次，且僅出現(xiàn)一次，此與項稱之量或以反變量形式出現(xiàn)一次，且僅出現(xiàn)一次，此與項稱之為為 n 個變量的最小項。個變量的最小項。對于對于 n 個變量就可構(gòu)成個變量就可構(gòu)成 2n個最小項，個最小項，分別記為分別記為 mi 。其中其中下標值下標值 I為：當各個最小項變量按一定順序排好為：當各個最小項變量按一定順序排好后，用后，用 1 代替其中的原變量，代替其中的原變量， 0 代替其中的反變量，便得代替其中的反變量，便得一個一個二進制數(shù)二進制數(shù)，該二進制數(shù)的，該二進制數(shù)的等值十進制等值十

36、進制即為即為 i 的值。的值。 例如：例如： 3 變量的變量的 8 個最小項可以表示為：個最小項可以表示為：ABC = m0 ABC = m1 ABC = m2 ABC = m3ABC = m4 ABC = m5 ABC = m6 ABC = m7 為區(qū)別不同為區(qū)別不同 n 值的相同值的相同 mi ，可記為：，可記為： m i n2. 最大項最大項 maxterm設(shè)有設(shè)有 n 個邏輯變量，它們組成的個邏輯變量，它們組成的或項或項中，每個變量或中，每個變量或以原變量形式或以反變量形式出現(xiàn)一次，且僅出現(xiàn)一次，以原變量形式或以反變量形式出現(xiàn)一次，且僅出現(xiàn)一次，此或項稱為此或項稱為 n 變量的最大項。

37、變量的最大項。對于對于 n 個變量可以構(gòu)成個變量可以構(gòu)成2n個最大項，分別記為個最大項，分別記為 Mi 。其中其中下標值下標值 i的取值規(guī)則與最小項中的取值規(guī)則與最小項中 i的取值規(guī)則相反，的取值規(guī)則相反，即將各變量按一定次序排好后，用即將各變量按一定次序排好后，用 0 代替其中的原變量，代替其中的原變量，用用 1 代替其中的反變量，得到一個代替其中的反變量，得到一個二進制數(shù)二進制數(shù)，該二進制數(shù)，該二進制數(shù)的的等值十進制等值十進制即為即為 i 的值。的值。 例如，三變量的最大項記為：例如，三變量的最大項記為：ABC = M0 ABC = M1 ABC = M2 ABC = M3 ABC = M

38、4 ABC = M5ABC = M6 ABC = M7 為區(qū)別不同為區(qū)別不同 n 值的相同值的相同 Mi ，可記為：，可記為： M i n3. 最小項與最大項的性質(zhì)最小項與最大項的性質(zhì)例：一個三變量函數(shù)例：一個三變量函數(shù) F(A，B，C)，它的真值表及其，它的真值表及其最小項及最大項的對應(yīng)關(guān)系如下表。最小項及最大項的對應(yīng)關(guān)系如下表。行號行號A B CF(A，B，C) 最小項及代號最小項及代號 最大項及代號最大項及代號01234567000001010011100101110111F( 0,0,0)=1F( 0,0,1)=0F( 0,1,0)=0F( 0,1,1)=1F( 1,0,0)=1F(

39、1,0,1)=0F( 1,1,0)=1F( 1,1,1)=1A B C = m0A B C = m1A B C = m2A B C = m3A B C = m4A B C = m5A B C = m6A B C = m7A+B+C = M0A+B+C = M1A+B+C = M2A+B+C = M3A+B+C = M4A+B+C = M5A+B+C = M6A+B+C = M7最小項與最大項具有如下性質(zhì)：最小項與最大項具有如下性質(zhì)： 對于任意對于任意最小項最小項，只有一組只有一組變量組合取值可使其值變量組合取值可使其值為為1；對于任意對于任意最大項最大項，只有一組只有一組變量組合取值可使其值變

40、量組合取值可使其值為為0。(用用Venn圖示意出圖示意出m i 和和M i 的區(qū)域的區(qū)域) 任意兩個最小項之積必為任意兩個最小項之積必為0，即，即： mi mj = 0(ij) 任意兩個最大項之和必為任意兩個最大項之和必為1，即，即： MiMj=1(ij) n變量的所有最小項之和必為變量的所有最小項之和必為1，記為：，記為： n變量的所有最大項之積必為變量的所有最大項之積必為0，記為：，記為：m i = = 12n -1i = 0M i = = 02n -1i = 0由上表可知，最小項與最大項具有如下性質(zhì)由上表可知，最小項與最大項具有如下性質(zhì) 同變量數(shù)下標相同的最小項和最大項互為反函數(shù)同變量數(shù)

41、下標相同的最小項和最大項互為反函數(shù) 即：即： m i = M i M i = m i 則：則： m i M i = 0 且且 m iM i = 14. 函數(shù)的最小項標準式函數(shù)的最小項標準式邏輯函數(shù)被表達成一系列邏輯函數(shù)被表達成一系列乘積項之和乘積項之和，則稱之為，則稱之為積積之和之和表達式表達式(SOP)，或稱為，或稱為與或表達式與或表達式。如果構(gòu)成函數(shù)的積之和表達式中如果構(gòu)成函數(shù)的積之和表達式中每一個乘積項每一個乘積項(與項與項)均為最小項均為最小項時，則這種表達式稱之為時，則這種表達式稱之為最小項標準式最小項標準式(The canonical SOP)，且這種表示是且這種表示是唯一唯一的。

42、的。如如：F(A,B,C) = AC + AB + BC = ABC + ABC + ABC + ABC = m2 m3 m5 m7 = m3(2,3,5,7)寫出邏輯函數(shù)的最小項標準式的方法：寫出邏輯函數(shù)的最小項標準式的方法： 如果給定的函數(shù)為如果給定的函數(shù)為一般的與或表達式一般的與或表達式，可以反復(fù)應(yīng)用，可以反復(fù)應(yīng)用公式公式X=X(YY) 代入缺少某變量代入缺少某變量(Y)的與項中，形成最小項之的與項中，形成最小項之和的形式。和的形式。 例例： F = AC AB BC = AC( BB ) AB( CC ) ( AA )BC = ABCABCABCABCABCABC = ABCABCAB

43、CABC = m3(3,4,5,7) 如果給定函數(shù)用真值表表示，顯然如果給定函數(shù)用真值表表示，顯然真值表每一行真值表每一行變量的組變量的組合合對應(yīng)一個最小項對應(yīng)一個最小項。如果對應(yīng)該行的。如果對應(yīng)該行的函數(shù)值為函數(shù)值為 1 ，則函數(shù)，則函數(shù)的最小項表達式中的最小項表達式中應(yīng)包含應(yīng)包含該行對應(yīng)的最小項；如果該行的該行對應(yīng)的最小項；如果該行的函數(shù)值為函數(shù)值為 0，則函數(shù)的最小項表達式中，則函數(shù)的最小項表達式中不包含不包含對應(yīng)該行的對應(yīng)該行的最小項。最小項。例：對應(yīng)前表例：對應(yīng)前表(P40 表表2.6 )中的中的F(A,B,C)，其最小，其最小項表達式應(yīng)為：項表達式應(yīng)為： F(A,B,C) = m0

44、 m3 m4 m6 m7 = m3( 0,3,4,6,7 )顯然顯然 F(A,B,C) = m1 m2 m5 = m3( 1,2,5 ) 如果給定函數(shù)用卡諾圖表示，則如果給定函數(shù)用卡諾圖表示，則卡諾圖上的每一塊區(qū)域卡諾圖上的每一塊區(qū)域?qū)?yīng)應(yīng)一個最小項一個最小項。如果對應(yīng)該區(qū)域的函數(shù)值為。如果對應(yīng)該區(qū)域的函數(shù)值為 1 ，則函數(shù)的，則函數(shù)的最小項表達式中應(yīng)包含該區(qū)域?qū)?yīng)的最小項；如果該區(qū)域最小項表達式中應(yīng)包含該區(qū)域?qū)?yīng)的最小項；如果該區(qū)域的函數(shù)值為的函數(shù)值為 0，則函數(shù)的最小項表達式中不包含對應(yīng)該區(qū)，則函數(shù)的最小項表達式中不包含對應(yīng)該區(qū)域的最小項。域的最小項。例：參見例：參見2.5.2 “卡諾圖

45、法卡諾圖法”。最小項與原函數(shù)、反函數(shù)的關(guān)系最小項與原函數(shù)、反函數(shù)的關(guān)系 對于對于 n 個變量的函數(shù)個變量的函數(shù) F ，它共有，它共有2n個最小項，這些最小項個最小項，這些最小項不是包含在原函數(shù)不是包含在原函數(shù) F 的最小項表達式中，就是包含在反函數(shù)的最小項表達式中，就是包含在反函數(shù) F的最小項表達式中。的最小項表達式中。 用邏輯代數(shù)可以證明：用邏輯代數(shù)可以證明：F(x1,x2,x3, ,xn) F(x1,x2,x3, ,xn) =m i = = 12n -1i = 05. 函數(shù)的最大項標準式函數(shù)的最大項標準式 邏輯函數(shù)被表達成一系列邏輯函數(shù)被表達成一系列和項之積和項之積，則稱為，則稱為和之積表

46、達和之積表達式式(POS)，或稱為，或稱為或與表達式或與表達式。 如果構(gòu)成函數(shù)的或與表達式中的如果構(gòu)成函數(shù)的或與表達式中的每一個和項每一個和項均為均為最大項最大項，則這種表達式稱為則這種表達式稱為最大項標準式最大項標準式 ( The Canonical POS)，且這且這種表示是種表示是唯一唯一的。的。如如：F(A,B,C) = (A + C) (A + B) = (A+B+C) (A+B+C) (A+B+C) (A+B+C) = M0 M2 M4 M5 = M3( 0,2,4,5 )寫出邏輯函數(shù)的最大項標準式的方法：寫出邏輯函數(shù)的最大項標準式的方法： 如果給定的函數(shù)是如果給定的函數(shù)是一般的或

47、與表達式一般的或與表達式，可以反復(fù)應(yīng)，可以反復(fù)應(yīng) 用用公式：公式：X = X + YY = (X +Y)(X +Y) 代入缺少某變量代入缺少某變量(Y)的的和項中以形成最大項之積的形式。和項中以形成最大項之積的形式。例：例： F = (A + C) (A + B) = (A + C + B B) (A + B + C C) = (A+B+C) (A+B+C) (A+B+C) (A+B+C) = M0 M2 M4 M5 = M3( 0,2,4,5 )如果給定函數(shù)用真值表表示，顯然如果給定函數(shù)用真值表表示，顯然真值表每一行變量真值表每一行變量的組合的組合對應(yīng)對應(yīng)一個最大項一個最大項。如果對應(yīng)該行的

48、。如果對應(yīng)該行的函數(shù)值為函數(shù)值為 0 ，則函數(shù)的最，則函數(shù)的最大項表達式中大項表達式中應(yīng)包含應(yīng)包含該行對應(yīng)的最大項；如果該行的該行對應(yīng)的最大項；如果該行的函數(shù)值函數(shù)值為為 1 ，則函數(shù)的最大項表達式中，則函數(shù)的最大項表達式中不包含不包含對應(yīng)該行的最大項。對應(yīng)該行的最大項。例：對應(yīng)前表例：對應(yīng)前表(P40 表表2.6)中的中的F(A,B,C)，其最大項表達式，其最大項表達式應(yīng)為：應(yīng)為： F(A,B,C) = M1 M2 M5 = M3( 1,2,5 )顯然顯然 F(A,B,C) = M0 M3 M4 M6 M7 = M3( 0,3,4,6,7 ) 如果給定函數(shù)用卡諾圖表示，則函數(shù)的最大項表達式如

49、果給定函數(shù)用卡諾圖表示，則函數(shù)的最大項表達式可以通過卡諾圖得到。可以通過卡諾圖得到。例：參見例：參見2.5.2 “卡諾圖法卡諾圖法”。最大項與原函數(shù)、反函數(shù)的關(guān)系最大項與原函數(shù)、反函數(shù)的關(guān)系 對于對于 n 個變量的函數(shù)個變量的函數(shù) F ，它共有，它共有2n個最大項，個最大項，這些最大項不是包含在原函數(shù)這些最大項不是包含在原函數(shù) F 的最大項表達式的最大項表達式中，就是包含在反函數(shù)中，就是包含在反函數(shù) F 的最大項表達式中。的最大項表達式中。 可以證明：可以證明：F(x1,x2,x3, ,xn) F(x1,x2,x3, ,xn) =M i = = 02n -1i = 0同一函數(shù)的最小項標準式與其

50、最大項標準式的關(guān)系同一函數(shù)的最小項標準式與其最大項標準式的關(guān)系: 同一邏輯函數(shù)的一種標準式變換成另一種標準式同一邏輯函數(shù)的一種標準式變換成另一種標準式時，互換時，互換mn 和和Mn 的符號，并在符號后的符號，并在符號后列出列出原式原式中中缺少缺少的那些數(shù)字。且這兩種標準式都是的那些數(shù)字。且這兩種標準式都是唯一唯一的。的。例：例： F = m3( 0,2,3 ) = M 3( 1,4,5,6,7 )證明：證明： F = m3( 0,2,3 ) 則則 F = m3 ( 1,4,5,6,7 ) = m1 m4 m5 m6 m7 F = F = m1 m4 m5 m6 m7 = m1 m4 m5 m6

51、 m7 = M1 M4 M5 M6 M7 = M 3( 1,4,5,6,7 )2.5 邏輯函數(shù)的化簡邏輯函數(shù)的化簡 Simplification of Switching Expression 一個邏輯函數(shù)對應(yīng)著一個實現(xiàn)其邏輯功能的邏輯一個邏輯函數(shù)對應(yīng)著一個實現(xiàn)其邏輯功能的邏輯電路，當使該函數(shù)最簡意味著使這個電路也最簡。電路，當使該函數(shù)最簡意味著使這個電路也最簡。 最簡邏輯電路：最簡邏輯電路：門數(shù)最少；門的輸入端最少；門數(shù)最少；門的輸入端最少； 門的級數(shù)最少。門的級數(shù)最少。 最簡與或式：最簡與或式：與項的數(shù)目最少；每個與項的變量與項的數(shù)目最少；每個與項的變量 個數(shù)最少。個數(shù)最少。 最簡或與式：

52、最簡或與式：或項的數(shù)目最少；每個或項的變量或項的數(shù)目最少；每個或項的變量 個數(shù)最少。個數(shù)最少。例： F = AB ( BC ) AC BC = AB C對應(yīng)兩種邏輯電路圖，如下11111ABCCABABB+CACB CAB(B+C)F=AB(B+C)+AC+BC&1ABABF=AB+C&C2.5.1 代數(shù)化簡法：代數(shù)化簡法： 要求要求熟記熟記化簡化簡公式公式、定理定理； 技巧性強技巧性強，可謂熟能生巧。特別是采用，可謂熟能生巧。特別是采用“配項配項法法”，要先找出，要先找出“配項配項” ，使表達式，使表達式 “由簡變由簡變繁繁”，再消除多余項，以達到化簡。，再消除多余項，以達到化簡。 代數(shù)化簡

53、的代數(shù)化簡的過程和結(jié)果呈多樣性過程和結(jié)果呈多樣性，且不易發(fā)現(xiàn)出，且不易發(fā)現(xiàn)出錯，也不易判斷是否最簡。錯，也不易判斷是否最簡。 上述問題在用上述問題在用卡諾圖法化簡卡諾圖法化簡時，均可得到較好的時，均可得到較好的解決解決。一、與或式的化簡一、與或式的化簡與或式化簡常用的公式主要有四個：與或式化簡常用的公式主要有四個： A + A = 1 A + AB = A + BAB + AB = A AB + AC + BC = AB + AC 所謂化簡過程就是運用代入規(guī)則，把某一子函所謂化簡過程就是運用代入規(guī)則，把某一子函數(shù)看成一個變量，進而應(yīng)用公式簡化，在這一過程數(shù)看成一個變量，進而應(yīng)用公式簡化，在這一

54、過程中經(jīng)常需要變換子函數(shù)的形式，以便能夠應(yīng)用公式中經(jīng)常需要變換子函數(shù)的形式，以便能夠應(yīng)用公式進行簡化，最終將函數(shù)化簡為進行簡化，最終將函數(shù)化簡為最簡與或式最簡與或式 (minimizing SOP) ，常用的方法有如下幾種：，常用的方法有如下幾種：1. 吸收法吸收法 利用公式：利用公式：A+AB=A 消去多余變量消去多余變量。例：。例： F AB+AB (C+D) E AB 利用公式：利用公式： A + AB = A + B 消去反變量消去反變量。例：。例： F = AB + AC + BC = AB + (A + B)C = AB + AB C = AB + C 3. 消去法消去法利用公式：

55、利用公式：ABACBCAB AC 消去多余項消去多余項。 例：例：F = AC + ADE + CD = AC + CD + AD + ADE = AC + CD 2. 合并項法合并項法 利用公式：利用公式： AB + AB = A ，兩項，兩項合并合并為一項且為一項且消去消去一個變量一個變量。例：。例： F = m4 (5,7,13,15) = ABCD + ABCD + ABCD + ABCD = ABD + ABD = BD 4. 配項法配項法 當無法發(fā)現(xiàn)直接應(yīng)用公式時，可先增加一些與當無法發(fā)現(xiàn)直接應(yīng)用公式時，可先增加一些與項，再利用增加項消除多余項，即項，再利用增加項消除多余項，即“先

56、繁后簡先繁后簡”。利用公式：利用公式：1 A A 增加項數(shù)增加項數(shù)。例：。例： F = AB + BC + BC + AB = AB + BC + BC(A+A) + AB(C+C) = AB + BC + ABC + ABC + ABC + ABC = AB + BC + AC解法解法2： F = AB + BC + BC + AB = AB(C+C) + BC (A+A) + BC + AB = ABC + AB C + ABC + ABC + BC + AB = AC + BC + AB利用公式利用公式： ABAC = ABACBC 增加項數(shù)增加項數(shù)。例：例： F = AB + BC +

57、 BC + AB = AB + BC + BC + AB + AC = AB + BC + AC解法解法2： F = AB + BC + BC + AB = AB + BC + AC + BC + AB = AB + BC + AC5. 綜合法綜合法 在一個函數(shù)的化簡中同時用幾種方法。例：在一個函數(shù)的化簡中同時用幾種方法。例： F = AB + AC + BC + CB + BD + DB + ADE ( F + G ) = A(B + C) + BC + CB + BD + DB + ADE ( F + G ) = ABC + BC + CB + BD + DB + ADE ( F + G

58、) = A + BC + CB + BD + DB + ADE ( F + G ) = A + BC + CB + BD + DB = A + BC + CB + BD + DB + CD = A + BC + CB + DB + CD = A + BC + DB + CD二、或與式的化簡二、或與式的化簡 或與式化簡有兩種方法：或與式化簡有兩種方法： 1. 常規(guī)法常規(guī)法 常規(guī)法化簡方式類似于與或式的化簡，化簡中常常規(guī)法化簡方式類似于與或式的化簡，化簡中常用的公式主要有：用的公式主要有： ( A + B )( A + B ) = A A ( A + B ) = A A ( A + B ) = A

59、B ( A + B )( A + C )( B + C ) = ( A + B )( A + C )例：例：F = A ( A + B )( A + D )( B + D )( A + C + E + H ) = A ( A + D )( B + D ) = AD ( B + D ) = AD2. 利用最簡與或式得到最簡或與式利用最簡與或式得到最簡或與式 二次對偶法二次對偶法 利用對偶規(guī)則，先求出利用對偶規(guī)則，先求出F的對偶式的對偶式F，再將對偶式，再將對偶式F 化簡為化簡為最簡與或式最簡與或式，最后再求一次對偶，最后再求一次對偶(F ) = F，則得到則得到 F 最簡或與式。最簡或與式。例：

60、例：F = (A + B)(A + B)(B + C)(C + D)(B + D) F = AB + AB + BC + CD + BD = A + BC + CD + BD = A + BC + CD則則 F = (F ) = A (B + C)(C + D)2二次求反法二次求反法 利用反演規(guī)則，先求出利用反演規(guī)則，先求出F的反函數(shù)的反函數(shù) F，再將反函數(shù)，再將反函數(shù) F 化簡為化簡為最簡與或式最簡與或式，最后再求一次反，最后再求一次反 F = F，則得到，則得到 F 最簡或與式。最簡或與式。例：例：F = AB + AB + AC + BD F = (A + B)(A + B)(A + C