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

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

2、該系統(tǒng)滿足下列公理：,公理1交換律 A+B=B+A, A ? B=B ? A,公理2結(jié)合律 (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 邏輯變量及基本邏輯運(yùn)算,邏輯變量：僅取值0或取值1的變量。這里0和1無大小之分，實(shí)際上代表著矛盾的雙方或事件的真假，例如開關(guān)的接通與斷開，電壓的高和底，信號(hào)的有和無，電燈的亮和滅等等。 只要是兩種穩(wěn)定的物理狀態(tài)，都可以用0和1這兩種不同的邏輯值來表征。,一、"或"運(yùn)算,如果決定某一事件發(fā)生的多個(gè)條件，只要有一個(gè)或一個(gè)以上

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

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

6、邏輯代數(shù)中"與"邏輯關(guān)系用"與"運(yùn)算描述。"與"運(yùn)算又稱邏輯乘，其運(yùn)算符為"?"或"?"。兩變量的"與"運(yùn)算可表示為F＝A ? B 或者 F=A?B讀作"F等于A與B"，意思是若A ? B 均為1，則F為1；否則F為0。,"與"運(yùn)算表,由“與”運(yùn)算的運(yùn)算表可知“與”

7、運(yùn)算法則為：,0 ? 0 = 01 ? 0 = 00 ? 1 = 01 ? 1 = 1,實(shí)現(xiàn)“與”運(yùn)算的邏輯電路稱為“與”門。,三、"非"運(yùn)算,如果某一事件的發(fā)生取決于條件的否定，則這種因果關(guān)系稱為"非"邏輯。"非"邏輯用"非"運(yùn)算描述。"非"運(yùn)算又稱求反運(yùn)算，運(yùn)算符為"－"或"¬"

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

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

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

11、uot;或"的順序去括號(hào), 如：(AB)＋(CD)＝AB＋CD,例：,,邏輯表達(dá)式書寫省略規(guī)則：,二、真值表,真值表是一種由邏輯變量的所有可能取值組合及其對(duì)應(yīng)的邏輯函數(shù)值所構(gòu)成的表格.,三、卡諾圖,卡諾圖是一種用圖形描述邏輯函數(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ī)則,任何一個(gè)含有變量A的邏輯等式，如果將所有出現(xiàn)A的位置都代之以同一個(gè)邏輯函數(shù)F，則等式仍然成立。,二、反演規(guī)則,如果將邏輯函數(shù)F中所有的"

13、? "變成"+", "+"變成" ? ", "0"變成"1", "1"變成"0", 原變量變成反變量，反變量變成原變量，所得到的新函數(shù)是原函數(shù)的反函數(shù),使用反演規(guī)則時(shí), 應(yīng)注意保持原函式中運(yùn)算符號(hào)的優(yōu)先順序不變。,例如：已知,三、對(duì)偶規(guī)則,如果將邏輯函數(shù)F中所有的" ? &quo

14、t;變成"+", "+"變成" ? ", "0"變成"1", "1"變成"0", 則所得到的新邏輯函數(shù)F的對(duì)偶式F'。如果F'是F的對(duì)偶式，則F也是F' 的對(duì)偶式，即F與F'互為對(duì)偶式。,求某一函數(shù)F的對(duì)偶式時(shí)，同樣要注意保持原函數(shù)的運(yùn)算順序不變。,對(duì)偶規(guī)則：若兩個(gè)邏

15、輯函數(shù)F的G相等，則其對(duì)偶式F' 和G' 也相等。,2.3 邏輯函數(shù)表達(dá)式的形式與變換,2.3.1 邏輯函數(shù)表達(dá)式的基本形式,兩種基本形式："積之和"表達(dá)式與"和之積"表達(dá)式.,2.3.2 邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式,一、最小項(xiàng),如果一個(gè)具有n個(gè)變量的函數(shù)的"積"項(xiàng)包含全部n個(gè)變量, 每個(gè)變量都以原變量或反變量形式出現(xiàn), 且僅出現(xiàn)一次，則這個(gè)"積&

16、quot;項(xiàng)被稱為最小項(xiàng)。假如一個(gè)函數(shù)完全由最小項(xiàng)所組成, 那么該函數(shù)表達(dá)式稱為標(biāo)準(zhǔn)"積之和"表達(dá)式, 即"最小項(xiàng)之和".,三變量函數(shù)的最小項(xiàng)：,=m2+ m3+ m6+ m7,注意：變量的順序.,即n個(gè)變量的所有最小項(xiàng)之和恒等于1。,所以,=? m(2, 3, 6, 7),最小項(xiàng)的性質(zhì)：,1）當(dāng)函數(shù)以最小項(xiàng)之和形式表示時(shí)，可很容易列出函數(shù)及反函數(shù)的真值表（在真值表中，函數(shù)所包含的最小項(xiàng)填“1

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

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

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

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

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

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

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

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

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

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

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

28、項(xiàng)"稱為函數(shù)的蘊(yùn)涵項(xiàng)；,質(zhì)蘊(yùn)涵項(xiàng)：不被其它蘊(yùn)涵項(xiàng)所包含的蘊(yùn)涵項(xiàng)；,必要質(zhì)蘊(yùn)涵項(xiàng)：質(zhì)蘊(yùn)涵項(xiàng)中至少有一個(gè)最小項(xiàng)不被其它蘊(yùn)涵項(xiàng)所包含。,用卡諾圖化簡(jiǎn)邏輯函數(shù)的一般步驟為：,第一步：作出函數(shù)的卡諾圖；,第二步：在卡諾圖上圈出函數(shù)的全部質(zhì)蘊(yùn)涵項(xiàng)；,第三步：從全部質(zhì)蘊(yùn)涵項(xiàng)中找出所有必要質(zhì)蘊(yùn)涵項(xiàng)；,第四步：若全部必要質(zhì)蘊(yùn)涵項(xiàng)尚不能覆蓋所有的1 方格，則需從剩余質(zhì)蘊(yùn)涵項(xiàng)中找出最簡(jiǎn)的所需質(zhì)蘊(yùn)涵項(xiàng)，使它和必要質(zhì)蘊(yùn)涵項(xiàng)一起構(gòu)成函數(shù)的最小覆蓋。,例：

29、用卡諾圖化簡(jiǎn)邏輯涵數(shù) F(A, B, C, D)=?m(0, 3, 5, 6, 7, 10, 11, 13, 15),解：,例：用卡諾圖化簡(jiǎn)邏輯函數(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)化簡(jiǎn)成最簡(jiǎn)"或與"

30、表達(dá)式。,1,2.4.4 邏輯函數(shù)化簡(jiǎn)中兩個(gè)實(shí)際問題的考慮,一、包含無關(guān)最小項(xiàng)的邏輯函數(shù)的化簡(jiǎn),無關(guān)最小項(xiàng)：一個(gè)邏輯函數(shù), 如果它的某些輸入取值組合因受特殊原因制約而不會(huì)再現(xiàn), 或者雖然每種輸入取值組合都可能出現(xiàn), 但此時(shí)函數(shù)取值為1還是為0無關(guān)緊要, 那么這些輸入取值組合所對(duì)應(yīng)的最小項(xiàng)稱為無關(guān)最小項(xiàng)。,無關(guān)最小項(xiàng)可以隨意加到函數(shù)表達(dá)式中，或不加到函數(shù)表達(dá)式中，并不影響函數(shù)的實(shí)際邏輯功能。,例：給定某電路的邏輯函數(shù)真值表如下，求F的最

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