四川大學(xué)數(shù)字邏輯第2章

第2章布爾開關(guān)代數(shù)Chapter2:BooleanSwitchingAlgebra計(jì)算機(jī)學(xué)院潘薇主要內(nèi)容布爾代數(shù)的基本概念邏輯問題的分析方法布爾代數(shù)的基本定理及規(guī)則功能完全操作集邏輯方程的標(biāo)準(zhǔn)形式邏輯方程的代數(shù)化簡(jiǎn)主要內(nèi)容布爾代數(shù)的基本概念邏輯問題的分析方法布爾代數(shù)的基本定理及規(guī)則功能完全操作集邏輯方程的標(biāo)準(zhǔn)形式邏輯方程的代數(shù)化簡(jiǎn)邏輯代數(shù)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ù)。邏輯代數(shù)是數(shù)子系統(tǒng)邏輯設(shè)計(jì)的理論基礎(chǔ)和重要數(shù)學(xué)工具！布爾代數(shù)的基本概念定義：布爾代數(shù)L，是一個(gè)封閉的代數(shù)系統(tǒng)，它由一個(gè)邏輯變量集K，常量0和1，以及“或”、“與”、“非”3種基本運(yùn)算所構(gòu)成。記作L={K，+，*，’，0，1}。該系統(tǒng)應(yīng)滿足下列公理：公理1交換律

A+B=B+AA*B=B*A公理2結(jié)合律

(A+B)+C=A+(B+C)(A*B)*C=A*(B*C)公理3分配律

A+(B*C)=(A+B)*(A+C)A*(B+C)=A*B+A*C公理40-1律

A+0=AA*0=0A+1=1A*1=A公理5互補(bǔ)律對(duì)任意的邏輯變量A，存在唯一的A’,

滿足A+A’=1A*A’=0思考假真0和1不表示數(shù)量的大??；而是表示完全對(duì)立的兩種狀態(tài)；“1”表示條件具備或者事情發(fā)生；“0”表示條件不具備或者事情沒有發(fā)生。邏輯變量邏輯代數(shù)和普通代數(shù)一樣，是用字母表示其值可以變化的量，即變量。任何邏輯變量的取值只有兩種可能性——取值0或取值1。邏輯值0和1是用來表征矛盾的雙方和判斷事件真?zhèn)蔚男问椒?hào)，無大小、正負(fù)之分。邏輯函數(shù)邏輯代數(shù)中函數(shù)的定義與普通代數(shù)中函數(shù)的定義類似，即隨自變量變化的因變量。但和普通代數(shù)中函數(shù)的概念相比，邏輯函數(shù)具有如下特點(diǎn)：和邏輯變量一樣，取值只有0和1兩種可能；函數(shù)和變量之間的關(guān)系是由邏輯運(yùn)算決定的。設(shè)某一邏輯電路的輸入邏輯變量為A1，A2，…，An，輸出邏輯變量為F，F(xiàn)被稱為A1，A2，…，An的邏輯函數(shù)，記為F=f(A1，A2，…，An)基本邏輯運(yùn)算描述一個(gè)數(shù)字系統(tǒng)，必須反映一個(gè)復(fù)雜系統(tǒng)中各開關(guān)元件之間的聯(lián)系，這種相互聯(lián)系反映到數(shù)學(xué)上就是幾種運(yùn)算關(guān)系。邏輯代數(shù)中定義了“或”、“與”、“非”三種基本運(yùn)算?；具壿嬤\(yùn)算——或（OR）如果決定某一事件發(fā)生的多個(gè)條件中，只要有一個(gè)或者一個(gè)以上條件成立，事件就可以發(fā)生，則這種因果關(guān)系稱之為“或”邏輯。運(yùn)算符號(hào)：+、∨?；蜻\(yùn)算——或門XYZ+Z=X+YXYZ≥1表達(dá)式運(yùn)算規(guī)則基本邏輯運(yùn)算——與（AND）如果決定某一事件發(fā)生的多個(gè)條件必須同時(shí)具備，事件才能發(fā)生，則這種因果關(guān)系稱之為“與”邏輯。運(yùn)算符號(hào)：·，*，×，∧，空。表達(dá)式運(yùn)算規(guī)則與運(yùn)算——與門XYZ&Z=XY基本邏輯運(yùn)算——非（NOT）如果某一事件的發(fā)生取決于條件的否定，即事件與條件之間構(gòu)成矛盾，則這種因果關(guān)系稱為“非”邏輯。運(yùn)算符號(hào)：’，▔。非運(yùn)算——非門表達(dá)式

