數(shù)字設(shè)計(jì)原理與實(shí)踐：第四章 COMBINATIONAL LOGIC DESIGN PRINCIPLES

1Chapter4CombinationalLogicDesignPrinciples

(組合邏輯設(shè)計(jì)原理)

BasicLogicAlgebra(邏輯代數(shù)基礎(chǔ))

Combinational-CircuitAnalysis(組合電路分析)

Combinational-CircuitSynthesis(組合電路綜合)TimingHazards(冒險(xiǎn))

24.1Switchingalgebra(開關(guān)代數(shù))邏輯代數(shù)也稱布爾代數(shù)，兩值代數(shù)，開關(guān)代數(shù)邏輯變量、邏輯函數(shù)只有2個(gè)取值：0和1，對(duì)應(yīng)于開、關(guān)狀態(tài)，有、無情況，真、假，肯定或否定，高、低電平在電路中，通過“開關(guān)”(Switch)的接通或斷開(OnorOff)，“晶體管”(Transistor)的飽和或截止（SaturationorCut-off），“熔絲”(Fuse)的接通或斷開實(shí)現(xiàn)通過電路電壓的高或低體現(xiàn)AND、OR、NOT三種基本的運(yùn)算與非、或非、與或非、同或、異或等復(fù)合邏輯運(yùn)算真值表：描述邏輯函數(shù)各個(gè)變量值的組合與邏輯函數(shù)值對(duì)應(yīng)關(guān)系的表格真值表的寫法：變量的所有取值組合為輸入，函數(shù)值為輸出

3

logicalgebraLogicalmultiplication(“與”運(yùn)算)ABFABFopenopen暗openclose暗closeopen暗closeclose亮InputOutputABF000010100111“與”運(yùn)算符號(hào)為：“

?

”，有時(shí)可以省略不寫。也使用“”或“”定義：當(dāng)決定某一事件的所有條件都具備后，事件才發(fā)生Electricalfunctiontable(功能描述表)設(shè)用0表示開、暗；用1表示關(guān)、亮。Truthtable(真值表)

4LogicalmultiplicationExpression(表達(dá)式)：F=A·BLogicsymbol(電路符號(hào))&ABFABFABF與門可以利用二極管等分離元件、或TTL、MOS集成電路等器件實(shí)現(xiàn)0?0=00?1=01?0=01?1=1Logicalmultiplication（與運(yùn)算）：推廣為n個(gè)變量0

?0?0?0?0……=0

0?1?1?1?0……=01?0

?0?0?1……=0

1?1?1?1?1……=1與運(yùn)算時(shí)，有一個(gè)為0，結(jié)果為0

5LogicaladditionLogicaladdition（“或”運(yùn)算）ABFopenopen暗closeclose亮closeopen亮openclose亮InputOutputABF000011101111“或”運(yùn)算符號(hào)為：“＋”，也有時(shí)使用“”或“”

定義：當(dāng)決定某一事件的任一個(gè)或多個(gè)條件具備后，事件就發(fā)生Electricalfunctiontable(功能描述表)設(shè)用0表示開、暗；用1表示關(guān)、亮。真值表ABF

6LogicaladditionExpression(表達(dá)式)：F=A+BLogicsymbol(電路符號(hào))與門可以利用二極管等分離元件、或TTL、MOS集成電路等器件實(shí)現(xiàn)。0+0=00+1=11+0=11+1=1Logicaladdition（“或”運(yùn)算）推廣為n個(gè)變量0+0+0+0+0……=0

0+1+1+1+0……=11+0+0+0+1……=1

1+1+1+1+1……=11ABF+ABFABF或運(yùn)算時(shí)，有一個(gè)1，結(jié)果就為1

7InverterInverter(“非”運(yùn)算)輸入輸出AFopen亮close暗“非”運(yùn)算符號(hào)為：′、￣定義：當(dāng)決定某事件的條件不具備時(shí)，事件卻發(fā)生；而條件具備時(shí)，結(jié)果卻不發(fā)生功能描述表設(shè)用0表示開、暗；用1表示關(guān)、亮。真值表AFAF0110“非”運(yùn)算：

8InverterExpression(表達(dá)式)

：1AFAFAFLogicsymbol(電路符號(hào))：由與、或、非三種基本邏輯運(yùn)算可以構(gòu)成復(fù)合運(yùn)算運(yùn)算的優(yōu)先順序是：按先非→與→或的順序進(jìn)行先括號(hào)內(nèi)，后括號(hào)外

9復(fù)合邏輯運(yùn)算AND-NOT(“與非”運(yùn)算)Logicsymbol(電路符號(hào))由“與”運(yùn)算及“非”運(yùn)算結(jié)合而導(dǎo)出邏輯運(yùn)算Expression(表達(dá)式)相當(dāng)于&ABFABFABF&ABF

10復(fù)合邏輯運(yùn)算OR-NOT(“或非”運(yùn)算)Logicsymbol(電路符號(hào))由“或”運(yùn)算及“非”運(yùn)算結(jié)合而導(dǎo)出邏輯運(yùn)算Expression(表達(dá)式)相當(dāng)于1ABFABF+ABFABF

+

11復(fù)合邏輯運(yùn)算AND-OR-NOT(“與或非”運(yùn)算)Logicsymbol(電路符號(hào))Expression(表達(dá)式)&ABF1CDABF＋CDFABCD

