1、邏輯代數(shù)基礎(chǔ)邏輯代數(shù)基礎(chǔ)山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系邏輯代數(shù)是數(shù)子系統(tǒng)邏輯設(shè)計(jì)的理論基礎(chǔ)和重要邏輯代數(shù)是數(shù)子系統(tǒng)邏輯設(shè)計(jì)的理論基礎(chǔ)和重要數(shù)學(xué)數(shù)學(xué)工具工具！ 18471847年年,英國數(shù)學(xué)家喬治布爾(G.Boole)提出了用數(shù)學(xué)分析方法表示命題陳述的邏輯結(jié)構(gòu)，并將形式邏輯歸結(jié)為一種代數(shù)演算，從而誕生了著名的“布爾代數(shù)布爾代數(shù)”。19381938年年，克勞德向農(nóng)(C.E.Shannon)將布爾代數(shù)應(yīng)用于電話繼電器的開關(guān)電路，提出了“開關(guān)代數(shù)開關(guān)代數(shù)”。隨著電子技術(shù)的發(fā)展，集成電路邏輯門已經(jīng)取代了機(jī)械觸點(diǎn)開關(guān)，故人們更習(xí)慣于把開關(guān)代數(shù)叫做邏輯代數(shù)邏輯代數(shù)。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系本章內(nèi)容本章內(nèi)容

2、邏輯代數(shù)的基本概念邏輯代數(shù)的基本概念1邏輯代數(shù)的公理、定理及規(guī)則邏輯代數(shù)的公理、定理及規(guī)則2邏輯函數(shù)表達(dá)式的形式與轉(zhuǎn)換邏輯函數(shù)表達(dá)式的形式與轉(zhuǎn)換3邏輯函數(shù)的化簡邏輯函數(shù)的化簡4山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系邏輯代數(shù)和普通代數(shù)一樣，是用字母表示其值可以變化邏輯代數(shù)和普通代數(shù)一樣，是用字母表示其值可以變化的量，即變量。所不同的是：的量，即變量。所不同的是：1任何邏輯變量的取值只有兩種可能性任何邏輯變量的取值只有兩種可能性取值取值0 0或或取值取值1 1。2邏輯值邏輯值0 0和和1 1是用來表征矛盾的雙方和判斷事件真?zhèn)问怯脕肀碚髅艿碾p方和判斷事件真?zhèn)蔚男问椒枺瑹o大小、正負(fù)之分。的形式符號，無大小、

3、正負(fù)之分。2.1.12.1.1邏輯變量邏輯變量 2.1 2.1 邏輯代數(shù)的基本概念邏輯代數(shù)的基本概念山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系描述一個(gè)數(shù)字系統(tǒng)，必須反映一個(gè)復(fù)雜系統(tǒng)中各開關(guān)元描述一個(gè)數(shù)字系統(tǒng)，必須反映一個(gè)復(fù)雜系統(tǒng)中各開關(guān)元件之間的聯(lián)系，這種相互聯(lián)系反映到數(shù)學(xué)上就是幾種運(yùn)算關(guān)件之間的聯(lián)系，這種相互聯(lián)系反映到數(shù)學(xué)上就是幾種運(yùn)算關(guān)系。系。邏輯代數(shù)中定義了邏輯代數(shù)中定義了“或或”、“與與” 、“非非”三種基本運(yùn)算。三種基本運(yùn)算。 1 1“或或”運(yùn)算運(yùn)算 如果決定某一事件是否發(fā)生的多個(gè)條件中，只要有一如果決定某一事件是否發(fā)生的多個(gè)條件中，只要有一個(gè)或一個(gè)以上條件成立，事件便可發(fā)生，則這種因果關(guān)系個(gè)或一

4、個(gè)以上條件成立，事件便可發(fā)生，則這種因果關(guān)系稱之為稱之為“或或”邏輯。邏輯。 例如，用兩個(gè)開關(guān)并聯(lián)控制一個(gè)燈的照明控制電路。例如，用兩個(gè)開關(guān)并聯(lián)控制一個(gè)燈的照明控制電路。2.1.2 2.1.2 邏輯運(yùn)算邏輯運(yùn)算山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系 電路中，開關(guān)電路中，開關(guān)A和和B并聯(lián)控制燈并聯(lián)控制燈F。可以看出，當(dāng)開關(guān)。可以看出，當(dāng)開關(guān)A、B中有一個(gè)閉合或者兩個(gè)均閉合時(shí)，燈中有一個(gè)閉合或者兩個(gè)均閉合時(shí)，燈F即亮。因此，燈即亮。因此，燈F與與開關(guān)開關(guān)A、B之間的關(guān)系是之間的關(guān)系是“或或”邏輯關(guān)系。可表示為邏輯關(guān)系。可表示為 并聯(lián)開關(guān)電路并聯(lián)開關(guān)電路 ABF如圖如圖所示所示電路電路：F = A + B或者

5、或者F = A B，讀作讀作“F F等于等于A A或或B B”。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系 假定開關(guān)斷開用假定開關(guān)斷開用0表示，開關(guān)閉合用表示，開關(guān)閉合用1表示；燈滅用表示；燈滅用0表示，燈亮用表示，燈亮用1表示，則燈表示，則燈F與開關(guān)與開關(guān)A、B的關(guān)系如下表所示。的關(guān)系如下表所示。 即：A、B中只要有一個(gè)為中只要有一個(gè)為1，則，則F為為1；僅當(dāng)；僅當(dāng)A、B均為均為0時(shí)，時(shí)，F(xiàn)才為才為0。A0111100BF01011“或或”運(yùn)算表運(yùn)算表 F 并聯(lián)開關(guān)電路并聯(lián)開關(guān)電路 AB“或或”運(yùn)算的運(yùn)算法則：運(yùn)算的運(yùn)算法則：0 + 0 = 01 + 0 = 10 + 1 = 11 + 1 = 1實(shí)現(xiàn)“或

6、”運(yùn)算關(guān)系的邏輯電路稱為“或或”門門。 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系 2 2“與與” 運(yùn)算運(yùn)算如果決定某一事件發(fā)生的多個(gè)條件必須同時(shí)具備，事如果決定某一事件發(fā)生的多個(gè)條件必須同時(shí)具備，事件才能發(fā)生，則這種因果關(guān)系稱之為件才能發(fā)生，則這種因果關(guān)系稱之為“與與”邏輯。邏輯。在邏輯代數(shù)中，在邏輯代數(shù)中，“與與”邏輯關(guān)系用邏輯關(guān)系用“與與”運(yùn)算描述。運(yùn)算描述。兩變量兩變量“與與”運(yùn)算關(guān)系可表示為運(yùn)算關(guān)系可表示為F = AB或者F = AB即：即：若若A A、B B均為均為1 1，則，則F F為為1 1；否則，；否則，F(xiàn) F為為0 0。 A0110000BF01011 “與與”運(yùn)算表運(yùn)算表 山東農(nóng)業(yè)大學(xué)

7、信息學(xué)院計(jì)算機(jī)系A(chǔ)BF 串聯(lián)開關(guān)電路串聯(lián)開關(guān)電路 例如，兩個(gè)開關(guān)串聯(lián)控制同一個(gè)燈。顯然，僅當(dāng)兩個(gè)開關(guān)例如，兩個(gè)開關(guān)串聯(lián)控制同一個(gè)燈。顯然，僅當(dāng)兩個(gè)開關(guān)均閉合時(shí)，燈才能亮，否則，燈滅。均閉合時(shí)，燈才能亮，否則，燈滅。假定開關(guān)閉合狀態(tài)用假定開關(guān)閉合狀態(tài)用1表示，斷開狀態(tài)用表示，斷開狀態(tài)用0表示，燈亮用表示，燈亮用1表示，燈滅用表示，燈滅用0表示，則表示，則F和和A、B之間的關(guān)系之間的關(guān)系 “與與”運(yùn)算關(guān)系運(yùn)算關(guān)系。 數(shù)字系統(tǒng)中，實(shí)現(xiàn)數(shù)字系統(tǒng)中，實(shí)現(xiàn)“與與”運(yùn)算關(guān)系的邏輯電路稱為運(yùn)算關(guān)系的邏輯電路稱為“與與”門門。 “與與”運(yùn)算的運(yùn)算法則運(yùn)算的運(yùn)算法則:0 0 = 01 0 = 00 1 = 01

