布林代数与逻辑闸课件.ppt

1、3-1布林代數3-2基本邏輯閘及其特性3-3正邏輯與負邏輯表示方式3-4函數完全運算集合3-5布林函數的表示方式3-6邏輯閘的基本應用3-7布林函數的化簡3-8以SSI來設計組合邏輯電路 一、布林代數的公理（Axiom）布林代數是由一群元素的集合N、兩個運算子與、與一個補數運算子 所組成的一個代數結構，滿足下列的公理（或公設）：1.集合N至少包含兩個不相等的元素a、b，即ab。2.具封閉性（closure properties）：對任意兩個元素而言 (1)(2)3.交換律（commutative law）(1)a+b=b+a (2)abN a bN a bb a(a,bN)4.單位元素 a0a

2、a 1a(aN)(1)(2)5.結合律（associative law）(a b)ca(b c)(a,b,cN)(ab)ca(bc)(1)(2)6.分配律（distributive laws）a(b c)(ab)(ac)(a,b,cN)a(bc)a ba c(1)(2)7.補數元素（complement）aa1(a,aN)a a0(1)(2)8.對偶原理（principle of duality）：在布林代數中，將一個成立的敘述中之二元運算子與交換、0與1交換後，得到的敘述也必然是個成立的敘述。n 110f(X,.,X,X,1,0)n 110Df(X,.,X,X,0,1)即：若為一成立的敘述，

3、則其也為一成立的敘述。對偶函數n 110f(X,.,X,X,1,0)n 110f(X,.,X,X,0,1)9.逆轉換原理：若為一成立的敘述，則其逆轉換也為一成立的敘述。函數(XY)1X Y0(X Y)0(X Y)1(X Y)1例1：邏輯算式中，之雙對式（Dual）為(B)(C)(D)(A)解：(B)對偶函數之取法：變數不變，AND變OR，OR變AND，0變1，1變0。二、布林代數之基本定理 aNaaaa aa1.等冪律（idempotent law）對於每一個元素而言(2)(1)a1 1 a 00(aN)2.邊界定理（Boundedness theorem）且(2)(1)a3.補數的唯一性：在

