第2章 邏輯代數(shù)基礎

1、1第二章第二章 邏輯代數(shù)基礎邏輯代數(shù)基礎Chapter 2 Logic Algebra Basic本章主要內(nèi)容本章主要內(nèi)容 第一節(jié)第一節(jié) 數(shù)制與碼制數(shù)制與碼制 第二節(jié)第二節(jié) 邏輯代數(shù)的基本概念與運算邏輯代數(shù)的基本概念與運算 第三節(jié)第三節(jié) 邏輯函數(shù)的公式化簡法邏輯函數(shù)的公式化簡法 第四節(jié)第四節(jié) 邏輯函數(shù)的卡諾圖化簡法邏輯函數(shù)的卡諾圖化簡法 第五節(jié)第五節(jié) 具有無關項的邏輯函數(shù)及其化簡具有無關項的邏輯函數(shù)及其化簡22.2 邏輯代數(shù)基本概念和運算規(guī)則邏輯代數(shù)基本概念和運算規(guī)則上次授課內(nèi)容上次授課內(nèi)容 回顧回顧布爾代數(shù)、真布爾代數(shù)、真(“1”)和和假假(“0”)、邏輯變量與邏輯函數(shù)邏輯變量與邏輯函數(shù)邏輯

2、代數(shù)的基本運算：邏輯代數(shù)的基本運算：與、或、非與、或、非及圖形符號表示：及圖形符號表示：復合邏輯運算：復合邏輯運算：與非、或非、與或非、同或、異或與非、或非、與或非、同或、異或等。等。3上次授課內(nèi)容上次授課內(nèi)容 回顧回顧復合邏輯復合邏輯運算：運算：與非、與非、或非、或非、與或非、與或非、同或、同或、異或異或等。等。4上次授課內(nèi)容上次授課內(nèi)容 回顧回顧一、邏輯表達式（函數(shù)式）一、邏輯表達式（函數(shù)式）二、真值表二、真值表三、邏輯電路圖三、邏輯電路圖四、卡諾圖四、卡諾圖五、波形圖（時序圖）五、波形圖（時序圖）六、文字描述六、文字描述描述邏輯函數(shù)的方法有以下六種：描述邏輯函數(shù)的方法有以下六種：5邏輯代