8、1 = 1山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系 3 3“非非” 運(yùn)算運(yùn)算 如果某一事件的發(fā)生取決于條件的否定，即事件與事件如果某一事件的發(fā)生取決于條件的否定，即事件與事件發(fā)生的條件之間構(gòu)成矛盾，則這種因果關(guān)系稱為發(fā)生的條件之間構(gòu)成矛盾，則這種因果關(guān)系稱為“非非”邏輯。邏輯。在邏輯代數(shù)中，在邏輯代數(shù)中，“非非”邏輯用邏輯用“非非”運(yùn)算描述。其運(yùn)算運(yùn)算描述。其運(yùn)算符號符號為為“”，有時(shí)也用，有時(shí)也用“”表示。表示。“非非”運(yùn)算的邏輯關(guān)系運(yùn)算的邏輯關(guān)系可表示為可表示為F = 或者或者 F = A讀作讀作“F等于等于A非非”。即：若若A為為0，則，則F為為1；若；若A為為1，則，則F為為0。A“非非”運(yùn)算表運(yùn)

9、算表 AF0101山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系A(chǔ)開關(guān)與燈并聯(lián)電路 F例如，下面開關(guān)與燈并聯(lián)的電路中，僅當(dāng)開關(guān)斷開時(shí)，燈例如，下面開關(guān)與燈并聯(lián)的電路中，僅當(dāng)開關(guān)斷開時(shí)，燈亮；一旦開關(guān)閉合，則燈滅。亮；一旦開關(guān)閉合，則燈滅。令開關(guān)斷開用令開關(guān)斷開用0表示，開關(guān)閉合表示，開關(guān)閉合用用1表示，燈亮用表示，燈亮用1表示，燈滅用表示，燈滅用0表示，則電路中燈表示，則電路中燈F與開關(guān)與開關(guān)A的關(guān)系即為上表所示的關(guān)系即為上表所示“非非”運(yùn)算關(guān)系。運(yùn)算關(guān)系。 “非非”運(yùn)算的運(yùn)算法則：運(yùn)算的運(yùn)算法則：；數(shù)字系統(tǒng)中實(shí)現(xiàn)“非”運(yùn)算功能的邏輯電路稱為“非非”門門，有時(shí)又稱為“反相器反相器”。10 01山東農(nóng)業(yè)大學(xué)信息學(xué)

10、院計(jì)算機(jī)系邏輯代數(shù)中函數(shù)的定義與普通代數(shù)中函數(shù)的定義類似，即即隨自變量變化的因變量隨自變量變化的因變量。但和普通代數(shù)中函數(shù)的概念相比，邏輯函數(shù)具有如下特點(diǎn)特點(diǎn)： 1邏輯函數(shù)和邏輯變量一樣，取值只有邏輯函數(shù)和邏輯變量一樣，取值只有0和和1兩種可兩種可能能 ； 2函數(shù)和變量之間的關(guān)系是由函數(shù)和變量之間的關(guān)系是由“或或”、“與與”、“非非”三種基本運(yùn)算決定的三種基本運(yùn)算決定的 。 2.1.3 2.1.3 邏輯函數(shù)邏輯函數(shù)山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系圖中，圖中，F(xiàn)被稱為被稱為A1，A2，An的邏輯函數(shù)，記為的邏輯函數(shù)，記為F = f( A1，A2，An )邏輯電路輸出函數(shù)的取值是由邏輯變量的取值和電路

11、本邏輯電路輸出函數(shù)的取值是由邏輯變量的取值和電路本身的結(jié)構(gòu)決定的身的結(jié)構(gòu)決定的。 廣義的邏輯電路邏輯電路邏輯電路 FA1A2An設(shè)某一邏輯電路的輸入邏輯變量為設(shè)某一邏輯電路的輸入邏輯變量為A1，A2，An，輸，輸出邏輯變量為出邏輯變量為F，如下圖所示。，如下圖所示。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系 邏輯函數(shù)和普通代數(shù)中的函數(shù)一樣存在是否邏輯函數(shù)和普通代數(shù)中的函數(shù)一樣存在是否相等相等的問題。的問題。設(shè)有兩個(gè)相同變量的邏輯函數(shù)設(shè)有兩個(gè)相同變量的邏輯函數(shù)F1 = f1( A 1,A 2, ,A n)F2 = f2( A 1,A 2, ,A n)若對應(yīng)于邏輯變量若對應(yīng)于邏輯變量 A1 ,A2 , , An

12、的任何一組取值，的任何一組取值，F(xiàn)1和和F2的值都相同，則稱函數(shù)的值都相同，則稱函數(shù)F1和和F2相等，記作相等，記作F1 = F2 。如何判斷兩個(gè)邏輯函數(shù)是否相等？如何判斷兩個(gè)邏輯函數(shù)是否相等？通常有兩種方法：真值表法真值表法，代數(shù)法代數(shù)法。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系 邏輯代數(shù)L是一個(gè)封閉的代數(shù)系統(tǒng)，它由一個(gè)邏輯變量集K，常量0和1以及“或”、“與”、“非”三種基本運(yùn)算所構(gòu)成，記為L=K,+,L=K,+,-,0,1,-,0,1。該系統(tǒng)應(yīng)滿足下列公理。 2.2 2.2 邏輯邏輯代數(shù)的公理、定理及規(guī)則代數(shù)的公理、定理及規(guī)則公公 理理 1 1 交交 換換 律律對于任意邏輯變量對于任意邏輯變量A、B

13、，有，有A + B = B + A；AB = B A公公 理理 2 2 結(jié)結(jié) 合合 律律對于任意的對于任意的邏輯變量邏輯變量A、B、C，有，有(A + B) + C = A + ( B + C )(A + B) + C = A + ( B + C )( A( AB )B ) C = A C = A( B( B C ) C )2.2.1 2.2.1 邏輯代數(shù)的公理和基本定理邏輯代數(shù)的公理和基本定理公公 理理 3 3 分分 配配 律律對于任意的邏輯變量對于任意的邏輯變量A、B、C，有，有A + ( BC ) = (A + B)(A + C) ；A( B + C) = AB + AC公公 理理 4

14、01 4 01 律律對于任意邏輯變量對于任意邏輯變量A，有，有 A + 0 = A A + 0 = A ； A A 1 = A 1 = A A + 1 = 1 A + 1 = 1 ； A A 0 = 0 0 = 0 公理是一個(gè)代數(shù)系統(tǒng)的基本出發(fā)點(diǎn)，無需加以證明。公理是一個(gè)代數(shù)系統(tǒng)的基本出發(fā)點(diǎn)，無需加以證明。A0AA 1AA公公 理理 5 5 互互 補(bǔ)補(bǔ) 律律對于任意邏輯變量對于任意邏輯變量A，存在唯一的，使得，存在唯一的，使得山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系常用的組定理：常用的組定理：基本基本定理定理 定理定理10 + 0 = 01 + 0 = 10 0 = 01 0 = 00 + 1 = 11

15、+ 1 = 10 1 = 01 1 = 1證明：在公理證明：在公理4中，中，A表示集合表示集合K中的任意元素，因而可中的任意元素，因而可以是以是0或或1。用。用0和和1代入公理代入公理4中的中的A，即可得到上述關(guān)系。，即可得到上述關(guān)系。 如果以如果以1和和0代替公理代替公理5中的中的A，則可得到如下推論：，則可得到如下推論： 0110 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系證明證明A+A = (A+A)1公理4 = (A+A)(A+A)公理5 = A+(AA)公理3 = A+0公理5 =A公理4定理定理2A + A = A ；A A = A 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系證明證明A+AB = A1+AB

