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

1、 數(shù)字邏輯基礎(chǔ)數(shù)字邏輯基礎(chǔ) 第二章第二章北京郵電大學(xué)北京郵電大學(xué)徐惠民徐惠民邏輯變量和邏輯系統(tǒng)邏輯變量和邏輯系統(tǒng) 在數(shù)字電路和數(shù)字系統(tǒng)中用邏輯值來表示在數(shù)字電路和數(shù)字系統(tǒng)中用邏輯值來表示實際的信號或電路狀態(tài)。一般邏輯值的取實際的信號或電路狀態(tài)。一般邏輯值的取值只有兩種：值只有兩種：0和和1，0表示邏輯假，表示邏輯假，1表示表示邏輯真。取值為邏輯值的變量稱為邏輯真。取值為邏輯值的變量稱為邏輯變邏輯變量量。 使用邏輯變量作為輸入使用邏輯變量作為輸入/輸出的系統(tǒng)，就是輸出的系統(tǒng)，就是邏輯系統(tǒng)邏輯系統(tǒng)。 一般的邏輯系統(tǒng)都是二值系統(tǒng)。一般的邏輯系統(tǒng)都是二值系統(tǒng)。正邏輯系統(tǒng)正邏輯系統(tǒng) 和負(fù)邏輯系統(tǒng)和負(fù)邏輯

2、系統(tǒng) 邏輯值只是信號或電路狀態(tài)的反映，并沒邏輯值只是信號或電路狀態(tài)的反映，并沒有規(guī)定邏輯值和信號范圍的具體映射關(guān)系。有規(guī)定邏輯值和信號范圍的具體映射關(guān)系。在實際應(yīng)用中，既可以用高電平來表示邏在實際應(yīng)用中，既可以用高電平來表示邏輯輯1，用低電平表示邏輯，用低電平表示邏輯0；也可以用低電；也可以用低電平表示邏輯平表示邏輯1，高電平表示邏輯，高電平表示邏輯0。 用高電平來表示邏輯用高電平來表示邏輯1，用低電平表示邏輯，用低電平表示邏輯0的邏輯系統(tǒng)稱為的邏輯系統(tǒng)稱為正邏輯系統(tǒng)正邏輯系統(tǒng)。 用低電平來表示邏輯用低電平來表示邏輯1，用高電平表示邏輯，用高電平表示邏輯0的邏輯系統(tǒng)是的邏輯系統(tǒng)是負(fù)邏輯系統(tǒng)負(fù)邏

3、輯系統(tǒng)。 基本邏輯運算基本邏輯運算 邏輯代數(shù)中的邏輯變量的基本運算只有邏輯代數(shù)中的邏輯變量的基本運算只有“與與”、“或或”、“非非”三種。三種。 對應(yīng)的邏輯電路是與門、或門、非門。非對應(yīng)的邏輯電路是與門、或門、非門。非門就是反相器。門就是反相器。 任何復(fù)雜的邏輯運算都可以通過這三種基任何復(fù)雜的邏輯運算都可以通過這三種基本邏輯運算來實現(xiàn)。本邏輯運算來實現(xiàn)。 基本邏輯運算基本邏輯運算 1.“與與”邏輯運算邏輯運算 與邏輯運算又叫邏輯乘。其定義是：當(dāng)且僅當(dāng)與邏輯運算又叫邏輯乘。其定義是：當(dāng)且僅當(dāng)決定事件決定事件F發(fā)生的各種條件發(fā)生的各種條件A、B、C 均具備均具備時，這件事才發(fā)生，時，這件事才發(fā)生，

4、 這種因果關(guān)系稱為這種因果關(guān)系稱為”與與”邏輯關(guān)系，邏輯關(guān)系， 即即”與與”邏輯運算。邏輯運算。 兩個變量的兩個變量的”與與”運算的邏輯關(guān)系可以用函數(shù)運算的邏輯關(guān)系可以用函數(shù)式表示為：式表示為：F = A B = A B基本邏輯運算基本邏輯運算 與門的邏輯符號與門的邏輯符號 |“與與”邏輯的真值表邏輯的真值表 基本邏輯運算基本邏輯運算 “與與”邏輯的波形表示邏輯的波形表示 “與與”邏輯運算可以進行這樣的邏輯判斷：邏輯運算可以進行這樣的邏輯判斷：”與與”門的輸入信號中是否有門的輸入信號中是否有“0”0”， 若輸入有若輸入有“0”0”，輸出就是，輸出就是“0”0”，只有當(dāng)輸入全為，只有當(dāng)輸入全為“

5、1”1”， 輸出才是輸出才是“1”1”。 基本邏輯運算基本邏輯運算 2.“或或”邏輯運算邏輯運算“或或”邏輯運算又叫邏輯加。其定義是：邏輯運算又叫邏輯加。其定義是：在決定事件在決定事件F發(fā)生的各種條件中只要有一發(fā)生的各種條件中只要有一個或一個以上條件具備時，個或一個以上條件具備時， 這件事就發(fā)這件事就發(fā)生，生， 這種因果關(guān)系稱為這種因果關(guān)系稱為“或或”邏輯運算邏輯運算關(guān)系。關(guān)系。兩個變量的兩個變量的“或或”運算可以用函數(shù)式表運算可以用函數(shù)式表示為：示為： F = AB = A + B 基本邏輯運算基本邏輯運算 或門的邏輯符號或門的邏輯符號 “或或”邏輯的真值表邏輯的真值表 基本邏輯運算基本邏輯

6、運算 或門的波形或門的波形 “或或”邏輯運算可以進行這樣的邏輯判邏輯運算可以進行這樣的邏輯判斷：斷：”或或”門的輸入信號中是否有門的輸入信號中是否有“1”1”，若輸入有，若輸入有“1”1”， 輸出就是輸出就是“1”1”；只有當(dāng)輸入全為；只有當(dāng)輸入全為“0”0”時，時， 輸輸出才是出才是“0”0”。 基本邏輯運算基本邏輯運算 3“非非”邏輯運算邏輯運算 “非非”邏輯運算又稱邏輯運算又稱“反相反相” 運算，或稱運算，或稱“求補求補”運算。其定義是：當(dāng)決定事件發(fā)運算。其定義是：當(dāng)決定事件發(fā)生的條件生的條件A具備時，具備時， 事件事件F不發(fā)生不發(fā)生; 條件條件A不具備時，不具備時， 事件事件F才發(fā)生。

