邏輯代數(shù)基礎(chǔ).ppt

1、,邏 輯 代 數(shù) 基 礎(chǔ),第 二 章,邏輯代數(shù)是數(shù)子系統(tǒng)邏輯設計的理論基礎(chǔ)和重要數(shù)學工 具！,1847年,英國數(shù)學家喬治布爾(G.Boole)提出了用數(shù)學分析方法表示命題陳述的邏輯結(jié)構(gòu)，并將形式邏輯歸結(jié)為一種代數(shù)演，從而誕生了著名的“布爾代數(shù)”。 1938年，克勞德向農(nóng)(C.E.Shannon)將布爾代數(shù)應用于電話繼電器的開關(guān)電路，提出了“開關(guān)代數(shù)”。 隨著電子技術(shù)的發(fā)展，集成電路邏輯門已經(jīng)取代了機械觸點開關(guān)，故人們更習慣于把開關(guān)代數(shù)叫 做邏輯代數(shù)。,本章知識要點： 基本概念 ； 基本定理和規(guī)則 ； 邏輯函數(shù)的表示形式 ； 邏輯函數(shù)的化簡 。,邏輯代數(shù)L是一個封閉的代數(shù)系統(tǒng)，它由一個邏輯變量集

2、K，常量0和1以及“或”、“與”、“非”三種基本運算所構(gòu)成，記為L=K,+,-,0,1。該系統(tǒng)應滿足下列公理。,2.1 邏輯代數(shù)的基本概念,公 理 1 交 換 律 對于任意邏輯變量A、B，有 A + B = B + A；AB = B A,公 理 2 結(jié) 合 律 對于任意的邏輯變量A、B、C，有 (A + B) + C = A + ( B + C ) ( AB ) C = A( B C ),公 理 3 分 配 律 對于任意的邏輯變量A、B、C，有 A + ( BC ) = (A + B)(A + C) ； A( B + C) = AB + AC,公 理 4 01 律 對于任意邏輯變量A，有 A

3、+ 0 = A ； A 1 = A A + 1 = 1 ； A 0 = 0,公理是一個代數(shù)系統(tǒng)的基本出發(fā)點，無需加以證明。,公 理 5 互 補 律 對于任意邏輯變量A，存在唯一的，使得,2.1.1 邏輯變量及基本邏輯運算,邏輯代數(shù)和普通代數(shù)一樣，是用字母表示其值可以變化的量，即變量。所不同的是：,1任何邏輯變量的取值只有兩種可能性取值0或取值1。,2邏輯值0和1是用來表征矛盾的雙方和判斷事件真?zhèn)蔚男问椒枺瑹o大小、正負之分。,一、變量,二、基本邏輯運算,描述一個數(shù)字系統(tǒng)，必須反映一個復雜系統(tǒng)中各開關(guān)元件之間的聯(lián)系，這種相互聯(lián)系反映到數(shù)學上就是幾種運算關(guān)系。 邏輯代數(shù)中定義了“或”、“與” 、“

4、非”三種基本運算。,1“或”運算 如果決定某一事件是否發(fā)生的多個條件中，只要有一個或一個以上條件成立，事件便可發(fā)生，則這種因果關(guān)系稱之為“或”邏輯。,例如，用兩個開關(guān)并聯(lián)控制一個燈的照明控制電路。,電路中，開關(guān)A和B并聯(lián)控制燈F?？梢钥闯?，當開關(guān)A、B中有一個閉合或者兩個均閉合時，燈F即亮。因此，燈F與開關(guān)A、B之間的關(guān)系是“或”邏輯關(guān)系?？杀硎緸?例如，下圖所示電路。,F = A + B或者F = A B，讀作“F等于A或B”。,假定開關(guān)斷開用0表示，開關(guān)閉合用1表示；燈滅用0表示，燈亮用1表示，則燈F與開關(guān)A、B的關(guān)系如下表所示。 即：A、B中只要有一個為1，則F為1；僅當A、B均為0時，