4、布林代數中，每一個元素a的補數是唯一的。i01 ii10 iii(a)a4.在布林代數中且，5.吸收律（absorption laws）aabaa(ab)a(a,bN)(1)且(2)a,b,cNa(bc)(ab)ca(bc)(ab)c6.結合律（associative law），則：且(2)(1)7.笛摩根定理（DeMorgans Theorem）a,bN，則：(ab)a b(ab)ab(1)且(2)證明：(1)(ab)(a b)(ab)a(ab)b (aa)b(a(bb)(1b)(1a)1 11 (2)(ab)(a b)(a(a b)b(a b)(a a)b(a(b b)0 ba 0 000

5、a b(ab)(ab)(ab)a b(ab)(ab)ab為的補數，但亦為的補數補數是唯一的，同理，由對偶原理得證。abbcacabac(ab)(bc)(ac)(ab)(ac)8.同等定理（Consensus Theorem）(2)(1)pf：(1)abbcacabac(aa)bc(ababc)(acabc)abac(2)(ab)(bc)(ac)(ab)(ac)(bcaa)(ab)(ac)(abc)(abc)(ab)(1c)(ac)(1b)(ab)(ac)a(ab)abaababa(ab)a aab0abab aaba(1b)abaababa(aa)bab9.簡化定理(2)證明：(1)(2)(1

6、)(ab)(ab)aababa(ab)(ab)a aa ba bb b aa ba b0 a(1bb)aababa(bb)a 1a 10.相鄰定理(2)證明：(1)(2)(1)XXY(A)XY(C)XY(D)Y例1：布林函數等於(B)X解：(A)XXYXX YXYABC(ABC)(A)AB(B)C(C)1(D)ABC例2：將布林運算式化簡後之最簡結果為：解：(C)令XABC，則原布林函數運算式等於 XX1(A)XYXYX(B)X(XY)XY(C)(XY)(XZ)XYZ(D)(XY)(XY)XY例3：下列布林敘述何者錯誤？解：(D)(XY)(XY)XXYXYYYX(A)(AB)(AB)A(B)A

7、ABAB(C)ABAB(D)ABACBCABBC例4：下列何者之表示式是錯誤的？解：(D)ABBCACABAC(A)XXY1(B)XXYX(C)XXYXY(D)XYYZXZXYYZ例5：下列布林代數何者不正確？解：(C)XXYXY一、反閘（Not Gate）（又稱為反相器）1、符號：2.真值表：AF0110此處的A為輸入變數，F為輸出。3.FA4.特性：輸出為輸入的1s補數。（唸成A bar，即A的補數）二、及閘（AND Gate）1.符號：2.真值表：(兩輸入的AND閘）ABF0000101001113.輸出F=AB（當A與B同時成立時，F才有輸出）4.特性：當輸入端有一為0，則輸出為0。5

8、.範例：(1)(2)(3)6.等效電路A和B兩開關要同時關閉，燈泡才會亮。三、或閘（OR Gate）1.符號：2.真值表：(兩輸入端的 OR Gate)ABF0000111011113.輸出F=A+B（當A或B有一成立時，F才有輸出）4.特性：當輸入端有一為1時，輸出即為1。5.範例：(1)(2)(3)6.等效電路：A或B其中一個開關關閉，燈泡就會亮。四、反及閘（NAND Gate）1.符號：（兩輸入的NADN Gate）2.真值表：ABF0010111011103.輸出4.特性：當輸入端有一為0時，輸出即為1。相當於：NAND=AND+NOT FAB5.範例：(1)(2)(3)五、反或閘（N

9、OR Gate）1.符號：（兩輸入端的NOR）2.真值表：ABF0010101001103.輸出FAB 4.特性：當輸入端都為”0”時，輸出才為”1”，否則為”0”。5.相當於：NOR=OR+NOT6.範例：(1)(2)(3)六、互斥或閘（XOR Gate）1.符號：（兩輸入端的XOR）2.真值表：ABF0000111011103.輸出FABABAB4.特性：當輸入端不相同時，輸出為1。當輸入端有奇數個”1”時，則輸出為1。用於奇同位元偵錯。5.範例：(1)(2)(3)七、互斥反或閘（XNOR Gate）1.符號：（兩輸入端的XNOR）2.真值表：ABF0010101001113.輸出FABA

10、BAB4.特性：當輸入端相同時，輸出為1。當輸入端有偶數個1時，輸出為1，用於偶同位偵錯 5.範例：(1)(2)(3)例1：假設一邏輯模擬程式（logic simulator）可以接受1,0,U（U表示訊號的狀態未知）三種邏輯訊號狀態，則下列哪一個真值表（truth table）可以代表兩個輸入之反及閘（NAND）？2X2X1X1X(A)(B)01U01 U011U001U110U1111U U UUU U1U2X2X1X1X(C)(D)01U01 U010U01111000110UUU0UU 1UU解：(D)NAND Gate的特性是當或有一為”0”時，輸出都為”1”，所以只有(D)是正確的

11、。例2：依據右圖所示之邏輯電路，下列那一組輸入及輸出值是不對的？(A)A1=0，A2=1，B=1(B)A1=0，A2=0，B=0(C)A1=1，A2=1，B=1(D)A1=1，A2=0，B=1 解：(C)BA1A2A2A1A1A2當A1與A2不等時，B才為1。例3：1 1 1 1 0 0 0 0等於(A)0 0 0 1 (B)1 1 1 1(C)1 0 0 1(D)1 1 0 0解：(C)1 1 1 1 0 0 0 0=1=1 0 0 1 例4：下列脈衝輸入圖中電路後，輸出結果為何？解：對互斥或閘而言，若輸入端1的數目為奇數，則輸出為1，否則為0。輸出結果為10001110。ABABABAB例

12、5：下列有關閘（gate）之敘述，何者不真？(A)輸入均為0時，才輸出為1的閘為NOR Gate。(B)布林函數 Exclusive-OR（XOR）Gate。(C)布林函數 Exclusive-NOR Gate。(D)當輸入同時為1時，NOR Gate以及XOR Gate之輸出不同。所代表的為兩個輸入的所代表的為有兩個輸入的解：(D)當輸入同時為1時，NOR Gate及XOR Gate均輸出為0。說明：1.（XOR）為奇數函數，當有奇數個交換變數為1時，其值才為1，否則為0。2.（XNOR）為偶數函數，當有偶數個交換變數為0時，其值才為1，否則為0。3.一般而言，當交換變數的個數是奇數時，XO

13、R=XNOR。當交換函數的個數為偶數時，XOR與XNOR互為補數。在實際的數位電路上，一般以0代表低電位，1代表高電位，即L=邏輯0，H=邏輯1，此稱為正邏輯。反之，若以0代表高電位，1代表低電位，即H=邏輯0，L=邏輯1，則稱為負邏輯。一、正邏輯的AND Gate=負邏輯的OR Gate A B ZLLLL H LH LLH H H二、正邏輯的NAND Gate=負邏輯的NOR Gate A B ZL L HL H HH L HH H L同理，正邏輯的NOR Gate等於負邏輯的AND Gate；正邏輯的NOR Gate等於負邏輯的NAND Gate。例1：一邏輯電路以負邏輯表示為NOR g

14、ate，若以正邏輯表示則為：(A)OR gate(B)NOR gate(C)NAND gate(D)AND gate 解:(C)1.若任意一交換函數可由一個集合內的運算子表示時，該集合稱為函數完全運算集合（functionally Complete/Universal Set）。由於交換函數是由AND，OR與NOT等運算子組成的，所以AND、OR、NOT為一個函數完全運算集合。2.依據DeMorgan定理：，即AND與NOT組合後，可以取代OR，所以AND、NOT也是函數完全集合。3.同理，即OR與NOT組合後，可以取代AND運算，所以OR、NOT也是函數完全運算集合。a b(ab)ab(ab

15、)4.證明一個運算集合是否為函數完全運算集合的方法：利用該集合內的運算子產生一個已知為函數完全運算集合內的每一個運算子（例：AND、MOT或OR、NOT等）即是。5.函數完全運算集合有很多，並且可能只包含一個運算子，例如：NOR、NAND等。例1：證明NOR與NAND為函數完全運算集合。證明：(a)因為NOR可以產生函數完全運算集合OR,NOT內的每一個運算子，即(aa)a（NOT）a b(ab)ab（OR）所以NOR為一個函數完全運算集合。(b)因為NAND可以產生函數完全運算集合AND,NOT內的每一個運算子，即(a a)a（NOT）(a b)(a b)a b（AND）所以NAND為一個函

16、數完全運算集合。f(x,y,z)xyyzxyzf(x,y)xyf(x,y,z)xyxzyz例2：證明下列集合為函數完全運算集合：(a)集合f而(b)集合f,1而(c)集合f,1而 f(x,y,z)xyyzxyzxy(xy)證明：(a)（NOR）得證 f(x,1)xf(x,y)xy(b)（NOR）（AND)得證 f(x,x,x)xxxxxxxf(x,y,1)xyx 0y 0 xy(c)（NOR）（AND）得證 一、布林代數的表示法：正規表示法有二：1.積之和（Sum of Product）或最小項的和。2.和之積（Product of Sum）或最大項的乘積。分別說明如下：(一)最小項的和或SO

17、P型式：將布林函數化為乘積項的和，每乘積項稱之為最小項（Minterm），積項中均包含所有的變數。1.將布林函數化為積之和的型式，步驟：(1)若布林函數中補數的符號位於數個變數的組合上，則利用狄摩根定理將之拆開，使補數符號只位於單一變數上。(2)利用分配律予以展開。(3)刪除重覆項、零項等即得。2.將積之和（SOP）轉換為最小項的和，步驟：(1)將所有積項缺少的變數乘上（所缺變數之補數加上所缺變數之補數）。(2)利用乘法分配律予以拆開。(3)刪除重覆項即得最小項的和。例1：三變數之最小項與最大項 XYZ最小項符號最大項符號000 XYZm0(X+Y+Z)M0001XYZm1(X+Y+Z)M10

18、10XYZm2(X+Y+Z)M2011XYZm3(X+Y+Z)M3100XYZm4(X+Y+Z)M4101XYZm5(X+Y+Z)M5110XYZm6(X+Y+Z)M6111XYZm7(X+Y+Z)M7F(a,b,c,d)abc(2,3,4,5,6,7,12,13,14,15)(0,1,2,3,5,7,12,13,14,15)(0,1,2,3,4,5,6,7,11,12)(2,3,6,7,10,11,12,13,14,15)例2：若，則其標準積之和表示方式為：(b)(c)(d)(a)解：(d)F(a,b,c,d)abcab(cc)(dd)c(aa)(bb)(dd)abcdabcdabcdabc

19、dabcdabcdabcdabcdabcdabcdabcdabcd(2,3,6,7,10,11,12,13,14,15)本題也可另解如下：a b c d a b c d 0 0 1 0(2)1 1 0 0(12)0 0 1 1(3)1 1 0 1(13)0 1 1 0(6)1 1 1 0(14)0 1 1 1(7)1 1 1 1(15)1 0 1 0(10)1 0 1 1(11)1 1 1 0(14)1 1 1 1(15)綜合以上兩項得 F(a,b,c,d)(2,3,6,7,10,11,12,13,14,15)F(1,A,B)AB,F(0,A,B)AB(A)(1,2,6,7)(B)(0,2,3

20、,4,5)(C)(1,2,3,7)(D)(2,3,6,7)例3：設F(X,A,B)為邏輯正數，且則F等於：解：(C)F(X,A,B)(1,2,3,7)(二)最大項的乘積（Product of Maxterms）：將布林函數化為和項的乘積，每個和項稱為最大項，和項中需包含所有的變數。1.將布林函數化為和之積（POS）的型式，步驟：(1)若布林函數中補數的符號位於數個變數的組合上，則利用狄摩根定理將之拆開，使補數符號只位於單一變數上。(2)利用加法分配律予以展開。(3)刪除重覆項、零項等即得。2.將和之積（POS）轉換為最大項的乘積，步驟：(1)將每一和項所缺的變數加上（所缺變數所缺變數的補數）。

21、(2)利用加法分配律予以展開。(3)刪除重覆項即得最大項的乘積。F(X,Y,Z)XYZ(XY)解 F(X,Y,Z)X(YZ)(XY)32(XYZ)(XY)(XYZ)(XYZZ)(XYZ)(XYZ)(XYZ)MMM(2,3)例4：試將三個變數的布林函數化為最大項的乘積函數。*加法分配律*(三)SOP與POS的關係：1.SOP型式著重在描述函數中，函數值為1的部份。POS型式著重在描述函數中，函數值為0的部份。2.對某一函數，其SOP與POS恰為互補的關係。例5：F(A,B,C)ABC以最小項的和與最大項的積表示。解：F(A,B,C)A(BB)(CC)(AA)(BC)76541ABCABCABCA

22、BCABCABCmmmmmm(1,4,5,6,7)M(0,2,3)*最小項的和*最大項的積*1F(w,x,y,z)(0,2,5,6,7,8,10,13)2F(w,x,y,z)(1,3,5,7,10,13,15)例6：假設，則下列何者為非？12F F(0,2,6,8)12FF(4,5,7,9,10,11,12,14),12F F(5,7,10,13)12FF(1,3,5)(a)(b)(c)(d)解：(b)2F(w,x,y,z)(1,3,5,7,10,13,15)(0,2,4,6,8,9,11,12,14)2F(w,x,y,z)(1,3,5,7,10,13,15)12F F(0,2,6,8)12F

23、F(4,5,7,9,10,11,12,13,14),12F F(5,7,10,13)12FF(0,2,4,5,6,7,8,9,10,11,12,13,14)(1,3,15)（AND）（XOR）（AND）（OR）四、布林函數的性質：1.對任意一布林函數f而言，其標準SOP（或POS）型式是唯一的。2.若兩個布林函數的標準SOP（或POS）型式相等時，則該兩個函數為邏輯相等（logically equivalent）。3.對於n個布林變數而言，共可組合成個布林函數。說明因n個布林變數可組成項SOP型式，而每一項有0與1兩種狀態，故共有 個交換函數組合。n22123F(x,x,x)112323123

24、F(x,x,x)F(0,x,x)xF(1,x,x)x111232323F(x,x,x)F(0,x,x)xF(1,x,x)x112323231F(x,x,x)F(0,x,x)xF(1,x,x)x123231231F(x,x,x)F(0,x,x)xF(1,x,x)x例7：設為邏輯函數，則下列何者為真？(B)(C)(D)(A)解：(C)一、基本邏輯閘在應用上一般用來控制數位信號的流向或改變數位信號的狀態，藉以控制後面的數位系統之動作方式。邏輯閘最常用的方式有四：C0F0C1FX C0FXC1F1 1.控制閘（Controlled gate）2.反相控制閘（Inverted Controlled-ga

25、te）C=0 F=1C=1 F=XC=0 F=XC=1 F=03.控制補數閘（Controlled-inverted gate）C=0 F=XC=1 F=XC=0 F=XC=1 F=X4.真值/補數/0/1元件：C1C0F00X01110X110二、布林函數的執行任何一個布林函數皆可以用下列三種方式之一執行。1.使用開關（Switch）：如CMOS傳輸閘或相當電路等。2.使用AND、OR或NOT等基本閘的結合。3.使用NAND或NOR等通用閘來執行（下節介紹）1F(A,B,C)ABBCAC2F(A,B,C)(AB)(BC)(AC)3F(A,B,C)(AB)AC 4F(A,B,C,D)(ABCD

26、)BC 例1：試以基本邏輯閘執行下列布林函數。(b)(c)(d)(a)解：(a)(b)(c)(d)三、由邏輯電路求布林函數由已知的邏輯電路求布林函數的步驟：1.從輸入端由左而右逐次寫出各個邏輯閘的輸出，一直到最後一級輸出。2.將最後一級的輸出利用布林代數的一般定理予以合併或分開，求得最後的標準SOP（或POS）型式。例8：求出下圖之輸出布林函數 ABA ABAB BFA AB AB BA ABAB BA ABAB BA(AB)(AB)BABABAB由1點得，由2點得由3點得（狄摩根定理）解：例9：列出下圖所示輪出函數的真值表。解：FAABBAB(AAB)(BAB)(AA B)(BA B)(AA

27、)(AB)(BA)(BB)(AB)(AB)ABABAB 其真值表如下：ABF001010100111例10：下圖求(a)其輸出函數f；(b)最簡的積之和型式；(c)最簡的和之積型式；(d)電路圖。f456 4D 3D 3C2B C 5C2D(12)CACBC6B CD(ABCAC)CACBC31 2 f(ABC)(ACD)2A CfACBD1A B C解：(a)f456(b)(c)(d)電路圖如下：例11：根據圖所示的邏輯電路圖，若A=1，B=0，C=1時，則之輸出應為：(a)(0,0)(b)(0,1)(c)(1,0)(d)(1,1)解:(b)X(ABC)(10 1)0Y(AB)CCD)(10

28、)10 1(1 1)01例12：如下圖所示電路中，假設G2或閘壞掉，而造成其輸出一 直為1。藉由觀察Z輸出值，試問下列哪一組輸入訊號(ABCD)可以偵測此電路錯誤的狀況？(A)0000 (B)0011 (C)1001 (D)0111 解:(A)當ABCD=0000時，G1輸出為0，因G3輸出為1，而G2輸出一直為1，造成Z的輸出為1，產生錯誤，故可偵測出G1故障。布林函數的化簡方法，一般分成三種：1.布林函數的定理化簡法2.卡諾圖化簡法3.列表法（Quine-McCluskey Method）茲分別介紹如下：係依據布林代數的一般定理，直接對指定的函數進行化簡動作。其缺點是較無規則可循，有時需靠

29、經驗才能化簡出較複雜的函數。x y0 xy?例1：若，則解：xyxyxyxyxyxyxy(A)xyxyx(B)x(xy)xy(C)(xy)(xz)xyz(D)(xy)(xy)xy例2：下列布林函數何者錯誤？解:(D)(xy)(xy)xxyxy0 x例3：如下圖，輸出P為何？解:P(XYZ)(XZ Y)Y(XYZXZ Y)Y(XYZXZY)Y(XYZXZY)YXYZ(A)BCABACD(B)BCABACD(C)BCABACD(D)BCABACD例4：如下圖所示電路，其布林函式F為何？解:(C)F(CD B)A)(BC)(CD B A)(BC)(CDB)ABCBCABACD f(A,B,C)(A(

30、AB)C)(A)C(B)BC(C)AC(D)ABC例5：布林函數等效函數是解:(B)A(AB)Bf(A,B,C)BC，fABCABCDBCD(A)BC(B)BCC(C)CBC(D)BBC例6：下列何者函數與布林函數不等效。解:(B)BCCBCBBCABCABCDBCDABCBC(ADD)ABCBC(AD)ABCABCBCDB(AAC)CBCDB(AC)CBCDAB(BCC)BCDABBCBCDBC(一)化簡原理 利用XY+XY=Y之基本概念做化簡工作。(二)化簡原則1.若兩項只差一個變數，則稱此兩項相鄰。2.圖的上下列、左右行均視為相鄰，可以圈起來（合併）。3.每一項可重覆使用，圈起的相鄰項愈

31、多，可消去的變數愈多。圈起的項數必須是2的次方。4.圈起相鄰的項時，可消去N個變數，N為1，2，.。5.若以SOP型式表示時，則合併卡諾圖中”1”的部份，並以最小的和項方式表示。若以POS型式表示時，則合併卡諾圖中“0”的部份，並以最小的積項方式表示。6.合併時，為求最簡型式，能合併多項時，不能只取其中一部份合併。(三)二個變數到五個變數的卡諾圖 1.二變數 Y X01 002 1132.三變數 YZ X00011110 00132 145763.四變數 YZ WX00011110 000132 014576 1112131514 108911104.五變數 XYZ VW00000101101

32、0100101111110 0001324576 0189111012131514 112425272628293130 101617191820212322K2WXYZ0101若布林函數有K個變數，則卡諾圖的方格數需表示方式：以補數來代表0，以非補數來代表1。例如四變數的卡諾圖，5的位置為。個。(四)卡諾圖的缺點：變數愈多，卡諾圖愈大，愈難找出關係化簡。F(A,B,C,D)BCDABCABCABCD(A)CDABD(B)CDABDBC(C)CDABCD(D)CABD例1：布林函數，則F化簡後為 FBCABDCD解:F(W,X,Y,Z)(2,3,5,8,9,10,11,12,13)(A)FWY

33、XYXYZ(B)FWXXYWYXYZ(C)F(XY)(WYZ)(WYZ)(WXY)(D)FWXXYWYZXYZ例2：求布林函數之最簡化式 解:(B)F(W,X,Y,Z)XYWYXYZf(A,B,C,D)(1,2,4,7,8,11,13,14)(A)(AB)(CD)(B)(AB)(CD)(C)(A B)(C D)(D)(AB)(CD)例3：簡化布林函數可得：解:(D)f(A,B,C,D)ABCDABCDABCDABCDABCDABCDABCDABCDAB(CD)AB(CD)AB(CD)AB(CD)(ABAB)(CD)(ABAB)(CD)(AB)(CD)(AB)(CD)(AB)(CD)(AB)(C

34、D)(AB)(CD)ABCDABCDABCDABCDABCDABCDABCD(A)(AB)(CD)(BD)(B)(AB)(CD)(BD)(C)(AB)(CD)(BD)(D)(AB)(CD)(BD)例4：布林函數可簡化為：解:(B)F(AB)(CD)(BD)ABCBCDABCDABCD(A)ABC(B)ABBDCD(C)BDCDABD(D)ABBD例6：布林函數可簡化為：解:(D)CD AB0001111000011111111110FABBD例7：Obtain the simplified output function in both sum of products and product

35、of sums for the following logic diagram.解:F(BCD)(AB)(CD)(A B C)B C DA BA BC DC DA B Cm(0,3,4,5,6,7,8,9,10,11,12,13,14,15)M(1,2,13)(1)sum of product 利用卡諾圖化簡如下：因此，FABABCDCDAC(2)product of sum 利用卡諾圖化簡如下：F(ABCD)(ABCD)(ABCD)(五)加入隨意項（Dont care）：所謂的 隨意項 即是一種不定狀態，對布林函數而言，是一種不可能發生的變數組合或對輸出結果沒有影響的項，其值可為0或1，依實

36、際使用而定。具有隨意項的卡諾圖化簡步驟：1.將具隨意項的布林函數在卡諾圖所對應的方格中填入。2.將其餘非隨意項的布林函數值填入卡諾圖對應的方格中(若是最小項則填“1”，最大項則填“0”)。3.選擇相鄰方格數最多的方格予以合併化簡，卡諾圖中的x可以不被選擇。例8：Simplify F together with is dont care condition d in(a)sum of product form(sop)and(b)Product of sum form(pos)。F(A,B,C,D)(0,1,2,8,9,12,13)D(A,B,C,D)(10,11,14,15)解:(a)sum

37、of product form F(A,B,C,D)ABCBD(b)Product of sum form F(A,B,C,D)(AB)(CD)例9：A logic circuit implements the following boolean function：FACACDIt is found that the circuit input combination A=C=1 can never occur.Find a simpler expression for F using the proper dont care conditions.(A)ACD(B)ACAC(C)ACAD(D

38、)CAD(E)none of above 解:(D)FACACD由題意，且A=C=1為一隨意條件（dont care condition）；因此，其真值表及卡諾圖可繪製如下：ACDF000000100101011110011010110 x111x經卡諾圖化簡後可得FCAD F(A,B,C,D)m(1,3,8,9,10,12)d(0,11,13,14)(A)BDAB(B)BDAC(C)ADBD(D)ADBD例10：化簡布林函數可得？（m代表mintern，d代表dont care）F(A,B,C,D)BDAD解:(六)最簡函數與最簡式 1.設兩個交換函數 與 ，若當G的值為1時，F的值也必然為

39、1，則稱F包含G，記為 。因此，當F包含G時，函數F在真值表上值為1的每一組合下，函數F的值也必為1。若函數F包含G，同時函數G也包含F，則函數F與G相等（F=G）。FGn 110F(X,.,X,X)n 110G(X,.,X,X)GWXYFWXYZFWXYZWX(YY)YZWXYWXY YZWXYGYZFG例13：設，而，則G為F的一個隱含項。，G為F的一個隱含項。證明：2.設G為交換函數 的乘積項且 ，若當中的任何一個字母變數去掉後，F不再包含G，則G稱為F的質隱項（prime implicant）。n 110F(X,.,X,X)FG例如：XY為F(X,Y,Z)XYXYYZ的一個質隱項。3.

40、卡諾圖上的隱含項與質隱項 (1)在卡諾圖中，所有圈起來的格子群，均形成隱含項，即所有可併的項的集合。(2)在卡諾圖化簡中，可以形成最簡型式的項，即為質隱項。例如：WXY,XZ,WXZ,WXY,WXZ,WYZWXY,XZ,WXY,WYZ在上面的卡諾圖中：質隱項（少了C與E）隱含項4.(1)一個交換函數F的任何最簡的SOP表示式，均為一個F的質隱項的和。(2)任何一個n個交換變數的交換函數 均可等效地表示為該函數的所有質隱項的和；此函數F之所有質隱項之和稱為F完全和（complete sum）。5.必要質隱項（Essential prime implicant）：係指一個質隱項若其所包含的最小項中

41、，至少有一個未被其它質隱項所包含時稱之。由於交換函數中的每一個最小項都必須包含於最簡式中，所以所有必要質隱項皆必須包含於最簡式中。n 110f(X,.,X,X)F(W,X,Y,Z)(4,5,8,12,13,14,15)F(W,X,Y,Z)(1,5,9,13,14,15)例14：下列交換函數中，那些是質隱項？那些是必要質隱項？(2)(1)解:(1)所有質隱項都為必要質隱項。FXY WXWYZ(2)=YZ,WXZ,WXYYZ,WXY所有質隱項必要質隱項 6.循環質隱項圖（cyclic prime implicant map）：若每一最小項均被兩個質隱項包含，造成沒有必要質隱項，謂之。例16：F(X

42、,Y,Z)(0,2,3,4,5,7)F(X,Y,Z)XZ YZXYF(X,Y,Z)YZ YZXY卡諾圖化簡後，可得兩個最簡式：質隱項XZ,YZ,XY,YZ,XZ,XY沒有必要質隱項。7.由上述說明，要獲得一個交換函數的最簡SOP表示式，其程序如下：(1)決定所有必要質隱項，並且也含在最簡式中。(2)由質隱項中刪除所有被必要質隱項包含的質隱項。(3)若步驟(1)得到的結果能包含函數F的所有最小項，該結果即為最簡式，否則適當選取質隱項以使函數F能完全被包含，並且質隱項的數目為最少。1.適用範圍：函數中變數數目超過4個以上。2.優點：可產生一簡化的標準式，且對多變數，計算機可分享快速處理。3.列表法

43、的簡化程序：(1)找出簡化函數中的質隱項。(2)從質隱項中再選出具有最少變數符號的表示式。4.簡化步驟：(1)將指定函數的全及項一一列出，並由所含1的個數來分組。(2)把每一全及項與其它全及項比較，若遇有兩個全及項僅差一個變數時，則消去該變數，形成一缺一變數的新項，以此循環，直到全部全及項比較完畢為止。(3)接著對新得的新項進行類似的比較，直到沒有變數可消除為止。(4)剩下的各項，以及在以上步驟不能合併的各項，就是列表法中第一部份要找的質隱項。例1：以列表法簡化下列布林函數F(0,1,2,8,10,11,14,15)解:WXYZ00000全及項中含1個“1”100012001081000101

44、010全及項中含2個“1”111011全及項中含3個“1”141110151111全及項中含4個“1”依照全及項中所含1的數目分組 2.全及項兩兩比較，只要有一個變數相異，就可消去該變數，以一代表。n2(n 0)WXYZ(0,1)000質隱項(0,2)000注意：只需比較各組之間相差為之數即可。(0,8)000(2,10)010(8,10)100(10,11)101(10,14)110“”代表已合併過的全及項，其不為質隱項。(11,15)111(14,15)1113.對所產生的新項，重覆步驟2。WXYZ(0,2,8,10)00由步驟2.合併而得。(0,8,2,10)00質隱項(10,11,14

45、,15)11兩項相同，只需寫一項即可。(10,14,11,15)104.未有 處即為質隱項Wwxyxzwy 例2：以列表法化簡布林函數 f(w,x,y,z)(1,4,6,7,8,9,10,11,15)解:(a)(b)(c)000111,9(8)8,9,10,11(1,2)010044,6(2)8,9,10,11(1,2)100088,9(1)8,10(2)01106100196,7(1)1010109,11(2)10,11(1)011171011117,15(8)11,5(4)111115簡化後xyzwxzwxyxyzwyzwx 每一項均為質隱項 5.必要質隱項（Essential prime

46、 implicant）的選擇。將所有質隱項列表，每一個質隱各佔一列，每一個全及項佔一行。每列中放置有x者表示該質隱項所含的全及項。選擇最少的質隱項來包含該函數的全部全及項。以上例為例，質隱項表如下：xyzwxzwxyxyzwyzwx14678910 11 151,94,66,7 7,1511,15 8,9,10,11 xyz,wxzwx(1)檢查質隱項表中，僅含一個“x”的各行，所選出的質隱項稱為必要質隱項。與為必要質隱項。(2)再者，檢查函數各行，是否都已包含在必要質隱項中，若是，則打一“”。xyzwxzwx從表中：包含全及項1,9包含全及項4,6 包含全及項8,9,10,11除7與15外，

47、函數的所有全及項均包含在必要質隱項中，所以必須把xyz(7,15)選入以得最簡函數 Fxyzwxzwxxyz例3：試求下列交換函數之最簡表示式 f(w,x,y,z)(2,6,7,8,13)d(0,5,9,12,15)解:由於求質隱項時，必須把Dont care項考慮進去，所以相當於求下列函數之質隱項。f(w,x,y,z)(0,2,5,6,7,8,9,12,13,15)WXYZ00000200108100050101601109100112110070111131101151111(1)wxzwyzwyzwxyWXYZ(0,2)000 (F)(0,8)000 (E)(2,6)010 (D)(8,

48、9)100(8,12)100(5,7)011(5,13)101(6,7)011 (C)(9,13)101(12,13)110(7,15)111(13,15)111(2)wyxzWXYZ(8,9,12,13)10 (B)(5,7,13,15)10 (A)(3)(4)函數f的質隱項表如下：xzwywxywyzxyzwxz267813(A)(B)(C)(D)(E)(F)由於每一最小項均包含於兩個質隱項中，所以沒有必要質隱項。最小項7,8,13只有A,B,E可以包含它們，但E較B複雜，故只取A與B。其次最小項2,6都可以由D包含，故函數f的最簡式為：f(w,x,y,z)ABDxzwywyz一、以雙層邏

49、輯電路來設計邏輯電路 1.雙層的邏輯電路設計是最簡單的設計方式，其基本形式有兩種，即AND-OR（SOP表示方式）與OR-AND（POS表示方式）。2.一般也常使用NAND與NOR兩個邏輯閘來設計組合電路，利用這四種邏輯閘的組合，雙層邏輯電路便有下列十六種不同的架構，如表3-2所示，表中有八種退化成單一運算的組合，不能執行任何交換函數，未退化的八種組合，依其性質可分成如表3-3的兩組。表3-2雙層邏輯電路組合方式執行的交換函數是否退化AND-ANDAND是AND-ORAND-OR否AND-NANDNAND是AND-NORAND-OR-NOT否OR-ANDOR-AND否OR-OROR是OR-NA

50、NDOR-AND-NOT否OR-NORNOR是NAND-ANDAND-OR-NOT否NAND-OROR是NAND-NANDAND-OR否NANDP-NORAND是NOR-ANDAND是NOR-OROR-AND-NOT否NOR-NANDOR是NOR-NOROR-AND否表3-3未退化之雙層邏輯電路之對偶關係 在上表中，SOP型式的一組相當於AND-OR組，而POS型式的一組相當於OR-AND組。同一組中，四種不同型式的轉換很容易，但是在不同組間的轉換就需採對偶關係，才能轉換。例1：將下列交換函數的最簡式表示成雙層邏輯電路的八種型式。F(A,B,C,D)(3,4,5,8,9,10,11,12,13