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

A+B=B+A,AB=BA公理2 結(jié)合律 (A+B)+C=A+(B+C),

(AB)C=A(BC)公理3 分配律

A+(B

C)=(A+B)(A+C),

A(

B+C)=AB+AC公理4 0－1律

A+0=A,A1=A

A+1=1,A0=0，公理5 互補律 A+A=1,AA=0第四頁，共九十頁，2022年，8月28日2.1.1邏輯變量及基本邏輯運算邏輯變量：僅取值0或取值1的變量。這里0和1無大小之分，實際上代表著矛盾的雙方或事件的真假，例如開關(guān)的接通與斷開，電壓的高和底，信號的有和無，電燈的亮和滅等等。只要是兩種穩(wěn)定的物理狀態(tài)，都可以用0和1這兩種不同的邏輯值來表征。第五頁，共九十頁，2022年，8月28日一、"或"運算如果決定某一事件發(fā)生的多個條件，只要有一個或一個以上的條件成立，事件便可發(fā)生，這種因果關(guān)系稱之為"或"邏輯。在邏輯代數(shù)中，"或"邏輯關(guān)系用"或"運算描述。"或"運算又稱邏輯加，其運算符為"+"或""，兩個變量的"或"運算可表示為:

F=A+B

或者F=AB讀作"F等于A或B",其中A、B是參加運算的兩個邏輯變量，F(xiàn)為運算結(jié)果。意思是：只要A、B中有一個為1，則F為1；僅當(dāng)A、B均為0時，F(xiàn)才為0。第六頁，共九十頁，2022年，8月28日ABF000011101111"或"運算表A+uBF由“或”運算的運算表可知“或”運算的法則為：0+0=0 1+0=10+1=1 1+1=1實現(xiàn)"或"運算的邏輯電路稱為"或"門。第七頁，共九十頁，2022年，8月28日二、"與"運算如果決定某一事件的發(fā)生的多個條件必須同時具備，事件才能發(fā)生，這種因果關(guān)系稱為"與"邏輯。邏輯代數(shù)中"與"邏輯關(guān)系用"與"運算描述。"與"運算又稱邏輯乘，其運算符為""或""。兩變量的"與"運算可表示為

F＝AB

或者F=AB

讀作"F等于A與B"，意思是若AB

均為1，則F為1；否則F為0。第八頁，共九十頁，2022年，8月28日ABF000010100111"與"運算表+uABF由“與”運算的運算表可知“與”運算法則為：00=0 10=0

01=0 11=1實現(xiàn)“與”運算的邏輯電路稱為“與”門。第九頁，共九十頁，2022年，8月28日三、"非"運算如果某一事件的發(fā)生取決于條件的否定，則這種因果關(guān)系稱為"非"邏輯。"非"邏輯用"非"運算描述。"非"運算又稱求反運算，運算符為"－"或"?"."非"運算可表示為F=A 或 F=?A讀作"F等于A非"，意思是若A＝0，則F為1；反之，若A=1,則F為0。第十頁，共九十頁，2022年，8月28日“非"運算表由“非”運算的運算表可知“非”運算法則為：A F0 11 0+uAF實現(xiàn)“非”運算的邏輯電路稱為“非”門。第十一頁，共九十頁，2022年，8月28日2.1.2邏輯函數(shù)一、邏輯函數(shù)的定義設(shè)某一電路的輸入邏輯變量為A1,A2,…,An,輸出邏輯變量為F。如果當(dāng)A1,A2,…,An

的值確定后，F(xiàn)的值就唯一地被定下來，則F稱為A1,A2,…,An,的邏輯函數(shù)，記為

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

(A1,A2,…,An)F2=f2

(A1,A2,…,An)若對應(yīng)于A1,A2,…,An的任何一組取值,F1和F2的值都相同,則稱函數(shù)F1和函數(shù)F2相等,記作F1=F2亦稱函數(shù)F1與F2等價。第十三頁，共九十頁，2022年，8月28日2.1.3邏輯函數(shù)的表示法一、邏輯表達式由邏輯變量、常量和邏輯運算符構(gòu)成的合法表達式。進行"非"運算可不加括號,如"與"運算符一般可省略,AB可寫成AB.可根據(jù)先"與"后"或"的順序去括號,如：