5、F才為0。,“或”運算的運算法則： 0 + 0 = 01 + 0 = 1 0 + 1 = 11 + 1 = 1 實現(xiàn)“或”運算關(guān)系的邏輯電路稱為“或”門。,2“與” 運算 如果決定某一事件發(fā)生的多個條件必須同時具備，事 件才能發(fā)生，則這種因果關(guān)系稱之為“與”邏輯。 在邏輯代數(shù)中，“與”邏輯關(guān)系用“與”運算描述。兩變量“與”運算關(guān)系可表示為 F = AB或者F = AB 即：若A、B均為1，則F為1；否則，F(xiàn)為0。,例如，兩個開關(guān)串聯(lián)控制同一個燈。顯然，僅當兩個開關(guān)均閉合時，燈才能亮，否則，燈滅。 假定開關(guān)閉合狀態(tài)用1表示，斷開狀態(tài)用0表示，燈亮用1 表示，燈滅用0表示，則F和A、B之間的關(guān)系

6、“與”運算關(guān)系。,數(shù)字系統(tǒng)中，實現(xiàn)“與”運算關(guān)系的邏輯電路稱為“與”門。,“與”運算的運算法則: 0 0 = 01 0 = 0 0 1 = 01 1 = 1,3“非” 運算 如果某一事件的發(fā)生取決于條件的否定，即事件與事件發(fā)生的條件之間構(gòu)成矛盾，則這種因果關(guān)系稱為“非”邏輯。 在邏輯代數(shù)中，“非”邏輯用“非”運算描述。其運算符 號為“”，有時也用“”表示?！胺恰边\算的邏輯關(guān)系可 表示為F = 或者 F = A 讀作“F等于A非”。 即：若A為0，則F為1；若A為1，則F為0。,例如，下面開關(guān)與燈并聯(lián)的電路中，僅當開關(guān)斷開時，燈亮；一旦開關(guān)閉合，則燈滅。令開關(guān)斷開用0表示，開關(guān)閉合用1表示，燈亮

7、用1表示，燈滅用0表示，則電路中燈F與開關(guān)A的關(guān)系即為上表所示“非”運算關(guān)系。,“非”運算的運算法則： ； 數(shù)字系統(tǒng)中實現(xiàn)“非”運算功能的邏輯電路稱為“非”門， 有時又稱為“反相器”。,2.1.2 邏輯函數(shù)及邏輯函數(shù)間的相等,邏輯代數(shù)中函數(shù)的定義與普通代數(shù)中函數(shù)的定義類似，即隨自變量變化的因變量。但和普通代數(shù)中函數(shù)的概念相比，邏輯函數(shù)具有如下特點：,1邏輯函數(shù)和邏輯變量一樣，取值只有0和1兩種可能 ；,2函數(shù)和變量之間的關(guān)系是由“或”、“與”、“非”三種基本運算決定的 。,一、邏輯函數(shù)的定義,圖中，F(xiàn)被稱為A1，A2，An的邏輯函數(shù)，記為 F = f( A1，A2，An ),邏輯電路輸出函數(shù)的

8、取值是由邏輯變量的取值和電路本身的結(jié)構(gòu)決定的。,設某一邏輯電路的輸入邏輯變量為A1，A2，An，輸出邏輯變量為F，如下圖所示。,邏輯函數(shù)和普通代數(shù)中的函數(shù)一樣存在是否相等的問題。設有兩個相同變量的邏輯函數(shù) F1 = f1( A 1,A 2, ,A n) F2 = f2( A 1,A 2, ,A n) 若對應于邏輯變量 A1 ,A2 , , An的任何一組取值，F(xiàn)1和F2的值都相同，則稱函數(shù)F1和F2相等，記作F1 = F2 。,如何判斷兩個邏輯函數(shù)是否相等？ 通常有兩種方法：真值表法，代數(shù)法。,2.1.3 邏輯函數(shù)的表示法,函數(shù)F和變量A、B的關(guān)系是： 當變量A和B取值不同時，函數(shù)F的值為“1

9、”； 取值相同時，函數(shù)F的值為“0”。,邏輯表達式是由邏輯變量和“或”、“與”、“非” 3種運算符以及括號所構(gòu)成的式子。例如,一、邏輯表達式,如何對邏輯功能進行描述？ 常用的方法有邏輯表達式、真值表、卡諾圖3種。,邏輯表達式的簡寫:,1.“非”運算符下可不加括號，如 ， 等。,2.“與”運算符一般可省略，如AB可寫成AB。,4.(A+B)+C或者A+(B+C)可用A+B+C代替；(AB)C或者 A(BC)可用ABC代替。,二、真值表,依次列出一個邏輯函數(shù)的所有輸入變量取值組合及其相應函數(shù)值的表格稱為真值表。一個n個變量的邏輯函數(shù)，其真值表有2n行。例如，,真值表由兩部分組成： 左邊一欄列出變量

