參考數(shù)電4-1定理chenyu

1、【Exercise 1】Which The maximumpropagation delayof the 74LS00is tpLH = tpHL=15ns. For both LOW-HIGH and HIGH-LOW transitions, determine the exact maximum propagation delay from INto OUT of hebelowcircuit. (Everygateusestheworst caseofdelay to calculate). 【Solution】Because the maximumpropagation delayo

2、f the 74LS00is tpLH = tpHL=15ns, so no matter the gate state transit from low state to high stateor fromhigh stateto lowstate, the propagation delays of thegates are the same. So the maximumpropagation delay in Figure 3.17 is .Exercise before class：【Exercise 2】Which logic gate of the following CMOS

3、gates is corresponding to in the sense of negative logic?(1）AND (2)OR (3)NAND (4)NOR 【Solution】(1)OR (2) AND (3)NOR (4)NANDExercise before class：c h a p t e r 4 CombinationalLogic Design Principles c h a p t e r 4 Switching Algebra Combinational Circuit Analysis Combinational Circuit Synthesis Timin

4、g Hazards Basic Concept (基本概念)Logic circuits are classified into two types（邏輯電路分為兩大類(lèi)） combinational logic circuit（組合邏輯電路） A combinational logic circuit is one whose outputs depend only on its current inputs.（任何時(shí)刻的輸出僅取決與當(dāng)時(shí)的輸入） characteristic：no feedback circuit sequential logic circuit（時(shí)序邏輯電路） The ou

5、tputs of a sequential logic circuit depend not only on the currentinputs, but also on the past sequence of inputs, possibly arbitrarily far backin time.（任一時(shí)刻的輸出不僅取決于當(dāng)時(shí)的輸入，還取決于過(guò)去的輸入順序）布爾（BooleGeorge）英國(guó)偉大的數(shù)學(xué)家、邏輯學(xué)家 1854年，他出版了思維規(guī)律的研究一書(shū)，其中完滿(mǎn)地討論了這個(gè)主題并奠定了現(xiàn)在所謂的符號(hào)邏輯的基礎(chǔ)。用一套符號(hào)來(lái)進(jìn)行邏輯演算 ，即邏輯的數(shù)學(xué)化。布爾一生共發(fā)表了50篇學(xué)術(shù)論文和兩

6、部教科書(shū)，其中主要是“論牛頓”(1835)和邏輯的數(shù)學(xué)分析，論演繹推理的演算法(1847)，以他的名字命名的布爾代數(shù)今天已發(fā)展為結(jié)構(gòu)極為豐富的代數(shù)理論，并且無(wú)論在理論方面還是在實(shí)際應(yīng)用方面都顯示出它的重要價(jià)值特別是近幾十年來(lái)，布爾代數(shù)在自動(dòng)化系統(tǒng)和計(jì)算機(jī)科學(xué)中已被廣泛應(yīng)用 Claude Elwood Shannon克勞德艾爾伍德香農(nóng) 美國(guó)數(shù)學(xué)家、信息論的創(chuàng)始人 1938年，他的碩士論文題目是A Symbolic Analysis of Relay and Switching Circuits(繼電器與開(kāi)關(guān)電路的符號(hào)分析)。他用布爾代數(shù)分析并優(yōu)化開(kāi)關(guān)電路，奠定了數(shù)字電路的理論基礎(chǔ)。1948年通訊

7、的數(shù)學(xué)原理、1949年噪聲下的通信。兩篇論文成為了信息論的奠基性著作。用布爾代數(shù)分析并優(yōu)化開(kāi)關(guān)電路，這就奠定了數(shù)字電路的理論基礎(chǔ)。1949年香農(nóng)發(fā)表了另外一篇重要論文Communication Theory of Secrecy Systems(保密系統(tǒng)的通信理論)，正是基于這種工作實(shí)踐，它的意義是使保密通信由藝術(shù)變成科學(xué)。 4.1 Switching Algebra 4.1.1 Axioms（公理 ） P185（A1）X = 0 if X 1, （A1） X = 1 if X 0（A2）If X = 0,then X = 1（A2）If X = 1,then X =0（A3）00 = 0 （

8、A3） 1+1 = 1（A4） 11 = 1 （A4） 0+0 = 0（A5） 01 = 10 = 0 （A5） 1+0 = 0+1 = 1We stated these axioms as a pair, with the only difference between A1 and A1 being the interchange of the symbols 0 and 1. This is a characteristic of all the axioms of switching algebra . P（185）邏輯乘 logical multiplication dot乘點(diǎn) mu

9、ltiplication dotLogical addition邏輯加Plus sign(+)4.1.2 Single-Variable Theorems (單變量開(kāi)關(guān)代數(shù)定理) P188Identities (自等律)： (T1) X + 0 = X (T1) X 1 = XNull Elements(0-1律)： (T2) X + 1 = 1 (T2) X 0 = 0Idempotency (同一律): (T3) X + X = X (T3) X X = XInvolution (還原律)：(T4) ( X ) = XComplements (互補(bǔ)律): (T5) X + X = 1 (T

10、5) X X =0 變量和常量的關(guān)系變量和其自身的關(guān)系4.1.3 Two- and Three-Variable Theorems(1)Commutativity (交換律) (T6)X + Y = Y + X (T6) X Y= Y X Associativity (結(jié)合律) (T7) X(YZ) = (XY)Z (T7) X+(Y+Z) = (X+Y)+ZDistributivity (分配律) (T8) X(Y+Z) = XY+XZ (T8) X+YZ = (X+Y)(X+Z)Each of these theorems is easily proved by perfect induc

11、tion.(可以利用完備歸納法證明公式和定理) P188 Similar Relationship with General Algebra (與普通代數(shù)相似的關(guān)系)4.1.2 Single-Variable Theorems (單變量開(kāi)關(guān)代數(shù)定理) P188Eg.4.1.3 Two- and Three-VariableTheorems(2)Covering(吸收律)(T9) X + XY = X (T9) X(X+Y) = XCombining(合并律)(T10) XY + XY = X (T10) (X+Y)(X+Y) = XConsensus（添加律（一致性定理）(T11) XY +

12、XZ + YZ = XY + XZ(T11) (X+Y)(X+Z)(Y+Z) = (X+Y)(X+Z)所有定理中，都可以用邏輯表達(dá)式替換變量！Notesno power of number(沒(méi)有變量的乘方) AAA A3common factor(允許提取公因子) AB+AC = A(B+C)no division(沒(méi)有定義除法) if AB=BC A=C ? No subtracting(沒(méi)有定義減法) if A+B=A+C B=C ?A=1, B=0, C=0AB=BC=0, ACA=1, B=0, C=1錯(cuò)！錯(cuò)！4.1.4 n-Variable Theorems (n變量定理)Gener

13、alized idempotency(廣義同一律)(T12) X + X + + X = X (T12) X X X = XDeMorgans Theorems(德.摩根定理)(T13) (X1X2X n)=X1+ X2 +X n(T13) (X1+ X2+ +X n)= X1 X2 X nGeneralized DeMorgans Theorems (廣義德.摩根定理) (T14)F(X1 ,X2 ,X n,+, )=F(X1, X2,X n, ,+)Most of these theorems can be proved using a two-step method called fin

14、ite inductionfirst proving that the theorem is true for n = 2 (the basis step) and then proving that if the theorem is true for n = i, then it is also true forn = i + 1 (the induction step). P(190)finite induction (P190)X + X + X + + X = X + (X + X + + X) (i + 1 Xs on either side) = X + (X) (if T12

15、is true for n = i) = X (according to T3)Demorgans Theorems(摩根定理) (P191)(A B) = A + B(A + B) = A BDemorgans Theorems(摩根定理) (P191)The 2-level NAND form is反演規(guī)則(Complement Rules)：swapping + and . and complementing all variables. +，0 1，變量取反 遵循原來(lái)的運(yùn)算優(yōu)先（Priority）次序 不屬于單個(gè)變量上的反號(hào)應(yīng)保留不變 complement of a logic exp

16、ression (F) (反演定理) ( P192)例1：寫(xiě)出下面函數(shù)的反函數(shù) （Complement function ) F1 = A (B + C) + C D F2 = (A B) + C D E例2：證明 (AB + AC) = AB + AC 合理地運(yùn)用反演定理能夠?qū)⒁恍﹩?wèn)題簡(jiǎn)化合理地運(yùn)用反演定理能夠?qū)⒁恍﹩?wèn)題簡(jiǎn)化(AB + AC)AB + AC + BC = AB + AC(A+B)(A+C)AA +AC + AB + BCAC + AB AC + AB + BCExample 2：prove (AB + AC) = AB + AC4.1.5 duality(對(duì)偶定理) (P19

17、3) FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , ,Xn , , + , ) Principle of Duality Any theorem or identity in switching algebra remains trueif 0 and 1 are swapped and . and + are swapped throughout. the dual of a logic expression F(X1,X2,Xn) = FD(X1,X2,Xn)4.1.5 duality(對(duì)偶定理) (P193)對(duì)偶規(guī)則 +；0 1變換時(shí)不能破壞原來(lái)的運(yùn)