(AB)＋(CD)＝AB＋CD例：邏輯表達式書寫省略規(guī)則：第十四頁，共九十頁，2022年，8月28日第十五頁，共九十頁，2022年，8月28日二、真值表真值表是一種由邏輯變量的所有可能取值組合及其對應(yīng)的邏輯函數(shù)值所構(gòu)成的表格.例如：函數(shù)F=AB+AC的真值表如右所示：ABC F000 0001 1010 0011 1100 1101 1110 0111 0第十六頁，共九十頁，2022年，8月28日三、卡諾圖卡諾圖是一種用圖形描述邏輯函數(shù)的方法。第十七頁，共九十頁，2022年，8月28日2.2邏輯代數(shù)的基本定理和規(guī)則2.2.1基本定理定理1 0＋0＝0 1＋0＝1

0＋1＝1 1＋1＝1

00＝0 10＝001＝0 11＝1推論：1=00=1第十八頁，共九十頁，2022年，8月28日定理2(重疊律)

A＋A＝A AA＝A定理3(吸收律) A＋AB＝AA(A+B)＝A定理4(吸收律)

A＋AB＝A+B A(A+B)＝AB定理5(對合律)

A＝A 定理6(德摩根定理)

A＋B＝A·B AB＝A＋B定理7

AB+AB＝A (A+B)(A+B)＝A定理8(包含律)

AB+AC+BC＝AB+AC第十九頁，共九十頁，2022年，8月28日f(A1,A2,…,An)＋f(A1,A2,…,An)＝12.2.2邏輯代數(shù)的重要規(guī)則一、代入規(guī)則任何一個含有變量A的邏輯等式，如果將所有出現(xiàn)A的位置都代之以同一個邏輯函數(shù)F，則等式仍然成立。例如：給定邏輯等式A(B+C)=AB+AC，若用A+BC代替A，則該等式仍然成立，即：

(A+BC)(B+C)=(A+BC)B+(A+BC)C

由公理5(A+A=1)同樣有等式第二十頁，共九十頁，2022年，8月28日二、反演規(guī)則F＝(A+B)(C+D)例如：已知F＝AB＋CD，根據(jù)反演規(guī)可得到:

如果將邏輯函數(shù)F中所有的""變成"+","+"變成"","0"變成"1","1"變成"0",原變量變成反變量，反變量變成原變量，所得到的新函數(shù)是原函數(shù)的反函數(shù)使用反演規(guī)則時,應(yīng)注意保持原函式中運算符號的優(yōu)先順序不變。例如：已知第二十一頁，共九十頁，2022年，8月28日三、對偶規(guī)則如果將邏輯函數(shù)F中所有的""變成"+","+"變成"","0"變成"1","1"變成"0",則所得到的新邏輯函數(shù)F的對偶式F'。如果F'是F的對偶式，則F也是F'的對偶式，即F與F’互為對偶式。求某一函數(shù)F的對偶式時，同樣要注意保持原函數(shù)的運算順序不變。對偶規(guī)則：若兩個邏輯函數(shù)F的G相等，則其對偶式F'和G'

也相等。例:F=A+B+C

