數(shù)字邏輯設(shè)計(jì)第4章 組合邏輯設(shè)計(jì)原理

1、1Chapter 4 Combinational Logic Design Principle（組合邏輯設(shè)計(jì)原理） Switching Algebra Combinational-circuit Analysis Combinational-circuit Synthesis12基本概念邏輯電路分為兩大類：combinational logic circuit（組合邏輯電路）sequential logic circuit（時(shí)序邏輯電路）任何時(shí)刻的輸出僅取決于當(dāng)時(shí)的輸入任一時(shí)刻的輸出不僅取決于當(dāng)時(shí)的輸入，還取決于過(guò)去的輸入序列電路特點(diǎn)：無(wú)反饋回路、無(wú)記憶元件23Switching algebr

2、a (Boolean algebra, Logic algebra) is a closure mathematical system that defines a series of logic operation (and, or, not) performed on set k of variables (a, b, c ) which can only have two values of 0 or 1.Notated as L=k, +, , , 0, 1Closure(封閉）A set is closed with respect to a operator if, the ope

3、ration is applied to members of the set, the result is also a member of the set.344.1 Switching Algebra（開(kāi)關(guān)代數(shù)）1、 Axioms（公理）X = 0 if X 1 X = 1 if X 0 0 = 1 1 = 0 00 = 0 1+1 = 1 11 = 1 0+0 = 0 01 = 10 = 0 1+0 = 0+1 = 1F = 0 + 1 ( 0 + 1 0 ) = 0 + 1 1= 0452、Single-Variable Theorems（單變量開(kāi)關(guān)代數(shù)定理）Identities（自

4、等率）：X + 0 = X X 1 = XNull elements（0-1 律）：X + 1 = 1 X 0 = 0Involution（還原律）：( X ) = XIdempotency（同一律）：X + X = X X X = XComplements（互補(bǔ)律）：X + X = 1 X X = 0變量和常量的關(guān)系變量和其自身的關(guān)系563、Two- and Three-variable Theorems（二變量或三變量開(kāi)關(guān)代數(shù)定理）與普通代數(shù)相似的關(guān)系Commutativity（交換律） A B = B A A + B = B + AAssociativity（結(jié)合律） A(BC) = (

5、AB)C A+(B+C) = (A+B)+CDistributivity（分配律） A(B+C) = AB+AC A+BC = (A+B)(A+C)可以利用真值表證明公式和定理67幾點(diǎn)注意不存在變量的指數(shù) AAA A3允許提取公因子 AB+AC = A(B+C)沒(méi)有定義除法 if AB=BC A=C ? 沒(méi)有定義減法 if A+B=A+C B=C ?A=1, B=0, C=0AB=AC=0, ACA=1, B=0, C=1錯(cuò)！錯(cuò)！78一些特殊的關(guān)系Covering（吸收律）X + XY = X X(X+Y) = XCombining（組合律）XY + XY = X (X+Y)(X+Y) = X

6、Consensus（添加律）（一致性定理）XY + XZ + YZ = XY + XZ(X+Y)(X+Z)(Y+Z) = (X+Y)(X+Z)89 proof A+AB=A+B A+AB=A1+AB (Identity)=A(1+B)+AB (Null element)=A1+AB+AB (Distributivity)=A+B(A+A) (Distributivity)=A+B1 (Complements)=A+B910Substitute theorems （代入定理） if replacing all variable A in a logic equation with a logic

7、 function F ,the equation would keep in equivalent. F1(a1,a2am)= F2(a1,a2am) substitute f(x1xn) for ai: F1(a1,a2,f,am)= F2(a1,a2,f,am)XY + XY = X(A+B)(A(B+C) + (A+B)(A(B+C) = (A+B)1011Prove that XY + XZ + YZ = XY + XZYZ = 1YZ = (X+X)YZXY + XZ + (X+X)YZ= XY + XZ + XYZ +XYZ= XY(1+Z) + XZ(1+Y)= XY + XZ

8、1112Ex. Prove if XZ =YZ and X+Z = Y+Z, then X=Y.XYZXZYZX+ZY+Z0000010100111001011101110000010100010001010111110111011112134、n-variable Theorems（n變量定理）Generalized idempotency（廣義同一律）X + X + + X = X X X X = XShannons expansion theorems（香農(nóng)展開(kāi)定理）1314Prove that： AD + AC + CD + ABCD = AD + AC= A ( 1D + 1C +

9、CD + 1BCD ) + A ( 0D + 0C + CD + 0BCD )= A ( D + CD + BCD ) + A ( C + CD )= AD( 1 + C + BC ) + AC( 1 + D )= AD + AC1415DeMorgans theorems（摩根定理）(A B) = A + B(A + B) = A B4、n-variable Theorems（n變量定理）Generalized DeMorgans theoremsInverse theorems （反演定理）1516Inverse theorems The complement of any switchi

10、ng function can be found by replacing every variable with its complement, each And with Or, and each Or with And; constants are replaced by their complement (0 is replaced by 1 and 1 by 0) ; the original logic operation order should be retained. F=G ; F=GEx. F=AB+ACDemorgans theorems F=(AB+AC)=(AB)(

11、AC) =(A+B)(A+C)Ex. F=AB+ACInverse theorems: F=A+BA+C ? F=(A+B)(A+C) 1617Ex. Prove that (AB + AC) = (AB + AC)AB + AC + BC = AB + AC(A+B)(A+C)AA +AC + AB + BCAC + AB AC + AB + BCEx：F1 = A (B + C) + C D F2 = (A B) + C D EF1 = ？F2= ？1718Duality propertyDuals are opposites or mirror images of original op

12、erators or constants.Operator and dual orOperator or dual andConstant 1 dual 0Constant 0 dual 15、 Duality（對(duì)偶性）1819Dual theorems The dual of any switching function can be found by replacing each And with Or, and each Or with And; constants are replaced by their complement (0 is replaced by 1 and 1 by

13、 0) ;and the logic operation order should hold in original.Ex. F=AB+ACFD=(A+B)(A+C) 5、 Duality（對(duì)偶性） FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) 19205、 Duality（對(duì)偶性）Principle of Duality （對(duì)偶原理）If F=G，then FD=GD（若兩邏輯式相等，則它們的對(duì)偶式也相等）Ex. F1 = A + B (C + D)X + X Y = XX X + Y = XX + Y = XX ( X +

14、 Y ) = X FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) F1D = ?2021proof：A+BC = (A+B)(A+C)A(B+C)AB+AC5、 Duality（對(duì)偶性）Principle of Duality （對(duì)偶原理）If F=G，then FD=GD（若兩邏輯式相等，則它們的對(duì)偶式也相等） FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) 2122對(duì)偶和反演對(duì)偶：FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2