7、這種因果關(guān)系才發(fā)生。這種因果關(guān)系叫叫“非非”邏輯運算。它的函數(shù)式為邏輯運算。它的函數(shù)式為 F = A基本邏輯運算基本邏輯運算 “非非”門的邏輯符號門的邏輯符號 |“非非”邏輯的真值表邏輯的真值表 布爾代數(shù)公理布爾代數(shù)公理 基本邏輯運算是布爾代數(shù)中最重要的運算，基本邏輯運算是布爾代數(shù)中最重要的運算，從這些運算規(guī)則中，可以歸納出布爾代數(shù)從這些運算規(guī)則中，可以歸納出布爾代數(shù)的公理。的公理。 公理公理1：若：若X=1，則，則 公理公理2：00 = 0 1 + 1 = 1 公理公理3：11 = 1 0 + 0 = 0 公理公理4：10 = 01 = 0 0 + 1 = 1 + 0 = 10X 1X 若若

8、X=0，則，則其他常用邏輯運算其他常用邏輯運算 1與非邏輯運算與非邏輯運算 實現(xiàn)先實現(xiàn)先“與與”后后“非非”的邏輯運算就是與非邏的邏輯運算就是與非邏輯運算。其邏輯函數(shù)式如下輯運算。其邏輯函數(shù)式如下: |“與非與非”門的邏輯符號門的邏輯符號 其他常用邏輯運算其他常用邏輯運算 “與非與非”邏輯的真值表邏輯的真值表 |“與非與非”邏輯運算可進行這樣的邏輯判斷：邏輯運算可進行這樣的邏輯判斷：“與非與非”門輸入信號中是否有門輸入信號中是否有“0 0”， 輸入有輸入有“0 0”， 輸出就是輸出就是“1 1”; ;只有當(dāng)輸入全為只有當(dāng)輸入全為“1 1”時，時， 輸出才是輸出才是“0 0”。 其他常用邏輯運算

9、其他常用邏輯運算 2“或非或非”邏輯運算邏輯運算實現(xiàn)先實現(xiàn)先”或或”后后“非非”的邏輯運算，的邏輯運算， 就是就是“或非或非”邏輯運算。其邏輯函數(shù)式如下：邏輯運算。其邏輯函數(shù)式如下：|“或非或非”門的邏輯符號門的邏輯符號 其他常用邏輯運算其他常用邏輯運算“或非或非”邏輯的真值表邏輯的真值表z“或非或非”邏輯運算可進行這樣的邏輯判斷：邏輯運算可進行這樣的邏輯判斷：“或非或非”門的輸入信號中是否有門的輸入信號中是否有“1”1”， 若輸入有若輸入有“1”1”， 輸出就是輸出就是“0”;0”;只有當(dāng)只有當(dāng)輸入全為輸入全為“0”0”時，時， 輸出才是輸出才是“1”1”。 其他常用邏輯運算其他常用邏輯運算

10、 3“與或非與或非”邏輯運算邏輯運算“與或非與或非”邏輯運算的邏輯函數(shù)式如下邏輯運算的邏輯函數(shù)式如下 z“與或非與或非”門的邏輯符號門的邏輯符號 其他常用邏輯運算其他常用邏輯運算 4“異或異或”邏輯運算邏輯運算 用先用先“非非”再再“與與”后后“或或”的邏輯運算，實的邏輯運算，實現(xiàn)如下邏輯函數(shù)式的稱為現(xiàn)如下邏輯函數(shù)式的稱為“異或異或”邏輯運算。邏輯運算。|“異或異或”門的邏輯符號門的邏輯符號 其他常用邏輯運算其他常用邏輯運算“異或異或”邏輯運算的真值表邏輯運算的真值表 z兩輸入兩輸入“異或異或”邏輯運算可以進行這樣的邏邏輯運算可以進行這樣的邏輯判斷：輯判斷：“異或異或”門的兩個輸入信號是否不門

11、的兩個輸入信號是否不相同，相同， 兩個輸入信號不相同時，兩個輸入信號不相同時， 輸出為輸出為“1”; 1”; 兩個輸入信號相同時，輸出為兩個輸入信號相同時，輸出為“0”0”。 其他常用邏輯運算其他常用邏輯運算 5“同或同或”邏輯運算邏輯運算同或邏輯的邏輯函數(shù)式為同或邏輯的邏輯函數(shù)式為: z“同或同或”門的邏輯符號門的邏輯符號 z注：原部頒標(biāo)準(zhǔn)和國外符號沒有專用的同或邏注：原部頒標(biāo)準(zhǔn)和國外符號沒有專用的同或邏輯符號，用異或非來代替。輯符號，用異或非來代替。 其他常用邏輯運算其他常用邏輯運算 “同或同或”邏輯的真值表邏輯的真值表 z兩輸入兩輸入“同或同或”邏輯運算可以進行這樣的邏邏輯運算可以進行這

12、樣的邏輯判斷：輯判斷：“同或同或”門的兩個輸入信號是否相門的兩個輸入信號是否相同，同， 兩個輸入信號相同時，兩個輸入信號相同時， 輸出為輸出為“1”; 1”; 兩個輸入信號不相同時，輸出為兩個輸入信號不相同時，輸出為“0”0”。 其他常用邏輯運算其他常用邏輯運算 異或異或/同或關(guān)系的一般定義同或關(guān)系的一般定義 盡管實際生產(chǎn)的異或門盡管實際生產(chǎn)的異或門/同或門只有兩個輸入，同或門只有兩個輸入，但是，可以定義多個輸入情況下的異或但是，可以定義多個輸入情況下的異或/同或邏同或邏輯關(guān)系。輯關(guān)系。 對于異或邏輯來說，當(dāng)輸入對于異或邏輯來說，當(dāng)輸入1的數(shù)目是奇數(shù)時，的數(shù)目是奇數(shù)時，輸出為輸出為1；當(dāng)輸入；