3、數(shù)基本定律總結表邏輯代數(shù)基本定律總結表定律名稱定律名稱公公 式式01律律自等律自等律重疊律重疊律互補律互補律交換律交換律結合律結合律分配律分配律還原律還原律反演律反演律吸收律（一）吸收律（一）吸收率（二）吸收率（二）吸收率（三）吸收率（三）吸收率（四）吸收率（四）00 A11AAA1AA0AAAAAA0 AA1 AAABBAABBACBACBA)()(CBACBA)()(ACABCBA)()(CABABCAAA BABABABAAA*)(ABAABAABABABAACAABBCCAABABABA)(ABAA)(ABBAA)()()()(CABACBCABA6二、邏輯代數(shù)的三個定理二、邏輯代數(shù)的

4、三個定理(規(guī)則規(guī)則) 1、代入定理、代入定理 2、反演定理、反演定理 3、對偶定理、對偶定理 上次授課內(nèi)容上次授課內(nèi)容 回顧回顧“”換成換成“+”，“+”換成換成“”，“0”換成換成“1”，“1”換換成成“0”，原變量換成反變量，反變量換成原變量。原變量換成反變量，反變量換成原變量?！啊睋Q成換成“+”，“+”換成換成“”，“0”換成換成“1”，“1”換成換成“0”72.3 邏輯函數(shù)的公式化簡法邏輯函數(shù)的公式化簡法一、邏輯函數(shù)的最簡形式一、邏輯函數(shù)的最簡形式 例：例： 邏輯式越是簡單，它所表示的邏輯關系越明顯，邏輯式越是簡單，它所表示的邏輯關系越明顯，同時也有利于用最少的電子器件實現(xiàn)這個邏輯函數(shù)

5、。同時也有利于用最少的電子器件實現(xiàn)這個邏輯函數(shù)。BAFBABBAF21,一個邏輯函數(shù)可以有多種不同的邏輯表達式，如一個邏輯函數(shù)可以有多種不同的邏輯表達式，如與與-或或表達式、表達式、或或-與與表達式、表達式、與非與非-與非與非表達式、表達式、或非或非-或非或非表達式以及表達式以及與與-或或-非非表達式表達式 （與或式）（與或式） （或與式）（或與式） （與非與非式（與非與非式 ） （或非或非式（或非或非式 ） （與或非式（與或非式 ） DCCADCCADCACDCCADCACL8Y=AB+(A+B)C = AB+ABC = AB+C= AB+C ABC例：例：Y=AB+AC+BC 化為化為=（

6、最簡與非最簡與非-與非式與非式）（最簡與或式最簡與或式） 著重討論著重討論與或表達式與或表達式的化簡，因為與或的化簡，因為與或表達式易于從真值表直接寫出，且只需運表達式易于從真值表直接寫出，且只需運用一次用一次De. Morgan定律定律就可以從最簡就可以從最簡與與或表達式或表達式變換為變換為與非與非-與非與非表達式，從而表達式，從而可以用可以用與非門與非門電路來實現(xiàn)。電路來實現(xiàn)。 9 二輸入四或門二輸入四或門74LS32一片一片 只需要：二輸入四與非門只需要：二輸入四與非門74LS00一片一片按與按與-或式或式 AB+C 設計此邏輯電路，設計此邏輯電路，需兩塊芯片需兩塊芯片1&YA

7、B C按與非按與非-與非式與非式 設計此邏輯電路，設計此邏輯電路， ABCC&A B二輸入四與門二輸入四與門74LS10一片一片10判別與或表達式是否最簡的條件是：判別與或表達式是否最簡的條件是： 1、乘積項乘積項(與項與項)最少最少； (所用的門最少所用的門最少) 2、每個乘積項里的因子最少每個乘積項里的因子最少。 (門的輸入門的輸入端數(shù)最少端數(shù)最少) 化簡邏輯函數(shù)的目的：消去化簡邏輯函數(shù)的目的：消去多余的乘積項多余的乘積項和每個和每個乘積項中多余的因子乘積項中多余的因子。乘積項最少乘積項最少 且且 乘積項中變量因子最少。乘積項中變量因子最少。11例：以下例：以下4個個“與或與或”表

8、達式是相等的，即它們表達式是相等的，即它們表示同一個函數(shù)：表示同一個函數(shù)：CABACACACBCACACBACACABACBCAF試判斷哪一個是最簡試判斷哪一個是最簡“與或與或”表達式？表達式？解：解：1) 對比可知式對比可知式1含含4個與項，其他個與項，其他3式都只含式都只含3個與項，個與項，所以式所以式1肯定不是最簡；肯定不是最簡；2) 式式3、4中各與項都含中各與項都含2個變量，而式個變量，而式2中有一個與中有一個與項含項含3個變量。結論：式個變量。結論：式3、4同為該函數(shù)的最簡與或同為該函數(shù)的最簡與或表達式。表達式。12（1）并項法）并項法 利用公式利用公式 可將兩項合并為一項可將兩項