16、公理4 = A (1+B)公理3 = A (B+1) 公理1 = A1公理4 = A公理4定理定理3A + A B = A；A ( A + B ) = A山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系定理定理4 A+AB = A+B ;A(A+B) = AB證明證明A+AB = (A+A) (A+B)公理3 = 1(A+B)公理5 = A+B公理4證明證明令A(yù)=X因而 XA = 0 X+A = 1公理5但是 AA = 0 A+A = 1公理5由于X和A都滿足公理5，根據(jù)公理5的唯一性，得到：A=X由于A=X，所以A=A定理定理5 = A A山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系定理定理7AB + A B = A ( A

17、+ B ) ( A+B ) = A 1 1、代入、代入規(guī)則規(guī)則 在一個(gè)邏輯等式兩邊出現(xiàn)某個(gè)變量（或表示式）的所有位置在一個(gè)邏輯等式兩邊出現(xiàn)某個(gè)變量（或表示式）的所有位置都代入另一個(gè)變量（或表達(dá)式），則等式仍然成立。都代入另一個(gè)變量（或表達(dá)式），則等式仍然成立。 例例: :在在A A（B+CB+C）=AB+AC=AB+AC中，用中，用BCDBCD代入原式所有出現(xiàn)代入原式所有出現(xiàn)A A，則等，則等 式仍成立。式仍成立。 左邊左邊=BCD=BCD（B+CB+C）=BCDB+BCDC=BCD+BCD=BCD=BCDB+BCDC=BCD+BCD=BCD 右邊右邊=BCDB+BCDC=BCD+BCD=BC

18、D=BCDB+BCDC=BCD+BCD=BCD 左邊左邊= =右邊，等式成立。右邊，等式成立。 同理，用同理，用CDCD代替等式的代替等式的B B變量，得到的等式仍是成立。變量，得到的等式仍是成立。2.2.22.2.2邏輯代數(shù)的重要規(guī)則邏輯代數(shù)的重要規(guī)則2 2、反演規(guī)則反演規(guī)則 對一個(gè)邏輯函數(shù)對一個(gè)邏輯函數(shù)F F進(jìn)行如下變換進(jìn)行如下變換: :將所有的將所有的“”換成換成“”，“”換成換成“”，“0 0”換成換成“1 1”，“1 1”換成換成“0 0”，原變量原變量換成換成反變量反變量，反變量反變量換成換成原變量原變量，并保持原來的運(yùn)算次序不變，則，并保持原來的運(yùn)算次序不變，則得到函數(shù)得到函數(shù)F

19、 F的反函數(shù)。的反函數(shù)。 使用反演規(guī)則時(shí)，要注意以下兩點(diǎn)使用反演規(guī)則時(shí)，要注意以下兩點(diǎn): :保持原函數(shù)中邏輯運(yùn)算保持原函數(shù)中邏輯運(yùn)算的優(yōu)先順序；不是單個(gè)變量上的反號應(yīng)保持不變。的優(yōu)先順序；不是單個(gè)變量上的反號應(yīng)保持不變。例例: :則：則： ZA BA CDZ(AB) AC D3 3、對偶規(guī)則對偶規(guī)則 對一個(gè)邏輯函數(shù)對一個(gè)邏輯函數(shù)F F進(jìn)行如下變換進(jìn)行如下變換: :將所有的將所有的“”換成換成“”，“”換成換成“”，“0 0”換成換成“1 1”，“1 1”換成換成“0 0”，則得到函數(shù)，則得到函數(shù)F F的的對偶函數(shù)對偶函數(shù)FF。 例例: F: F1 1=A(B+C) F=A(B+C) F1 1=

20、A+BC=A+BC F F2 2=AB+AC F=AB+AC F2 2=(A+B)(A+C)=(A+B)(A+C) 如果兩個(gè)函數(shù)相等，則它們的對偶函數(shù)亦相等。這就是對如果兩個(gè)函數(shù)相等，則它們的對偶函數(shù)亦相等。這就是對偶規(guī)則偶規(guī)則。 例例: : 已知已知 A(B+C)=A(B+C)=AB+ACAB+AC 則則:A+BC:A+BC=(A+B)(A+C)=(A+B)(A+C)山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系2.3 2.3 邏輯函數(shù)表達(dá)式的形式與變換邏輯函數(shù)表達(dá)式的形式與變換任何一個(gè)邏輯函數(shù)，其表達(dá)式的形式都不是唯一的。下面介紹邏輯函數(shù)表達(dá)式的基本形式、標(biāo)準(zhǔn)形式及其相互轉(zhuǎn)基本形式、標(biāo)準(zhǔn)形式及其相互轉(zhuǎn)換。換

21、。 2.3.1 2.3.1 邏輯函數(shù)表達(dá)式的邏輯函數(shù)表達(dá)式的兩種兩種基本形式基本形式 兩種基本形式：指兩種基本形式：指“與與- -或或”表達(dá)式和表達(dá)式和“或或- -與與”表達(dá)式表達(dá)式。 1 1、“與與- -或或”表達(dá)式表達(dá)式 “與與-或或”表達(dá)式：是指由若干表達(dá)式：是指由若干“與項(xiàng)與項(xiàng)”進(jìn)行進(jìn)行“或或”運(yùn)算構(gòu)成運(yùn)算構(gòu)成的表達(dá)式。例如，的表達(dá)式。例如，CCBABAF“與項(xiàng)與項(xiàng)”有時(shí)又被稱為有時(shí)又被稱為“積項(xiàng)積項(xiàng)”，相應(yīng)地，相應(yīng)地“與與或或” 表達(dá)式表達(dá)式又稱為又稱為“積之和積之和”表達(dá)式。表達(dá)式。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系2 2、“或或- -與與”表達(dá)式表達(dá)式 “或項(xiàng)或項(xiàng)”有時(shí)又被稱為有時(shí)又被

22、稱為“和項(xiàng)和項(xiàng)”，相應(yīng)地，相應(yīng)地“或或與與”表達(dá)式又稱為表達(dá)式又稱為“和之積和之積”表達(dá)式。表達(dá)式。 C)DB)(ACB)(BA(D)C,B,F(A,“或或- -與與”表達(dá)式：是指由若干表達(dá)式：是指由若干“或項(xiàng)或項(xiàng)”進(jìn)行進(jìn)行“與與”運(yùn)算構(gòu)成的運(yùn)算構(gòu)成的表達(dá)式。例如，表達(dá)式。例如，該函數(shù)既不是該函數(shù)既不是“與與或或”式？也不是式？也不是“或或與與”式！式！B)CBC)(AB(AC)B,F(A,邏輯函數(shù)的基本邏輯函數(shù)的基本形式可以相互轉(zhuǎn)換形式可以相互轉(zhuǎn)換山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系2.3.2 2.3.2 邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式 為了在邏輯問題的研究中使邏輯功能能和唯一的邏

23、輯為了在邏輯問題的研究中使邏輯功能能和唯一的邏輯表達(dá)式對應(yīng)，引入了邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式。邏輯函表達(dá)式對應(yīng)，引入了邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式。邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式是建立在最小項(xiàng)和最大項(xiàng)概念的基礎(chǔ)數(shù)表達(dá)式的標(biāo)準(zhǔn)形式是建立在最小項(xiàng)和最大項(xiàng)概念的基礎(chǔ)之上的。之上的。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系（1）定義：）定義：如果一個(gè)具有如果一個(gè)具有n個(gè)變量的函數(shù)的個(gè)變量的函數(shù)的“與項(xiàng)與項(xiàng)”包含包含全部全部n個(gè)變量，每個(gè)變量都以原變量或反變量形式出現(xiàn)一次，個(gè)變量，每個(gè)變量都以原變量或反變量形式出現(xiàn)一次，且僅出現(xiàn)一次，則該且僅出現(xiàn)一次，則該“與項(xiàng)與項(xiàng)”被稱為被稱為最小項(xiàng)最小項(xiàng)。有時(shí)又將最小項(xiàng)有時(shí)又將最小項(xiàng)稱為稱

24、為標(biāo)準(zhǔn)標(biāo)準(zhǔn)“與項(xiàng)與項(xiàng)”。 1最小項(xiàng)最小項(xiàng)（3）簡寫：）簡寫：用用mi表示最小項(xiàng)。表示最小項(xiàng)。下標(biāo)下標(biāo)i的取值規(guī)則是：的取值規(guī)則是：按照變量順序?qū)⒆钚№?xiàng)中的原變按照變量順序?qū)⒆钚№?xiàng)中的原變量用量用1表示，反變量用表示，反變量用0表示，由此得到一個(gè)二進(jìn)制數(shù)，與表示，由此得到一個(gè)二進(jìn)制數(shù)，與該二進(jìn)制數(shù)對應(yīng)的十進(jìn)制數(shù)即下標(biāo)該二進(jìn)制數(shù)對應(yīng)的十進(jìn)制數(shù)即下標(biāo)i的值。的值。 （2）最小項(xiàng)的數(shù)目：）最小項(xiàng)的數(shù)目：n個(gè)變量可以構(gòu)成個(gè)變量可以構(gòu)成2n個(gè)最小項(xiàng)。個(gè)最小項(xiàng)。 例如，例如，3個(gè)變量個(gè)變量A、B、C可以構(gòu)成可以構(gòu)成、 A B C共共8個(gè)最小項(xiàng)。個(gè)最小項(xiàng)。 CBACBA山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系在由在由n個(gè)