10、的所有取值組合，為了不發(fā)生遺漏，通常各變量取值組合按二進制數(shù)碼順序給出；右邊一欄為邏輯函數(shù)值。,三、卡諾圖,卡諾圖是由表示邏輯變量所有取值組合的小方格所構(gòu)成的平面圖。 這種用圖形描述邏輯函數(shù)的方法，在邏輯函數(shù)化簡中十分有用，將在后面結(jié)合函數(shù)化簡問題進行詳細介紹。,描述邏輯邏輯函數(shù)的3種方法可用于不同場合。但針對某個具體問題而言，它們僅僅是同一問題的不同描述形式，相互之間可以很方便地進行變換。,2 .2 邏輯代數(shù)的基本定理和規(guī)則,常用的組定理：,2.2.1 基本定理,定理1 0 + 0 = 01 + 0 = 10 0 = 01 0 = 0 0 + 1 = 11 + 1 = 10 1 = 01 1

11、 = 1,證明：在公理4中，A表示集合K中的任意元素，因而可以是0或1。用0和1代入公理4中的A，即可得到上述關(guān)系。,如果以1和0代替公理5中的A，則可得到如下推論：,證明A+AB = A1+AB 公理4 = A (1+B)公理3 = A (B+1) 公理1 = A1公理4 = A公理4,定理2A + A = A ；A A = A,定理3A + A B = A；A ( A + B ) = A,定理7AB + A = A ( A + B ) ( A+ ) = A,第二章 邏輯代數(shù)基礎(chǔ),2.2.2 重要規(guī)則,邏輯代數(shù)有3條重要規(guī)則。,例如，將邏輯等式A(B+C)=AB+AC中的C都用(C+D)代替

12、，該邏輯等式仍然成立，即 AB+(C+D)= AB+A(C+D) 代入規(guī)則的正確性是顯然的，因為任何邏輯函數(shù)都和邏 輯變量一樣，只有0和1兩種可能的取值。,任何一個含有變量A的邏輯等式,如果將所有出現(xiàn)A的位 置都代之以同一個邏輯函數(shù)F，則等式仍然成立。這個規(guī)則 稱為代入規(guī)則。,一、代入規(guī)則,代入規(guī)則的意義： 利用代入規(guī)則可以將邏輯代數(shù)公理、定理中的變量用任 意函數(shù)代替，從而推導出更多的等式。這些等式可直接當作 公使用，無需另加證明。,注意：使用代入規(guī)則時,必須將等式中所有出現(xiàn)同一變量的地方均以同一函數(shù)代替，否則代入后的等式將不成立。,二、反演規(guī)則,例如，已知函數(shù)，根據(jù)反演規(guī)則可得到,若將邏輯函

13、數(shù)表達式F中所有的“”變成“+”，“+”變 成“”,“0”變成“1”,“1”變成“0”,原變量變成反變量，反變 量變成原變量，并保持原函數(shù)中的運算順序不變，則所 得到的新的函數(shù)為原函數(shù)F的反函數(shù)。,注意: 使用反演規(guī)則時，應保持原函數(shù)式中運算符號的優(yōu)先順序不變！,三、對偶規(guī)則,如果將邏輯函數(shù)表達式F中所有的“”變成“+”,“+”變成 “”，“0”變成“1”，“1”變成“0”，并保持原函數(shù)中的運算順 序不變，則所得到的新的邏輯表達式稱為函數(shù)F的對偶式， 并記作F。例如，,例如，已知函數(shù)，根據(jù)反演規(guī)則 得到的反函數(shù)應該是 而不應該是！錯誤,注意:求邏輯表達式的對偶式時，同樣要保持原函數(shù)的運算順序不