13、當(dāng)輸入1的數(shù)目是偶數(shù)時，輸出為的數(shù)目是偶數(shù)時，輸出為0。 對于同或邏輯來說，當(dāng)輸入對于同或邏輯來說，當(dāng)輸入0的數(shù)目是偶數(shù)時的數(shù)目是偶數(shù)時（0也算偶數(shù)），輸出為也算偶數(shù)），輸出為1；當(dāng)輸入；當(dāng)輸入0的數(shù)目是的數(shù)目是奇數(shù)時，輸出為奇數(shù)時，輸出為0。其他常用邏輯運算其他常用邏輯運算 對于對于3輸入函數(shù)來說，當(dāng)有奇數(shù)個輸入是輸入函數(shù)來說，當(dāng)有奇數(shù)個輸入是1時，一定也是有偶數(shù)個輸入是時，一定也是有偶數(shù)個輸入是0： 奇數(shù)個輸入是奇數(shù)個輸入是1： 偶數(shù)個輸入是偶數(shù)個輸入是0： 所以，對于所以，對于3變量異或函數(shù)和變量異或函數(shù)和3變量同或函變量同或函數(shù)，具有相同的表達式。數(shù)，具有相同的表達式。 此結(jié)論可以推廣

14、到所有奇數(shù)個輸入的異或此結(jié)論可以推廣到所有奇數(shù)個輸入的異或/同或函數(shù)。同或函數(shù)。CBA,CBA,CBA,ABCCBA,CBA,CBA,ABC真值表真值表 真值表是表示邏輯真值表是表示邏輯函數(shù)的一種方式。函數(shù)的一種方式。 真值表的左面，列真值表的左面，列出函數(shù)的各種輸入出函數(shù)的各種輸入組合，右邊是和輸組合，右邊是和輸入組合相對應(yīng)的輸入組合相對應(yīng)的輸出。出。 多數(shù)表決的真值表。多數(shù)表決的真值表。10111000 XXXXXX阿德里安阿德里安 卡特卡特 布福德布福德 阿德里安（阿德里安（A）、布）、布福德（福德（B）和卡特（）和卡特（K）三人去餐館吃飯，他三人去餐館吃飯，他們每人要的不是火腿們每人要

15、的不是火腿就是就是 豬排。豬排。 （1）如果阿德里安）如果阿德里安要的是火腿，那么布要的是火腿，那么布福德要的就是豬排。福德要的就是豬排。 （2）阿德里安或卡）阿德里安或卡特要的是火腿，但是特要的是火腿，但是不會兩人都要火腿。不會兩人都要火腿。 （3）布福德和卡特）布福德和卡特不會兩人都要豬排。不會兩人都要豬排。 XXXXXX阿德里安阿德里安 卡特卡特 布福德布福德 很容易將結(jié)果轉(zhuǎn)換為很容易將結(jié)果轉(zhuǎn)換為真值表：真值表：結(jié)論是結(jié)論是A=0，A（阿（阿德里安）選的是豬排，德里安）選的是豬排，K都等于都等于1，K（卡特）（卡特）選的是火腿，選的是火腿，B可以可以是是1或者或者0，說明，說明B（布福德

16、）可以選豬（布福德）可以選豬排或火腿，排或火腿， 邏輯代數(shù)的基本定律邏輯代數(shù)的基本定律 邏輯代數(shù)的基本定律邏輯代數(shù)的基本定律 布爾代數(shù)中的交換律、結(jié)合律、分配律和布爾代數(shù)中的交換律、結(jié)合律、分配律和普通代數(shù)中的三大定律的形式基本相同，普通代數(shù)中的三大定律的形式基本相同，但是具有普通代數(shù)中所沒有的但是具有普通代數(shù)中所沒有的“加對乘加對乘”的分配律：的分配律：A+BC=(A+B)(A+C)，需要特別，需要特別注意。在實際應(yīng)用中，這個公式經(jīng)常會用注意。在實際應(yīng)用中，這個公式經(jīng)常會用到。到。 布爾代數(shù)的常用公式布爾代數(shù)的常用公式 這些公式都可以用基本定律來證明：這些公式都可以用基本定律來證明：吸收律吸

17、收律1：(a) A+AB =A 證明證明 A + A B = A1 + A B （自等律）（自等律） = A (1 + B)（分配律）（分配律） = A1（0-1律）律） = A（自等律）（自等律）布爾代數(shù)的常用公式布爾代數(shù)的常用公式 布爾代數(shù)的常用公式布爾代數(shù)的常用公式 布爾代數(shù)的常用公式布爾代數(shù)的常用公式布爾代數(shù)的三個規(guī)則布爾代數(shù)的三個規(guī)則 1代入規(guī)則代入規(guī)則 在一個包含一個或多個邏輯變量的邏輯等在一個包含一個或多個邏輯變量的邏輯等式中，如果將等式兩邊相同的變量用相同式中，如果將等式兩邊相同的變量用相同的邏輯表達式替換，邏輯等式仍然成立。的邏輯表達式替換，邏輯等式仍然成立。這個規(guī)則稱為代入

18、規(guī)則。這個規(guī)則稱為代入規(guī)則。 因為邏輯表達式也只有因為邏輯表達式也只有0、1兩種取值，和兩種取值，和邏輯變量的取值是一樣的。當(dāng)?shù)仁絻蛇叺倪壿嬜兞康娜≈凳且粯拥摹．?dāng)?shù)仁絻蛇叺南嗤兞坑孟嗤倪壿嫳磉_式替換后，不相同變量用相同的邏輯表達式替換后，不會改變等式的相等性。會改變等式的相等性。布爾代數(shù)的三個規(guī)則布爾代數(shù)的三個規(guī)則 對于結(jié)合律對于結(jié)合律A+BC=(A+B)(A+C)， 等式兩邊都用表達式等式兩邊都用表達式A+D代替變量代替變量A A+D+BC=(A+D+B)(A+D+C)，等式仍然成立。，等式仍然成立。 又如，對于摩根定理：又如，對于摩根定理： ， 用表達式用表達式a+b代替變量代替變量A

19、，用表達式，用表達式c+d代替變代替變量量B 則有：則有： 就是摩根定理的擴展形式。就是摩根定理的擴展形式。 BABAdcbadcba布爾代數(shù)的三個規(guī)則布爾代數(shù)的三個規(guī)則以上變換過程的最后，就是將公式以上變換過程的最后，就是將公式BABAA中的中的A用表達式用表達式CAB代換，變量代換，變量B用用ED代入的結(jié)果。代入的結(jié)果。布爾代數(shù)的三個規(guī)則布爾代數(shù)的三個規(guī)則 2反演規(guī)則反演規(guī)則 任何一個邏輯函數(shù)式任何一個邏輯函數(shù)式F，如果將，如果將F式中所有式中所有的邏輯與變?yōu)檫壿嫾?，邏輯加變?yōu)檫壿嬇c，的邏輯與變?yōu)檫壿嫾?，邏輯加變?yōu)檫壿嬇c，“1”變?yōu)樽優(yōu)椤?”，“0”變?yōu)樽優(yōu)椤?”，原變量變，原變量變?yōu)榉醋?/p>