15、, , Xn , , + , ) 反演： F(X1 , X2 , , Xn , + , ) = F(X1 , X2, , Xn , , + ) F(X1 , X2 , , Xn) = FD(X1 , X2, , Xn ) 正邏輯約定和負(fù)邏輯約定互為對(duì)偶關(guān)系2223A function is a term used in mathematics and logic to denote a relationship between input and output variables.Each variable is restricted to binary (0,1) valuesThe rel

16、ationship is the complex of three primitive functions (AndNotOr)Standard Representations of Logic Functions （邏輯函數(shù)的基本表示方法）2324Describe a switching functionTruth table Logic equation (switching equation) Logic diagramKarnaugh mapsThey are equivalent in function.2425舉重裁判電路Y = F (A,B,C ) = A(B+C)ABYCLog

17、ic equationLogic diagram開(kāi)關(guān)ABC1表閉合指示燈1 表亮000001110 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 ABCYTruth tableExample:2526A tabular representation of the combinations that a group of binary input and output variables can assumeIt illustrates all of the input variable combination values and the outp

18、ut variables values.Number of combinations = 2inputTruth table2627Input A,B,C Output FF=1(0,0,0)(0,1,1)(1,0,0)(1,1,0)(1,1,1)Truth table2728A logic equation defines the relationship between an output variable and a set of input variables The expression composed of logic variables and the three primit

19、ive operator and, or, not F(A,B,C)=ABC+BC+BCLogic equation2829F(A,B,C)=ABC+BC+BC2930Literal （文字） A literal is a Boolean variable or its complementProduct term（乘積項(xiàng)） A product term is a literal or the logical product (AND) of multiple literalsSum term（和項(xiàng)） A sum term is a literal or the logical OR of m