14、變。,顯然，利用對偶規(guī)則可以使定理、公式的證明減少一半。,若兩個邏輯函數(shù)表達式F和G相等，則其對偶式F和G也相等。這一規(guī)則稱為對偶規(guī)則。 根據(jù)對偶規(guī)則，當已證明某兩個邏輯表達式相等時，即可知道它們的對偶式也相等。,例如，已知AB+ C+BC=AB+ C，根據(jù)對偶規(guī)則對等式兩 端的表達式取對偶式，即可得到等式 (A+B)( +C)(B+C)=(A+B)( +C),2.2.3 復合邏輯,實際應用中廣泛采用“與非”門、“或非”門、“與或非”門、“異或”門等門電路。這些門電路輸出和輸入之間的邏輯關(guān)系可由3種基本運算構(gòu)成的復合運算來描述，故通常將這種邏輯關(guān)系稱為復合邏輯，相應的邏輯門則稱為復合門。,一、

15、與非邏輯,與非邏輯是由與、非兩種邏輯復合形成的，可用邏輯函 數(shù)表示為 邏輯功能：只要變量A、B、C、中有一個為0，則函數(shù) F為1；僅當變量A、B、C、全部為1時，函數(shù)F為0。 實現(xiàn)與非邏輯的門電路稱為“與非”門。,只要有了與非門便可組成實現(xiàn)各種邏輯功能的電路，通常稱與非門為通用門。,與:,或:,非:,使用與非門可以實現(xiàn)與、或、非三種基本運算：,二、或非邏輯,邏輯功能：只要變量A、B、C中有一個為1，則函數(shù)F為0；僅當變量A、B、C全部為0時，函數(shù)F為1。實現(xiàn)或非邏輯的門電路稱為“或非”門。,或非邏輯是由或、非兩種邏輯復合形成的，可表示為,與：,或:,非: ,或非門同樣可實現(xiàn)各種邏輯功能，是一種

16、通用門。,同樣，或非邏輯也可以實現(xiàn)與、或、非3種基本邏輯。以兩變量或非邏輯為例：,三、與或非邏輯,邏輯功能：僅當每一個“與項”均為0時，才能使F為1， 否則F為0。 實現(xiàn)與或非功能的門電路稱為“與或非”門。,顯然，可以僅用與或非門去組成實現(xiàn)各種功能的邏輯電路。 但實際應用中這樣做一般會很不經(jīng)濟，所以，與或非門主要用 來實現(xiàn)與或非形式的函數(shù)。必要時可將邏輯函數(shù)表達式的形式 變換成與或非的形式。,與或非邏輯是由3種基本邏輯復合形成的，邏輯函數(shù)表達 式的形式為,四、異或邏輯及同或邏輯,邏輯功能：變量A、B取值相同，F(xiàn)為0；變量A、B取值 相異，F(xiàn)為1。 實現(xiàn)異或運算的邏輯門稱為“異或門”。,1異或邏

17、輯,當多個變量進行異或運算時，可用兩兩運算的結(jié)果再運算，也可兩兩依次運算。,異或邏輯是一種兩變量邏輯關(guān)系，可用邏輯函數(shù)表示為,根據(jù)異或邏輯的定義可知： A 0 = AA 1 = A A = 0A = 1,注意：在進行異或運算的多個變量中，若有奇數(shù)個變量的值為1，則運算結(jié)果為1；若有偶數(shù)個變量的值為1，則運算結(jié)果為0。,例如， F = A B C D = (A B) (C D)(兩兩運算的結(jié)果再運算) =(A B) C D(兩兩依次運算),2同或邏輯,同或邏輯也是一種兩變量邏輯關(guān)系，其邏輯函數(shù)表達式為,功能邏輯：變量A、B取值相同，F(xiàn)為1；變量A、B取值相異，F(xiàn)為0。 實現(xiàn)同或運算的邏輯門稱為“

18、同或門” 。,F = A B = + AB 式中，“”為同或運算的運算符。,同或邏輯與異或邏輯的關(guān)系既互為相反，又互為對偶。即有：,由于同或?qū)嶋H上是異或之非，所以實際應用中通常用異或門加非門實現(xiàn)同或運算。,注意：當多個變量進行同或運算時，若有奇數(shù)個變量的值為0，則運算結(jié)果為0；反之，若有偶數(shù)個變量的值為0，則運算結(jié)果為1。,2.3 邏輯函數(shù)表達式的形式與變換,任何一個邏輯函數(shù)，其表達式的形式都不是唯一的。下面介紹邏輯函數(shù)表達式的基本形式、標準形式及其相互轉(zhuǎn)換。,2.3.1 邏輯函數(shù)表達式的兩種基本形式,兩種基本形式：指“與-或”表達式和“或-與”表達式。,一、“與-或”表達式,“與-或”表達式