20、量，反變量變?yōu)樵兞?，運算關(guān)系為反變量，反變量變?yōu)樵兞?，運算關(guān)系保持不變，即可得到函數(shù)保持不變，即可得到函數(shù)F的反函數(shù)的反函數(shù) 反演規(guī)則定義了如何獲得函數(shù)反演規(guī)則定義了如何獲得函數(shù)F的反函數(shù)的反函數(shù) FF布爾代數(shù)的三個規(guī)則布爾代數(shù)的三個規(guī)則 在使用反演規(guī)則時，要適時的增加括號。目的是要遵守反在使用反演規(guī)則時，要適時的增加括號。目的是要遵守反演規(guī)則中規(guī)定的演規(guī)則中規(guī)定的“保持運算關(guān)系不變保持運算關(guān)系不變”。 布爾代數(shù)的三個規(guī)則布爾代數(shù)的三個規(guī)則 在以上的取反過程中，也要隨時注意加上括號，保持原來在以上的取反過程中，也要隨時注意加上括號，保持原來的運算關(guān)系。的運算關(guān)系。 推論：將一個邏輯等式的兩

21、邊都取反，等式依然成立。推論：將一個邏輯等式的兩邊都取反，等式依然成立。 布爾代數(shù)的三個規(guī)則布爾代數(shù)的三個規(guī)則 3. 對對偶規(guī)則偶規(guī)則 將邏輯函數(shù)式將邏輯函數(shù)式F中所有邏輯與運算變?yōu)檫壿嬛兴羞壿嬇c運算變?yōu)檫壿嫾舆\算，邏輯加運算變?yōu)檫壿嬇c運算，邏加運算，邏輯加運算變?yōu)檫壿嬇c運算，邏輯常量輯常量“0”變?yōu)樽優(yōu)椤?”，“1”變?yōu)樽優(yōu)椤?”，并，并保留變量的運算關(guān)系和順序不變，所得到保留變量的運算關(guān)系和順序不變，所得到的新的邏輯函數(shù)式稱為的新的邏輯函數(shù)式稱為F的對偶函數(shù)的對偶函數(shù) 對偶規(guī)則定義了如何獲得函數(shù)對偶規(guī)則定義了如何獲得函數(shù)F的對偶函數(shù)的對偶函數(shù) dFdF布爾代數(shù)的三個規(guī)則布爾代數(shù)的三個規(guī)則

22、 推論：若有兩個函數(shù)式相等：推論：若有兩個函數(shù)式相等：F1 = F2 ，則它們的對偶式也，則它們的對偶式也相等：相等： d2d1FF 邏輯函數(shù)的標(biāo)準(zhǔn)表達式邏輯函數(shù)的標(biāo)準(zhǔn)表達式 一個邏輯函數(shù)的多種表示形式，為實現(xiàn)邏輯函數(shù)提供了多一個邏輯函數(shù)的多種表示形式，為實現(xiàn)邏輯函數(shù)提供了多種選擇。種選擇。 或門實現(xiàn)或門實現(xiàn)與非門實現(xiàn)與非門實現(xiàn)邏輯函數(shù)的最小項表達式邏輯函數(shù)的最小項表達式 最小項表達式是一種與或表達式，有時也稱為標(biāo)最小項表達式是一種與或表達式，有時也稱為標(biāo)準(zhǔn)與或式。準(zhǔn)與或式。 最小項最小項是由邏輯函數(shù)的全部變量組成的乘積項是由邏輯函數(shù)的全部變量組成的乘積項（邏輯與項），這些變量可以是原變量或反

23、變量（邏輯與項），這些變量可以是原變量或反變量的形式出現(xiàn)的形式出現(xiàn) ，且僅出現(xiàn)一次。，且僅出現(xiàn)一次。 一個最小項就對應(yīng)邏輯函數(shù)的一種輸入組合。如一個最小項就對應(yīng)邏輯函數(shù)的一種輸入組合。如最小項最小項ABC對應(yīng)輸入對應(yīng)輸入A=1、B=1、C=1。最小項。最小項 BCA對應(yīng)輸入對應(yīng)輸入A=0、B=1、C=1。邏輯函數(shù)的最小項表達式邏輯函數(shù)的最小項表達式 最小項通常用最小項通常用mi來表示。其下標(biāo)來表示。其下標(biāo)i是這樣確定的：是這樣確定的：把最小項中的原變量記為把最小項中的原變量記為1，反變量記為，反變量記為0，變量，變量取值按順序排列成二進制數(shù)。那么這個二進制數(shù)取值按順序排列成二進制數(shù)。那么這個二

24、進制數(shù)的等值十進制數(shù)就是下標(biāo)的等值十進制數(shù)就是下標(biāo)i。 如最小項如最小項ABC用用m7表示。表示。 最小項表達式最小項表達式是由邏輯函數(shù)值為是由邏輯函數(shù)值為1的輸入組合所的輸入組合所對應(yīng)的最小項所組成的或式。對應(yīng)的最小項所組成的或式。 F F（A A、B B、C C）= m= m0 0D D0 0+ m+ m1 1D D1 1+ m+ m2 2D D2 2+ m+ m3 3D D3 3+ m+ m4 4D D4 4+ + m m5 5D D5 5+ m+ m6 6D D6 6+ m+ m7 7D D7 7 其中其中Di就是某個最小項（輸入組合）對應(yīng)的函數(shù)值。就是某個最小項（輸入組合）對應(yīng)的函數(shù)

25、值。BCA用用m3表示。表示。邏輯函數(shù)的最小項表達式邏輯函數(shù)的最小項表達式 寫出和以下真值表對應(yīng)的最小項表達式：寫出和以下真值表對應(yīng)的最小項表達式：|對應(yīng)的最小項表達式是：對應(yīng)的最小項表達式是：邏輯函數(shù)的最小項表達式邏輯函數(shù)的最小項表達式 最小項具有如下三個主要性質(zhì)：最小項具有如下三個主要性質(zhì)： 對于任意一個最小項，只有一組變量值使最小項本身對于任意一個最小項，只有一組變量值使最小項本身取值為取值為1。 任意兩個不同的最小項之積必為任意兩個不同的最小項之積必為0，即：，即： mimj = 0 n個變量的所有個變量的所有2n個最小項之和必為個最小項之和必為1，即，即 式中符號式中符號“”表示最小