18、算順序（優(yōu)先級(jí)）對(duì)偶原理 (Principle of Duality)若兩邏輯式相等，則它們的對(duì)偶式也相等例： 寫(xiě)出下面函數(shù)的對(duì)偶函數(shù)F1 = A + B (C + D)F2 = ( A(B+C) + (C+D) )X + X Y = XX X + Y = X(錯(cuò))X ( X + Y ) = X FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) 對(duì)偶定理（Duality Theorems）證明公式：A+BC = (A+B)(A+C)A(B+C)AB+ACDuality and Complement (對(duì)偶和反演) (P194.P1

19、95)對(duì)偶(Duality)：FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) 反演(Complement)： F(X1 , X2 , , Xn , + , ) = F(X1 , X2, , Xn , , + ) F(X1 , X2 , , Xn) = FD(X1 , X2, , Xn ) 正邏輯約定和負(fù)邏輯約定互為對(duì)偶關(guān)系G1ABFA B FL L LL H LH L LH H HElectrical FunctionTable (電氣功能表)A B F0 0 00 1 01 0 01 1 1Positive-LogicConv

20、entionA B F1 1 11 0 10 1 10 0 0Negative-LogicConventionPositive-Logic (正邏輯)： F = ABNegative-Logic (負(fù)邏輯)： F = A+BThe relationship of Positive-Logic Convention and Negative-Logic Convention are Duality (正邏輯約定和負(fù)邏輯約定互為對(duì)偶關(guān)系) Shannons expansion theorems(香農(nóng)展開(kāi)定理)香農(nóng)展開(kāi)定理主要用于證明等式或展開(kāi)函數(shù),將函數(shù)展開(kāi)一次可以使函數(shù)內(nèi)部的變量數(shù)從n個(gè)減少到n