19、：是指由若干“與項”進行“或”運算構(gòu)成的表達式。例如，,“與項”有時又被稱為“積項”，相應地“或與”表達式又稱為“積之和”表達式。,二、“或-與”表達式,“或項”有時又被稱為“和項”，相應地“或與”表達式又稱為“和之積”表達式。,“或-與”表達式：是指由若干“或項”進行“與”運算構(gòu)成的表達式。例如，,該函數(shù)既不是“與或”式？也不是“或與”式！,2.3.2 邏輯函數(shù)表達式的標準形式,邏輯函數(shù)表達式可以被表示成任意的混合形式。例如，,邏輯函數(shù)的基本形式都不是唯一的。例如,為了在邏輯問題的研究中使邏輯功能能和唯一的邏輯表達式對應，引入了邏輯函數(shù)表達式的標準形式。邏輯函數(shù)表達式的標準形式是建立在最小項

20、和最大項概念的基礎(chǔ)之上的。,一、最小項和最大項,（1）定義：如果一個具有n個變量的函數(shù)的“與項”包含全部n個變量，每個變量都以原變量或反變量形式出現(xiàn)一次，且僅出現(xiàn)一次，則該“與項”被稱為最小項。有時又將最小項稱為標準“與項”。,1最小項,（3）簡寫：用mi表示最小項。下標i的取值規(guī)則是：按照變量順序?qū)⒆钚№椫械脑兞坑?表示，反變量用0表示，由此得到一個二進制數(shù)，與該二進制數(shù)對應的十進制數(shù)即下標i的值。,（2）最小項的數(shù)目：n個變量可以構(gòu)成2n個最小項。,例如，3個變量A、B、C可以構(gòu)成、 A B C共8個最小項。,在由n個變量構(gòu)成的任意“與項”中，最小項是使其值為1的變量取值組合數(shù)最少的一種

21、“與項”，這也就是最小項名字的由來。,（4） 性質(zhì) 最小項具有如下四條性質(zhì)。 性質(zhì)1： 任意一個最小項，其相應變量有且僅有一種取值使這個最小項的值為1。并且，最小項不同，使其值為1的變量取值不同。,性質(zhì)3： n個變量的全部最小項相“或”為1。 通常借用數(shù)學中的累加符號“”，將其記為,性質(zhì)2： 相同變量構(gòu)成的兩個不同最小項相“與” 為0。因為任何一種變量取值都不可能使兩個不同最小項同時為1，故相“與”為0。即mi mj = 0,性質(zhì)4： n個變量構(gòu)成的最小項有n個相鄰最小項。相鄰最小項：是指除一個變量互為相反外，其余部分 均相同的最小項。例如 ，三變量最小項A B C和相 鄰 。,定義：如果一個

22、具有n個變量函數(shù)的“或項”包含全部n個變量，每個變量都以原變量或反變量形式出現(xiàn)一次，且僅出現(xiàn)一次，則該“或項”被稱為最大項。有時又將最大項稱為標準“或項”。,2最大項,數(shù)目：n個變量可以構(gòu)成2n 個最大項。 例如，3個變量A、B、C可構(gòu)成、 共8個最大項。,性質(zhì)：最大項具有如下四條性質(zhì)。,性質(zhì)1 任意一個最大項，其相應變量有且僅有一種取值使這個最大項的值為0。并且，最大項不同，使其值為0的變量取值不同。,在n個變量構(gòu)成的任意“或項”中，最大項是使其值為1的變量取值組合數(shù)最多的一種“或項”，因而將其稱為最大項。,性質(zhì)2 相同變量構(gòu)成的兩個不同最大項相“或”為1。 因為任何一種變量取值都不可能使兩