20、ultiple literalsSum of products (SOP)（積之和） A SOP is the logical OR of multiple product terms. Product of sums (POS)（和之積） A POS is the logical AND of multiple sum terms. 3031Logic equation truth tableY = A + BC + ABC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABCBCABCY110000000111111000000100Sum-of-produ

21、cts expressionAND-OR expression3132Y = (B+C) (A+B+C)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABCB+CA+B+CY001111111111111111110000product-of-sums expressionOR-AND expressionLogic equation truth table3233Truth table logic equationABC0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0ABCFtruth tabl

22、eABCABCF = ABC + ABC + ABC0 反變量1 原變量Product term：Sum-of-products expression333411101111G0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 01 1 0 01 1 1 0ABCF(ABC) = A+B+CF = ABCG = (A+B+C)0 原變量1 反變量Truth table logic equationtruth table34350 0 0 10 0 1 10 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1ABCFA+B+CA+B+C

23、F = (A+B+C) (A+B+C)0 原變量1 反變量Sum termProduct-of-sums expressionTruth table logic equation3536Minterms A minterm is a special case product terms that contains all of the input variables (each literal no more than once) that make up a Boolean expression.ABCABCABCABCABCABCABCABC0 0 00 0 10 1 00 1 11 0

24、01 0 11 1 01 1 1ABC乘積項(xiàng)Each minterm has one and only one input variable combination meeting the its value 1. And the combinations is different by the minterms.m0m1 m2m3 m4 m5 m6 m7 3637 MintermA more concise format for writing a minterm is mi. Subscript i is a decimal number produced by encoding the

25、minterm to a binary sequence. 1 represents the original variable, and 0 is the complement. The product of mi and mj is 0, if the subscript i is not equal to j.The sum of all minterms consisting of the common n literals is constant 1.112=i=0inm3738Maxterms A maxterm is a special case sum terms that c

26、ontains all of the input variables (each literal no more than once) that make up a Boolean expressionA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+C0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABC求和項(xiàng)Each maxterm has one and only one input variable combination meeting the its value 0. And the combinations is dif

27、ferent by the maxterms.M0M1 M2M3 M4 M5 M6 M7 3839 MaxtermA more concise format for writing a maxterm is Mi.Subscript i is a decimal number produced by encoding the maxterm to a binary sequence. 0 represents the original variable, and 1 is the complement. The sum of Mi and Mj is 1, if the subscript i

28、 is not equal to j.The product of all maxterms constructed by the common n literals is constant 0.012=i=0inM3940ABCABCABCABCABCABCABCABCmintermm0m1m2m3m4m5m6m70 0 0 00 0 1 10 1 0 20 1 1 31 0 0 41 0 1 51 1 0 61 1 1 7ABCrowA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CM0M1M2M3M4M5M6M7maxtermMi vs miA Maxter

29、m is the complement of a Minterm with the same subscript and literals.Mi = mi4041Canonical formsCanonical sum of productsIt is a complete set of minterms that defines when a output variable is a logic 1. Each minterm corresponds to the row in the truth table where the output is a 1. 41420 0 0 00 0 1

30、 00 1 0 00 1 1 11 0 0 01 0 1 01 1 0 11 1 1 1ABCF00010000F1= + +00000010F200000001F3why？4243Canonical formsCanonical product of sumsIt is a complete set of maxterms that defines when a output variable is a logic 0. Each maxterm corresponds to the row in the truth table where the output is a 0. 43440

31、0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 11 1 0 11 1 1 0ABCF01111111F1= 11101111F211111110F3why？4445Minterm and Maxterm11101001G0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0ABCF(ABC) = A+B+C(ABC) = A+B+C(ABC) = A+B+CMi = mimi = Mi標(biāo)號(hào)互補(bǔ)4546最大項(xiàng)與最小項(xiàng)之間的關(guān)系、 Mi = mi ； mi = Mi ；、一個(gè)n變量函數(shù)，既可用最小項(xiàng)之和表示，