F’=A·B·C例:AB+AC+BC=AB+C則(A+B)?(A+C)?(B+C)=(A+B)?C第二十二頁，共九十頁，2022年，8月28日2.3邏輯函數(shù)表達式的形式與變換2.3.1邏輯函數(shù)表達式的基本形式兩種基本形式："積之和"表達式與"和之積"表達式."積之和"：由若干個"與"項經(jīng)"或"運算形成的表達式。例如："和之積"：由若干個"或"項經(jīng)"與"運算形成的表達式。例如：既不是與或表達式也不是或與表達式。而第二十三頁，共九十頁，2022年，8月28日2.3.2邏輯函數(shù)表達式的標(biāo)準(zhǔn)形式一、最小項如果一個具有n個變量的函數(shù)的"積"項包含全部n個變量,每個變量都以原變量或反變量形式出現(xiàn),且僅出現(xiàn)一次，則這個"積"項被稱為最小項。假如一個函數(shù)完全由最小項所組成,那么該函數(shù)表達式稱為標(biāo)準(zhǔn)"積之和"表達式,即"最小項之和".第二十四頁，共九十頁，2022年，8月28日變量的各組取值A(chǔ)BC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1對應(yīng)的最小項及其編號最小項編號三變量函數(shù)的最小項：第二十五頁，共九十頁，2022年，8月28日=m2+m3+m6+m7注意：變量的順序.即n個變量的所有最小項之和恒等于1。所以=m(2,3,6,7)第二十六頁，共九十頁，2022年，8月28日最小項的性質(zhì)：1）當(dāng)函數(shù)以最小項之和形式表示時，可很容易列出函數(shù)及反函數(shù)的真值表（在真值表中，函數(shù)所包含的最小項填“1”）。2）當(dāng)時，。3）n變量的最小項有n個相鄰項。相鄰項：只有一個變量不同（以相反的形式出現(xiàn)）。一對相鄰項可以消去一個變量。第二十七頁，共九十頁，2022年，8月28日二、最大項如果一個具有n個變量的函數(shù)的"和"項包含全部n個變量，每個變量都以原變量或反變量形式出現(xiàn)，且僅出現(xiàn)一次，則這個"和"項稱為最大項。假如一個函數(shù)完全由最大項組成，那么這個函數(shù)表達式稱為標(biāo)準(zhǔn)"和之積"表達式。第二十八頁，共九十頁，2022年，8月28日變量的各組取值A(chǔ)BC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1對應(yīng)的最大項及其編號最大項編號三變量函數(shù)的最大項：第二十九頁，共九十頁，2022年，8月28日注意：變量順序.與最小項類似，有例如：第三十頁，共九十頁，2022年，8月28日最大項的性質(zhì)：1）當(dāng)函數(shù)以最大項之積形式表示時，可很容易列出函數(shù)及反函數(shù)的真值表（在真值表中，函數(shù)所包含的最大項填“0”）。2）當(dāng)時，。3）n變量的最大項有n個相鄰項。相鄰項：只有一個變量不同（以相反的形式出現(xiàn)）。一對相鄰項可以消去一個變量。第三十一頁，共九十頁，2022年，8月28日三、兩種標(biāo)準(zhǔn)形式的轉(zhuǎn)換：以最小項之和的形式表示的函數(shù)可以轉(zhuǎn)換成最大項之積的形式，反之亦然。=m(2,3,6,7)F(A,B,C)=m(0,1,4,5)=(A+B+C)(A+B+C)(A+B+C)(A+B+C)F(A,B,C)=m(0,1,4,5)同理且有即：最大項與最小項互補。例如：M3=A+B+C=ABC=m3第三十二頁，共九十頁，2022年，8月28日2.3.3邏輯函數(shù)表達式的轉(zhuǎn)換任何一個邏輯函數(shù)，總可以將其轉(zhuǎn)換成"最小項之和"及"最大項之積"的形式,常用代數(shù)轉(zhuǎn)換法或真值表轉(zhuǎn)換法.第三十三頁，共九十頁，2022年，8月28日一、代數(shù)轉(zhuǎn)換法用代數(shù)法求一個函數(shù)"最小項之和"的形式，一般分為兩步：第一步：將函數(shù)表達式變換成一般的"與或"式.第二步：反復(fù)使用X=X(Y+Y)將非最小項的"與項"擴展為最小項。第三十四頁，共九十頁，2022年，8月28日例：將F(A,B,C)=(AB+BC)AB轉(zhuǎn)換成"最小項之和"形式第三十五頁，共九十頁，2022年，8月28日F(A,B,C)=m0+m1+m3+m6+m7=Σm(0,1,3,6,7)第三十六頁，共九十頁，2022年，8月28日類似地，用代數(shù)法求一個函數(shù)"最大項之積"的形式，也可分為兩步：第一步：將函數(shù)表達式轉(zhuǎn)換成一般"或與"式；如果給出的函數(shù)已經(jīng)是"與或"式或者是"或與"式，則可直接進行第二步。第二步：反復(fù)使用將非最大項的"或項"擴展成為最大項第三十七頁，共九十頁，2022年，8月28日例：將F(A,B,C)=AB+AC轉(zhuǎn)換成“最大項之積的形式。解：1）F(A,B,C)