23、個不同最大項同時為 0，故相“或”為1。 即 M i + M j = 1,性質(zhì)3 n個變量的全部最大項相“與”為0。通常借用數(shù)學中的累乘符號“”將其記為,性質(zhì)4 n個變量構(gòu)成的最大項有n個相鄰最大項。相鄰最大項是指除一個變量互為相反外，其余變量均相同的最大項。,兩變量最小項、最大項的真值表如下。,真值表反映了最小項、最大項的有關(guān)性質(zhì)。,3最小項和最大項的關(guān)系,在同一問題中，下標相同的最小項和最大項互為反函數(shù)?；蛘哒f，相同變量構(gòu)成的最小項mi和最大項Mi之間存在互補關(guān)系。即 或者,例如，由3變量A、B、C構(gòu)成的最小項m3和最大項M3之間有,二、邏輯函數(shù)表達式的標準形式,邏輯函數(shù)表達式的標準形式有

24、標準“與-或”表達式和標準“或-與”表達式兩種類型。,1標準“與 - 或”表達式,由若干最小項相“或”構(gòu)成的邏輯表達式稱為標準“與-或”表達式，也叫做最小項表達式。,該函數(shù)表達式又可簡寫為 F(A，B，C) = m1 + m2 + m4 + m7 =,例如，如下所示為一個3變量函數(shù)的標準“與-或”表達式,2標準“或-與”表達式,由若干最大項相“與”構(gòu)成的邏輯表達式稱為標準“或-與”表達式，也叫做最大項表達式 。,該表達式又可簡寫為,例如， 、 、 為3變量構(gòu)成的3個最大項，對這3個最大項進行“與”運算，即可得到一個3變量函數(shù)的標準“或-與”表達式,2.3.3 邏輯函數(shù)表達式的轉(zhuǎn)換,將一個任意邏

25、輯函數(shù)表達式轉(zhuǎn)換成標準表達式有兩種常用方法。,一、代數(shù)轉(zhuǎn)換法,1 . 求標準“與-或” 式,一般步驟如下： 第一步：將函數(shù)表達式變換成一般“與-或”表達式。,所謂代數(shù)轉(zhuǎn)換法，就是利用邏輯代數(shù)的公理、定理和規(guī)則進行邏輯變換，將函數(shù)表達式從一種形式變換為另一種形式。,第二步：反復使用將表達式中所有非 最小項的“與項”擴展成最小項。,例 將邏輯函數(shù)表達式 轉(zhuǎn)換成標準“與-或”表達式。,解 第一步：將函數(shù)表達式變換成“與-或”表達式。即,第二步：把“與-或”式中非最小項的“與項”擴展成最小 項。,所得標準“與-或”式的簡寫形式為,當給出函數(shù)表達式已經(jīng)是“與-或”表達式時，可直接進行第二步。,2 . 求

26、一個函數(shù)的標準“或-與” 式,一般步驟： 第一步：將函數(shù)表達式轉(zhuǎn)換成一般“或-與”表達式。,第二步：反復利用定理把表達式中 所有非最大項的“或項”擴展成最大項。,解 第一步：將函數(shù)表達式變換成“或-與”表達式。即,例 將邏輯函數(shù)表達式變 換成標準“或-與”表達式。,第二步：將所得“或-與”表達中的非最大項擴展成最大項。即,當給出函數(shù)已經(jīng)是“或-與”表達式時，可直接進行第二步。,該標準“或-與”表達式的簡寫形式為,二、真值表轉(zhuǎn)換法,具體：真值表上使函數(shù)值為1的變量取值組合對應的最小項相“或”,即可構(gòu)成一個函數(shù)的標準“與-或”式 。,邏輯函數(shù)的最小項表達式與真值表具有一一對應的關(guān)系。 假定函數(shù)F的

27、真值表中有k組變量取值使F的值為1，其他變量取值下F的值為0，那么，函數(shù)F的最小項表達式由這k組變量取值對應的k個最小項相或組成。,1 . 求標準“與-或” 式,解:首先，列出F的真值表如下表所示，然后，根據(jù)真 值表可直接寫出F的最小項表達式,例 將函數(shù)表達式變換成標準 “與-或”表達式。,具體：真值表上使函數(shù)值為0的變量取值組合對應的最大項相“與”即可構(gòu)成一個函數(shù)的標準“或-與”式 。,2 . 求一個函數(shù)的標準“或-與” 式 邏輯函數(shù)的最大項表達式與真值表之間同樣具有一一 對應的關(guān)系。 假定在函數(shù)F的真值表中有p組變量取值使F的值為0，其他變量取值下F的值為1，那么，函數(shù)F的最大項表達式由這

