布林代数与逻辑闸

1、第二章第二章布林代數與邏輯閘2-1 基本定義基本定義封閉性結合律交換律單位元素 ,則e為單位元素反元素分配律)()(zyxzyxxyyxxexxeeyx)()()(zxyxzyx2-2 布林代數的公理與定義布林代數的公理與定義1.(a)運算符號 + 具有封閉性。 (b)運算符號 具有封閉性。2. (a) + 具有單位元素0： (b) 具有單位元素1： 3. (a) + 具有交換律： (b) 具有交換律： xxx00 xxx11xyyxxyyx布林代數的公理與定義布林代數的公理與定義4.(a) 對 + 具有分配性： (b) + 對 具有分配性： 5.對任一元素 ，則存在一元素 (稱為 的補數)，

2、使得(a). 且 (b).6.至少存在兩個元素 ，使得 。 )()()(zxyxzyx)()(zxyxzyxBxBx x1 xx0 xxByx,yx 2-3 2-3 布林代數的基本定理與性質布林代數的基本定理與性質定理1 (a) (b)定理2 (a) (b)定理3 自補定理定理4 結合律 (a) (b) xxxxxx11x00 xxx)(zyxzyx)()(zxyyzx)()(布林代數的基本定理與性質布林代數的基本定理與性質定理5 迪摩根定理 (a) (b) 定理6 消去定理 (a) (b)yxyx )(yxxy )(xxyxxyxx )(Boolean LawsNameAND formOR

3、formIdentity law1A = A0 + A = ANull law0A = 01 + A = 1Idempotent lawAA = AA + A = AInverse lawAA = 0A + A = 1Commutative law AB = BAA + B = B + AAssociative law(AB)C = A(BC)(A+B)+C = A+(B+C)Distributive lawA+BC = (A+B)(A+C)A(B+C) = AB + ACAbsorption lawA(A+B) = AA + AB = ADeMorgans lawAB = A + BA +

4、B = ABWhy do we need boolean laws?These laws allow us to simplify expressions.The has the effect ofMaking the expression smaller and easier to manipulateRemoving redundancy from expressionUsing fewer logic gatesThis usually translates into smaller hardwareHowever, not logic structures cannot take ad

5、vantage of simplificationMay wish to reduce other metric like packagesExamples of application of boolean lawsSimplify the following expression: ABC ABC B (A A)BC B1BC B BC B B(C 1) B2-4 布林函數布林函數布林函數- 包含二元變數、常數值1和0以及邏輯運算符號的代數表示式。布林函數之閘電路圖布林函數布林函數布林函數之閘電路圖重合定理與迪摩根定理重合定理與迪摩根定理重合定理 1. 2.迪摩根定理 1. 2.)()()