32、 也可用最大項(xiàng)之積表示。兩者下標(biāo)互補(bǔ)。、某邏輯函數(shù) F，若用 P項(xiàng)最小項(xiàng)之和表示， 則其反函數(shù) F 可用 P 項(xiàng)最大項(xiàng)之積表示， 兩者標(biāo)號(hào)完全一致。46470 0 0 00 0 1 00 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1ABCFEX. Write the canonical sum and product for the logic function.On setOff setF=ABC+ABC+ABCF=(A+B+C)(A+B+C)(A+B+C)(A+B+C)(A+B+C)4748Ex. F(A,B,C)=AB+ABC+ABC F=m(3,4,

33、6,7) =ABC+ABC+ABC+ABC F=M(0,1,2,5) =(A+B+C)(A+B+C)(A+B+C)(A+B+C)Place a equation into canonical form Each maxterm corresponds to the row in the truth table where the output is a 0. Each minterm corresponds to the row in the truth table where the output is a 1. 4849Place a SOP equation into canonical

34、 form1. Identify the missing variable(s) in each AND term2. AND the missing term and its complement with the original AND term , xy=xy(z+z)3. Expand the term by application of the property of distribution, xy(z+z)=xyz+xyz Ex. F(A,B,C)=AB+ABC+ABC =AB(C+C)+ABC+ABC =ABC+ABC+ABC+ABC111110100011= A,B,C(3

35、,4,6,7)4950Place a POS equation into canonical form1. Identify the missing variable(s) in each OR term2. OR the missing term and its complement with the original OR term , x+y=x+y+zz3. Expand the term by application of the property of distribution, x+y+zz =(x+y+z)(x+y+z) Ex. F(A,B,C)=(A+C)(B+C) =(A+

36、C+BB)(AA+B+C) =(A+B+C)(A+B+C)(A+B+C)(A+B+C)= A,B,C(0,1,2,5)0 0 00 1 00 0 11 0 150邏輯函數(shù)的基本運(yùn)算OR（或）AND（與）NOT（非）F1 = A,B,C,D ( 1, 5, 7, 9, 13 )F2 = A,B,C,D ( 2, 6, 9, 13, 15 )F = F1 + F2 = A,B,C,D(1,2,5,6,7,9,13,15)F = F1 F2 = A,B,C,D (9,13)F1 = A,B,C,D ( 1, 5, 7, 9, 13 )= A,B,C,D ( 0,2,3,4,6,8,10,11,12,

37、14,15 )51Logic diagramF=AB+ABF(A,B,C)=AB+ABC+ABCG(A,B,C)=AC+BCF=G ?52Any variables or terms in a switching equation that a redundant should be eliminated. Because they add cost to the circuit.Minimize logic function 項(xiàng)數(shù)最少 每項(xiàng)中的變量數(shù)最少什么是最簡(jiǎn)Using Boolean algebraUsing karnaugh Maps53并項(xiàng)法： AB+AB=A(B+B)=A吸收法：

38、 A+AB=A(1+B)=A消項(xiàng)法： AB+AC+BC = AB+AC消因子法： A+AB = A+B配項(xiàng)法： A+A=A A+A=1Reduction of switching equations using Boolean algebra54并項(xiàng)法= B + CD= B ( C + C )AB+AB=AF1 = AB + ACD + AB + ACDF2 = BCD + BCD + BCD + BCD= B ( CD + CD + CD + CD )= BReduction of switching equations using Boolean algebra55 X Y = X + Y

39、吸收法A+AB = AF1 = AB + ABC + ABD + ABCD= AB( 1 + C + D + CD )= ABF2= A + A(BC)A+(BC+D) + BCA(BC)= A + BC= A + (A+BC) + BC = A+BCReduction of switching equations using Boolean algebra56消項(xiàng)法利用： AB + AC + BC = AB + ACY1 = ABCD + (A+B)E + CDE A + B= (A+B)= (AB)= (AB)CD + (AB)E + CDE= (AB)CD + (AB)EY2 = AB

40、+ BC + CD + DA + AC + AC= AB + BC + CD + DAReduction of switching equations using Boolean algebra57消因子法利用 A + AB = A + BY1= A + ACD + ABC= A + A(CD + BC)= A + CD + BCY2 = AC + AD + CD= AC + (A+C)D= AC + (AC)D= AC + DReduction of switching equations using Boolean algebra58配項(xiàng)法利用 A+A=A; A+A=1Y1 = AB +

41、AB + BC + BC= AB + AB(C+C) + BC +BC(A+A)= AB + ABC + ABC + BC + ABC + ABC= AB+ AC+ BCReduction of switching equations using Boolean algebra59Ex. F=(AB+BC+CA)+ABC=(AB)(BC)(AC)+ABC=(AB)+ABC)(B+C+ABC)(A+C+ABC)=(AB)+C)(B+C)(A+C)=(A+B+C)(B+C)(A+C)=(B+C)(A+C)=AB+C60Karnaugh MapsYX0 101m0m2m1m3m0m2m6m4m1m3