9、合并為一項.二、常用的公式化簡方法二、常用的公式化簡方法ABAAB=+例例: F=ABC +ABC =AB(C +C) =AB 例：例：試用并項法化簡下列邏輯函數(shù)試用并項法化簡下列邏輯函數(shù)Y1=ABCD+ABCD =A(BCD+BCD)=AY2=AB+ACD+AB+ACDY3=ABC+AC+BCY4=BCD+BCD+BCD+BCD=A(B+CD)+A(B+CD) =B+CD=ABC+(A+B)C=B(CD+CD)+B(CD+CD)=B(C D)+B(C D)=B=(AB)C+(AB)C=C13ABAABABABA)(吸收律（一）吸收律（一）AABAABAA)(吸收律（二）吸收律（二）BABAA

10、ABBAA)(吸收律（三）吸收律（三）CAABBCCAAB)()()(CABACBCABA吸收律（四）吸收律（四）利用吸收律給利用吸收律給函數(shù)式消腫函數(shù)式消腫(2) 吸收法吸收法14 (2) 吸收法吸收法 利用公式利用公式 A+AB=A 可將可將AB項消去。項消去。 例：例：試用吸收法化簡下列邏輯函數(shù)試用吸收法化簡下列邏輯函數(shù)BCDCBABCAAYDCABABDCABABY)()(21Y=AB +ABCD(E+F)=AB (1+CDE+CDF) =ABY1 = AB = A+BCAB=A+BY2 = (A+BC)+(A+BC)(A+BC+D) = ADY3 = (AB+C)ABD+AD = A

11、D+ADB(AB+C)15ABAABAABABABAACAABBCCAABABABA)(ABAA)(ABBAA)()()()(CABACBCABA吸收律（一）吸收律（一）吸收律（二）吸收律（二）吸收律（三）吸收律（三）吸收律（四）吸收律（四）Y = AC+ABCD+ABC+CD+ABD = AC+CD+ABD = AC+CDY = AC+ABCD+ABC+CD+ABD = AC+CD+ABDAABACAABBCCAABY=AB+AC+BC=AB+(A+B)C = AB+ABC =AB+CBABABABAA16A(A+B)Y = A(A+B)(A+C)(B+D)(A+C+E+F)(B+F)(D+

12、E+F)(B+D)(B+F)(D+E+F)(A+C)(A+C+E+F)ABAA)(ABAA)()()()(CABACBCABAY = A(A+C)(B+D)(B+F) 解法解法2：將或與式：將或與式 與或式與或式 化簡化簡 或與式或與式對偶對偶對偶對偶公式公式Y* = A+AB+AC+BD+ACEF+BF+DEF = (A+AB)+(AC+ACEF)+(BD+BF+DEF)AABAAABACAABBCCAAB = A+AC+BD+BF =AC(B+D)(B+F)BABAA= A+C+BD+BFY=(Y*)* = AC(B+D)(B+F)17 (3) 消項法消項法 利用公式利用公式 將將BC或或

13、BCD消去。消去。 例：例：用消項法化簡下列邏輯函數(shù)用消項法化簡下列邏輯函數(shù)CAABBCDCAABCAABBCCAAB及Y = AC+AB+B+C = AC+AB+BCBABA = CA+CB+AB = AC+BCCAABBCCAAB18EDBCDBCADBADBAABCCBAYEDCAEBADCBAY21 Y1= (AB)CD+(AB)E+(CD)(E)A = ABCD+ABECAABBCCAAB Y2 = (AB+AB)C+(AB+AB)D+BCD(A+E)A BA BCAABBCCAAB= (A B)C+ (A B)DDBADBAABCCBABEEADCBA19 (4) 消因子法消因子法

14、 利用公式利用公式 消去。中的可將ABABABAA例：例：試用消因子法化簡下列邏輯函數(shù)試用消因子法化簡下列邏輯函數(shù)DCDAACYBABBAY21 Y1= AB+B+AB = A+B+ABBABAA = A+BY2= AC+AD+CD+CDCAABBCCAAB = AC+AD+DAABA = AC+DAABAY2= AC+(A+C)D= AC+ACD= AC+DBABABABAA20 (5) 配項法配項法 1、根據(jù)基本公式、根據(jù)基本公式A+A=A可添加重復項進行化簡。可添加重復項進行化簡。 例：例：試化簡邏輯函數(shù)試化簡邏輯函數(shù) 2、根據(jù)基本公式中的、根據(jù)基本公式中的 可以在函數(shù)式中的可以在函數(shù)式

15、中的 某一項上乘以某一項上乘以 進行化簡。進行化簡。ABCBCACBAY)(AA1 AAY=AB +AC+BC = AB+AC+ (A+A) BC=AB+ABC+AC+ABC =AB+ACAABAABCBCACBAYBCBA ABCBCABCACBAAABCCCBA21CBCBBABAYY = AB +AB(C+C)+BC+(A+A)BC = AB +ABC+ABC+BC+ABC+ABC = AB+BC+ACAABAAABAABAAB = (AB +ABC)+(BC+ABC)+(ABC+ABC)Y = AB(C+C)+AB+(A+A)BC+BC= ABC+ABC+AB+ABC+ABC+BCAA

16、BAAABAABAAB = AB+BC+AC= (AB+ABC)+(BC+ABC)+(ABC+ABC)22AB+BC+AC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 AB+BC+ACA B CAB+BC+AC AB+BC+AC=?0 + 0 + 0 = 00 + 0 + 1 = 10 + 1 + 0 = 10 + 0 + 1 = 11 + 0 + 0 = 11 + 0 + 0 = 10 + 1 + 0 = 10 + 0 + 0 = 00 + 0 + 0 = 00 + 1 + 0 = 11 + 0 + 0 = 11 + 0 + 0 = 10 + 0 + 1

17、= 10 + 1 + 0 = 10 + 0 + 1 = 10 + 0 + 0 = 0AB+BC+AC AB+BC+AC=注：公注：公式化簡式化簡的結果的結果不一定不一定唯一。唯一。23 Y=AC+BC+BD+CD+A(B+C)+ABCD+ABDE Y=AC+BC+BD+CD+AB+AC+ABDE =AC+BC+BD+CD+ABC+ABDE =AC+BC+BD+CD+A+ABDE =BC+BD+CD+A =A+BC+BDAABABABAAAABACAABBCCAAB =A+BC+BD+AB+AC+ABDE =A+BC+BDAABACAABBCCAAB24 All the logic functi

18、ons introduced in this chapter are commercially available in integrated circuit (IC) form.For example:Block diagram of 7400 IC chip25Some of the available IC gatesIC NO.DescriptionPINs7400Quad 2-input NAND gates147402Quad 2-input NOR gates147404Hex inverters147408Quad 2-input AND gates147410Triple 3

19、-input NAND gates147427Triple 3-input NOR gates147432Quad 2-input OR gates147486,74386Quad EX-OR gates1474135Quad EX-OR/NOR gates1426 用門電路實現(xiàn)邏輯函數(shù)時，需要使用與門、或門、非門、用門電路實現(xiàn)邏輯函數(shù)時，需要使用與門、或門、非門、與或非門等器件，究竟將函數(shù)式變換成什么形式，要視所用與或非門等器件，究竟將函數(shù)式變換成什么形式，要視所用門電路的功能而定。門電路的功能而定。 例例1：將邏輯函數(shù)將邏輯函數(shù) 化為與非與化為與非與非形式。非形式。 例例2：試用或非門畫出

20、函數(shù)試用或非門畫出函數(shù) 的邏輯圖。的邏輯圖。BDCBCABY三、指定器件的邏輯函數(shù)化簡（三、指定器件的邏輯函數(shù)化簡（*） 注：注：將最簡與或式直接變換為其他類型的邏輯式時，將最簡與或式直接變換為其他類型的邏輯式時，得到的結果不一定也是最簡的。得到的結果不一定也是最簡的。CBAY27&ABCDY1CADCABACADCABAY128CACDACABACACDACABACADCABAY1&ABCDY1AC最簡最簡29本本小節(jié)小節(jié)內(nèi)容內(nèi)容 小結小結2.3 邏輯函數(shù)的公式化簡法邏輯函數(shù)的公式化簡法著重討論著重討論與或表達式與或表達式的化簡的化簡 一個邏輯函數(shù)可以有多種不同的邏輯表達式，

21、如一個邏輯函數(shù)可以有多種不同的邏輯表達式，如與與-或或表達式、表達式、或或-與與表達式、表達式、與非與非-與非與非表達式、表達式、或或非非-或非或非表達式以及表達式以及與與-或或-非非表達式表達式 乘積項最少且乘積項中變量因子最少。乘積項最少且乘積項中變量因子最少。常用的公式化簡方法常用的公式化簡方法(1) 并項法并項法( 2) 吸收法吸收法( 3) 消項法消項法(4) 消因子法消因子法( 5) 配項法配項法注：公式化簡的結果不一定唯一。注：公式化簡的結果不一定唯一。302.4.1 邏輯函數(shù)的兩種標準形式邏輯函數(shù)的兩種標準形式一、最小項和最大項定義一、最小項和最大項定義2.4 邏輯函數(shù)的卡諾圖

22、化簡法邏輯函數(shù)的卡諾圖化簡法 任何一個邏輯函數(shù)均可化成任何一個邏輯函數(shù)均可化成“最小項之和最小項之和”與與“最最大項之積大項之積”這兩種標準形式。這兩種標準形式。1、最小項、最小項 在在n變量邏輯函數(shù)中，變量邏輯函數(shù)中，若若m為包含為包含n個因子個因子的的乘積項乘積項，而且這幾個變量均以而且這幾個變量均以 原變量原變量或或反變量反變量 的形式在的形式在m中中出出現(xiàn)且僅出現(xiàn)一次現(xiàn)且僅出現(xiàn)一次，則稱，則稱m為該組變量的為該組變量的最小項最小項。311、二變量的全部最小項、二變量的全部最小項A B最小項最小項編號編號0 00 11 01 1A Bm0A BA BA Bm1m2m32、三變量的全部最小

23、項、三變量的全部最小項A B C最小項最小項編號編號0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0A B CA B CA B CA B CA B CA B CA B CA B Cm1m2m3m4m5m6m73、四變量的全部最小項、四變量的全部最小項編號為編號為 m0 m15（略）個變量邏輯函數(shù)必有且僅有個變量邏輯函數(shù)必有且僅有2 2個最小項個最小項N個變量的最小項個變量的最小項32表表2-4-1 三變量最小項編號表三變量最小項編號表33約定：原變量用約定：原變量用“1”1”表示；表示；反變量用反變量用“0”0”表示。表示。注：用編號表示最小項時，變量數(shù)注：

24、用編號表示最小項時，變量數(shù)不同，相同編號所對應的最小項名不同，相同編號所對應的最小項名也不同。也不同。如，如，6：對三變量邏輯函數(shù)為對三變量邏輯函數(shù)為 ABC；對四變量邏輯函數(shù)為對四變量邏輯函數(shù)為 ABCD34最小項的性質(zhì)最小項的性質(zhì): :任意一個最小項，只有一組變量取值使其值為任意一個最小項，只有一組變量取值使其值為1 1。任意兩個不同的最小項的乘積必為任意兩個不同的最小項的乘積必為0 0。全部最小項的和必為全部最小項的和必為1 1。CBACBA 35從最小項的定義出發(fā)可證明它還具有如下性質(zhì)：從最小項的定義出發(fā)可證明它還具有如下性質(zhì)：某一最小項若不包含在某一最小項若不包含在 F 中，則必在中

25、，則必在 中中； 具有具有相鄰性相鄰性的兩個最小項的兩個最小項之和可以合并成一項并之和可以合并成一項并消去一對因子消去一對因子。F將它們合并，可消去因子:只有一個因子不同的兩個最小項是只有一個因子不同的兩個最小項是具有相鄰性的最小項。具有相鄰性的最小項。 和 具有邏輯相鄰性。例如:ABCBCABCBCAAABCBCA最小項的性質(zhì)最小項的性質(zhì): :36 任何一個邏輯函數(shù)都可以表示成唯一的任何一個邏輯函數(shù)都可以表示成唯一的一組最小項之和，稱為一組最小項之和，稱為標準標準 與或與或 表達式表達式，也稱為也稱為最小項表達式最小項表達式。邏輯函數(shù)的最小項表達式邏輯函數(shù)的最小項表達式 對于不是最小項表達式

26、的與或表達式，對于不是最小項表達式的與或表達式，可利用公式可利用公式AA1 和和A(B+C)ABAC來配項展開成最小項表達式。來配項展開成最小項表達式。37 =(m0, m2, m3)= m 3+ m 2+ m 0利用基本公式利用基本公式 可以把任何邏輯可以把任何邏輯函數(shù)化為最小項之和函數(shù)化為最小項之和 的標準形式。的標準形式。1 AA例例1：可化為：BABYBAAABYBABAABY3, 2, 02m 邏輯邏輯 或或 運算運算邏輯函數(shù)的最小項表達式邏輯函數(shù)的最小項表達式38例例2：Y=AB+C 可化為可化為= (m1,m3,m5,m6,m7) = m3(1,3,5,6,7) + m 6+ m

27、 7 + m 3 + m 5+ m 1= m 7 邏輯邏輯 或或 運算運算利用基本公式利用基本公式 可以把任何邏輯可以把任何邏輯函數(shù)化為最小項之和函數(shù)化為最小項之和 的標準形式。的標準形式。1 AA CBBAACCABYCBACBABCAABCCABABC邏輯函數(shù)的最小項表達式邏輯函數(shù)的最小項表達式39CBAm2CBAm1如果列出了函數(shù)的真值表，則只要將函數(shù)值為如果列出了函數(shù)的真值表，則只要將函數(shù)值為1 1的那些最小項相加，便是函數(shù)的最小項表達式。的那些最小項相加，便是函數(shù)的最小項表達式。A B CY最小項0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10111

28、0100m0m1m2m3m4m5m6m7BCAm3CBAm55, 3, 2, 135321mmmmmY真值表真值表最小項之和最小項之和402、最大項、最大項表表2-4-2 三變量最大項編號表三變量最大項編號表 在在n變量函數(shù)中，若變量函數(shù)中，若M為為n個變量之個變量之和和，且這，且這n個變量均以原變量或反變量的形式在個變量均以原變量或反變量的形式在M中出現(xiàn)一次，中出現(xiàn)一次，則稱則稱M為該組變量的最大項。為該組變量的最大項。41從最大項定義出發(fā)可證明它具有如下重要性質(zhì)：從最大項定義出發(fā)可證明它具有如下重要性質(zhì)：在輸入變量的任何取值下在輸入變量的任何取值下必有一個且僅有一個必有一個且僅有一個最大項

29、最大項的值為的值為0； 全體最大項之積為全體最大項之積為0；某一最大項若不包含在某一最大項若不包含在F中，則必在中，則必在 中中； 任意兩個最大項之和為任意兩個最大項之和為1；(1) 只有一個變量不同的兩個最大項的乘積等于只有一個變量不同的兩個最大項的乘積等于各相同各相同變量之和變量之和。F CBCBACBA最大項的性質(zhì)：最大項的性質(zhì)：42由上面給出的最大項和最小項編號表及示例可知，由上面給出的最大項和最小項編號表及示例可知，最大項與最小項之間存在如下關系：最大項與最小項之間存在如下關系：iiiiMmmM,最大項與最小項之間的關系最大項與最小項之間的關系Y=ABC+ABC+ABC+ABC= m3(0,2,3,6) 用最大項之積表示用最大項之積表示Y=ABC+