6、(zxyxzyzxyxzxxyyzzxxyFCBAFCBA.).(FCBAFABC.).(2-5 正規型式與標準型式正規型式與標準型式正規型式 全及項(minterm)的和與全或項(maxterm)的積標準型式 積項和(Sum of Products) 和項積(Product of Sums)三個二元變數之全及項與全或項三個二元變數之全及項與全或項全及項(minterm)與全或項(maxterm)全及項全或項xyz項目符號項目符號000 xyzm0 x+y+zM0001xyzm1x+y+zM1010 xyzm2x+y+zM2011xyzm3x+y+zM3100 xyzm4x+y+zM4101x

7、yzm5x+y+zM5110 xyzm6x+y+zM6111xyzm7x+y+zM7Truth TablesTruth tables show all possible inputs of a function and the values that the output takes for all those inputs.Given n inputs, there are 2n possible input combinations.Order the rows of the table in increasing order for binary word of n bits.ABCf(

8、A,B,C)00000010010001111000101111011111From Truth Tables to Min Term ExpressionsIt is trivial to convert a truth table to a min term expression.The individual parts of a min term expression (the AND parts) describe when the function will be one.Any one of the and parts will cause the expression to be

9、 true.At all other times the expression is false.Only one AND term can be true for any given input set.Forming min term expressionsABCf(A,B,C)00000010010001111000101111011111Expression is one hereABCABCABCABCM ABC ABC ABC ABCTherefore the following expression totally captures the functionImplementin

10、g this with logicABC BCABCABCABCABCAMDont Care cases in Boolean expressionsABCf(A,B,C)000001000X111000X01111X1Expression is one hereTherefore the following expression totally captures the functionACBCABM AC BC ABImplementing any boolean function1Write down the truth table for the function2Provide in

11、verters to generate the complement of each input3Draw an AND gate for each term with a 1 in the result column4Wire the AND gate to the appropriate input lines5Feed the output of all and gates into an OR gateConvert the following truth table to a boolean expressionABCf(A,B,C)0001001001010110100010101

12、1011111Some examples .ABCf(A,B,C)00010010010101101000101011011111ABC f = Some examples .ABCf(A,B,C)00010010010101101000101011011111ABC ABC f = Some examples .ABCf(A,B,C)00010010010101101000101011011111ABC ABC ABC f = Some examples .ABCf(A,B,C)00010010010101101000101011011111ABC ABC ABC ABCf = Implem

13、ent it with logic devices?Implement it with logic devicesImplement it with logic devicesImplement it with logic devicesABCBACABCCBADesign of logic from Truth Table to NAND gatesABCf(A,B,C)00000011010001111000101111011110ABCFrom Truth Table to NOR gatesABCf(A,B,C)00000011010001111000101111011110ABCSu

14、m-of-Products (Minterms)An expression is on a sum-of-products form if it isformed by the sum of products, and all the products are formed by single variables only.Examples:AB + CDE + ACEABC + DEFG + HA + B + C + DEThe following expressions are not sum-of-products:(A+B)CD + EF(X + Y)(X + Z)Product-of

15、-Sums (Maxterms)Similarly, a product-of-sums is formedby the product of sums in which all thesums are formed by single variables only.Examples:(A + B)(C + D + E)(A + C + E)(A + B)(C + D +E)FABC(D + E)The following expressions are not sum-of-products:(A+B)CD + EFA + B + C + DEMax Term expressionsMin

16、term expressions have terms which describe when the function is true.Oring these terms together means the function becomes true when any of them is trueMax term expressions have terms which describe when a function is falseThese terms are Anded together which means that the expression if false if an

17、y one of the terms is falsef (.)(.)(.)(.)All terms must be trueWhy use Max term expressions?If there are more 0s in the function than 1s, then the Max term expression is smaller.Each term is built as an OR expressionMax term expressions use different gates.Sometimes there are spare gates of a paricu

18、lar type available and these can be usedFrom Truth Table to Max term expressionABCf(A,B,C)00000010010001111000101111011111Expression is false hereTherefore the following expression totally captures the functionA B CA B CA B CA B CM (A B C)(A B C)(A B C)(A B CWhich expressions is smaller?As a Min ter

19、m expression:As a Max term expression:As a complemented Min term expressionABCf(A,B,C)00010011010101111001101111011110M ABCABC ABCABC ABCABC ABCM A B CM ABC M ABCCost of Implementing a Logic CircuitThe cost of implementing a logic circuit is related to the number of gates used and with the number of

20、 inputs in each gate.A literal is a boolean variable or its complement.Cost of Implementing a Logic CircuitThe cost of a boolean equation represented in a sum-of-products form is given by:. of term in the literals ofnumber the torelated is and,in termsofnumber the torelated is ,in termsofnumber thei

21、s where)(th10iijiiikjiijiBjBPBBOBkBOBPBCiBCost of Implementing a Logic Circuit10)(kjiijiBOBPBC term.1 has if 0 terms has if literals 1 has of term theif 0literals has of term theif ththiiiiiijBmBmBOBjmBjmBPCost of a Logic CircuitExamples10)(kjiijiBOBPBC term.1 has if 0 terms has if literals 1 has of

22、 term theif 0literals has of term theif ththiiiiiijBmBmBOBjmBjmBPWhat is the cost of the followingboolean equations?f1(w,x,y,z) = wxyz + wxyzg1(XYZ) = XY + XZ + YZf2(w,x,y,z) = w + x + yz + yzg2(XYZ) = XY + XZh1(a,b) = abh2(a,b) = bC(f1) = 4+4+2=10C(g1) = 2+2+2+3=9C(f2) = 0+0+2+2+4=8C(g2) = 2+2+2=6C(h1) = 2 + 0 = 2C(h