28、p組變量取值對應的p個最大項“相與”組成。,解：首先，列出F的真值表如下表所示。然后，根據(jù)真 值表直接寫出F的最大項表達式,例 將函數(shù)表達式 表示成最大項表達式的形式。,由于函數(shù)的真值表與函數(shù)的兩種標準表達式之間存在一一對應的關(guān)系，而任何個邏輯函數(shù)的真值表是唯一的，可見，任何一個邏輯函數(shù)的兩種標準形式也是唯一的。 邏輯函數(shù)表達式的唯一性給我們分析和研究邏輯問題帶來了很大的方便。,2.4 邏輯函數(shù)化簡,實現(xiàn)某一邏輯功能的邏輯電路的復雜性與描述該功能的邏輯表達式的復雜性直接相關(guān)。為了降低系統(tǒng)成本、減小復雜度、提高可靠性，必須對邏輯函數(shù)進行化簡。,由于“與-或”表達式和“或-與”表達式可以很方便地轉(zhuǎn)

29、換成任何其他所要求的形式。因此，從這兩種基本形式出發(fā)討論函數(shù)化簡問題，并將重點放在“與-或”表達式的化簡上。,邏輯函數(shù)化簡有3種常用方法。即：代數(shù)化簡法、卡諾圖化簡法和列表化簡法。,2.4.1 代數(shù)化簡法,代數(shù)化簡法就是運用邏輯代數(shù)的公理、定理和規(guī)則對邏輯函數(shù)進行化簡的方法。,一、“與-或”表達式的化簡,最簡“與-或”表達式應滿足兩個條件：,1表達式中的“與”項個數(shù)最少；,2在滿足上述條件的前提下，每個“與”項中的變量個 數(shù)最少。,滿足上述兩個條件可以使相應邏輯電路中所需門的數(shù)量以及門的輸入端個數(shù)均為最少，從而使電路最經(jīng)濟。,幾種常用方法如下：,1并項法,2吸收法,利用定理3中A + AB =

30、 A ，吸收多余的項。例如，,利用定理7中的，將兩個“與”項合并成一 個“與”項，合并后消去一個變量。例如，,3消去法,利用定理4中，消去多余變量。例如，,4配項法,例 化簡,解,實際應用中遇到的邏輯函數(shù)往往比較復雜，化簡時應靈活使用所學的公理、定理及規(guī)則，綜合運用各種方法。,例 化簡,解,二、“或-與”表達式的化簡,最簡“或-與”表達式應滿足兩個條件：,1表達式中的“或”項個數(shù)最少；,2在滿足上述條件的前提下，每個“或”項中的變量個數(shù)最少。,用代數(shù)化簡法化簡“或-與”表達式可直接運用公理、定理中的“或-與”形式，并綜合運用前面介紹“與-或”表達式化簡時提出的各種方法進行化簡。,例 化簡,解,

31、此外，可以采用兩次對偶法。具體如下：,第一步：對“或-與”表達式表示的函數(shù)F求對偶，得到“與-或”表達式F；,第二步：求出F的最簡“與-或”表達式；,第三步：對F再次求對偶,即可得到F的最簡“或-與” 表達式。,例 化簡,第二步：化簡F ；,第三步：對F求對偶, 得到F的最簡“或-與”表達式。,解 第一步：求F的對偶式F；,歸納：,代數(shù)化簡法的優(yōu)點是：不受變量數(shù)目的約束；當對公理、定理和規(guī)則十分熟練時，化簡比較方便。,缺點是：沒有一定的規(guī)律和步驟，技巧性很強，而且在很多情況下難以判斷化簡結(jié)果是否最簡。,2.4.2 卡諾圖化簡法,卡諾圖化簡法具有簡單、直觀、容易掌握等優(yōu)點，在邏輯設計中得到廣泛應

32、用。,一、卡諾圖的構(gòu)成,卡諾圖是一種平面方格圖，每個小方格代表一個最小項，故又稱為最小項方格圖。 結(jié)構(gòu)特點：(1) n個變量的卡諾圖由2n個小方格構(gòu)成；(2) 幾何圖形上處在相鄰、相對、相重位置的小方格所代表的最小項為相鄰最小項。,2變量、3變量、4變量卡諾圖如圖(a)、(b)、(c)所示。,例如，四變量卡諾圖中，如m5的4個相鄰最小項分別是和m5相連的 m1，m4，m7，m13。 m2的4個相鄰最小項除了與之幾何相鄰的m3和m6之外，另外兩個是處在“相對”位置的m0 ( 同一列的兩端)和m10( 同一行的兩端)。這種相鄰稱為相對相鄰。,從各卡諾圖可以看出，在n個變量的卡諾圖中，能從圖形上直觀