12復(fù)合邏輯運(yùn)算Exclusiveor(“異或”運(yùn)算）多個(gè)值“異或”運(yùn)算時(shí)Expression(表達(dá)式)RULES：A、B相異則F為1；A、B相同則F為0ABCDE……＝1 當(dāng)1的個(gè)數(shù)為奇數(shù)時(shí)0 當(dāng)1的個(gè)數(shù)為偶數(shù)時(shí)=1ABFABFABFLogicsymbol(電路符號(hào))AA=0AA’=1A0=AA1=A’

13“異或”運(yùn)算特性Commutativity(交換律)：A⊕B=B⊕AAssociativity(結(jié)合律)：(A⊕B)⊕C=A⊕(B⊕C)Distributivity(分配律)：A(B⊕C)=(AB)⊕(AC)因果互換關(guān)系:AB=CAC=BBC=AABCD=00ABC=DA⊕B⊕(AB)=A+B

14復(fù)合邏輯運(yùn)算Inclusiveor(“同或”運(yùn)算)多個(gè)值“同或”運(yùn)算時(shí)邏輯函數(shù)表達(dá)式：F=A⊙B=AB+A’B’RULES：A、B相同則F為1；A、B相異則F為0“同或”門電路符號(hào)A⊙B⊙C⊙D⊙E……＝1 當(dāng)0的個(gè)數(shù)為偶數(shù)時(shí)0 當(dāng)0的個(gè)數(shù)為奇數(shù)時(shí)=ABFABFABFABF是異或非門的形式A⊙A=1A⊙A’=0A⊙1=AA⊙0=A’

15“同或”運(yùn)算特性Commutativity(交換律)：A⊙B=B⊙AAssociativity(結(jié)合律)：(A⊙B)⊙C=A⊙(B⊙C)Distributivity(分配律)：A(B⊙C)≠(AB)⊙(AC)，A⊙B⊙(AB)=A+B因果互換關(guān)系A(chǔ)⊙B=CA⊙C=BB⊙C=A

16ExclusiveORandInclusiveOR偶數(shù)個(gè)變量的異或運(yùn)算和同或運(yùn)算具有互補(bǔ)關(guān)系。奇數(shù)個(gè)變量的異或運(yùn)算和同或運(yùn)算具有相等關(guān)系。AB＝(A⊙B)’ABCD＝(A⊙B⊙C⊙D)’ABC＝A⊙B⊙CABCDE＝A⊙B⊙C⊙D⊙E(ABCD)’＝A⊙B⊙C⊙DAB’=A⊙BAB=A⊙B’

AB’=A’

BA’⊙B=A⊙B’

17邏輯運(yùn)算的完備性完備邏輯運(yùn)算集合：任何邏輯運(yùn)算都可以用某邏輯運(yùn)算集合來表示，則該運(yùn)算集合是完備的。與、或、非運(yùn)算集合是完備的運(yùn)算集合。與非、或非也分別是完備運(yùn)算集合。由于同一個(gè)邏輯關(guān)系可以用多種運(yùn)算中的任何一種或幾種來表示，因此造成了邏輯關(guān)系表達(dá)式的不唯一性。電路圖&AF非運(yùn)算&AF&B&或運(yùn)算&F&AB與運(yùn)算證明“與非”運(yùn)算是完備運(yùn)算集

18AXIOM(公理)ANDoperation：0·0=00·1=01·0=01·1=1ORoperation：0+0=00+1=11+0=11+1=1INVERTERoperation：若A0，則A＝1；若A1，則A＝0

19theorems0－1律反映邏輯變量和邏輯常量“0”、“1”的運(yùn)算規(guī)律。1.A?0＝0 A＋1＝12.A?1＝A A＋0＝A其中2中的兩個(gè)公式也稱為Identities“自等律”Nullelements(0－1律)

20Idempotency(同一律、重疊律)可見：在一個(gè)表達(dá)式中，出現(xiàn)的重復(fù)變量（或變量 組合）是多余的。 由“與”重疊律可知，邏輯代數(shù)中不存在變量的 指數(shù)運(yùn)算。

A?A=A A＋A=A

21Commutativity,Associativity,Distributivity(交換律、結(jié)合律、分配律)

這三個(gè)定律和普通代數(shù)中的相應(yīng)定律基本一致Commutativity(交換律)Associativity(結(jié)合律)Distributivity(分配律)AB＝BA A＋B＝B＋AA（BC）＝（AB）CA＋（B＋C）＝（A＋B）＋CA（B＋C）＝AB＋AC A＋BC＝（A＋B）（A＋C）

將該式從右往左看，可知邏輯代數(shù)中允許提取公因子注意：普通代數(shù)中沒有這樣的“加法分配律”

22(AB)’＝A’＋B’ (A＋B)’＝A’B’(A’)’

＝A

A?

A’＝0 A＋A’

＝1Complements,Involution,DeMorgan’stheorems

[互補(bǔ)律、還原律（非非律）、反演律（摩根定理）] 這三組公式都與“非”運(yùn)算有關(guān)1.Complements互補(bǔ)律2.Involution還原律（非非律）

3.DeMorgan’stheorems

反演律（摩根定理）

23基本公式的證明Perfectinduction(完備歸納法)/列表法證明：如果變量的每種取值，兩邊都對(duì)應(yīng)相等，則等式成立/證明分配律A＋BC＝(A＋B)(A＋C)ABCBCA+BA+C左邊右邊0000000000100100010010000111111110001111101011111100111111111111

24利用公式證明試證：A＋BC＝（A＋B）（A＋C）證明：等式右邊＝（A＋B）（A＋C） （分配律）（重疊律）＝AA

＋AC＋BA＋BC＝A

＋AC＋BA＋BC ＝A?（1＋C＋B）＋BC＝A

＋BC ＝等式左邊（分配律）（0–1律）對(duì)偶式：A（B＋C）＝AB＋AC基本公式的證明＝

A＋AC＋AB

＋BC （交換律）

25Covering[吸收(添加)律]：A＋AB＝AA(A＋B)＝AConsensus[冗余項(xiàng)公式]：證：AB＋A’C＋BCDAB＋A’C＋BCD（A＋A’）互補(bǔ)律AB（1＋CD）＋A’C（1＋BD）分配律AB＋A’C0-1律冗余項(xiàng)公式證明：

26Notes(幾點(diǎn)注意)允許提取公因子AB+AC=A(B+C)不存在變量的指數(shù)A·A·AA3沒有定義除法

ifAB=BCA=C??沒有定義減法

ifA+B=A+CB=C??A=1,B=0,C=0AB=BC=0,ACA=1,B=0,C=1錯(cuò)！錯(cuò)！

27代入定理：在含有變量A的邏輯等式中，如果將式中所有出現(xiàn)A的地方都用另一個(gè)函數(shù)F來代替，則等式仍然成立X·Y+X·Y’=X(A’+B)·(A·(B’+C))+(A’+B)·(A·(B’+C))’=(A’+B)例：已知分配律：A＋BC＝（A＋B）（A＋C）即得到四變量的分配律：A＋BCD＝(A＋B)(A＋C)(A＋D)有：A＋B(CD)＝(A＋B)(A＋CD)＝(A＋B)(A+C)(A+D)

28GeneralizedDeMorgan’stheorem[廣義德.摩根定理]

(反演規(guī)則)對(duì)于給定的任一邏輯函數(shù)表達(dá)式，若將表達(dá)式中的“原變量”換“反變量”，“反變量”換“原變量”，“1”與“0”互換、“?”與“＋”互換，則得到的邏輯函數(shù)為原函數(shù)F的反函數(shù)，表示為F’（complementofalogicexpression一個(gè)邏輯表達(dá)式的反）則其反函數(shù)F’＝g（x1’

,x2,…,xn’

,1,0,?,＋）注意：1、變換前后的運(yùn)算優(yōu)先級(jí)保持不變。2、不是單個(gè)變量的非運(yùn)算，保持不變。設(shè)邏輯函數(shù)F＝f（x1,x2’,…,xn,0,1,＋,?）

29Duality(對(duì)偶定理) 對(duì)偶式的定義：對(duì)任一個(gè)邏輯函數(shù)F，將其中的“1”與“0”互換、“?”與“＋”互換，并保持原來的運(yùn)算順序不變，得到的新表達(dá)式即稱為F的對(duì)偶式FD

?；竟交閷?duì)偶關(guān)系一個(gè)函數(shù)F的反函數(shù)F’與對(duì)偶函數(shù)FD