26、項求和。表示最小項求和。邏輯函數(shù)的最大項表達式邏輯函數(shù)的最大項表達式 最大項表達式是一種或與表達式，有時也稱為標(biāo)最大項表達式是一種或與表達式，有時也稱為標(biāo)準(zhǔn)或與式。準(zhǔn)或與式。 最大項最大項是由邏輯函數(shù)的全部變量組成的相加項是由邏輯函數(shù)的全部變量組成的相加項（邏輯或項），這些變量可以是原變量或反變量（邏輯或項），這些變量可以是原變量或反變量的形式出現(xiàn)的形式出現(xiàn) ，且僅出現(xiàn)一次。，且僅出現(xiàn)一次。 一個最大項就對應(yīng)邏輯函數(shù)的一種輸入組合。如一個最大項就對應(yīng)邏輯函數(shù)的一種輸入組合。如最大項最大項A+B+C對應(yīng)輸入對應(yīng)輸入A=0、B=0、C=0。最大。最大項項 當(dāng)某個輸入當(dāng)某個輸入變量取值為變量取值為1

27、時，它在最大項中以時，它在最大項中以反變量反變量形式出現(xiàn)形式出現(xiàn)；當(dāng)某個輸入；當(dāng)某個輸入變量取值為變量取值為0時，它在最大項時，它在最大項中就以中就以原變量形式出現(xiàn)原變量形式出現(xiàn)。 CBA對應(yīng)輸入對應(yīng)輸入A=1、B=0、C=0。邏輯函數(shù)的最大項表達式邏輯函數(shù)的最大項表達式 最大項通常用最大項通常用Mi來表示。其下標(biāo)來表示。其下標(biāo)i是這樣確定的：把是這樣確定的：把最大項中的原變量記為最大項中的原變量記為0，反變量記為，反變量記為1，變量取值，變量取值按順序排列成二進制數(shù)。那么這個二進制數(shù)的等值按順序排列成二進制數(shù)。那么這個二進制數(shù)的等值十進制數(shù)就是下標(biāo)十進制數(shù)就是下標(biāo)i。 如最小項如最小項A+B

28、+C用用M0表示。表示。 最大項表達式最大項表達式是由邏輯函數(shù)值為是由邏輯函數(shù)值為0的輸入組合所對應(yīng)的輸入組合所對應(yīng)的最大項所組成的與式。的最大項所組成的與式。 =(m=(m0 0+D D0 0) )( m m1 1+D D1 1) )( m m2 2+D D2 2) )( m m3 3+D D3 3) )( m m4 4+D D4 4) )( m m5 5+D D5 5) )( m m6 6+D D6 6) )( m m7 7+D D7 7) ) 其中其中Di就是某個最大項（輸入組合）對應(yīng)的函數(shù)值。就是某個最大項（輸入組合）對應(yīng)的函數(shù)值。CBA用用M4表示。表示。F（A、B、C）邏輯函數(shù)的最

