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

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

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

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

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

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

畫出邏輯圖

寫出邏輯表達式及化簡

構(gòu)造真值表

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

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

化簡邏輯表達式

寫出邏輯表達式電路分析示例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’)]’對一個確定的邏輯關(guān)系來說，邏輯方程和邏輯圖都不是唯一的練習練習2.1：用邏輯圖和真值表來表示以下邏輯方程：G=xy+z’xyzG00010010010101101001101011011111邏輯關(guān)系的表示描述邏輯關(guān)系的3種方法可用于不同場合。但針對某個具體問題而言，它們僅僅是同一問題的不同描述形式，相互之間可以很方便地進行變換。真值表與邏輯關(guān)系是一一對應的。邏輯方程與邏輯關(guān)系是多對一的。邏輯圖與邏輯關(guān)系是多對一的。主要內(nèi)容布爾代數(shù)的基本概念邏輯問題的分析方法布爾代數(shù)的基本定理及規(guī)則功能完全操作集邏輯方程的標準形式邏輯方程的代數(shù)化簡已有公理公理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互補律對任意的邏輯變量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——對合律（還原律）定理3A’’=A證明:令A’’=X，則有

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

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

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——增項消項法定理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律、互補律…分配律…交換律、分配律…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ù)互補律的唯一性，有：

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

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

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

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

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

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

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

相鄰最小項：是指除一個變量互為相反外，其余部分均相同的最小項。例如，三變量最小項ABC和AB’C相鄰。最大項最大項：包含所有輸入變量（每個變量都以原變量或者反變量的形式出現(xiàn)且僅出現(xiàn)一次）的和項，用Mi表示。n個變量可以構(gòu)成2n個最大項。下標i的取值規(guī)則是：將最大項中的原變量用0表示，反變量用1表示，由此得到一個二進制數(shù)，與該二進制數(shù)對應的十進制數(shù)即下標i的值。例如：3變量A、B、C構(gòu)成的最大項A’+B+C’可以用M5表示。最大項的性質(zhì)任意一個最大項，其相應變量有且僅有一種取值使這個最大項的值為0。并且，最大項不同，使其值為0的變量取值不同。在n個變量構(gòu)成的任意“或項”中，最大項是使其值為1的變量取值組合數(shù)最多的一種“或項”，因而將其稱為最大項。相同變量構(gòu)成的兩個不同最大項相“或”為1。因為任何一種變量取值都不可能使兩個不同最大項同時為0，故相“或”為1。

Mi+Mj=1最大項的性質(zhì)n個變量的全部最大項相“與”為0。通常借用數(shù)學中的累乘符號“Π”將其記為n個變量構(gòu)成的最大項有n個相鄰最大項。相鄰最大項是指除一個變量互為相反外，其余變量均相同的最大項。三變量的最小項和最大項表示最小項最大項思考：最小項與最大項之間的關(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ù)的標準形式邏輯函數(shù)表達式的標準形式有2種：最小項之和：當輸出變量為邏輯1的所有最小項的和。也稱為標準與-或表達式。F=∑mi最大項之積：當輸出變量為邏輯0的所有最大項的乘積。也稱為標準或-與表達式。F=∏