25、變量構(gòu)成的任意個(gè)變量構(gòu)成的任意“與項(xiàng)與項(xiàng)”中，最小項(xiàng)是使其值為中，最小項(xiàng)是使其值為1的變的變量取值組合數(shù)最少的一種量取值組合數(shù)最少的一種“與項(xiàng)與項(xiàng)”，這也就是最小項(xiàng)名字的由來。，這也就是最小項(xiàng)名字的由來。 （4） 性質(zhì)性質(zhì) 最小項(xiàng)具有最小項(xiàng)具有如下性質(zhì)如下性質(zhì)。 性質(zhì)性質(zhì)1： 任意一個(gè)最小項(xiàng)，其相應(yīng)變量有且僅有一種取任意一個(gè)最小項(xiàng)，其相應(yīng)變量有且僅有一種取值使這個(gè)最小項(xiàng)的值為值使這個(gè)最小項(xiàng)的值為1。并且，最小項(xiàng)不同，使其值為。并且，最小項(xiàng)不同，使其值為1的的變量取值不同。變量取值不同。 例如，例如，3變量變量A、B、C構(gòu)成的最小項(xiàng)構(gòu)成的最小項(xiàng) A C 可用可用 m5 表示。表示。因?yàn)橐驗(yàn)?m5

26、 (5)10 101ACBB山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系性質(zhì)性質(zhì)3： n個(gè)變量的全部最小項(xiàng)相個(gè)變量的全部最小項(xiàng)相“或或”為為1。通常借用數(shù)學(xué)中的累加符號通常借用數(shù)學(xué)中的累加符號“”，將其記為，將其記為1n20i1mi性質(zhì)性質(zhì)2： 相同變量構(gòu)成的兩個(gè)不同最小項(xiàng)相相同變量構(gòu)成的兩個(gè)不同最小項(xiàng)相“與與” 為為0。因?yàn)槿魏我环N變量取值都不可能使兩個(gè)不同最小項(xiàng)同時(shí)因?yàn)槿魏我环N變量取值都不可能使兩個(gè)不同最小項(xiàng)同時(shí)為為1，故相，故相“與與”為為0。即即mi mj = 0 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系定義定義：如果一個(gè)具有如果一個(gè)具有n個(gè)變量函數(shù)的個(gè)變量函數(shù)的“或項(xiàng)或項(xiàng)”包含全部包含全部n個(gè)變量，每個(gè)變量都以

27、原變量或反變量形式出現(xiàn)一次，且個(gè)變量，每個(gè)變量都以原變量或反變量形式出現(xiàn)一次，且僅出現(xiàn)一次，則該僅出現(xiàn)一次，則該“或項(xiàng)或項(xiàng)”被稱為最大項(xiàng)。有時(shí)又將最大被稱為最大項(xiàng)。有時(shí)又將最大項(xiàng)稱為標(biāo)準(zhǔn)項(xiàng)稱為標(biāo)準(zhǔn)“或項(xiàng)或項(xiàng)”。 2 2最大項(xiàng)最大項(xiàng)數(shù)目：數(shù)目：n個(gè)變量可以構(gòu)成個(gè)變量可以構(gòu)成2n 個(gè)最大項(xiàng)。個(gè)最大項(xiàng)。例如，例如，3個(gè)變量個(gè)變量A、B、C可構(gòu)成、可構(gòu)成、共共8個(gè)最大項(xiàng)。個(gè)最大項(xiàng)。 CBACBACBA簡寫：用簡寫：用Mi表示最大項(xiàng)。表示最大項(xiàng)。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系性質(zhì)：性質(zhì)：最大項(xiàng)具有最大項(xiàng)具有如下性質(zhì)如下性質(zhì)。 性質(zhì)性質(zhì)1 任意一個(gè)最大項(xiàng)，其相應(yīng)變量有且僅有一種取值任意一個(gè)最大項(xiàng)，其相應(yīng)變量

28、有且僅有一種取值使這個(gè)最大項(xiàng)的值為使這個(gè)最大項(xiàng)的值為0。并且，最大項(xiàng)不同，使其值為。并且，最大項(xiàng)不同，使其值為0的變的變量取值不同。量取值不同。 下標(biāo)下標(biāo)i的取值規(guī)則是的取值規(guī)則是：將最大項(xiàng)中的原變量用將最大項(xiàng)中的原變量用0表示，反變表示，反變量用量用1表示，由此得到一個(gè)二進(jìn)制數(shù)，與該二進(jìn)制數(shù)對應(yīng)的十表示，由此得到一個(gè)二進(jìn)制數(shù)，與該二進(jìn)制數(shù)對應(yīng)的十進(jìn)制數(shù)即下標(biāo)進(jìn)制數(shù)即下標(biāo) i 的值。例如，的值。例如，3變量變量A、B、C構(gòu)成的最大項(xiàng)構(gòu)成的最大項(xiàng) 可用 M5 表示。因?yàn)?M5 (5)10 101CBACBA在在n個(gè)變量構(gòu)成的任意個(gè)變量構(gòu)成的任意“或項(xiàng)或項(xiàng)”中，最大項(xiàng)是使其值為中，最大項(xiàng)是使其值為

29、1的的變量取值組合數(shù)最多的一種變量取值組合數(shù)最多的一種“或項(xiàng)或項(xiàng)”，因而將其稱為，因而將其稱為最大項(xiàng)。最大項(xiàng)。 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系性質(zhì)性質(zhì)2 相同變量構(gòu)成的兩個(gè)不同最大項(xiàng)相相同變量構(gòu)成的兩個(gè)不同最大項(xiàng)相“或或”為為1。因?yàn)槿魏我环N變量取值都不可能使兩個(gè)不同最大項(xiàng)同時(shí)為因?yàn)槿魏我环N變量取值都不可能使兩個(gè)不同最大項(xiàng)同時(shí)為0，故相，故相“或或”為為1。即即 M i + M j = 1 性質(zhì)性質(zhì)3 n個(gè)變量的全部最大項(xiàng)相個(gè)變量的全部最大項(xiàng)相“與與”為為0。通常借用數(shù)學(xué)。通常借用數(shù)學(xué)中的累乘符號中的累乘符號“”將其記為將其記為 010ii2nM山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系兩變量最小項(xiàng)、最大項(xiàng)的