42、m7m5 graphical representation of truth tableZXY00 01 11 1001YZWX0000011110011110041215139371526141081161It is a matrix of squares. each square represent a minterm or maxterm from a Boolean equation. N-variable karnaugh map have 2n squares.The binary numeral on the sides of k-map is the variable coor

43、dinates. Karnaugh Maps620 0 0 10 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0ABCFF = (A,B,C)(0,3,5,6)10100101CAB00 01 11 1001Describe a switching function by K-map63F=A,B,C,D (1,3,5,12,13,14,15)00011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 1111111 Writing 1 in the square correspond to

44、 a minterm.Describe a switching function by K-map64F=A,B,C,D (2,3,5,7,10,11,14,15)00011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 00000000 Writing 0 in the square correspond to a maxterm.Describe a switching function by K-mapEx: F(A,B,C) = AC+BCD+B65The squares correspond to the adjacent m

45、interms are adjacent squares.Across the top and down the side of k- map, only one bit changes occur between adjacent squares for each column and row Logically adjacent 00011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 (5,4) (5,1) (5,7) (5,13)(0,4) (0,1) (0,8) (0,2)66Simplify a equation use N

46、-variable K-map67Boolean Identity AB+AB=AA sum of 2 logically adjacent m-minterms can be simplified by eliminating one variable , which is the different literal in the two minterms . The resulting product term has m-1 literals.68Boolean Identity AB+AB=AAll minterm groups must occur in a power of 2,

47、2n, n is the number of variables to be eliminated by the group. The resulting product term have m-n literals, which are the common variables to all minterms69m1=ABCD, m9=ABCD00011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 11Common literals:B, C, Dm1+m9=BCDm=4, n=1m-1=370m0=ABCD, m2=ABCD m8

48、=ABCD, m10=ABCD00011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 11Common literalsB & Dm0+m2+m8+m9=BDm=4, n=2m -n =21171m0=ABCD, m1=ABCD, m2=ABCD, m3=ABCDm4=ABCD, m5=ABCD, m6=ABCD, m7=ABCDm0+m1+m2+m3=ABm4+m5+m6+m7=AB00011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 11111111AB+AB=Am=4

49、, n=3m -n =172m0=ABCD, m1=ABCD, m2=ABCD, m3=ABCDm4=ABCD, m5=ABCD, m6=ABCD, m7=ABCD00011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 11111111m=4, n=3m -n =1Common literalsA(0,1,2,3,4,5,6,7)= Am73m1=ABCD, m3=ABCD, m9=ABCD, m11=ABCDm4=ABCD, m12=ABCD, m6=ABCD, m14=ABCD00011110ABCD000111100 4 12

50、8 1 5 13 9 3 7 15 11 2 6 14 10 11111111m1+m3+m9+m11=BDm4+m12+m6+m14=BD74m0=ABCD, m1=ABCD, m2=ABCD, m3=ABCDm4=ABCD, m5=ABCD, m6=ABCD, m7=ABCDm8=ABCD, m9=ABCD, m10=ABCD, m11=ABCDm12=ABCD, m13=ABCD, m14=ABCD, m15=ABCD00011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 11111111111111117500011110AB

51、CD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 11111111Common literalsA(0,1,2,3,4,5,6,7)= Am11111111Common literalsA(8,9,10,11,12,13,14,15)= Am(0-15)= A+A=1mm=4, n=4m -n =076m0=ABCD, m1=ABCD, m2=ABCD, m3=ABCDm4=ABCD, m5=ABCD, m6=ABCD, m7=ABCDm8=ABCD, m9=ABCD, m10=ABCD, m11=ABCDm12=ABCD, m13=ABCD, m

52、14=ABCD, m15=ABCD00011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 1111111111111111112=i=0inm77卡諾圖的特點(diǎn)邏輯相鄰性：相鄰兩方格只有一個(gè)因子互為反變量合并最小項(xiàng)兩個(gè)最小項(xiàng)相鄰可消去一個(gè)因子四個(gè)最小項(xiàng)相鄰可消去兩個(gè)因子八個(gè)最小項(xiàng)相鄰可消去三個(gè)因子2n個(gè)最小項(xiàng)相鄰可消去n個(gè)因子78Find a minimal SOP expression ofF2 = (A,B,C,D) ( 0, 2, 3, 5, 7, 8, 10, 11, 13)ABCD00 01 11 1000011110ABDB