33、、方便地找到每個最小項的n個相鄰最小項。,5變量卡諾圖如圖（d）所示。,此外， 處在“相重”位置的最小項相鄰，如五變量卡諾圖中的m3，除了幾何相鄰的m1，m2，m7和相對相鄰的m11外，還與m19相鄰。這種相鄰稱為重疊相鄰。,二、卡諾圖的性質(zhì),用卡諾圖化簡邏輯函數(shù)的基本原理：把卡諾圖上表征相鄰最小項的相鄰小方格“圈”在一起進行合并，達到用一個簡單“與”項代替若干最小項的目的。 通常把用來包圍那些能由一個簡單“與”項代替的若干最小項的“圈”稱為卡諾圈。,性質(zhì)：可以從圖形上直觀地找出相鄰最小項合并。合并的理論依據(jù)是并項定理： 。,三、邏輯函數(shù)在卡諾圖上的表示,當邏輯函數(shù)為標準“與-或”表達式時，只

34、需在卡諾圖上找出和表達式中最小項對應的小方格填上1，其余小方格填上0，即可得到該函數(shù)的卡諾圖。,1給定邏輯函數(shù)為標準“與-或”表達式,例如，3變量函數(shù) 的卡諾圖如下圖 所示。,例如，4變量函數(shù) 的卡諾圖如右圖所示。,為了敘述的方便，通常將卡諾圖上填1的小方格稱為1方格，填0的小方格稱為0方格。0方格有時用空格表示。,2邏輯函數(shù)為一般“與-或”表達式,當邏輯函數(shù)為一般“與-或”表達式時，可根據(jù)“與”的 公共性和“或”的疊加性作出相應卡諾圖。,四、卡諾圖上最小項的合并規(guī)律,1兩個小方格相鄰, 或處于某行(列)兩端時，所代表的最小項可以合并，合并后可消去一個變量。,例如，下圖給出了2、3變量卡諾圖上

35、兩個相鄰最小項合并的典型情況的。,當一個函數(shù)用卡諾圖表示后，究竟哪些最小項可以合并呢？下面以2、3、4變量卡諾圖為例予以說明。,2四個小方格組成一個大方格、或組成一行（列）、或處于相鄰兩行（列）的兩端、或處于四角時，所代表的最小項可以合并，合并后可消去兩個變量。,例如,下圖給出了3變量卡諾圖上四個相鄰最小項合并的 典型情況的。,4變量卡諾圖上四個相鄰最小項合并的典型情況：,3八個小方格組成一個大方格、或組成相鄰的兩行(列)、或處于兩個邊行(列)時，所代表的最小項可以合并，合并后可消去三個變量。,例如，下圖給出了3、4變量卡諾圖上八個相鄰最小項合并的典型情況的。,n個變量卡諾圖中最小項的合并規(guī)律

36、歸納如下：,(1) 卡諾圈中小方格的個數(shù)必須為2m個，m為小于或等于n的整數(shù)。,(2) 卡諾圈中的2m個小方格有一定的排列規(guī)律，具體地說，它們含有m個不同變量，(n-m)個相同變量。,(3) 卡諾圈中的2m個小方格對應的最小項可用(n-m)個變量的“與”項表示，該“與”項由這些最小項中的相同變量構(gòu)成。,(4) 當m = n 時，卡諾圈包圍了整個卡諾圖，可用1表示，即n個變量的全部最小項之和為1。,蘊涵項:在函數(shù)的“與-或”表達式中，每個“與”項被稱為該函數(shù)的蘊涵項(Implicant)。,在函數(shù)卡諾圖中，任何一個1方格所對應的最小項或者卡諾圈中的2m個1方格所對應的“與”項都是函數(shù)的蘊涵項。,五、卡諾圖化簡邏輯函數(shù)的步驟,1幾個定義,質(zhì)蘊涵項:若函數(shù)的一個蘊