布耳代数与逻辑闸

1、布耳代數與邏輯閘Outlinen2-1 基本定義n2-2 布耳代數的公理定義n2-3 布耳代數的基本定義與性質n2-4 布耳函數n2-5 典式與標準式n2-6 其他的邏輯運算n2-7 數位邏輯閘n2-8積體電路基本定義n代數結構公設：封閉性 對於Set的每對元素，若二元運算子只訂一條規則已得到一個Set的唯一元素。結合律（ x * y）* z = x * ( y * z )交換律 x * y = y* x基本定義n代數結構公設：單位元素 e S，對於任何x S，e * x = x * e = x，則e稱為集合S二運算元*的單位元素反相性 集合S相對於二元運算*具有單位元素e，若對每個x S，存

2、在y S，使得x * y = e，成立時，稱其有反相性。分配律 x * ( y * z ) = ( x * y ).( x * z ) 布耳代數的公理定義n韓丁頓公設：封閉性：+、*單位元素：+、*交換性：+、*分配性：+、*X B，存在有一個X BnX+X=1nX*X =0至少存在二個元素x , y B，使得x y布耳代數的公理定義n二值布耳代數定義在一個二元素集合上，即 B=0，1x yx .y0 0 00 1 01 0 01 1 1x yx + y0 0 00 1 11 0 11 1 1 x x 0 1 1 0布耳代數的基本定義與性質n對偶性(duality principles) 若二

3、進位運算子與單位元素互相交換，可從一部分得出另部份。 (a) x + 0 = x (b) x*1=x (b) x +x = 1 (b) x*x=0布耳代數的基本定義與性質n基本定理公設2(a) x+0=x(b) x.1=x公設5(a) x+x=1(b) x.x=0定理1(a) x+x=x(b) x.x=x定理2(a) x+1=1(b) x.0=0定理3,乘方性(x)=x公設3,交換性(a) x+y=y+x(b) xy=yx定理4,結合性(a) x+(y+z)=(x+y)+z(b) x(yz)=(xy)z公設4,分配性(a) x(y+z)=xy+xz(b) x+yz=(x+y)(x+z)定理5,

4、第摩根(a) (x+y)=xy(b) (xy)=x+y定理6,吸收性(a) x+xy=x(b) x(x+y)=x布耳代數的基本定義與性質n基本定理定理1(a):x+x=x.證明: x+x=(x+x)*1 由公設:2(b) =(x+x)(x+x) 5(a) =x+xx 4(b) =x+0 5(b) =x 2(a) 布耳代數的基本定義與性質n基本定理定理1(b) ：x*x=x證明: x*x=xx+0 由公設: 2(a) =xx+xx 5(b) =x(x+x) 4(a) =x*1 5(a) =x 2(b) 布耳代數的基本定義與性質n基本定理定義2 ：x + 1 = 1證明: x + 1 = 1*(x

5、 +1) 由公設: 2(b) =(x + x)(x + 1) 5(a) = x + x*1 4(b) = x + x 2(b) = 1 5(a)布耳代數的基本定義與性質n基本定理定理 3： (x) = x，已知x + x =1及 x * x=0，定義了x的補數。故x的補數為x，亦即為(x)，由於補數是唯一，因此可得到(x)=x布耳代數的基本定義與性質n基本定理定理6： x + xy =x證明： x + xy =x*1 +xy 由公設: 2(b) =x(1+y) 4(a) =x(y+1) 3(a) =x*1 2(a) =x 2(b)布耳代數的基本定義與性質n基本定理第摩根定理： (x + y)=

6、xy x y x+y(x+y)xyxy 0 0 0 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0布耳代數的基本定義與性質n運算子的先序性 (1)括號 (2)NOT (3)AND (4)ORn文氏圖 yxxyxy xyxy布耳函數n布耳函數即由二進位變數，OR、AND兩個二進位運算元，及單一運算子NOT，括弧，以及一各等號所組成表示式。 F1=xyz F2=x+yz F3=xyz+xyz+xy F4=xy+xz x y z F1 F2 F3 F4 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0布耳函數-代數

7、運算n個文字符號為一各有撇號或無撇號的變數n可以藉由待數運算而加以簡化n例： x + xy=(x + x)(x + y)=1*(x + y)=x + y x(x + y)=xx + xy =0 + xy =xy典式與標準式n全及項: 考慮x、y二進位變數，xy、xy、xy、xy此四項表示文氏圖的一個不同區域。n全或項: 考慮x、y二進位變數，x+y、x+y、x+y、x+y典式與標準式 x y z 全及項全或項 積項 符號和項 符號 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1xyz m0 xyz m1xyz m2xyz m3xyz m4xyz

8、m5xyz m6xyz m7x+y+z M0 x+y+z M0 x+y+z M0 x+y+z M0 x+y+z M0 x+y+z M0 x+y+z M0 x+y+z M0 x+y+z M0典式與標準式nf1=xyz+xyz+xyz+xyz+xyz (f1)=(x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z) =M0.M2.M3.M5.M6n任何布耳代數可表示成全或向的積n將布耳函數表示成全及項的和或者全或項的積，統稱為典式(canonical form)典式與標準式n標準式n積項之和(sum of products) : F=y + xy+ xyzn和項之積(product

9、 of sums) : F=x(y+z)(x+y+z+w)n非表準式n例:F=(AB+CD)(AB+CD)n轉化: F=(AB+CD)(AB+CD)=ABCD+ABCD 數位邏輯閘名 稱圖示符號代數函數ANDF=xy ORF=x+y 反項器F=x 緩衝器F=xXYXYxx圖示符號圖示符號數位邏輯閘圖示符號圖示符號F=xy互斥-NORF=x y XORF=(x+y) NORF=(xy)NAND代數函數圖示符號名 稱XYXYXYXY數位邏輯閘n除了反相器與緩衝器之外，均可擴展至多於二個的輸入端。 XYZ三輸入之NOR閘(x+y+z)XYZ(xyz)三輸入之NAND閘積體電路nIC是一種稱為晶片的小

10、型矽半導體晶體n各種閘在晶片中互相連結成所需要的電路n以陶瓷或是塑膠封裝，接腳焊接至外部(1464 or more)積體電路n積體的層次數位IC通常根據邏輯閘數目所決定之電路複雜度來分類n小型積體(small-scale integration，SSI):10n中型積體(medium-scale integration，MSI):10100n大型積體(large-scale integration，LSI):數百到數千n超大型積體( very large-scale integration，LSI):數千電路積體n數位邏輯族以電路技術予以分類，此種電路技術為數位邏輯族nTTL 電晶體-電晶體邏輯nECL 射極耦合邏輯nMOS 金屬氧化物半導體nCOMS 互補式金屬氧化物半導體電路積體n積體電路閘-TTL區分為5400、7400系列n 5400適於軍事使用n 7400適於商業用途 Vcc與GRD(接地):電源