運(yùn)算規(guī)則XX?XX?其他通用的邏輯運(yùn)算與非（NAND）或非（NOR）異或（XOR）異或非（XNOR）與非表達(dá)式XYZ&Z=XY或非XYZ+Z=X+Y表達(dá)式異或當(dāng)兩個(gè)輸入變量不一致時(shí)輸出為真。表達(dá)式XYZ=1Z=X⊕

YXYZ⊕異或非所有輸入變量相同的時(shí)候輸出為真。表達(dá)式XYZ=1Z=X☉Y布爾代數(shù)的基本概念相等（Equivalent）：對(duì)于邏輯變量的任何一組取值，兩個(gè)邏輯表達(dá)式A和B的輸出都相等，則認(rèn)為A=B。例：A=xy+x，B=x(x+y)，A和B是否相等？xyAB0000010010111111A=B布爾代數(shù)的基本概念封閉（Closure）：對(duì)于給定的集合A，當(dāng)輸入為A的元素時(shí)，經(jīng)過運(yùn)算B進(jìn)行運(yùn)算，結(jié)果也是A的元素，則稱A對(duì)B是封閉的。例：對(duì)布爾變量來說，運(yùn)算(*,+)是封閉的。主要內(nèi)容布爾代數(shù)的基本概念邏輯問題的分析方法布爾代數(shù)的基本定理及規(guī)則功能完全操作集邏輯方程的標(biāo)準(zhǔn)形式邏輯方程的代數(shù)化簡(jiǎn)數(shù)字邏輯課程要解決的問題根據(jù)需求設(shè)計(jì)一個(gè)邏輯電路來描述問題。分析已有的邏輯設(shè)計(jì)完成的功能。功能需求邏輯設(shè)計(jì)邏輯關(guān)系的表示方式1邏輯方程用邏輯表達(dá)式來表示邏輯關(guān)系，其中的變量是二元值的邏輯變量。

2真值表采用表格來表示邏輯函數(shù)的輸入輸出，需要枚舉出所有情況。3邏輯圖采用規(guī)定的圖形符號(hào)，來構(gòu)成邏輯函數(shù)運(yùn)算關(guān)系的網(wǎng)絡(luò)圖形。設(shè)計(jì)邏輯問題的步驟

畫出邏輯圖

寫出邏輯表達(dá)式及化簡(jiǎn)

構(gòu)造真值表

問題描述邏輯設(shè)計(jì)示例例：三人就某一提議進(jìn)行表決，請(qǐng)給出對(duì)應(yīng)的邏輯方程、真值表、邏輯圖。解：step1:問題描述設(shè)輸入變量A、B、C代表三人的表決意見。F代表表決結(jié)果。規(guī)則：>=兩人同意，則表決通過，否則不通過。A、B、C：同意為1，不同意為0。F：通過為1，不通過為0。step2:列出真值表邏輯設(shè)計(jì)示例邏輯設(shè)計(jì)示例step3:由真值表給出邏輯方程并化簡(jiǎn)將輸出為真的行的輸入積用“或”連接起來step4:由邏輯方程畫出邏輯圖列出所需的輸入變量用反相器對(duì)輸入變量求反獲得所需的反變量把邏輯表達(dá)式中相應(yīng)的運(yùn)算用門電路的符號(hào)來代替邏輯圖邏輯設(shè)計(jì)示例真值表邏輯方程邏輯圖邏輯設(shè)計(jì)示例已有電路的功能分析步驟

確定邏輯功能構(gòu)造真值表

化簡(jiǎn)邏輯表達(dá)式

寫出邏輯表達(dá)式電路分析示例A1A0&&&&11分析下面邏輯圖的邏輯功能電路分析示例A1A0&&&&11step1.根據(jù)邏輯圖寫出邏輯方程電路分析示例A1

A0F0

F1

F2