=AB·AC=(A+B)(A+C)2)F(A,B,C)=(A+B+CC)(A+BB+C)=(A+B+C)(A+B+C)(A+B+C)(A+B+C)F(A,B,C)=M1·M3·M6·M7=ΠM(1,3,6,7)第三十八頁，共九十頁，2022年，8月28日二、真值表轉(zhuǎn)換法一個邏輯函數(shù)的真值表與它的最小項表達式和最大項表達式均存在一一對應(yīng)的關(guān)系。函數(shù)F的最小項表達式由使F取值為1的全部最小項之和組成。函數(shù)F的最大項表達式由使F取值為0的全部最大項之積組成。第三十九頁，共九十頁，2022年，8月28日和"最大項之積"的形式。解：ABC F000 0001 1010 0011 1100 1101 0110 0111 0注意：任何一個邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式唯一.第四十頁，共九十頁，2022年，8月28日2.4邏輯函數(shù)的簡化一般來說,邏輯函數(shù)表達式越簡單,設(shè)計出來的電路也就越簡單。把邏輯函數(shù)簡化成最簡形式稱為邏輯函數(shù)的最小化,有三種常用的方法,即代數(shù)化簡法、卡諾圖化簡法和列表化簡法。第四十一頁，共九十頁，2022年，8月28日2.4.1代數(shù)化簡法該方法運用邏輯代數(shù)的公理、定理和規(guī)則對邏輯函數(shù)進行推導(dǎo)、變換而進行化簡，沒有固定的步驟可以遵循，主要取決于對公理、定理和規(guī)則的熟練掌握及靈活運用的程度。有時很難判定結(jié)果是否為最簡。第四十二頁，共九十頁，2022年，8月28日一、"與或"式的化簡化簡應(yīng)滿足的兩個條件：1）表達式中"與項"的個數(shù)最少；2）在滿足1）的前提下,每個"與項"中的變量個數(shù)最少。第四十三頁，共九十頁，2022年，8月28日第四十四頁，共九十頁，2022年，8月28日二、"或與"式的化簡化簡應(yīng)滿足的兩個條件：1）表達式中"或項"的個數(shù)最少；2）在滿足1）的前提下,每個"或項"中的變量個數(shù)最少。第四十五頁，共九十頁，2022年，8月28日例：F=(A+B)(A+B)(B+C)(B+C+D)解：F=(A+B)(A+B)(B+C)(B+C+D)=（A+B)(A+B)(B+C)=A(B+C)例：F=(A+B)(A+B)(B+C)(A+C)解：F′=AB+AB+BC+AC=AB+AB+(B+A)C=AB+AB+ABC=AB+AB+CF=(F′)′=(A+B)(A+B)C第四十六頁，共九十頁，2022年，8月28日2.4.2卡諾圖化簡法該方法簡單、直觀、容易掌握,當(dāng)變量個數(shù)小于等于6時非常有效,在邏輯設(shè)計中得到廣泛應(yīng)用。一、卡諾圖的構(gòu)成n個變量的卡諾圖是一種由2n個方格構(gòu)成的圖形,每一個方格表示邏輯函數(shù)的一個最小項,所有的最小項巧妙地排列成一種能清楚地反映它們相鄰關(guān)系的方格陣列。因為任意一個邏輯函數(shù)都可表示成"最小項之和"的形式,所以一個函數(shù)可用圖形中若干方格構(gòu)成的區(qū)域來表示。第四十七頁，共九十頁，2022年，8月28日mo

m2m1

m30 101ABAB0 101二變量卡諾圖第四十八頁，共九十頁，2022年，8月28日mo

m2m6

m4m1

m3m7

m50001111001ABC0001111001ABC三變量卡諾圖第四十九頁，共九十頁，2022年，8月28日0001111000011110ABCD04

1281

5