30、真值表如下。兩變量最小項(xiàng)、最大項(xiàng)的真值表如下。m2 000101001000M3 M2 M 1 M 0 m 3 m1m 0 001011101101101101110 00 11 01 1A B最最 大大 項(xiàng)項(xiàng) 最最 小小 項(xiàng)項(xiàng) 變變 量量 2變量最小項(xiàng)、最大項(xiàng)真值表變量最小項(xiàng)、最大項(xiàng)真值表 BABABAABBABABABA真值表反映了最小項(xiàng)、最大項(xiàng)的有關(guān)性質(zhì)。真值表反映了最小項(xiàng)、最大項(xiàng)的有關(guān)性質(zhì)。 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系3最小項(xiàng)和最大項(xiàng)的關(guān)系最小項(xiàng)和最大項(xiàng)的關(guān)系 在同一問題中，下標(biāo)相同的最小項(xiàng)和最大項(xiàng)互為反函數(shù)。在同一問題中，下標(biāo)相同的最小項(xiàng)和最大項(xiàng)互為反函數(shù)。或者說，相同變量構(gòu)成的最

31、小項(xiàng)mi和最大項(xiàng)Mi之間存在互補(bǔ)關(guān)系。即 或者iiMm iiMm 例如，由3變量A、B、C構(gòu)成的最小項(xiàng)m3和最大項(xiàng)M3之間有 33MCBABCAm33mBCACBAM山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系二、邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式二、邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式 邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式有標(biāo)準(zhǔn)標(biāo)準(zhǔn)“與與-或或”表達(dá)式表達(dá)式和和標(biāo)標(biāo)準(zhǔn)準(zhǔn)“或或-與與”表達(dá)式表達(dá)式兩種類型兩種類型。 1標(biāo)準(zhǔn)標(biāo)準(zhǔn)“與與 - 或或”表達(dá)式表達(dá)式 由若干最小項(xiàng)相由若干最小項(xiàng)相“或或”構(gòu)成的邏輯表達(dá)式稱為標(biāo)準(zhǔn)構(gòu)成的邏輯表達(dá)式稱為標(biāo)準(zhǔn)“與與-或或”表達(dá)式，也叫做最小項(xiàng)表達(dá)式。表達(dá)式，也叫做最小項(xiàng)表達(dá)式。 該函數(shù)表達(dá)式又可簡寫為該函數(shù)表達(dá)