F3000110111000010000100001F1=A1A0F3=A1A0F2=A1A0F0=A1A0譯碼器step2.根據(jù)邏輯方程構(gòu)造真值表step3.根據(jù)真值表確定功能示例用真值表來表示以下邏輯方程：G1=xy+xzG2=[(x’+y’)(x’+z’)]’xyzG1G20000000100010000110010000101111101111111真值表相同說明G1=G2示例用邏輯圖來表示以下邏輯方程：G1=xy+xzG2=[(x’+y’)(x’+z’)]’對(duì)一個(gè)確定的邏輯關(guān)系來說，邏輯方程和邏輯圖都不是唯一的練習(xí)練習(xí)2.1：用邏輯圖和真值表來表示以下邏輯方程：G=xy+z’xyzG00010010010101101001101011011111邏輯關(guān)系的表示描述邏輯關(guān)系的3種方法可用于不同場(chǎng)合。但針對(duì)某個(gè)具體問題而言，它們僅僅是同一問題的不同描述形式，相互之間可以很方便地進(jìn)行變換。真值表與邏輯關(guān)系是一一對(duì)應(yīng)的。邏輯方程與邏輯關(guān)系是多對(duì)一的。邏輯圖與邏輯關(guān)系是多對(duì)一的。主要內(nèi)容布爾代數(shù)的基本概念邏輯問題的分析方法布爾代數(shù)的基本定理及規(guī)則功能完全操作集邏輯方程的標(biāo)準(zhǔn)形式邏輯方程的代數(shù)化簡(jiǎn)已有公理公理1交換律

A+B=B+AA*B=B*A公理2結(jié)合律(A+B)+C=A+(B+C)(A*B)*C=A*(B*C)公理3分配律

A+(B*C)=(A+B)*(A+C)A*(B+C)=A*B+A*C公理40-1律

A+0=AA*0=0A+1=1A*1=A公理5互補(bǔ)律對(duì)任意的邏輯變量A，存在唯一的A’，滿足A+A’=1A*A’=0定理1——吸收律定理1：A+A*B=A,A*(A+B)=AA+A’B=A+B,A*(A’+B)=A*B證明：A+A*B=A*1+A*B……0-1律

=A*(1+B)……分配律

=A*1……交換律、0-1律

=A……0-1律

ABA+A*BA*(A+B)0000010010111111消除冗余真值表證明：定理2——等冪律（同一律）定理2A+A=A,A*A=A證明：A+A=A*1+A*1=A*(1+1)=A*1=A定理3——對(duì)合律（還原律）定理3A’’=A證明:令A(yù)’’=X，則有

A’*X=0，A’+X=1

由于A*A’=0，A’+A=1，而根據(jù)互補(bǔ)律的唯一性，因此有

X=A

所以A’’=A定理4——鄰接律（合并律）定理4A*B+A*B’=A(A+B)*(A+B’)=A證明：A*B+A*B’=A*(B+B’)=A*1=A定理5——增項(xiàng)消項(xiàng)法定理5A*B+A’*C+B*C=A*B+A’*C(A+B)*(A’+C)*(B+C)=(A+B)*(A’+C)證明：

A*B+A’*C+B*C=A*B+A’*C+(B*C)*(A+A’)=A*B+A’*C+B*C*A+B*C*A’=A*B*(1+C)+A’*C*(1+B)=A*B+A’*C…0-1律、互補(bǔ)律…分配律…交換律、分配律…0-1律定理6摩根律定理6(A+B)’=A’*B’,(A*B)’=A’+B’證明：(A’*B’)+(A+B)=(A’*B’+A)+B=(B’+A)+B=A+1=1(A’*B’)*(A+B)=A’*B’*A+A’*B’*B=0+0=0

所以，根據(jù)互補(bǔ)律的唯一性，有：

A’*B’=(A+B)’摩根定理“與”運(yùn)算的取反等于輸入變量取反的“或”運(yùn)算“或”運(yùn)算的取反等于輸入變量取反的“與”運(yùn)算x1x2x3…xn=x1+x2+x3+…+xnx1+x2+x3+…+xn=x1.x2.x3…xn示例例：利用摩根定理求出F=x(y+z’)’的等價(jià)式。解：1.令A(yù)=(y+z’)’，則F=xA2.應(yīng)用摩根定理有