1393715112614100001111000011110ABCD四變量卡諾圖第五十頁，共九十頁，2022年，8月28日定義：彼此只有一個變量不同，且這個不同變量互為反變量的兩個最小項(或"與項")稱為相鄰最小項(或相鄰"與項").相鄰最小項在卡諾圖中有三種特征，即幾何相鄰、相對相鄰和重疊相鄰。卡諾圖在構(gòu)造上具有以下兩個特點：1）n個變量的卡諾圖由2n個小方格組成,每個小方格代表一個最小項。2）卡諾圖上處在相鄰、相對、相重位置的小方格所代表的最小項為相鄰最小項。第五十一頁，共九十頁，2022年，8月28日二、邏輯函數(shù)的卡諾圖表示將邏輯函數(shù)所對應(yīng)的最小項在卡諾圖的相應(yīng)方格中標(biāo)以1，剩余方格標(biāo)以0或不標(biāo)。第五十二頁，共九十頁，2022年，8月28日1、"與或"式的卡諾圖表示.直接將表達式的"與項"或"最小項"所對應(yīng)的方格標(biāo)以1.0001111001ABC11111可表示為：例如：2、其它形式函數(shù)的卡諾圖表示要轉(zhuǎn)換成"與或"式再在卡諾圖上表示。第五十三頁，共九十頁，2022年，8月28日三、卡諾圖的性質(zhì)根據(jù)定理7有AB+AB=A,它表明兩個相鄰"與項"或"最小項"可以合并為一項，這一項由兩個"與項"中相同的變量組成，可以消去兩個"與項"中不同的變量。在卡諾圖上把相鄰最小項所對應(yīng)的小方格"圈"在一起可進行合并，以達到用一個簡單"與項"代替若干最小項的目的。這樣的"圈"稱為"卡諾圈"。第五十四頁，共九十頁，2022年，8月28日0 101AB110 101AB110 101AB111二變量卡諾圖的典型合并情況第五十五頁，共九十頁，2022年，8月28日0001111001ABC1111AB0001111001C1111111101ABC00011110三變量卡諾圖的典型合并情況第五十六頁，共九十頁，2022年，8月28日10001111000011110ABCD11111110001111000011110ABCD111111110001111000011110ABCD1111111111四變量卡諾圖的典型合并情況第五十七頁，共九十頁，2022年，8月28日一個卡諾圈中的小方格滿足以下規(guī)律：1）卡諾圈中的小方格的數(shù)目為2m,m為整數(shù)且mn;3）2m個小方格可用(n-m)個變量的"與項"表示,該"與項"由這些最小項中的相同變量構(gòu)成。2）2m個小方格含有m個不同變量和(n-m)個相同變量;4）當(dāng)m=n時,卡諾圈包圍整個卡諾圖,可用1表示，即n個變量的全部最小項之和為1。第五十八頁，共九十頁，2022年，8月28日四、卡諾圖化簡邏輯函數(shù)的步驟：蘊涵項："與或"式中的每一個"與項"稱為函數(shù)的蘊涵項；質(zhì)蘊涵項：不被其它蘊涵項所包含的蘊涵項；必要質(zhì)蘊涵項：質(zhì)蘊涵項中至少有一個最小項不被其它蘊涵項所包含。第五十九頁，共九十頁，2022年，8月28日用卡諾圖化簡邏輯函數(shù)的一般步驟為：第一步：作出函數(shù)的卡諾圖；第二步：在卡諾圖上圈出函數(shù)的全部質(zhì)蘊涵項；第三步：從全部質(zhì)蘊涵項中找出所有必要質(zhì)蘊涵項；第四步：若全部必要質(zhì)蘊涵項尚不能覆蓋所有的1方格，則需從剩余質(zhì)蘊涵項中找出最簡的所需質(zhì)蘊涵項，使它和必要質(zhì)蘊涵項一起構(gòu)成函數(shù)的最小覆蓋。第六十頁，共九十頁，2022年，8月28日例：用卡諾圖化簡邏輯涵數(shù)

F(A,B,C,D)=m(0,3,5,6,7,10,11,13,15)10001111000011110ABCD11111111解：第六十一頁，共九十頁，2022年，8月28日110001111000011110ABCD11111110001111000011110ABCD1*1111*1*1*1*1*第六十二頁，共九十頁，2022年，8月28日例：用卡諾圖化簡邏輯函數(shù)

F(A,B,C,D)=m(2,3,6,7,8,10,12)10001111000011110ABCD111111解：10001111000011110ABCD111111第六十三頁，共九十頁，2022年，8月28日0001111000011110ABCD1*1111*1*1*110001111000011110ABCD1*1*1*1*1第六十四頁，共九十頁，2022年，8月28日例：用卡諾圖把邏輯函數(shù)