32、式又可簡寫為F(A，B，C) = m1 + m2 + m4 + m7 =m(1,2,4,7)例如，如下所示為一個(gè)例如，如下所示為一個(gè)3變量函數(shù)的標(biāo)準(zhǔn)變量函數(shù)的標(biāo)準(zhǔn)“與與-或或”表達(dá)表達(dá)式式 ABCCBACBACBAC)B,F(A,山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系2標(biāo)準(zhǔn)標(biāo)準(zhǔn)“或或-與與”表達(dá)式表達(dá)式 由若干最大項(xiàng)相由若干最大項(xiàng)相“與與”構(gòu)成的邏輯表達(dá)式稱為標(biāo)準(zhǔn)構(gòu)成的邏輯表達(dá)式稱為標(biāo)準(zhǔn)“或或-與與”表達(dá)式，也叫做最大項(xiàng)表達(dá)式表達(dá)式，也叫做最大項(xiàng)表達(dá)式 。該表達(dá)式又可簡寫為該表達(dá)式又可簡寫為 M(1,5,7)MMMC)B,F(A,751CBA 例如，例如， 、 、 為為3變量構(gòu)成的變量構(gòu)成的3個(gè)最大項(xiàng)，

33、對這個(gè)最大項(xiàng)，對這3個(gè)最大項(xiàng)進(jìn)行個(gè)最大項(xiàng)進(jìn)行“與與”運(yùn)算，即可得到一個(gè)運(yùn)算，即可得到一個(gè)3變變量函數(shù)的標(biāo)準(zhǔn)量函數(shù)的標(biāo)準(zhǔn)“或或-與與”表達(dá)式表達(dá)式CBACBA)CBA)(CBA)(CB(AC),B,F(A山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系2.3.3 2.3.3 邏輯函數(shù)表達(dá)式的轉(zhuǎn)換邏輯函數(shù)表達(dá)式的轉(zhuǎn)換 將一個(gè)任意邏輯函數(shù)表達(dá)式轉(zhuǎn)換成標(biāo)準(zhǔn)表達(dá)式有兩種將一個(gè)任意邏輯函數(shù)表達(dá)式轉(zhuǎn)換成標(biāo)準(zhǔn)表達(dá)式有兩種常用方法。常用方法。一、代數(shù)轉(zhuǎn)換法一、代數(shù)轉(zhuǎn)換法 1 . 求標(biāo)準(zhǔn)求標(biāo)準(zhǔn)“與與-或或” 式式一般步驟如下：一般步驟如下： 第一步第一步：將函數(shù)表達(dá)式變換成一般將函數(shù)表達(dá)式變換成一般“與與-或或”表達(dá)式。表達(dá)式。 所

34、謂代數(shù)轉(zhuǎn)換法，就是利用邏輯代數(shù)的公理、定理和規(guī)所謂代數(shù)轉(zhuǎn)換法，就是利用邏輯代數(shù)的公理、定理和規(guī)則進(jìn)行邏輯變換，將函數(shù)表達(dá)式從一種形式變換為另一種形則進(jìn)行邏輯變換，將函數(shù)表達(dá)式從一種形式變換為另一種形式。式。 第二步：第二步：反復(fù)使用將表達(dá)式中所有非反復(fù)使用將表達(dá)式中所有非最小項(xiàng)的最小項(xiàng)的“與項(xiàng)與項(xiàng)”擴(kuò)展成最小項(xiàng)。擴(kuò)展成最小項(xiàng)。 )YX(YX山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系例例 將邏輯函數(shù)將邏輯函數(shù)表達(dá)式轉(zhuǎn)換表達(dá)式轉(zhuǎn)換成標(biāo)準(zhǔn)成標(biāo)準(zhǔn)“與與-或或”表達(dá)式。表達(dá)式。 AB)CBB(AC)B,F(A,C)C( ABA)BCA(B)BC(AC)C(BAC)B,F(A,ABCC ABABCBCABCACBACB

35、ACBAABCCABBCACBACBA解解 第一步：第一步：將函數(shù)表達(dá)式變換成將函數(shù)表達(dá)式變換成“與與-或或”表達(dá)式。即表達(dá)式。即ABCBBAABC)BB)(A(ABBCCABAAB)CBB(A C)B,F(A,第二步：第二步：把把“與與-或或”式中非最小項(xiàng)的式中非最小項(xiàng)的“與項(xiàng)與項(xiàng)”擴(kuò)展成擴(kuò)展成最小項(xiàng)最小項(xiàng)。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系所得標(biāo)準(zhǔn)“與-或”式的簡寫形式為 當(dāng)給出函數(shù)表達(dá)式已經(jīng)是當(dāng)給出函數(shù)表達(dá)式已經(jīng)是“與與-或或”表達(dá)式時(shí)，可直接進(jìn)表達(dá)式時(shí)，可直接進(jìn)行第二步。行第二步。 2 . 求一個(gè)函數(shù)的標(biāo)準(zhǔn)求一個(gè)函數(shù)的標(biāo)準(zhǔn)“或或-與與” 式式一般步驟：一般步驟：第一步：第一步：將函數(shù)表達(dá)式轉(zhuǎn)

36、換成一般將函數(shù)表達(dá)式轉(zhuǎn)換成一般“或或-與與”表達(dá)式。表達(dá)式。 第二步：第二步：反復(fù)利用定理把表達(dá)式中反復(fù)利用定理把表達(dá)式中所有非最大項(xiàng)的所有非最大項(xiàng)的“或項(xiàng)或項(xiàng)”擴(kuò)展成最大項(xiàng)。擴(kuò)展成最大項(xiàng)。 )BB)(A(AA76310mmmmmC)B,F(A,)(0,1,3,6,7m山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系解解 第一步：第一步：將函數(shù)表達(dá)式變換成將函數(shù)表達(dá)式變換成“或或-與與”表達(dá)式。即表達(dá)式。即 例例 將邏輯函數(shù)表達(dá)式將邏輯函數(shù)表達(dá)式 變變換成標(biāo)準(zhǔn)換成標(biāo)準(zhǔn)“或或-與與”表達(dá)式。表達(dá)式。 CBC)A(ABC)B,F(A,CBC)A(ABC)B,F(A,CBCAABCB)C(AB)A(C)C)(ABA(B

37、)C)(ABA(C)CC)(ABA)(BC)(ABBA(C)BA)(CB)(ABA(=1山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系第二步第二步：將所得將所得“或或-與與”表達(dá)中的非最大項(xiàng)擴(kuò)展成最大表達(dá)中的非最大項(xiàng)擴(kuò)展成最大項(xiàng)。即項(xiàng)。即 當(dāng)給出函數(shù)已經(jīng)是當(dāng)給出函數(shù)已經(jīng)是“或或-與與”表達(dá)式時(shí)，可直接進(jìn)行第二表達(dá)式時(shí)，可直接進(jìn)行第二步。步。 該標(biāo)準(zhǔn)該標(biāo)準(zhǔn)“或或-與與”表達(dá)式的簡寫形式為表達(dá)式的簡寫形式為 M(3,6,7)MMMC)B,F(A,763C)BA)(CB)(ABA(C)B,F(A,C)BA)(CBC)(ABA)(CBA()CBAC)(BA)(CB(A山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系二、真值表轉(zhuǎn)換法二、真值

38、表轉(zhuǎn)換法 具體：具體：真值表上使函數(shù)值為真值表上使函數(shù)值為1的變量取值組合對應(yīng)的最的變量取值組合對應(yīng)的最小項(xiàng)相小項(xiàng)相“或或”,即可構(gòu)成一個(gè)函數(shù)的標(biāo)準(zhǔn)即可構(gòu)成一個(gè)函數(shù)的標(biāo)準(zhǔn)“與與-或或”式式 。 邏輯函數(shù)的最小項(xiàng)表達(dá)式與真值表具有一一對應(yīng)的關(guān)系。邏輯函數(shù)的最小項(xiàng)表達(dá)式與真值表具有一一對應(yīng)的關(guān)系。 假定函數(shù)假定函數(shù)F的真值表中有的真值表中有k組變量取值使組變量取值使F的值為的值為1，其他，其他變量取值下變量取值下F的值為的值為0，那么，函數(shù)，那么，函數(shù)F的最小項(xiàng)表達(dá)式由這的最小項(xiàng)表達(dá)式由這k組組變量取值對應(yīng)的變量取值對應(yīng)的k個(gè)最小項(xiàng)相或組成。個(gè)最小項(xiàng)相或組成。1 . 求標(biāo)準(zhǔn)求標(biāo)準(zhǔn)“與與-或或” 式

39、式山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系1 0 0 1 1 0 1 1 0 1 1 0 A B C F 1 1 0 11 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 函數(shù)的真值表 CBBAC)B,F(A,解解:首先，列出F的真值表如下表所示，然后，根據(jù)真值表可直接寫出F的最小項(xiàng)表達(dá)式 m(2,4,5,6)C)B,F(A,)6 , 5 , 4 , 2(),(mCBAF例例 將函數(shù)表達(dá)式變換成標(biāo)準(zhǔn)“與-或”表達(dá)式。 CBBAC)B,F(A,山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系具體：具體：真值表上使函數(shù)值為真值表上使函數(shù)值為0的變量取值組合對應(yīng)的最的變量取值組合對應(yīng)的最大項(xiàng)相大項(xiàng)相“與與”即可構(gòu)成一個(gè)

40、函數(shù)的標(biāo)準(zhǔn)即可構(gòu)成一個(gè)函數(shù)的標(biāo)準(zhǔn)“或或-與與”式式 。 2 . 求一個(gè)函數(shù)的標(biāo)準(zhǔn)求一個(gè)函數(shù)的標(biāo)準(zhǔn)“或或-與與” 式式 邏輯函數(shù)的最大項(xiàng)表達(dá)式與真值表之間同樣具有一一邏輯函數(shù)的最大項(xiàng)表達(dá)式與真值表之間同樣具有一一對應(yīng)的關(guān)系。對應(yīng)的關(guān)系。 假定在函數(shù)F的真值表中有p組變量取值使F的值為0，其他變量取值下F的值為1，那么，函數(shù)F的最大項(xiàng)表達(dá)式由這p組變量取值對應(yīng)的p個(gè)最大項(xiàng)“相與”組成。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系解：解：首先，列出首先，列出F的真值表如下表所示。然后，根據(jù)真的真值表如下表所示。然后，根據(jù)真值表直接寫出值表直接寫出F的最大項(xiàng)表達(dá)式的最大項(xiàng)表達(dá)式 )7 , 6 , 5 , 2 , 0(

41、),(MCBAF) 7 , 6 , 5 , 2 , 0 (),(MCBAF函數(shù)的真值表 1010 0111 0100 1001 1110 1100 CBACAC)B,F(A,ABC F 0000 0011 例例 將函數(shù)表達(dá)式將函數(shù)表達(dá)式 表示成最表示成最大項(xiàng)表達(dá)式的形式。大項(xiàng)表達(dá)式的形式。 CBACACBAF),(山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系由于函數(shù)的真值表與函數(shù)的兩種標(biāo)準(zhǔn)表達(dá)式之間存在由于函數(shù)的真值表與函數(shù)的兩種標(biāo)準(zhǔn)表達(dá)式之間存在一一對應(yīng)的關(guān)系，而任何個(gè)邏輯函數(shù)的真值表是唯一的，一一對應(yīng)的關(guān)系，而任何個(gè)邏輯函數(shù)的真值表是唯一的，可見，可見，任何一個(gè)邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式也是唯一的任何一個(gè)邏輯

42、函數(shù)的兩種標(biāo)準(zhǔn)形式也是唯一的。邏輯函數(shù)表達(dá)式的唯一性給我們分析和研究邏輯問題邏輯函數(shù)表達(dá)式的唯一性給我們分析和研究邏輯問題帶來了很大的方便。帶來了很大的方便。 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系2.4 2.4 邏輯函數(shù)化簡邏輯函數(shù)化簡實(shí)現(xiàn)某一邏輯功能的邏輯電路的復(fù)雜性與描述該功能的實(shí)現(xiàn)某一邏輯功能的邏輯電路的復(fù)雜性與描述該功能的邏輯表達(dá)式的復(fù)雜性直接相關(guān)。邏輯表達(dá)式的復(fù)雜性直接相關(guān)。為了降低系統(tǒng)成本、減小復(fù)雜度、提高可靠性，必須對為了降低系統(tǒng)成本、減小復(fù)雜度、提高可靠性，必須對邏輯函數(shù)進(jìn)行化簡。邏輯函數(shù)進(jìn)行化簡。 由于由于“與與-或或”表達(dá)式和表達(dá)式和“或或-與與”表達(dá)式可以很方便地轉(zhuǎn)換表達(dá)式可以很

43、方便地轉(zhuǎn)換成任何其他所要求的形式。因此，從這兩種基本形式出發(fā)討成任何其他所要求的形式。因此，從這兩種基本形式出發(fā)討論函數(shù)化簡問題，并將重點(diǎn)放在論函數(shù)化簡問題，并將重點(diǎn)放在“與與-或或”表達(dá)式的化簡上。表達(dá)式的化簡上。 邏輯函數(shù)化簡有邏輯函數(shù)化簡有3種常用方法。種常用方法。即：代數(shù)化簡法即：代數(shù)化簡法、卡諾卡諾圖化簡法圖化簡法和列表化簡法列表化簡法。 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系2.4.1 2.4.1 代數(shù)化簡法代數(shù)化簡法 代數(shù)化簡法就是運(yùn)用邏輯代數(shù)的公理、定理和規(guī)則對邏代數(shù)化簡法就是運(yùn)用邏輯代數(shù)的公理、定理和規(guī)則對邏輯函數(shù)進(jìn)行化簡的方法。輯函數(shù)進(jìn)行化簡的方法。1、“與與-或或”表達(dá)式的化簡表達(dá)

44、式的化簡 最簡最簡“與與-或或”表達(dá)式應(yīng)滿足兩個(gè)條件：表達(dá)式應(yīng)滿足兩個(gè)條件： 1表達(dá)式中的表達(dá)式中的“與與”項(xiàng)個(gè)數(shù)最少；項(xiàng)個(gè)數(shù)最少； 2在滿足上述條件的前提下，每個(gè)在滿足上述條件的前提下，每個(gè)“與與”項(xiàng)中的變量個(gè)項(xiàng)中的變量個(gè) 數(shù)最少。數(shù)最少。 滿足上述兩個(gè)條件可以使相應(yīng)邏輯電路中所需門的數(shù)量以及門的輸入端個(gè)數(shù)均為最少，從而使電路最經(jīng)濟(jì)。 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系 幾種常用方法如下：幾種常用方法如下： 1并項(xiàng)法并項(xiàng)法 2吸收法吸收法 利用定理利用定理3中中A + AB = A ，吸收多余的項(xiàng)。例如，吸收多余的項(xiàng)。例如， BACBABA利用定理利用定理7中的，將兩個(gè)中的，將兩個(gè)“與與”項(xiàng)合并成

45、一項(xiàng)合并成一個(gè)個(gè)“與與”項(xiàng)，合并后消去一個(gè)變量。例如，項(xiàng)，合并后消去一個(gè)變量。例如， BACBABCAAABBA山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系3消去法消去法 利用定理利用定理4中，消去多余變量。例如，中，消去多余變量。例如，BABAACABCABABCBAABCBCAAB4配項(xiàng)法配項(xiàng)法 利用公理利用公理4和公理和公理5中的中的 A1=A及及 A+A=1，先從函數(shù)式中，先從函數(shù)式中適當(dāng)選擇某些適當(dāng)選擇某些“與與”項(xiàng)，并配上其所缺的一個(gè)合適的變量，然項(xiàng)，并配上其所缺的一個(gè)合適的變量，然后再利用并項(xiàng)、吸收和消去等方法進(jìn)行化簡。例如，后再利用并項(xiàng)、吸收和消去等方法進(jìn)行化簡。例如，CBABCACBACBA

46、CBBACCBACBAACBBABACBCBBA CACBBA山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系例例 化簡化簡 CBADCBDDBCF解解 DBCBADDBCCBADBCDBCCBADCBDBCCBADCBDDBCF 實(shí)際應(yīng)用中遇到的邏輯函數(shù)往往比較復(fù)雜，化簡時(shí)應(yīng)實(shí)際應(yīng)用中遇到的邏輯函數(shù)往往比較復(fù)雜，化簡時(shí)應(yīng)靈活使用所學(xué)的公理、定理及規(guī)則，綜合運(yùn)用各種方法靈活使用所學(xué)的公理、定理及規(guī)則，綜合運(yùn)用各種方法。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系例例 化簡化簡 CBACBACBAF)( )(解解 CBACCBACACBACBACBACBACBACBACBAF )()( )()( )()(山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)

47、系2、“或或-與與”表達(dá)式的化簡表達(dá)式的化簡 最簡最簡“或或-與與”表達(dá)式應(yīng)滿足兩個(gè)條件：表達(dá)式應(yīng)滿足兩個(gè)條件： 1表達(dá)式中的表達(dá)式中的“或或”項(xiàng)個(gè)數(shù)最少；項(xiàng)個(gè)數(shù)最少； 2在滿足上述條件的前提下，每個(gè)在滿足上述條件的前提下，每個(gè)“或或”項(xiàng)中的變量個(gè)項(xiàng)中的變量個(gè)數(shù)最少。數(shù)最少。 用代數(shù)化簡法化簡用代數(shù)化簡法化簡“或或-與與”表達(dá)式可直接運(yùn)用公理、定表達(dá)式可直接運(yùn)用公理、定理中的理中的“或或-與與”形式，并綜合運(yùn)用前面介紹形式，并綜合運(yùn)用前面介紹“與與-或或”表達(dá)式化表達(dá)式化簡時(shí)提出的各種方法進(jìn)行化簡簡時(shí)提出的各種方法進(jìn)行化簡。 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系例例 化簡化簡 CADCACBBAF)(

48、)(解解 )( )()()( )()()()(CBBACACBBACADCACBBAF此外，可以采用兩次對偶法。具體如下：具體如下： 第一步：第一步：對“或-與”表達(dá)式表示的函數(shù)F求對偶，得到“與-或”表達(dá)式F； 第二步：第二步：求出F的最簡“與-或”表達(dá)式； 第三步：第三步：對F再次求對偶,即可得到F的最簡“或-與”表達(dá)式。 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系例例 化簡化簡 )()()()CACBBABAF （第二步：第二步：化簡化簡F ； CBABA CBABABA )CA(BBABA CABCBABAF第三步：第三步：對F求對偶, 得到F的最簡“或-與”表達(dá)式。 CBABAF)()(解解 第一

49、步：第一步：求求F的對偶式的對偶式F； CABCBABAF山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系歸納：歸納： 代數(shù)化簡法的優(yōu)點(diǎn)是：代數(shù)化簡法的優(yōu)點(diǎn)是：不受變量數(shù)目的約束；當(dāng)對公理、不受變量數(shù)目的約束；當(dāng)對公理、定理和規(guī)則十分熟練時(shí)，化簡比較方便。定理和規(guī)則十分熟練時(shí)，化簡比較方便。 缺點(diǎn)是：缺點(diǎn)是：沒有一定的規(guī)律和步驟，技巧性很強(qiáng)，而且在沒有一定的規(guī)律和步驟，技巧性很強(qiáng)，而且在很多情況下難以判斷化簡結(jié)果是否最簡。很多情況下難以判斷化簡結(jié)果是否最簡。 1. F=ABC+A CD+AC=A(BC+C)+A CD=ACABA CD=C(AD)AB=AC+CD+ABA2. F=AC D+BC+BD+AB+AC+

50、B C=AC D+BC+BD+AB+AC+BC+B C=AC D+BC+AC+B=AD+C+B練習(xí)：練習(xí)：3. F=(A+B)(A+B+C)(A +C)(B+C+D)F*= AB+ABC+AC+BCD= AB+AC+BCD=AB+AC F=(F*)*=(A+B)(A +C)=AC+AB4. F=AB+ABBC+B CAB+ABBC+B CAB+ABBC+B CAB CAAFCABBCCABB CC山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系2.4.2 2.4.2 卡諾圖化簡法卡諾圖化簡法 卡諾圖化簡法具有簡單、直觀、容易掌握等優(yōu)點(diǎn)簡單、直觀、容易掌握等優(yōu)點(diǎn)，在邏輯設(shè)計(jì)中得到廣泛應(yīng)用。 一、卡諾圖的構(gòu)成一、卡諾

51、圖的構(gòu)成 卡諾圖是一種平面方格圖，每個(gè)小方格代表一個(gè)最小項(xiàng)，卡諾圖是一種平面方格圖，每個(gè)小方格代表一個(gè)最小項(xiàng)，故又稱為最小項(xiàng)方格圖。故又稱為最小項(xiàng)方格圖。 結(jié)構(gòu)特點(diǎn)：結(jié)構(gòu)特點(diǎn)：(1) n n個(gè)變量的卡諾圖由2n個(gè)小方格構(gòu)成；(2) 幾何圖形上處在相鄰、相對相鄰、相對、相重相重位置的小方格所代表的最小項(xiàng)為相鄰最小項(xiàng)。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系2變量、3變量、4變量卡諾圖如圖(a)、(b)、(c)所示。m3 m1 m2 m0 AB0110( a ) 0m5m4m7m6m3 m1 m2 m0 100011110ABC( b ) m10m14m6m2m11m15m7m3m9m8m13m12m5 m1

52、 m4 m0 00011110ABCD00011110( c ) 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系例如，四變量卡諾圖中，如m5的4個(gè)相鄰最小項(xiàng)分別是和m5相連的 m1，m4，m7，m13。 m2的4個(gè)相鄰最小項(xiàng)除了與之幾何相鄰的m3和m6之外，另外兩個(gè)是處在“相對”位置的m0 ( 同一列的兩端)和m10( 同一行的兩端)。這種相鄰稱為相對相鄰相對相鄰。 m10m14m6m2m11m15m7m3m9m8m13m12m5 m1 m4 m0 00011110ABCD00011110從各卡諾圖可以看出，在在n個(gè)變量的卡諾圖中，能從圖形個(gè)變量的卡諾圖中，能從圖形上直觀、方便地找到每個(gè)最小項(xiàng)的上直觀、方便地找

53、到每個(gè)最小項(xiàng)的n個(gè)相鄰最小項(xiàng)。個(gè)相鄰最小項(xiàng)。山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系1014621115739813125 1 4 0 26302218273123192524292821 17 2016 00011110000 001 011 010100 101 111 110ABCDE( d ) 5變量卡諾圖 5變量卡諾圖如變量卡諾圖如圖（圖（d）所）所示示：此外，此外， 處在處在“相重相重”位置的最小項(xiàng)相鄰，如五變量卡諾圖中位置的最小項(xiàng)相鄰，如五變量卡諾圖中的的m3，除了幾何相鄰的，除了幾何相鄰的m1，m2，m7和相對相鄰的和相對相鄰的m11外，還與外，還與m19相鄰。這種相鄰稱為相鄰。這種相鄰稱

54、為重疊相鄰重疊相鄰。 m15m7m13m5 00011110ABCD00011110ABCDDCABBCDADCBAABDBDAB D卡卡諾圖的性質(zhì)諾圖的性質(zhì) 用卡諾圖化簡邏輯函用卡諾圖化簡邏輯函數(shù)的基本原理：數(shù)的基本原理：把卡諾圖把卡諾圖上表征相鄰最小項(xiàng)的相鄰上表征相鄰最小項(xiàng)的相鄰小方格小方格“圈圈”在一起進(jìn)行合在一起進(jìn)行合并，達(dá)到用一個(gè)簡單并，達(dá)到用一個(gè)簡單“與與”項(xiàng)代替若干最小項(xiàng)的目的。項(xiàng)代替若干最小項(xiàng)的目的。 通常把用來包圍那些通常把用來包圍那些能由一個(gè)簡單能由一個(gè)簡單“與與”項(xiàng)代替項(xiàng)代替的若干最小項(xiàng)的的若干最小項(xiàng)的“圈圈”稱為稱為卡諾圈。卡諾圈。 性質(zhì)：可以從圖形上直觀地找出可以從圖

55、形上直觀地找出相鄰相鄰最小項(xiàng)合并。最小項(xiàng)合并。合并的理論依據(jù)是并項(xiàng)定理： 。A ABBA山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系邏輯函數(shù)邏輯函數(shù)在卡諾圖上的表示在卡諾圖上的表示 當(dāng)邏輯函數(shù)為標(biāo)準(zhǔn)當(dāng)邏輯函數(shù)為標(biāo)準(zhǔn)“與與-或或”表達(dá)式時(shí)，只需在卡諾圖上表達(dá)式時(shí)，只需在卡諾圖上找出和表達(dá)式中最小項(xiàng)對應(yīng)的小方格找出和表達(dá)式中最小項(xiàng)對應(yīng)的小方格填上填上1 1，其余小方格填，其余小方格填上上0 0，即可得到該函數(shù)的卡諾圖。，即可得到該函數(shù)的卡諾圖。 1給定邏輯函數(shù)為標(biāo)準(zhǔn)給定邏輯函數(shù)為標(biāo)準(zhǔn)“與與-或或”表達(dá)式表達(dá)式例如，例如，3 3變量函數(shù)變量函數(shù) 的卡諾圖如下圖的卡諾圖如下圖所示。所示。 7 , 3 , 2 , 1,

56、mCBAF000101 1 1 0 100011110ABC F(A,B,C)=m(1,2,3,7)F(A,B,C)=m(1,2,3,7)的卡諾圖的卡諾圖 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系例如，例如，4 4變量函數(shù)變量函數(shù) 的卡諾圖如右圖所示。的卡諾圖如右圖所示。 CBACDABDCBAF,0101111100110 0 00 00011110ABCD00011110為了敘述的方便，通常將卡諾圖上填為了敘述的方便，通常將卡諾圖上填1的小方格稱為的小方格稱為1方格，填方格，填0的小方格稱為的小方格稱為0方格。方格。0方格有時(shí)用空格表示。方格有時(shí)用空格表示。 2邏輯函數(shù)為一般邏輯函數(shù)為一般“與與-或或

57、”表達(dá)式表達(dá)式 當(dāng)邏輯函數(shù)為一般當(dāng)邏輯函數(shù)為一般“與與-或或”表達(dá)式時(shí)，可根據(jù)表達(dá)式時(shí)，可根據(jù)“與與”的的公共性和公共性和“或或”的疊加性作出相應(yīng)卡諾圖。的疊加性作出相應(yīng)卡諾圖。 山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系 解：（解：（1）利用摩根定律去掉非號，）利用摩根定律去掉非號， 直到最后得到一個(gè)與或表直到最后得到一個(gè)與或表達(dá)式，即達(dá)式，即 ACCBACABCBAY),(ACCBACABACCBACBA)(ACCBACBCA （2） 根據(jù)與或表達(dá)式畫出卡諾根據(jù)與或表達(dá)式畫出卡諾圖圖ACCBACABCBAY),(例：例： 3.從真值表畫卡諾圖從真值表畫卡諾圖根據(jù)變量個(gè)數(shù)畫出卡諾圖，再按真值表填寫每一個(gè)小

58、方根據(jù)變量個(gè)數(shù)畫出卡諾圖，再按真值表填寫每一個(gè)小方塊的值（塊的值（0或或1）即可。需注意二者順序不同）即可。需注意二者順序不同。例：例： 已知已知Y的真值表，要求畫的真值表，要求畫Y的卡諾圖。的卡諾圖。邏輯函數(shù)Y的真值表 A B CY0 0 000 0 110 1 010 1 101 0 011 0 101 1 001 1 11例3的卡諾圖 練習(xí)：三變量表決邏輯真值表填入卡諾圖練習(xí)：三變量表決邏輯真值表填入卡諾圖A B CY0 0 000 0 100 1 000 1 111 0 001 0 111 1 011 1 11山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系卡卡諾圖上最小項(xiàng)的合并規(guī)律諾圖上最小項(xiàng)的合并規(guī)律

59、 1 1兩個(gè)小方格相鄰兩個(gè)小方格相鄰, , 或處于某行或處于某行( (列列) )兩端時(shí)，所代表兩端時(shí)，所代表的最小項(xiàng)可以合并，合并后可消去一個(gè)變量。的最小項(xiàng)可以合并，合并后可消去一個(gè)變量。 例如，下圖給出了2、3變量卡諾圖上兩個(gè)相鄰最小項(xiàng)合并的典型情況的。 當(dāng)一個(gè)函數(shù)用卡諾圖表示后，究竟哪些最小項(xiàng)可以合并究竟哪些最小項(xiàng)可以合并呢？呢？下面以2、3、4變量卡諾圖為例予以說明。 兩個(gè)相鄰最小項(xiàng)合并的情況A0110B10100110B1010B1101B1010ABA01000 101 00011110ABC01ABBC山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系2 2四個(gè)小方格組成一個(gè)大方格、或組成一行（列）、或

60、四個(gè)小方格組成一個(gè)大方格、或組成一行（列）、或處于相鄰兩行（列）的兩端、或處于四角時(shí)，所代表的最小處于相鄰兩行（列）的兩端、或處于四角時(shí)，所代表的最小項(xiàng)可以合并，合并后可消去兩個(gè)變量。項(xiàng)可以合并，合并后可消去兩個(gè)變量。 例如例如,下圖給出了下圖給出了3變量卡諾圖上四個(gè)相鄰最小項(xiàng)合并的變量卡諾圖上四個(gè)相鄰最小項(xiàng)合并的典型情況的。典型情況的。 00111 010 00011110ABC01BB11000 101 00011110ABC01山東農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)系 四個(gè)相鄰最小項(xiàng)合并的幾種情況00 01 11 10CD1001011001101 0 01AB00011110BDBD00 01 1