29、大項表達式邏輯函數(shù)的最大項表達式 寫出和以下真值表對應(yīng)的最大項表達式：寫出和以下真值表對應(yīng)的最大項表達式：|對應(yīng)的最大項表達式是：對應(yīng)的最大項表達式是：)6 , 5 , 1 , 0(MMMMM)CBA)(CBA()CBA()CBA()C,B,A(f6510邏輯函數(shù)的最大項表達式邏輯函數(shù)的最大項表達式 最大項具有下列三個主要性質(zhì)：最大項具有下列三個主要性質(zhì)： 對于任意一個最大項，只有一組變量取值對于任意一個最大項，只有一組變量取值可使其值為可使其值為0。 任 意 兩 個 最 大 項 之 和 必 為任 意 兩 個 最 大 項 之 和 必 為 1 ， 即 ：， 即 ： Mi + Mj = 1 (i

30、j ) n個變量的所有個變量的所有2n個最大項之積必為個最大項之積必為0，即：，即： 120iin0M最小項表達式和最大項表達式的關(guān)系最小項表達式和最大項表達式的關(guān)系 若已經(jīng)知道函數(shù)的最小項表達式，很容易寫出這若已經(jīng)知道函數(shù)的最小項表達式，很容易寫出這個函數(shù)的最大項表達式：個函數(shù)的最大項表達式： 若最小項表達式中最小項的數(shù)目是若最小項表達式中最小項的數(shù)目是k，最大項表達式中，最大項表達式中最大項的數(shù)目是最大項的數(shù)目是2n-k，n是函數(shù)的輸入變量的數(shù)目；是函數(shù)的輸入變量的數(shù)目； 若認(rèn)為若認(rèn)為0，1，2n-1是編號的全集，則最小項表達式是編號的全集，則最小項表達式中最小項的編號和最大項表達式中最大

31、項的編號互為補中最小項的編號和最大項表達式中最大項的編號互為補集，即兩者編號之或為編號的全集。集，即兩者編號之或為編號的全集。 例：如果三變量函數(shù)的最小項表達式是例：如果三變量函數(shù)的最小項表達式是Y=m (0、1、6)，這個函數(shù)的最大項表達式就是，這個函數(shù)的最大項表達式就是Y=M (2、3、4、5、7)。 非標(biāo)準(zhǔn)表達式到標(biāo)準(zhǔn)表達式的轉(zhuǎn)換非標(biāo)準(zhǔn)表達式到標(biāo)準(zhǔn)表達式的轉(zhuǎn)換 如果在與或表達式中，某一個與項和最小項相比，如果在與或表達式中，某一個與項和最小項相比，還缺少變量還缺少變量X，則可以利用基本定律中的，則可以利用基本定律中的A+A=1，將這個與項乘以，將這個與項乘以 (X+X)，轉(zhuǎn)換為最小項。其

32、，轉(zhuǎn)換為最小項。其他與項也作類似處理。最后消除表達式中的重復(fù)他與項也作類似處理。最后消除表達式中的重復(fù)項，就是最小項表達式。項，就是最小項表達式。任意項的定義及表示任意項的定義及表示 在以下兩種情況下，對應(yīng)函數(shù)的某一種輸入組合，在以下兩種情況下，對應(yīng)函數(shù)的某一種輸入組合，相應(yīng)的輸出可以是任意指定的：相應(yīng)的輸出可以是任意指定的： 若某些輸入組合在實際上不可能出現(xiàn)，其相應(yīng)的輸出若某些輸入組合在實際上不可能出現(xiàn)，其相應(yīng)的輸出是可以任意指定的；是可以任意指定的； 某些輸入雖然可能出現(xiàn)，但是相應(yīng)的輸出并不被使用，某些輸入雖然可能出現(xiàn)，但是相應(yīng)的輸出并不被使用，這樣的輸出也可以任意指定。這樣的輸出也可以任

33、意指定。 輸出可以任意指定的輸入項，稱為任意項。有時輸出可以任意指定的輸入項，稱為任意項。有時也稱為無關(guān)項。也稱為無關(guān)項。 帶有任意項的邏輯函數(shù)也稱為不完全確定的邏輯帶有任意項的邏輯函數(shù)也稱為不完全確定的邏輯函數(shù)。這樣的函數(shù)在沒有完成設(shè)計前，有些輸入函數(shù)。這樣的函數(shù)在沒有完成設(shè)計前，有些輸入組合的輸出是沒有確定的。組合的輸出是沒有確定的。任意項的定義及表示任意項的定義及表示 任意項在最小項表達式或者最大項表達式中也可任意項在最小項表達式或者最大項表達式中也可以表示。以表示。 帶有任意項的函數(shù)的最小項表達式，可以寫為以帶有任意項的函數(shù)的最小項表達式，可以寫為以下的形式：下的形式：F= m (輸出

34、為輸出為1 的最小項的編號的最小項的編號) + d (輸出不指定輸出不指定的最小項的編號的最小項的編號) 帶有任意項的函數(shù)的最大項表達式，可以寫為以帶有任意項的函數(shù)的最大項表達式，可以寫為以下的形式：下的形式：F= M (輸出為輸出為0 的最大項的編號的最大項的編號) d (輸出不指定輸出不指定的最大項的編號的最大項的編號)用約束條件表示任意項用約束條件表示任意項 任意項有時候也可以用一個恒等于任意項有時候也可以用一個恒等于0的表達的表達式來表示，如式來表示，如 將恒等于將恒等于0的約束條件左邊的表達式展開為的約束條件左邊的表達式展開為最小項表達式，其中所包含的最小項就是最小項表達式，其中所包

35、含的最小項就是這個函數(shù)的任意項。這個函數(shù)的任意項。 對于三變量函數(shù)，以上約束條件展開為：對于三變量函數(shù)，以上約束條件展開為： 對應(yīng)于任意項：對應(yīng)于任意項： 是否可以用恒等于是否可以用恒等于1的表達式表示任意項？的表達式表示任意項？0BACBACBABACBA,CBA代數(shù)法化簡邏輯函數(shù)代數(shù)法化簡邏輯函數(shù) 邏輯函數(shù)化簡的標(biāo)準(zhǔn)邏輯函數(shù)化簡的標(biāo)準(zhǔn) 對于小規(guī)模邏輯電路而言，化簡的要求是使得對于小規(guī)模邏輯電路而言，化簡的要求是使得邏輯表達式中的項數(shù)（邏輯表達式中的項數(shù)（“與與”項或者項或者“或或”項）項）最少，并使得每項中的變量數(shù)最少。最少，并使得每項中的變量數(shù)最少。 還可以有其他的優(yōu)化標(biāo)準(zhǔn)還可以有其他的

36、優(yōu)化標(biāo)準(zhǔn) 低延遲低延遲 低扇入（集成電路的輸入引腳都是有限的）低扇入（集成電路的輸入引腳都是有限的）代數(shù)法化簡邏輯函數(shù)代數(shù)法化簡邏輯函數(shù) 1. 按基本定律、公式進行化簡按基本定律、公式進行化簡 代數(shù)法化簡邏輯函數(shù)代數(shù)法化簡邏輯函數(shù) 基本定律和公式結(jié)合代入規(guī)則進行化簡基本定律和公式結(jié)合代入規(guī)則進行化簡 代數(shù)法化簡邏輯函數(shù)代數(shù)法化簡邏輯函數(shù) 通過在表達式中增項通過在表達式中增項(拆項拆項 )，以便進一步簡化，以便進一步簡化 增項增項拆項拆項卡諾圖法化簡邏輯函數(shù)卡諾圖法化簡邏輯函數(shù) 卡諾圖是真值表的圖形表示。它和真值表卡諾圖是真值表的圖形表示。它和真值表具有相同的信息。具有相同的信息。 卡諾圖中將卡

37、諾圖中將n個輸入變量分為兩組，將兩組個輸入變量分為兩組，將兩組變量的取值按格雷碼排列于縱橫坐標(biāo)，每變量的取值按格雷碼排列于縱橫坐標(biāo)，每兩個相鄰的變量取值都只有一位的差別。兩個相鄰的變量取值都只有一位的差別。 一個一個n變量的卡諾圖有變量的卡諾圖有2n個小方格，每一個個小方格，每一個小方格對應(yīng)一個輸入的組合，或者說對應(yīng)小方格對應(yīng)一個輸入的組合，或者說對應(yīng)一個最小項或最大項。小方格中所填入的一個最小項或最大項。小方格中所填入的是相應(yīng)輸入組合下函數(shù)的輸出。是相應(yīng)輸入組合下函數(shù)的輸出。 卡諾圖法化簡邏輯函數(shù)卡諾圖法化簡邏輯函數(shù) 卡諾圖法化簡邏輯函數(shù)卡諾圖法化簡邏輯函數(shù) 四變量卡諾圖：四變量卡諾圖：卡諾

38、圖法化簡邏輯函數(shù)卡諾圖法化簡邏輯函數(shù) 五變量卡諾圖：五變量卡諾圖：卡諾圖法化簡邏輯函數(shù)卡諾圖法化簡邏輯函數(shù) 相鄰項：相鄰項：直接相鄰直接相鄰 兩端相鄰兩端相鄰鏡像相鄰鏡像相鄰鏡像相鄰鏡像相鄰兩端相鄰兩端相鄰卡諾圖法化簡邏輯函數(shù)卡諾圖法化簡邏輯函數(shù) 卡諾圖化簡邏輯函數(shù)的基本原理卡諾圖化簡邏輯函數(shù)的基本原理 相鄰項可以合并?；诠较噜忢椏梢院喜ⅰ；诠?輸入項可以重復(fù)使用?；诠捷斎腠椏梢灾貜?fù)使用?；诠紸+A=A 由相鄰項寫合并項由相鄰項寫合并項 2k個相鄰項也可以合并為一個與項。個相鄰項也可以合并為一個與項。 合并項由這些相鄰項中取值相同的變量組成：合并項由這些相鄰項中取值相同的變量組

39、成：變量值為變量值為1的寫為原變量，變量值為的寫為原變量，變量值為0的寫為反的寫為反變量。變量。 ABAAB卡諾圖法化簡邏輯函數(shù)卡諾圖法化簡邏輯函數(shù) 相鄰項：相鄰項：A=0,B=0,D=0,E=1,合并項合并項:EDBAB=0,C=0,D=1,E=1,合并項合并項:DECBC=1,D=1,E=0,合并項合并項:ECD卡諾圖法化簡邏輯函數(shù)卡諾圖法化簡邏輯函數(shù) 為了合并的需要，輸為了合并的需要，輸入項可以重復(fù)使用。入項可以重復(fù)使用。11111重用重用重用重用BACCA1邏輯函數(shù)的卡諾圖表示邏輯函數(shù)的卡諾圖表示 1）從真值表到卡諾圖）從真值表到卡諾圖 由邏輯函數(shù)的真值表或邏輯表達式作該邏由邏輯函數(shù)的

40、真值表或邏輯表達式作該邏輯函數(shù)卡諾圖的基本方法是：輯函數(shù)卡諾圖的基本方法是： 根據(jù)邏輯函數(shù)中變量的數(shù)目根據(jù)邏輯函數(shù)中變量的數(shù)目n，畫出，畫出n 個變個變量的卡諾圖量的卡諾圖 ； 在真值表中輸出為在真值表中輸出為1的最小項所對應(yīng)的卡諾的最小項所對應(yīng)的卡諾圖的圖的mi小方格中填入小方格中填入1，或者在真值表輸出，或者在真值表輸出為為0的最大項所對應(yīng)的的最大項所對應(yīng)的Mi的小方格填入的小方格填入0，就是該函數(shù)的卡諾圖。就是該函數(shù)的卡諾圖。 邏輯函數(shù)的卡諾圖表示邏輯函數(shù)的卡諾圖表示 例：畫出三人表決器所對應(yīng)的邏輯函數(shù)的真值表。例：畫出三人表決器所對應(yīng)的邏輯函數(shù)的真值表。z相應(yīng)的卡諾圖是：相應(yīng)的卡諾圖是

41、：邏輯函數(shù)的卡諾圖表示邏輯函數(shù)的卡諾圖表示 2）由非標(biāo)準(zhǔn)與或式填卡諾圖）由非標(biāo)準(zhǔn)與或式填卡諾圖 對于每個與項中不帶非的變量，和卡諾圖中相對于每個與項中不帶非的變量，和卡諾圖中相應(yīng)變量取值為應(yīng)變量取值為1的行或列對應(yīng)，每個帶非的變的行或列對應(yīng)，每個帶非的變量，和卡諾圖中相應(yīng)變量取值為量，和卡諾圖中相應(yīng)變量取值為0的行或列對的行或列對應(yīng)。在這些行、列相交的小格內(nèi)填應(yīng)。在這些行、列相交的小格內(nèi)填1； 對于每個與項都按以上方法填圖，如果小格已對于每個與項都按以上方法填圖，如果小格已經(jīng)有經(jīng)有1就不再重填。就不再重填。 所有沒有填所有沒有填1的格內(nèi)填入的格內(nèi)填入0。邏輯函數(shù)的卡諾圖表示邏輯函數(shù)的卡諾圖表示

42、 例例: 填寫函數(shù)填寫函數(shù)z解：先畫出解：先畫出3 3變量的卡諾圖。變量的卡諾圖。 的卡諾圖的卡諾圖11111對于對于AB，應(yīng)在，應(yīng)在A=B=1的各小方格內(nèi)填的各小方格內(nèi)填1。對 于對 于，應(yīng)在，應(yīng)在B=0,C=1的小方格內(nèi)填的小方格內(nèi)填1。對 于對 于，應(yīng)在，應(yīng)在A=1,C=0的小方格內(nèi)填的小方格內(nèi)填1。邏輯函數(shù)的卡諾圖表示邏輯函數(shù)的卡諾圖表示 3）由非標(biāo)準(zhǔn)或與式填卡諾圖）由非標(biāo)準(zhǔn)或與式填卡諾圖 對于每個或項中不帶非的變量，和卡諾圖對于每個或項中不帶非的變量，和卡諾圖中相應(yīng)變量取值為中相應(yīng)變量取值為0的行或列對應(yīng)，每個帶的行或列對應(yīng)，每個帶非的變量，和卡諾圖中相應(yīng)變量取值為非的變量，和卡諾圖

43、中相應(yīng)變量取值為1的的行或列對應(yīng)。在這些行、列相交的小格內(nèi)行或列對應(yīng)。在這些行、列相交的小格內(nèi)填填0； 對于每個與項都按以上方法填圖，如果小對于每個與項都按以上方法填圖，如果小格已經(jīng)有格已經(jīng)有0就不再重填。就不再重填。 所有沒有填所有沒有填0的格內(nèi)填入的格內(nèi)填入1。邏輯函數(shù)的卡諾圖表示邏輯函數(shù)的卡諾圖表示 例例: 填寫函數(shù)填寫函數(shù)F=z解：先畫出解：先畫出3 3變量的卡諾圖。變量的卡諾圖。 的卡諾圖的卡諾圖00000對 于對 于對 于對 于，應(yīng)在，應(yīng)在A=0,B=1的小方格內(nèi)填的小方格內(nèi)填0。對 于對 于，應(yīng)在，應(yīng)在B=1,C=0的小方格內(nèi)填的小方格內(nèi)填0。)CB)(BA)(CA（)CA（)B