F=[x’+A’]’=[x’+(y+z’)]’=(x’+y+z’)’3.再次應(yīng)用摩根定理

F=(x’+y+z’)’=xy’z練習(xí)練習(xí)2.2：對(duì)下列表達(dá)式使用德摩根定理。布爾代數(shù)的重要規(guī)則代入規(guī)則反演規(guī)則對(duì)偶規(guī)則代入規(guī)則任何一個(gè)含有變量A的邏輯等式，如果將所有出現(xiàn)A的位置都代之以同一個(gè)邏輯函數(shù)F，則等式仍然成立。例：給定等式A(B+C)=AB+AC，若等式中的C都用C+D代替，則該等式仍然成立，即有：

A(B+C+D)=AB+A(C+D)代入規(guī)則在公式推導(dǎo)中有重要意義，利用這條規(guī)則可以對(duì)公理、定理中的變量進(jìn)行替換，從而推導(dǎo)出更多的等式。例：A+A’=1(A+B+C)+(A+B+C)’=1反演規(guī)則將邏輯函數(shù)中*變+，+變成*1變成0，0變成1原變量變成反變量,反變量變成原變量即得到原邏輯函數(shù)F的反函數(shù)。練習(xí)練習(xí)2.3：求下列函數(shù)的反函數(shù)。解：注意：求反函數(shù)時(shí)應(yīng)保持原函數(shù)中運(yùn)算符號(hào)的優(yōu)先順序

X√反函數(shù)示例例：求下列函數(shù)的反函數(shù)。解：

長(zhǎng)非號(hào)不變，長(zhǎng)非號(hào)內(nèi)部應(yīng)用反演規(guī)則。對(duì)偶規(guī)則將邏輯函數(shù)中*變+，+變成*1變成0，0變成1邏輯變量保持不變即得到原邏輯函數(shù)F的對(duì)偶函數(shù)F*。對(duì)偶規(guī)則：如果兩個(gè)邏輯函數(shù)相等，則他們的對(duì)偶函數(shù)也相等。對(duì)偶規(guī)則示例例：摩根律例：鄰接律利用對(duì)偶規(guī)則可以使證明減少一半。主要內(nèi)容布爾代數(shù)的基本概念邏輯問題的分析方法布爾代數(shù)的基本定理及規(guī)則功能完全操作集邏輯方程的標(biāo)準(zhǔn)形式邏輯方程的代數(shù)化簡(jiǎn)功能完全操作集功能完全操作集：是一組邏輯函數(shù)集，它能實(shí)現(xiàn)所有的組合邏輯表達(dá)式。FC1={與、非、或}FC2={或非}FC3={與非}FC4={異或、與}用或非實(shí)現(xiàn)操作集或非門實(shí)現(xiàn)非運(yùn)算或非門實(shí)現(xiàn)與運(yùn)算或非門實(shí)現(xiàn)或運(yùn)算用與非實(shí)現(xiàn)操作集與非門實(shí)現(xiàn)非運(yùn)算與非門實(shí)現(xiàn)與運(yùn)算與非門實(shí)現(xiàn)或運(yùn)算用異或和與實(shí)現(xiàn)操作集異或門實(shí)現(xiàn)非運(yùn)算與門實(shí)現(xiàn)與運(yùn)算異或門和與門實(shí)現(xiàn)或運(yùn)算主要內(nèi)容布爾代數(shù)的基本概念邏輯問題的分析方法布爾代數(shù)的基本定理及規(guī)則功能完全操作集邏輯方程的標(biāo)準(zhǔn)形式邏輯方程的代數(shù)化簡(jiǎn)邏輯方程的基本形式積之和（SOP）和之積（POS）注意：邏輯函數(shù)的基本形式都不是唯一的。例如：邏輯函數(shù)的標(biāo)準(zhǔn)形式為了在邏輯問題的研究中使邏輯功能能和唯一的邏輯表達(dá)式對(duì)應(yīng)，引入了邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式。邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式是建立在最小項(xiàng)和最大項(xiàng)概念的基礎(chǔ)之上的。最小項(xiàng)最小項(xiàng)：包含所有輸入變量（每個(gè)變量都以原變量或者反變量的形式出現(xiàn)且僅出現(xiàn)一次）的乘積項(xiàng)，用mi表示。n個(gè)變量可以構(gòu)成2n個(gè)最小項(xiàng)。下標(biāo)i的取值規(guī)則是：按照變量順序?qū)⒆钚№?xiàng)中的原變量用1表示，反變量用0表示，由此得到一個(gè)二進(jìn)制數(shù)，與該二進(jìn)制數(shù)對(duì)應(yīng)的十進(jìn)制數(shù)即下標(biāo)i的值。例如：3變量A、B、C構(gòu)成的最小項(xiàng)AB’C可以用m5表示。最小項(xiàng)的性質(zhì)任意一個(gè)最小項(xiàng)，其相應(yīng)變量有且僅有一種取值使這個(gè)最小項(xiàng)的值為1。并且，最小項(xiàng)不同，使其值為1的變量取值不同。在由n個(gè)變量構(gòu)成的任意“與項(xiàng)”中，最小項(xiàng)是使其值為1的變量取值組合數(shù)最少的一種“與項(xiàng)”，這也就是最小項(xiàng)名字的由來。相同變量構(gòu)成的兩個(gè)不同最小項(xiàng)相“與”為0。因?yàn)槿魏我环N變量取值都不可能使兩個(gè)不同最小項(xiàng)同時(shí)為1，故相“與”為0。即