的關(guān)系是：兩式中的所有對(duì)應(yīng)變量都互為反變量。F’(A,B,…,Z)=FD(A’,B’,…,Z’)FD(A,B,…,Z)=F’(A’,B’,…,Z’)性質(zhì)：1、(F+G)D=FDGD2、(FG)D=FD+GD3、若F=G，則FD=GD4、(FD)D=F注意：變換前后的運(yùn)算優(yōu)先級(jí)保持不變

30complementofalogicexpression

(反函數(shù)）dual

ofalogicexpression（對(duì)偶函數(shù)）example：F=(BD’)’+A(BCE+AB’)complementofalogicexpression

F’=(B’+D)’(A’+(B’+C’+E’)(A’+B))dual

ofalogicexpression

FD=(B+D’)’(A+(B+C+E)(A+B’))example：F=AB(AC’+AD’+((A+1)C)’)complementofalogicexpression

F’=A’+B’+(A’+C)(A’+D)(A’0+C’)’dual

ofalogicexpression

FD＝A+B+(A+C’)(A+D’)(A0+C)’

31Shannon’sexpansiontheorems(香農(nóng)展開定理)任何邏輯函數(shù)都可對(duì)它的某一變量xi展開成積之和（與－或）式或和之積（或－與）式f(A,A’,B,…,Z)=Af(1,0,B,…,Z)+A’f(0,1,B,…,Z)f(A,A’,B,…,Z)=(A+f(0,1,B,…,Z))(A’+f(1,0,B,…,Z))積之和式例：將函數(shù)F(A,B,C)＝A’B’C＋A(B＋C’)對(duì)A展開成“和之積”形式解：F（A,B,C）

=[A+F(

0,B,C)]?[A’+F(1,B,C)]=(A+B’C)(A’+B+C’)=(A+B’)(A+C)(A’+B+C’)和之積式

32小結(jié)1.邏輯代數(shù)中定義了三種基本運(yùn)算，即：與、或、非。而沒有定義“減法”和“除法”運(yùn)算，所以下面兩個(gè)推導(dǎo)是錯(cuò)誤的：AB＝BCA＝CAB+AC＝AB+B+CAC＝B+C2.邏輯代數(shù)中定義了五種復(fù)合運(yùn)算，包括：與非、或非、與或非、異或、同或。其中與非、或非、與或非運(yùn)算都具有完備性，因此同一邏輯關(guān)系的表達(dá)式以不唯一。3.每個(gè)邏輯函數(shù)都有自己的反函數(shù)和對(duì)偶函數(shù)。注意在求反函數(shù)和對(duì)偶函數(shù)時(shí)不能改變變量間的運(yùn)算次序。各運(yùn)算優(yōu)先級(jí)為（降序）：括號(hào)、非、與、或。4.利用邏輯代數(shù)中現(xiàn)有的公理、定律及四個(gè)主要定理，可以將看來很復(fù)雜的邏輯函數(shù)化簡(jiǎn)。

33

StandardRepresentationofLogicFunctions

邏輯函數(shù)的標(biāo)準(zhǔn)表示方法TruthTable(真值表)ProductTerm,SumTerm(乘積項(xiàng)、求和項(xiàng))Sum-of-ProductsExpression(“積之和”表達(dá)式)Product-of-SumExpression(“和之積”表達(dá)式)CanonicalSumandProduct(標(biāo)準(zhǔn)和與標(biāo)準(zhǔn)積)N-variableMinterm(n變量最小項(xiàng))N-variableMaxterm(n變量最大項(xiàng))(4.1.6)——最小項(xiàng)之和——最大項(xiàng)之積標(biāo)準(zhǔn)和標(biāo)準(zhǔn)積NormalTerm(標(biāo)準(zhǔn)項(xiàng)）

34Y=F(A,B,C)=A·(B+C)ABYC邏輯函數(shù)邏輯圖開關(guān)ABC1表閉合指示燈1表亮000001010011100101110111

ABCY真值表example：舉重裁判電路&≥1ABCY00000111

35WaveForm波形圖將輸出與輸入信號(hào)變化的時(shí)間關(guān)系用波形的形式描述，就得到了波形圖。

36邏輯函數(shù)5種基本表達(dá)式1、與或式F=AB+A’C5、與或非式F=(AB’+A’C’)’2、或與式F=(A’+B)(A+C)3、與非-與非式F=((AB)’(A’C)’)’4、或非-或非式F=((A’+B)’+(A+C)’)’&AF&A&BC&AF&A≥1BCF≥1AA&BC≥1≥1AFABC≥1≥1＆AFABC≥1

37

1、Logicexpression

LogictruthtableEX：Y=(B’+C)·(A’+B+C’)000001010011100101110111ABCB’+CA’+B+C’Y001111111111111111110000可省略

382、Logictruthtable

Logicexpression

A’·B·C00000010010001111000101111011110ABCF真值表A·B’·CA·B·C’F=A’·B·C+A·B’·C+A·B·C’0反變量1

原變量乘積項(xiàng)：Sum-of-Products[“積之和”表達(dá)式]“與-或”式

392、Logictruthtable

Logicexpression00010011010001111000101111011111ABCF真值表A+B’+CA’+B+CF=(A+B’+C)·(A’+B+C)0原變量1

反變量求和項(xiàng)Product-of-Sums[“和之積”表達(dá)式]“或-與”式

40Logicexpression

LogicCircuitex:已知邏輯函數(shù)為F=A’BC’+(A+B’C)’+C,

解：將式中的所有的與、或、非運(yùn)算符號(hào)用圖形符號(hào)代替，并依據(jù)非→與→或的運(yùn)算優(yōu)先順序把這些圖形符號(hào)連接起來。

41LogicCircuit

Logicexpression

從輸入端到輸出端逐級(jí)寫出每個(gè)圖形符號(hào)對(duì)應(yīng)的邏輯式，得到對(duì)應(yīng)的邏輯函數(shù)式。練習(xí)：已知函數(shù)的邏輯圖，求它的邏輯函數(shù)式。

42

StandardRepresentationofLogicFunctions

A’·B’·C’A’·B’·CA’·B·C’A’·B·CA·B’·C’A·B’·CA·B·C’A·B·C000001010011100101110111ABCProductterm(乘積項(xiàng))Minterms(最小項(xiàng))

——

Ann-variableMinterm

isanormalproducttermwithnliterals(n個(gè)因子的標(biāo)準(zhǔn)乘積項(xiàng))Thereare2nsuchproductterms(n變量函數(shù)具有2n個(gè)最小項(xiàng))Anytwodifferentmintermsproduce0.

(任意兩個(gè)不同最小項(xiàng)的乘積為0)

43輸入變量的一組取值，必使某最小項(xiàng)的值為1，這組取值對(duì)應(yīng)的數(shù)為該最小項(xiàng)的序號(hào)mi。全體最小項(xiàng)之和為1。若兩個(gè)最小項(xiàng)只有一個(gè)因子不同，則稱這兩個(gè)最小項(xiàng)具有邏輯相鄰性。具有邏輯相鄰性的兩個(gè)最小項(xiàng)之和可以合并成一項(xiàng)并消去一對(duì)因子。AB’C’+AB’C=AB’A’·B’·C’A’·B’·CA’·B·C’A’·B·CA·B’·C’A·B’·CA·B·C’A·B·C000001010011100101110111ABCProductTerm(乘積項(xiàng))Minterm(最小項(xiàng)）

44在n變量邏輯函數(shù)中，若M為n個(gè)變量之和(Sum)，而且這n個(gè)變量均以原變量或反變量的形式在M中出現(xiàn)且僅出現(xiàn)一次，則稱M為該組變量的最大項(xiàng)(Maxterm)n個(gè)因子的標(biāo)準(zhǔn)求和項(xiàng)n變量函數(shù)具有2n個(gè)最大項(xiàng)A+B+CA+B+C’A+B’+CA+B’+C’A’+B+CA’+B+C’A’+B’+CA’+B’+C’000001010011100101110111ABCSumTerm(求和項(xiàng))Maxterm（最大項(xiàng)）

45輸入變量的一組取值，必使一個(gè)最大項(xiàng)的值為0，該取值對(duì)應(yīng)的數(shù)為該最大項(xiàng)的序號(hào)Mi。全體最大項(xiàng)之積為0。任意兩個(gè)最大項(xiàng)之和為1。只有一個(gè)變量不同的兩個(gè)最大項(xiàng)的乘積等于各相同變量之和。(A+B+C)(A+B+C’)=(A+B)A+B+CA+B+C’A+B’+CA+B’+C’A’+B+CA’+B+C’A’+B’+CA’+B’+C’000001010011100101110111ABCSumTerm(求和項(xiàng))Maxterm（最大項(xiàng)）

46A’·B’·C’A’·B’·CA’·B·C’A’·B·CA·B’·C’A·B’·CA·B·C’A·B·Cm0m1m2m3m4m5m6m7

Minterm(最小項(xiàng))00000011010201131004101511061117ABC編號(hào)A+B+CA+B+C’A+B’+CA+B’+C’A’+B+CA’+B+C’A’+B’+CA’+B’+C’M0M1M2M3M4M5M6M7

Maxterm(最大項(xiàng))Mintermand

Maxtermnumber(最小項(xiàng)與最大項(xiàng)序號(hào))練習(xí)：仔細(xì)觀察上表，找出mi與Mi的關(guān)系？

47Normalterm（標(biāo)準(zhǔn)項(xiàng)）Product-of-sumexpression(積之和表達(dá)式)

利用互補(bǔ)律X+X’=1可以把任何一個(gè)邏輯函數(shù)化為最小項(xiàng)之和的標(biāo)準(zhǔn)形式。例：將邏輯函數(shù)F=A+B’C化為Canonicalsum(積之和的標(biāo)準(zhǔn)形式)－－最小項(xiàng)之和F=A(B+B’)(C+C’)+(A+A’)B’C

=ABC+ABC’+AB’C+AB’C’+AB’C+A’B’C =ABC+ABC’+AB’C+AB’C’+A’B’C =m7+m6+m5+m4+m1

48sum-of-Productexpression(和之積表達(dá)式)Canonicalproduct(和之積的標(biāo)準(zhǔn)形式)－－即最大項(xiàng)之積的形式利用互補(bǔ)律X·X’=0，在缺少某一變量的和項(xiàng)中加上該變量，然后利用分配律A=A+X·X’=(A+X)(A+X’)展開，就可以把任何一個(gè)邏輯函數(shù)化為最大項(xiàng)之積的標(biāo)準(zhǔn)形式例：試將邏輯函數(shù)F=A+B’C變換成Canonicalproduct(和之積的標(biāo)準(zhǔn)形式)F=A+B’C=(A+B’)(A+C)=(A+B’+CC’)(A+C+BB’) =(A+B’+C)(A+B’+C’)(A+C+B)(A+C+B’) =(A+B+C)(A+B’+C)(A+B’+C’) =M0M2M3思考：比較最大項(xiàng)表達(dá)式及上頁(yè)的最小項(xiàng)表達(dá)式，有規(guī)律嗎？

49

Mintermand

Maxterm(最小項(xiàng)和最大項(xiàng))11101001G00000010010001111000101111011110ABCF(A’·B·C)’=A+B’+C’(A·B’·C)’=A’+B+C’(A·B·C’)’=A’+B’+CMi=mi’mi=Mi’標(biāo)號(hào)互補(bǔ)

50如：對(duì)3變量A、B、C來說，最小項(xiàng)m6＝ABC’＝(A’+B’+C)’＝M6’Mintermand

Maxterm(最小項(xiàng)和最大項(xiàng))

任何一個(gè)函數(shù)兩種標(biāo)準(zhǔn)式中所含的最小項(xiàng)mi、最大項(xiàng)Mj

的編號(hào)i和j是互不重復(fù)而相互補(bǔ)充的相同編號(hào)的最小項(xiàng)和最大項(xiàng)存在互補(bǔ)關(guān)系，即mi=Mi’如：F＝A＋B’C＝

m（1,4,5,6,7）＝

M

(0,2,3） 由若干個(gè)最小項(xiàng)之和表示的函數(shù)F，其反函數(shù)可用等同個(gè)對(duì)應(yīng)的最大項(xiàng)之積來表示。如：F’＝(A＋B’C)’＝

M（1，4，5，6，7）＝

m（0，2，3）注：n變量共有2n

個(gè)不重復(fù)的編號(hào)，最小項(xiàng)和最大項(xiàng)的編號(hào)應(yīng)從0至（2n-1）maxtermlist(最大項(xiàng)列表)

mintermlist(最小項(xiàng)列表)

51Combinational-CircuitMinimization

（組合電路最小化）MinimizationFormsofLogicFunctions（邏輯函數(shù)最簡(jiǎn)形式）AND-OR(與或式)表達(dá)式中與項(xiàng)個(gè)數(shù)最少。在滿足上述條件的情況下，要求每個(gè)與項(xiàng)中的變量的個(gè)數(shù)最少。OR-AND(或與式)表達(dá)式中或項(xiàng)個(gè)數(shù)最少。在滿足上述條件的情況下，要求每個(gè)或項(xiàng)中的變量的個(gè)數(shù)最少。

52FormulaMethodSimplification

（公式法化簡(jiǎn)方法）CombiningMethod(并項(xiàng)法)：利用A·B+A·B’=A·(B+B’)=ACoveringMethod(吸收法)：利用A+A·B=A·(1+B)=ARemovingMethod(消項(xiàng)法)：利用A·B+A’·C+B·C=A·B+A’·CRemoveliteralMethod(消因子法)：利用A+A’·B=A+BConsensusMethod(配項(xiàng)法)：利用A+A=AA+A’=1總之：利用公式、定理、規(guī)則等

53CombiningMethod(并項(xiàng)法)：=B’+C·D=A=B·(C’+C)利用A·B+A·B’=AF1=A·(B·C’·D)’+A·B·C’DF2=A·B’+A·C·D+A’·B’+A’·C·DF3=B·C’·D+B·C·D’+B·C·D+B·C’·D’=A·[(B·C’·D)’+B·C’·D]=B·(C’·D+C·D’+C·D+C’·D’)=B

54[X’·Y’]’=X+YCoveringMethod(吸收法)A+A·B=AF1=(A’·B+C)·A·B·D+A·D=A·D·[1+B·(…)]F2=A·B+A·B·C’+A·B·D+A·B·C·D’=A·B·(1+C’+D+C·D’)=A·BF3=A+[A’·(B·C)’]’·[A’+(B’·C’+D’)’]+B·C[A’·(B·C)’]’=A+B·C=A+(A+B·C)·[…]+B·C=A+BC=A·D

55RemovingMethod(消項(xiàng)法)：

A·B+A’·C+B·C=A·B+A’·CY1=A·C+A·B’+B’·C’=A·C+B’·C’Y2=A·B’·C·D’+(A’+B)·E+C·D’·EA’+B=[(A’+B)’]’=(A·B’)’=(A·B’)·C·D’+(A·B’)’·E+C·D’·E=(A·B’)·C·D’+(A·B’)’·EY3=A·B’+B·C’+C·D’+D·A’+A·C’+A’·C=A·B’+B·C’+C·D’+D·A’

56RemoveliteralMethod(消因子法)：

A+A’·B=A+BY1=A·B’·C’·D+(A·B’·C’)’=D+(A·B’·C’)’Y2=A+A’·C·D+A’·B·C’=A+A’·(C·D+B·C’)=A+C·D+B·C’Y3=A·C+A’·D+C’·D=A·C+(A’+C’)·D=A·C+(A·C)’·D=A·C+D=A’+B+C+D

57ConsensusMethod(配項(xiàng)法)：

A+A=A;A+A’=1Y1=A’·B·C’+A’·B·C+A·B·C=A’·B·C’+A’·B·C+A’·B·C+A·B·C=A’·B+B·CY2=A·B’+A’·B+B·C’+B’·C=A·B’+A’·B·(C+C’)+B·C’+B’·C·(A+A’)=A·B’+A’·B·C+A’·B·C’+B·C’+A·B’·C+A’·B’·C=A·B’+A’·C+B·C’

58FormulaMethodSimplification——EXAMPLEEx.1：Ex.2：Ex.3：Ex.4：

59

60

61

62

63LogicFunctionsSimplifiedbyKarnaughMap(卡諾圖法化簡(jiǎn)邏輯函數(shù))YX0101m0m2m1m3m0m2m6m4m1m3m7m5ZXY0001111001YZWX00000111100111100412151393715261410811卡諾圖是真值表的另一種表現(xiàn)形式，它是將最小項(xiàng)按“邏輯相鄰”關(guān)系排列而成的一種方格圖形

64m26m27m25m24110m30m31m29m28111m22m23m21m20101m18m19m17m16100m10m14m6m210m11m15m7m311m9m13m5m101m8m12m4m000010011001000DEABC5變量K圖5變量以上的K圖可能有不同的形式，但不影響使用含有6個(gè)以上變量的邏輯關(guān)系一般不再使用K圖

65KarnaughMapEx.

F＝A＋BC＝m（3，4，5，6，7）＝M(0，1，2）111111010110100CABMinterm最小項(xiàng)0100010110100CABMaxterm最大項(xiàng)在無約束項(xiàng)的邏輯函數(shù)中，沒添的格子意味著為0在無約束項(xiàng)的邏輯函數(shù)中，沒添的格子意味著為100000010010001111001101111011111ABCF

66exercise將下面兩個(gè)邏輯函數(shù)用卡諾圖表示出來F1=A,B,C(1,3,5,7)

F2(A,B,C,D)=A·C’+B·C·D’+B

67卡諾圖的特點(diǎn)及應(yīng)用卡諾圖（K圖）的特點(diǎn)：n個(gè)變量對(duì)應(yīng)的K圖有2n

個(gè)小方格，每個(gè)小方格對(duì)應(yīng)一個(gè)最小項(xiàng)(最大項(xiàng))。各個(gè)小方格“邏輯相鄰”，即幾何位置上相鄰的小方格對(duì)應(yīng)的最小項(xiàng)彼此只有一個(gè)變量不同。因此K圖邊框處標(biāo)記的變量取值應(yīng)按格雷碼順序排列?？ㄖZ圖可用于進(jìn)行邏輯運(yùn)算，如求邏輯函數(shù)的反函數(shù)等。其中小方格的“邏輯相鄰”特性使K圖能夠非常容易地實(shí)現(xiàn)邏輯關(guān)系的化簡(jiǎn)。邏輯相鄰包括：幾何相鄰、幾何相對(duì)、幾何相疊

68RulesofLogicFunctionsSimplifiedbyKarnaughMap(卡諾圖化簡(jiǎn)邏輯函數(shù)的規(guī)則)最小項(xiàng)(最大項(xiàng))表示的邏輯函數(shù)（取值為1(0)的方格）化簡(jiǎn)，可得最簡(jiǎn)與或式(或與式)Rules:滿足相鄰關(guān)系的2k個(gè)取值為1(0)的小方格可化簡(jiǎn)k個(gè)變量。滿足最多原則。任意某個(gè)1(0)可以被多次使用。任意一個(gè)與(或)項(xiàng)的圈中，至少有一個(gè)1(0)沒有被任何其他的圈包含。1(0)必須被全部包含完，不能剩余。

69兩個(gè)最小項(xiàng)相鄰，可消去一個(gè)因子。111111ZXY0001111001YZWX000001111001111011111111X·Y·Z’+X·Y·Z=X·Y

X’·Y’·Z+X·Y’·Z=Y’·Z

70ABCD00011110000111101111111111A’BC‘D+A’BCD+ABC‘D+ABCD=A‘BD+ABD=BD四個(gè)最小項(xiàng)相鄰可消去二個(gè)因子ZXY00011110011

1

1

11

1

71ABCD00

01

11

10000111101111111111110000AD’八個(gè)最小項(xiàng)相鄰可消去三個(gè)因子F1=A·B·C+A·B·D+A·C’·D+C’·D’+A·B’·C+A’·C·D’

72StepsofLogicFunctionsSimplifiedbyKarnaughMap

(卡諾圖化簡(jiǎn)步驟)填寫卡諾圖直接表示，或先將函數(shù)化為最小項(xiàng)之和的形式圈組：找出可以合并的最小項(xiàng)組(圈)數(shù)最少、每組(圈)包含的方塊數(shù)最多方格可重復(fù)使用，但至少有一個(gè)未被其它組圈過讀圖：寫出化簡(jiǎn)后的乘積項(xiàng)0反變量1原變量圈1，得“與或式”；圈0，得“或與式”

73

LogicFunctionsSimplifiedbyKarnaughMap

(卡諾圖化簡(jiǎn)邏輯函數(shù))化簡(jiǎn)函數(shù)：F2=(A,B,C,D)(0,2,3,5,7,8,10,11,13)ABCD0001111000011110A’·B·DB·C’·DB’·CB’·D’1111111111、填圖2、圈組3、讀圖，得到結(jié)果F2=A’·B·D+B·C’·D+B’·C+B’·D’

741.Y=AB+A’C+B’C＝C

+AB1011011000ABC111111CAB=(A+B’)(A+C)(A+B’+C)(A+B+C)2.F=(A’(B+C’))’(A+B’+C)(A’B’C’)’=(A+B’C)(A+B’+C)(A+B+C)=(A+B’)(A+C)=A+B’C1011011000ABC00000011111A+B’A+C注意：最后兩個(gè)都是最簡(jiǎn)式。Ex.2、3

753.Y=AB+BC+BC+AB=AC+

BC+AB1011011000ABC11111111ACBCABEx.3

764.Y=AB+BC+CD+DA+AC+AC=AB+BC+CD+DA5.Y=ABC+ABC+ABC=AC+BC1011010010110100ABCD1111111111111111111111111011011000ABC111Ex.4、5

7711111110111111011110011011111101100010011001000ABCDEY(A,B,C,D,E)=m(2,6,9,10,11,12,14,18,19,22,23,24,27,28,31)Ex.6

＝A’BC’E+A’DE’+BCD’E’+ABD’E’+ADE+AB’D或=A’BC’E+A’DE’+BCD’E’+ABD’E’+ADE+B’DE’

78Ex.7:化為最簡(jiǎn)或與式Y(jié)(A,B,C,D)=M(0,2,3,4,6,8,10,11,12,13,14)1011010010110100ABCD00000000000=D(B+C’)(A’+B’+C)

79exercise2、Y(A,B,C,D)=m(1,3,4,6,9,11,12,14)3、Y(A,B,C,D)=m(5,7,8,9,13)用卡諾圖法化簡(jiǎn)下列函數(shù)為最簡(jiǎn)與非-與非式：1、Y(A,B,C,D)=m(0,3,4,5,6,7,9,12,14,15)

80練習(xí)結(jié)果

81exercise

:LogicFunctionsSimplifiedbyKarnaughMapF1=(A,B,C,D)(0,3,4,5,6,7,9,12,13,14,15)F2=(A,B,C,D)(1,5,6,7,11,12,13,15)F3=(A,B,C,D)(0,1,3,4,5,7)F4=(A,B,C,D)(1,2,3,5,6,7,9,10,11,13,14)

82SeveralConcepts(幾個(gè)概念)

AlogicfunctionP(X1,…,Xn)impliesalogicfunctionF(X1,…,Xn)

ifforeveryinputcombinationsuchthatP=1,thenF=1also.(對(duì)于邏輯函數(shù)P(X1,…,Xn)和F(X1,…,Xn)，若對(duì)任何使P=1的輸入組合，也能使F為1，則稱P隱含F(xiàn)，或者F包含P。)P1(A,B,C)=A·B·C’F(A,B,C)=A·B+B’·CP2(A,B,C)=B’·CP=A,B,C(1,3,6)F=A,B,C(1,3,5,6,7)

83SeveralConcepts(幾個(gè)概念)

AprimeimplicantofalogicfunctionF(X1,…,Xn)isanormalproducttermP(X1,…,Xn)thatinpliesF,suchthatifanyvariableisremovedfromP,thentheresultingproducttermdoesnotimplyF.

(邏輯函數(shù)F(X1,…,Xn)的主蘊(yùn)含項(xiàng)是隱含F(xiàn)的常規(guī)乘積項(xiàng)P(X1,…,Xn)，如果從P中移去任何變量，則所得的乘積項(xiàng)不隱含F(xiàn)。)F(A,B,C)=A·B·C+B·C+A·C’=B·C+A·C’主蘊(yùn)含項(xiàng)定理：最小和是主蘊(yùn)含項(xiàng)之和

84SeveralConcepts(幾個(gè)概念)蘊(yùn)含項(xiàng)（implicant）：只包含1的一個(gè)矩形圈；主蘊(yùn)含項(xiàng)（primeimplicant）：擴(kuò)展到最大的蘊(yùn)含項(xiàng)；

85SeveralConcepts(幾個(gè)概念)Distinguished1-cell

(奇異“1”單元)Aninputcombinationthatiscoveredbyonlyoneprimeinplicant(僅被單一主蘊(yùn)含項(xiàng)覆蓋的輸入組合)沒有可能被重復(fù)“圈”過的1單元ABCD00

01

11

10000111101111111111

86SeveralConcepts(幾個(gè)概念)EssentialPrimeImplicant(質(zhì)主蘊(yùn)含項(xiàng))Aprimeimplicantthatcoversoneormoredistinguished1-cell(覆蓋1個(gè)或多個(gè)奇異“1”單元的主蘊(yùn)含項(xiàng))沒有可能被重復(fù)“圈”過的1單元ABCD00

01

11

10000111101111111111

87SeveralConcepts(幾個(gè)概念)ABCD000111100001111011111111奇異“1”單元僅被單一主蘊(yùn)含項(xiàng)覆蓋的輸入組合質(zhì)主蘊(yùn)含項(xiàng)覆蓋1個(gè)或多個(gè)奇異“1”單元的主蘊(yùn)含項(xiàng)圈組時(shí)應(yīng)從合并奇異“1”單元開始

88SeveralConcepts(幾個(gè)概念)質(zhì)主蘊(yùn)含項(xiàng)(EssentialPrimeimplicant)：含有其他圈不含的最小項(xiàng)的主蘊(yùn)含項(xiàng)；奇異1單元(Distinguished1-cell)：只存在于一個(gè)質(zhì)主蘊(yùn)含項(xiàng)中的1單元；

89例：化簡(jiǎn)F=A,B,C,D(0,1,2,3,4,5,7,14,15)CDAB00

01

11

10000111101111111111、填圖2、圈組找奇異“1”單元圈質(zhì)主蘊(yùn)含項(xiàng)圈其它的13、讀圖F(A,B,C,D)=A’·B’+A’·C’+A’·D+A·B·C

90CDAB00

01

11

100001111011111111111CDAB00

01

11

100001111011111111111化簡(jiǎn)結(jié)果不一定唯一（但代價(jià)相同）

91CDAB00

01

11

1000011110111111沒有奇異“1”單元沒有質(zhì)主蘊(yùn)含項(xiàng)CDAB00

01

11

1000011110111111注意：不要重疊至少有一個(gè)1未被圈過

92CompleteDescriptionFunctionsand

Non-CompleteDescriptionFunctions

(完全描述函數(shù)和非完全描述函數(shù)）在n變量的邏輯關(guān)系中，若每一種輸入變量的取值組合都有確定的輸出，則稱這樣的邏輯關(guān)系為完全描述函數(shù)(CompleteDescriptionFunctions)

。在n變量的邏輯關(guān)系中，若某些輸入變量的取值組合是不允許的或不會(huì)出現(xiàn)的，則這些輸入組合所對(duì)應(yīng)的最小項(xiàng)稱為約束項(xiàng)(RestrictionTerms)；若某些輸入變量的取值組合使得輸出可為任意值，則這些輸入組合所對(duì)應(yīng)的最小項(xiàng)稱為無關(guān)項(xiàng)(Don’tCareTerm)。約束項(xiàng)和無關(guān)項(xiàng)統(tǒng)稱為任意項(xiàng)(ArbitraryTerm)。具有任意項(xiàng)的邏輯函數(shù)稱為非完全描述函數(shù)(Non-CompleteDescriptionFunctions)

93expressofArbitraryTerm

任意項(xiàng)的表示方法在邏輯函數(shù)式中，任意項(xiàng)通常用d表示，或用約束方程d＝0來表示；在卡諾圖中，任意項(xiàng)通常用、d或來表示；

94帶任意項(xiàng)的邏輯函數(shù)的化簡(jiǎn)規(guī)則化簡(jiǎn)時(shí)，任意項(xiàng)的處理：實(shí)際上，非完全描述邏輯函數(shù)中任意項(xiàng)（包括約束項(xiàng)和無關(guān)項(xiàng)）的取值對(duì)輸出來說是無關(guān)緊要的，所以從方便化簡(jiǎn)的角度出發(fā)，根據(jù)需要視為“1”，或視為“0”。帶任意項(xiàng)邏輯函數(shù)的化簡(jiǎn)規(guī)則：最小項(xiàng)(最大項(xiàng))表示的邏輯函數(shù)：把所有的任意項(xiàng)看成1

(0)

，按普通邏輯函數(shù)化簡(jiǎn)，但任意一個(gè)與(或)項(xiàng)的圈中，至少有一個(gè)真實(shí)1(0)

（不是任意