44、A()CB(，應(yīng)在，應(yīng)在A=1,C=0的小方格內(nèi)填的小方格內(nèi)填0?？ㄖZ圖化簡的步驟卡諾圖化簡的步驟 卡諾圖化簡邏輯函數(shù)為最簡與或式的步驟：卡諾圖化簡邏輯函數(shù)為最簡與或式的步驟： 1）根據(jù)給定的函數(shù)表達式填畫卡諾圖；）根據(jù)給定的函數(shù)表達式填畫卡諾圖； 2）尋找只有一個合并方向的最小項，并圈出）尋找只有一個合并方向的最小項，并圈出盡可能大的合并項，寫出相應(yīng)的盡可能大的合并項，寫出相應(yīng)的“與與”項；項； 3）如果還有沒有圈入的）如果還有沒有圈入的“1”格，繼續(xù)進行合格，繼續(xù)進行合并，要求用盡可能少的合并項，來覆蓋這些最并，要求用盡可能少的合并項，來覆蓋這些最小項，寫出相應(yīng)的小項，寫出相應(yīng)的“與與”項

45、。項。 4）將合并時寫出的）將合并時寫出的“與與”項，組成與或式，項，組成與或式，就是化簡的結(jié)果。就是化簡的結(jié)果?？ㄖZ圖化簡的舉例卡諾圖化簡的舉例 化簡函數(shù)化簡函數(shù)F = m (0, 4, 5, 7, 9, 12, 13, 14)為最簡與或為最簡與或式。式。 作卡諾圖；作卡諾圖； 從只有一個合并方向的從只有一個合并方向的小格小格m0、m7、m9、m14出發(fā)選取合并項；出發(fā)選取合并項； 所有的所有的1已經(jīng)被圈入，組已經(jīng)被圈入，組成與或式就是結(jié)果成與或式就是結(jié)果: 11111111DCABDADABDCA卡諾圖化簡的舉例卡諾圖化簡的舉例 如果從選取最大合并項如果從選取最大合并項出發(fā)，就會是如圖的結(jié)

46、出發(fā)，就會是如圖的結(jié)果；果； 還要再選取還要再選取4個合并項；個合并項； 結(jié)果就出現(xiàn)冗余；結(jié)果就出現(xiàn)冗余； 所以一定要從只有一個所以一定要從只有一個合并方向的小格開始。合并方向的小格開始?？ㄖZ圖化簡的舉例卡諾圖化簡的舉例 化簡化簡 F= DCBCAABDDCBBA為最簡與或式。為最簡與或式。1ADDB1111111111BC 作卡諾圖；作卡諾圖； 從只有一個合并方向的從只有一個合并方向的小格小格m13、m7、m0出出發(fā)選取合并項；發(fā)選取合并項； 所有的所有的1已經(jīng)被圈入，組已經(jīng)被圈入，組成與或式就是結(jié)果成與或式就是結(jié)果: 卡諾圖化簡的舉例卡諾圖化簡的舉例 如果不是從只有一如果不是從只有一個合并

47、方向的格開個合并方向的格開始化簡，也可能得始化簡，也可能得到冗余的結(jié)果。到冗余的結(jié)果。 先圈出先圈出AC，最后就，最后就得到了得到了4項：有一項項：有一項是多余的。是多余的。ADDB11111111111BCAC卡諾圖化簡的舉例卡諾圖化簡的舉例 2單輸出最簡或與式單輸出最簡或與式 從卡諾圖上獲得最簡或與式的過程和獲得從卡諾圖上獲得最簡或與式的過程和獲得最簡與或式基本相似，但是有兩點不同：最簡與或式基本相似，但是有兩點不同： 1）選取合并項時要從卡諾圖上的）選取合并項時要從卡諾圖上的0格出發(fā)。格出發(fā)。合并項是這些圈入的合并項是這些圈入的0格中取值相同的變量格中取值相同的變量的邏輯或。但是要注意：

48、的邏輯或。但是要注意：變量值為變量值為0的寫為原的寫為原變量，變量值為變量，變量值為1的寫為反變量的寫為反變量。 2）由合并項相與構(gòu)成最簡）由合并項相與構(gòu)成最簡或與式或與式。 卡諾圖化簡的舉例卡諾圖化簡的舉例 例例2.26 試求函數(shù)試求函數(shù)F(A、B、C、D)=m (1, 5, 7, 8, 9, 10, 11, 14, 15)的最簡表達式。的最簡表達式。 解：當(dāng)題目中沒有明確指出是求哪一種最簡式時，需要解：當(dāng)題目中沒有明確指出是求哪一種最簡式時，需要求兩種簡化結(jié)果，選取最簡化的一個。求兩種簡化結(jié)果，選取最簡化的一個。1111111DCAACBDABA11最簡與或式是：最簡與或式是：BDADCA

49、BAACF卡諾圖化簡的舉例卡諾圖化簡的舉例 例例2.26 試求函數(shù)試求函數(shù)F(A、B、C、D)=m (1, 5, 7, 8, 9, 10, 11, 14, 15)的最簡表達式。的最簡表達式。 解：當(dāng)題目中沒有明確指出是求哪一種最簡式解：當(dāng)題目中沒有明確指出是求哪一種最簡式時，需要求兩種簡化結(jié)果，選取最簡化的一個。時，需要求兩種簡化結(jié)果，選取最簡化的一個。000000DACBACBA0最簡或與式是：最簡或與式是：)CBA)(CBA)(DA(F這也是本例題的最簡表達這也是本例題的最簡表達式。式?？ㄖZ圖化簡的舉例卡諾圖化簡的舉例 3帶有任意項的邏輯函數(shù)化簡帶有任意項的邏輯函數(shù)化簡 用卡諾圖化簡帶有任

50、意項的邏輯函數(shù)時，用卡諾圖化簡帶有任意項的邏輯函數(shù)時，可以根據(jù)化簡的需要，可以根據(jù)化簡的需要，將某些任意項的輸將某些任意項的輸出指定為出指定為1，或者指定為，或者指定為0。目的是使。目的是使得合并項可以更加簡單，從而得到更加簡得合并項可以更加簡單，從而得到更加簡單的化簡結(jié)果。單的化簡結(jié)果?？ㄖZ圖化簡的舉例卡諾圖化簡的舉例 例例2.27 用卡諾圖化簡函數(shù)用卡諾圖化簡函數(shù)F = m(2, 5, 7, 8, 10, 12, 13, 14, 15) + (1, 3, 11)為最簡與或式為最簡與或式 。 解：題目中有三個任意項，可以根據(jù)需要指定其輸出是解：題目中有三個任意項，可以根據(jù)需要指定其輸出是0或者是或者是1。111111BDCBDA11最簡