53、CDBCBD1111111111、填圖2、圈組3、讀圖，得到結(jié)果F2 = ABD+BCD+BC+BDSimplify a equation use K-map79卡諾圖化簡(jiǎn)步驟填寫卡諾圖可以先將函數(shù)化為最小項(xiàng)之和的形式圈組：找出可以合并的最小項(xiàng)組(圈)數(shù)最少、每組(圈)包含的方塊數(shù)最多方格可重復(fù)使用，但至少有一個(gè)未被其它組圈過(guò)讀圖：寫出化簡(jiǎn)后的乘積項(xiàng)消掉既能為0也能為1的變量保留始終為0或1的變量乘積項(xiàng)：0 反變量1 原變量80Simplify a equation use N-variable K-map81Some DefinitionsA minimal sum of a logic f

54、unction F(X1,Xn) is a sum-of-products expression for F such that no sum-of-products expression for F has fewer product terms, and any sum-of-products expression with the same number of product terms has at least as many literals.邏輯函數(shù)F(X1,Xn) 的最小和是F的一個(gè)“積之和”表達(dá)式，F(xiàn)的其它“積之和”表達(dá)式不會(huì)比最小和式中的乘積項(xiàng)更少，而且具有同樣乘積項(xiàng)數(shù)的“積

55、之和”表達(dá)式至少有同樣多的變量。82Some Definitions 對(duì)于邏輯函數(shù) P(X1,Xn) 和 F(X1,Xn) ，若對(duì)任何使P=1的輸入組合，也能使F為1，則稱P隱含F(xiàn)，或者F包含P。P1(A,B,C) = ABCF(A,B,C) = AB + BCP2(A,B,C) = BCP = A,B,C (1,3,6)F = A,B,C (1,3,5,6,7)A logic function P(X1,Xn) implies a logic function F(X1,Xn) if for every input combination such that P=1, then F=1 al

56、so.83 邏輯函數(shù) F(X1,Xn) 的主蘊(yùn)含項(xiàng) 是隱含 F 的常規(guī)乘積項(xiàng) P，如果從 P 中移去任何變量，則所得的乘積項(xiàng)不隱含F(xiàn)。F(A,B,C) = ABC + BC + AC = BC + ACA minimal sum is a sum of prime implicants. 最小和是主蘊(yùn)含項(xiàng)之和A prime implicant of a logic function F(X1,Xn) is a normal product term P(X1,Xn) that implies F, such that if any variable is removed from P, the

57、n the resulting product term does not imply F.Some Definitions84Some DefinitionsA distinguished 1-cell of a logic function is an input combination that is covered by only one prime implicant.奇異“ 1 ”單元：僅被單一主蘊(yùn)含項(xiàng)覆蓋的輸入組合An essential prime implicant of a logic function is a prime implicant that covers on

58、e or more distinguished 1-cells.質(zhì)主蘊(yùn)含項(xiàng)：覆蓋1個(gè)或多個(gè)奇異“1”單元的主蘊(yùn)含項(xiàng)85ABCD00 01 11 10000111101111111111Some DefinitionsABCD00 01 11 100001111011111111圈組時(shí)應(yīng)從合并奇異“1”單元開(kāi)始奇異“ 1 ”單元：沒(méi)有可能被重復(fù)“圈”過(guò)的1單元86Step of simplificationLoad the minterms into the k-map by placing a 1 in the appropriate squareLook for all prime impl

59、icantsLook for all essential prime implicantsSelect all EPI and a minimal set of remaining implicants that cover all remaining 1s in the karnaugh mapMore than one equally simplified result is possible when more than one set of remaining prime implicants contain the same number of minterms 87Examples

60、88F(A,B,C,D)=m(1,3,5,12,13,14,15)00011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 1111111PI: PI1(1,3) PI2(1,5) PI3(5,13) PI4(12,13,14,15)89F(A,B,C,D)=m(1,3,5,12,13,14,15)EPI: PI1,PI400011110ABCD000111100 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 1111111PI: PI1(1,3)=ABD PI2(1,5)=ACD PI3(5,13)=BCD