mi·mj=0最小項(xiàng)的性質(zhì)n個(gè)變量的全部最小項(xiàng)相“或”為1。通常借用數(shù)學(xué)中的累加符號(hào)“Σ”，將其記為n個(gè)變量構(gòu)成的最小項(xiàng)有n個(gè)相鄰最小項(xiàng)。

相鄰最小項(xiàng)：是指除一個(gè)變量互為相反外，其余部分均相同的最小項(xiàng)。例如，三變量最小項(xiàng)ABC和AB’C相鄰。最大項(xiàng)最大項(xiàng)：包含所有輸入變量（每個(gè)變量都以原變量或者反變量的形式出現(xiàn)且僅出現(xiàn)一次）的和項(xiàng)，用Mi表示。n個(gè)變量可以構(gòu)成2n個(gè)最大項(xiàng)。下標(biāo)i的取值規(guī)則是：將最大項(xiàng)中的原變量用0表示，反變量用1表示，由此得到一個(gè)二進(jìn)制數(shù)，與該二進(jìn)制數(shù)對(duì)應(yīng)的十進(jìn)制數(shù)即下標(biāo)i的值。例如：3變量A、B、C構(gòu)成的最大項(xiàng)A’+B+C’可以用M5表示。最大項(xiàng)的性質(zhì)任意一個(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)。相同變量構(gòu)成的兩個(gè)不同最大項(xiàng)相“或”為1。因?yàn)槿魏我环N變量取值都不可能使兩個(gè)不同最大項(xiàng)同時(shí)為0，故相“或”為1。

Mi+Mj=1最大項(xiàng)的性質(zhì)n個(gè)變量的全部最大項(xiàng)相“與”為0。通常借用數(shù)學(xué)中的累乘符號(hào)“Π”將其記為n個(gè)變量構(gòu)成的最大項(xiàng)有n個(gè)相鄰最大項(xiàng)。相鄰最大項(xiàng)是指除一個(gè)變量互為相反外，其余變量均相同的最大項(xiàng)。三變量的最小項(xiàng)和最大項(xiàng)表示最小項(xiàng)最大項(xiàng)思考：最小項(xiàng)與最大項(xiàng)之間的關(guān)系？m3=?M3=?m3’=?M3’=?m3=a’bcM3=a+b’+c’m3’=(a’bc)’=a+b’+c’M3’=(a+b’+c’)=a’bcm3=M3’M3=m3’邏輯函數(shù)的標(biāo)準(zhǔn)形式邏輯函數(shù)表達(dá)式的標(biāo)準(zhǔn)形式有2種：最小項(xiàng)之和：當(dāng)輸出變量為邏輯1的所有最小項(xiàng)的和。也稱為標(biāo)準(zhǔn)與-或表達(dá)式。F=∑mi最大項(xiàng)之積：當(dāng)輸出變量為邏輯0的所有最大項(xiàng)的乘積。也稱為標(biāo)準(zhǔn)或-與表達(dá)式。F=∏