邏輯代數(shù)基礎(chǔ).ppt_第1頁
邏輯代數(shù)基礎(chǔ).ppt_第2頁
邏輯代數(shù)基礎(chǔ).ppt_第3頁
邏輯代數(shù)基礎(chǔ).ppt_第4頁
邏輯代數(shù)基礎(chǔ).ppt_第5頁
已閱讀5頁,還剩89頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

2、K,常量0和1以及“或”、“與”、“非”三種基本運(yùn)算所構(gòu)成,記為L=K,+,-,0,1。該系統(tǒng)應(yī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,公理是一個(gè)代數(shù)系統(tǒng)的基本出發(fā)點(diǎn),無需加以證明。,公 理 5 互 補(bǔ) 律 對于任意邏輯變量A,存在唯一的,使得,2.1.1 邏輯變量及基本邏輯運(yùn)算,邏輯代數(shù)和普通代數(shù)一樣,是用字母表示其值可以變化的量,即變量。所不同的是:,1任何邏輯變量的取值只有兩種可能性取值0或取值1。,2邏輯值0和1是用來表征矛盾的雙方和判斷事件真?zhèn)蔚男问椒?,無大小、正負(fù)之分。,一、變量,二、基本邏輯運(yùn)算,描述一個(gè)數(shù)字系統(tǒng),必須反映一個(gè)復(fù)雜系統(tǒng)中各開關(guān)元件之間的聯(lián)系,這種相互聯(lián)系反映到數(shù)學(xué)上就是幾種運(yùn)算關(guān)系。 邏輯代數(shù)中定義了“或”、“與” 、“

4、非”三種基本運(yùn)算。,1“或”運(yùn)算 如果決定某一事件是否發(fā)生的多個(gè)條件中,只要有一個(gè)或一個(gè)以上條件成立,事件便可發(fā)生,則這種因果關(guān)系稱之為“或”邏輯。,例如,用兩個(gè)開關(guān)并聯(lián)控制一個(gè)燈的照明控制電路。,電路中,開關(guān)A和B并聯(lián)控制燈F??梢钥闯?,當(dāng)開關(guān)A、B中有一個(gè)閉合或者兩個(gè)均閉合時(shí),燈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中只要有一個(gè)為1,則F為1;僅當(dāng)A、B均為0時(shí),

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

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

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

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

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

10、的所有取值組合,為了不發(fā)生遺漏,通常各變量取值組合按二進(jìn)制數(shù)碼順序給出;右邊一欄為邏輯函數(shù)值。,三、卡諾圖,卡諾圖是由表示邏輯變量所有取值組合的小方格所構(gòu)成的平面圖。 這種用圖形描述邏輯函數(shù)的方法,在邏輯函數(shù)化簡中十分有用,將在后面結(jié)合函數(shù)化簡問題進(jìn)行詳細(xì)介紹。,描述邏輯邏輯函數(shù)的3種方法可用于不同場合。但針對某個(gè)具體問題而言,它們僅僅是同一問題的不同描述形式,相互之間可以很方便地進(jìn)行變換。,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ī)則的正確性是顯然的,因?yàn)槿魏芜壿嫼瘮?shù)都和邏 輯變量一樣,只有0和1兩種可能的取值。,任何一個(gè)含有變量A的邏輯等式,如果將所有出現(xiàn)A的位 置都代之以同一個(gè)邏輯函數(shù)F,則等式仍然成立。這個(gè)規(guī)則 稱為代入規(guī)則。,一、代入規(guī)則,代入規(guī)則的意義: 利用代入規(guī)則可以將邏輯代數(shù)公理、定理中的變量用任 意函數(shù)代替,從而推導(dǎo)出更多的等式。這些等式可直接當(dāng)作 公使用,無需另加證明。,注意:使用代入規(guī)則時(shí),必須將等式中所有出現(xiàn)同一變量的地方均以同一函數(shù)代替,否則代入后的等式將不成立。,二、反演規(guī)則,例如,已知函數(shù),根據(jù)反演規(guī)則可得到,若將邏輯函

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

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

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

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

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

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

19、:是指由若干“與項(xiàng)”進(jìn)行“或”運(yùn)算構(gòu)成的表達(dá)式。例如,,“與項(xiàng)”有時(shí)又被稱為“積項(xiàng)”,相應(yīng)地“或與”表達(dá)式又稱為“積之和”表達(dá)式。,二、“或-與”表達(dá)式,“或項(xiàng)”有時(shí)又被稱為“和項(xiàng)”,相應(yīng)地“或與”表達(dá)式又稱為“和之積”表達(dá)式。,“或-與”表達(dá)式:是指由若干“或項(xiàng)”進(jìn)行“與”運(yùn)算構(gòu)成的表達(dá)式。例如,,該函數(shù)既不是“與或”式?也不是“或與”式!,2.3.2 邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式,邏輯函數(shù)表達(dá)式可以被表示成任意的混合形式。例如,,邏輯函數(shù)的基本形式都不是唯一的。例如,為了在邏輯問題的研究中使邏輯功能能和唯一的邏輯表達(dá)式對應(yīng),引入了邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式。邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式是建立在最小項(xiàng)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論