21、-1個(gè).Shannons expansion theoremsF=X.Y+Y.Z =X(1.Y+Y.Z)+X(0.Y+Y.Z)+Y(1.X+1.Z)+Y(0.X+0.Z)+Z(X.Y+Y.1)+Z(X.Y+Y.0) =X.Y.Z+X.Y.Z+X.Y.ZShannons expansion theorems【例】試將下列邏輯函數(shù)化為最簡(jiǎn)與或式【解題指導(dǎo)】如果要化簡(jiǎn)的邏輯函數(shù)變量較多，也比較復(fù)雜，這時(shí)可以利用香農(nóng)展開(kāi)定理及其推論對(duì)邏輯函數(shù)進(jìn)行化簡(jiǎn)。邏輯等式證明邏輯等式證明常用以下方法：真值表法：列出等式兩邊邏輯表達(dá)式的真值表，若兩個(gè)真值表相同，則等式成立。對(duì)偶定理法：等式兩邊的對(duì)偶式仍相等。代入定理法：等式兩邊的同一變量若用同一函數(shù)代替，等式仍成立。公式法：利用邏輯代數(shù)中的定理和規(guī)則，將等式兩邊化成相同的形式，則等式成立。Basic formula 異或(XOR)交換律：AB = BA結(jié)合律：A(BC) = (AB)