F(A,B,C,D)=M(3,4,6,7,11,12,13,14,15)化簡成最簡"或與"表達式。第六十五頁，共九十頁，2022年，8月28日10001111000011110ABCD001001011001001第六十六頁，共九十頁，2022年，8月28日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ù)的實際邏輯功能。第六十七頁，共九十頁，2022年，8月28日ABCD F0000 d0001 d0010 d0011 10100 10101 10110 00111 01000 01001 01010 11011 11100 11101 d1110 d1111 d10001111000011110ABCD11111例：給定某電路的邏輯函數(shù)真值表如下，求F的最簡"與或"式。解：1)不考慮無關(guān)最小項：第六十八頁，共九十頁，2022年，8月28日110001111000011110ABCD1111dddddd2)考慮無關(guān)最小項：第六十九頁，共九十頁，2022年，8月28日二、多輸出邏輯函數(shù)的化簡.對于多輸出邏輯函數(shù)，如果孤立地將單個輸出一一化簡，然后直接拼在一起，通常并不能保證整個電路最簡，因為各個輸出函數(shù)之間往往存在可供共享的部分。多輸出邏輯函數(shù)化簡的標(biāo)準(zhǔn)：2）在滿足上述條件的前提下，各不同"與項"中所含的變量總數(shù)最少。1）所有邏輯表達式包含的不同"與項"總數(shù)最小；第七十頁，共九十頁，2022年，8月28日例：多輸出函數(shù).對應(yīng)的卡諾圖為10001111001ABC11F110001111001ABC11F2第七十一頁，共九十頁，2022年，8月28日從多輸出函數(shù)化簡的觀點來看，它們不是最佳的，應(yīng)該是：對應(yīng)的卡諾圖為10001111001ABC11F11110001111001ABCF2第七十二頁，共九十頁，2022年，8月28日列表化簡法

列表化簡法是Quine-Mccluskey提出的一種系統(tǒng)化簡法，故也稱作Q-M法，也稱作表格法。這種方法具有嚴(yán)格的算法，雖然其工作量大、方法繁瑣，但便于計算機化簡多變量邏輯函數(shù)。吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院第七十三頁，共九十頁，2022年，8月28日列表化簡法

Q-M法化簡邏輯函數(shù)的步驟如下：第一步，將函數(shù)表示成最小項表達式。第二步，找出函數(shù)的全部質(zhì)蘊涵項。1、將n變量函數(shù)中的相鄰最小項合并，消去相異的一個變量，得到(n-1)個變量的與項（蘊涵項）。這時如果存在不能合并的最小項，它便是所尋找的部分質(zhì)蘊涵項。2、再將相鄰的（n-1）個變量的與項合并，消去相異的一個變量，得到（n-2）個變量的與項（蘊涵項），這里如果存在不能合并的（n-1）個變量的與項，則它們也是所尋找的質(zhì)蘊涵項。如此進行下去，直到不能再合并為止。得全部的質(zhì)蘊涵項?！稊?shù)字邏輯電路》吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院第七十四頁，共九十頁，2022年，8月28日列表化簡法

第三步，找出函數(shù)的必要質(zhì)蘊涵項。先畫出質(zhì)蘊涵表，然后在表上找出僅屬于一個質(zhì)蘊涵項的最小項，則包含該最小項的質(zhì)蘊涵項就是必要質(zhì)蘊涵項。第四步，找出函數(shù)的最小覆蓋。當(dāng)?shù)谌秸页龅谋匾|(zhì)蘊涵項不能包含函數(shù)的全部最小項時，可以通過行、列消去法，找出最小覆蓋的其他必要質(zhì)蘊涵項。最小覆蓋指包含函數(shù)的全部最小項的最小質(zhì)蘊涵項集合。《數(shù)字邏輯電路》吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院第七十五頁，共九十頁，2022年，8月28日列表化簡法

用Q-M法化簡函數(shù):《數(shù)字邏輯電路》吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院

111111111ABCD0001111000011110第七十六頁，共九十頁，2022年，8月28日列表化簡法

（1）找出全部質(zhì)蘊涵項①做最小項分組表并找出不能合并者:將最小項mi按變量取值表示成二進制數(shù)；其次，再根據(jù)這些二進制數(shù)中所包含1的個數(shù)從少到多的次序進行分組排隊；最后，把含有1的個數(shù)相同的最小項劃分成一組，組內(nèi)按下標(biāo)i的取值從小到大排列，如此制成最小項分組。從含有1個數(shù)最少的那組開始，在相鄰組內(nèi)比較最小項，將只有一個變量值不同的兩個最小項合并，消去一個變量，并在已合并的最小項的右邊Pi欄內(nèi)做記號“√”，表示該項已被合并。在不能合并的最小項的右邊Pi欄內(nèi)填入P1，則就是所尋找的質(zhì)蘊涵項。注意合并最小項只能處于相鄰的兩組內(nèi)，而不能處于同組或隔組內(nèi)?！稊?shù)字邏輯電路》吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院第七十七頁，共九十頁，2022年，8月28日列表化簡法

《數(shù)字邏輯電路》吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院√1111154√√√011173√101010P110019√√√01106√√010152√√√01004√√√001021√√000000Pi變量ABCD最小項編號組號（1的個數(shù)）最小項分組表第七十八頁，共九十頁，2022年，8月28日列表化簡法

②做（n-1）個變量與項分組表并找出不能合并者:在最小項合并過程中，用符號“—”表示被消去的變量，這樣便得到若干個帶有“—”的與項，或稱作合并項。按照對最小項的分組方法，對帶有“—”的與項進行分組。對相鄰組中的“—”處于相同位置的那些與項進行合并，已合并的與項做記號“√”，并記入Pi欄；在不能合并的與項的Pi欄內(nèi)記入P2和P3，則

也是質(zhì)蘊涵項。《數(shù)字邏輯電路》吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院第七十九頁，共九十頁，2022年，8月28日列表化簡法

組號（1）最小項編號變量ABCDPi00200—0√040—00√1260—10√210—010P245010—√4601—0√√25701—1√67011—√3715—111P3《數(shù)字邏輯電路》吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院√1111154√√√011173√101010P110019√√√01106√√010152√√√01004√√√001021√√000000Pi變量ABCD最小項編號組號（1的個數(shù)）最小項分組表

（n-1）個變量與項分組表第八十頁，共九十頁，2022年，8月28日列表化簡法

③做（n-2）個變量與項分組表并找出不能合并者：在（n-1）個變量與項合并過程中，也用符號“—”表示被消去的變量，這樣便得到若干個帶有兩個“—”的與項。按照上述的分組方法，得到（n-2）個變量與項分組表。由表可以看出，僅有的兩（n-2）個變量與項不能再合并，在Pi欄內(nèi)分別記入P4和P5，P4和P5就是最后所尋找的質(zhì)蘊涵項?！稊?shù)字邏輯電路》吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院第八十一頁，共九十頁，2022年，8月28日列表化簡法

組號（1的個數(shù)）最小項編號變量ABCDPi

002460——0P41456701——P5《數(shù)字邏輯電路》吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院組號（1）最小項編號變量ABCDPi00200—0√040—00√1260—10√210—010P245010—√4601—0√√25701—1√67011—√3715—111P3（n-2）個變量與項分組表（n-1）個變量與項分組表第八十二頁，共九十頁，2022年，8月28日列表化簡法

④列出全部質(zhì)蘊涵項由上述分析可得全部質(zhì)蘊涵項：《數(shù)字邏輯電路》吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院第八十三頁，共九十頁，2022年，8月28日列表化簡法

（2）找出必要質(zhì)蘊涵項將函數(shù)的最小項和上述的質(zhì)蘊涵項做序列表，并在質(zhì)蘊涵項包含的最小項下面填入符號“×”,即做所謂質(zhì)蘊涵表。找出那些僅屬于一個質(zhì)蘊涵項的最小項，如m0僅屬于P4；m5僅屬于P5；m9僅屬于P1；m10僅屬于P2；m15僅屬于P3；并在相應(yīng)的×處加圓圈。質(zhì)蘊涵項P1～P5均包含一個不屬于其他質(zhì)蘊涵項的最小項，即它們均包含一個，所以它們均為必要質(zhì)蘊涵項，并在其左邊加“﹡”號?！稊?shù)字邏輯電路》吉