数字逻辑设计及应用教学课件：4-1定理

1、If number A twos-complement =11111001 and B twos-complement=11010101 , calculate -A-B twos-complement, -A+B twos-complement and indicate whether or not overflow occurs.,Exercise before class：,If number A twos-complement =11111001 and B twos-complement=11010101 , calculate -A-B twos-complement, -A+B

2、twos-complement and indicate whether or not overflow occurs. -A-B twos-complement= 00111110 , overflow: no -A+B twos-complement= 11011100 , overflow: no ,Answer,c h a p t e r 4,Combinational Logic Design Principles,c h a p t e r 4 Switching Algebra Combinational Circuit Analysis Combinational Circui

3、t Synthesis Timing Hazards,Basic Concept (基本概念),Logic circuits are classified into two types（逻辑电路分为两大类） combinational logic circuit（组合逻辑电路） A combinational logic circuit is one whose outputs depend only on its current inputs.（任何时刻的输出仅取决与当时的输入） characteristic：no feedback circuit sequential logic circ

4、uit（时序逻辑电路） The outputs of a sequential logic circuit depend not only on the current inputs, but also on the past sequence of inputs, possibly arbitrarily far back in time.（任一时刻的输出不仅取决于当时的输入，还取决于过去的输入顺序）,布尔（BooleGeorge）英国伟大的数学家、逻辑学家,1854年，他出版了思维规律的研究一书，其中完满地讨论了这个主题并奠定了现在所谓的符号逻辑的基础。用一套符号来进行逻辑演算 ，即逻辑的

5、数学化。 布尔一生共发表了50篇学术论文和两部教科书，其中主要是“论牛顿”(1835)和逻辑的数学分析，论演绎推理的演算法(1847)，以他的名字命名的布尔代数今天已发展为结构极为丰富的代数理论，并且无论在理论方面还是在实际应用方面都显示出它的重要价值特别是近几十年来，布尔代数在自动化系统和计算机科学中已被广泛应用,Claude Elwood Shannon克劳德艾尔伍德香农 美国数学家、信息论的创始人,1938年，他的硕士论文题目是A Symbolic Analysis of Relay and Switching Circuits(继电器与开关电路的符号分析)。他用布尔代数分析并优化开关电

6、路，奠定了数字电路的理论基础。 1948年通讯的数学原理、1949年噪声下的通信。两篇论文成为了信息论的奠基性著作。用布尔代数分析并优化开关电路，这就奠定了数字电路的理论基础。 1949年香农发表了另外一篇重要论文Communication Theory of Secrecy Systems(保密系统的通信理论)，正是基于这种工作实践，它的意义是使保密通信由艺术变成科学。,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

7、 = 1,then X =0 （A3）00 = 0 （A3） 1+1 = 1 （A4） 11 = 1 （A4） 0+0 = 0 （A5） 01 = 10 = 0 （A5） 1+0 = 0+1 = 1,We 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）,逻辑乘

8、logical multiplication dot 乘点 multiplication dot,4.1.2 Single-Variable Theorems (单变量开关代数定理) P188,Identities (自等律)： (T1) X + 0 = X (T1) X 1 = X Null Elements(0-1律)： (T2) X + 1 = 1 (T2) X 0 = 0 Idempotency (同一律): (T3) X + X = X (T3) X X = X Involution (还原律)：(T4) ( X ) = X Complements (互补律): (T5) X + X

9、 = 1 (T5) X X =0,变量和 常量的 关系,变量和 其自身 的关系,4.1.3 Two- and Three-Variable Theorems(1),Commutativity (交换律) (T6)X + Y = Y + X (T6) X Y= Y X Associativity (结合律) (T7) X(YZ) = (XY)Z (T7) X+(Y+Z) = (X+Y)+Z Distributivity (分配律) (T8) X(Y+Z) = XY+XZ (T8) X+YZ = (X+Y)(X+Z),Each of these theorems is easily proved

10、by perfect induction. (可以利用完备归纳法证明公式和定理) P188 Similar Relationship with General Algebra (与普通代数相似的关系),4.1.2 Single-Variable Theorems (单变量开关代数定理) P188,Eg.,4.1.3 Two- and Three-VariableTheorems(2),Covering(吸收律) (T9) X + XY = X (T9) X(X+Y) = X Combining(合并律) (T10) XY + XY = X (T10) (X+Y)(X+Y) = X Consen

11、sus（添加律（一致性定理） (T11) XY + XZ + YZ = XY + XZ (T11) (X+Y)(X+Z)(Y+Z) = (X+Y)(X+Z),所有定理中，都可以用逻辑表达式替换变量！,Notes,no power of number(没有变量的乘方) AAA A3 common factor(允许提取公因子) AB+AC = A(B+C) no division(没有定义除法) if AB=BC A=C ?,No subtracting(没有定义减法) if A+B=A+C B=C ?,A=1, B=0, C=0 AB=BC=0, AC,A=1, B=0, C=1,错！,错！,

12、4.1.4 n-Variable Theorems (n变量定理),Generalized idempotency(广义同一律) (T12) X + X + + X = X (T12) X X X = X DeMorgans Theorems(德.摩根定理) (T13) (X1X2X n)=X1+ X2 +X n (T13) (X1+ X2+ +X n)= X1 X2 X n Generalized DeMorgans Theorems (广义德.摩根定理) (T14)F(X1 ,X2 ,X n,+, )=F(X1, X2,X n, ,+),Most of these theorems can

13、 be proved using a two-step method called finite 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 for n = i + 1 (the induction step). P(190),finite induction (P190),X + X + X + + X = X + (X + X + +

14、 X) (i + 1 Xs on either side) = X + (X) (if T12 is true for n = i) = X (according to T3),Demorgans Theorems(摩根定理) (P191),(A B) = A + B,(A + B) = A B,反演规则(Complement Rules)： swapping + and . and complementing all variables. +，0 1，变量取反 遵循原来的运算优先（Priority）次序 不属于单个变量上的反号应保留不变,complement of a logic expre

15、ssion (F) (反演定理) ( P192),例1：写出下面函数的反函数 （Complement function ) F1 = A (B + C) + C D F2 = (A B) + C D E,例2：证明 (AB + AC) = AB + AC,合理地运用反演定理能够将一些问题简化,合理地运用反演定理能够将一些问题简化,(AB + AC),AB + AC + BC = AB + AC,(A+B)(A+C),AA +AC + AB + BC,AC + AB,AC + AB + BC,Example 2：prove (AB + AC) = AB + AC,4.1.5 duality(对偶

16、定理) (P193),FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , ,Xn , , + , ),Principle of Duality Any theorem or identity in switching algebra remains true if 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(对偶定理) (P193),对偶规则 +；0 1

17、 变换时不能破坏原来的运算顺序（优先级） 对偶原理 (Principle of Duality) 若两逻辑式相等，则它们的对偶式也相等,例： 写出下面函数的对偶函数 F1 = A + B (C + D) F2 = ( A(B+C) + (C+D) ),X + X Y = X X X + Y = X(错),X ( X + Y ) = X,FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ),对偶定理（Duality Theorems）,证明公式：A+BC = (A+B)(A+C),Duality and Complement (对偶和反

18、演) (P194.P195),对偶(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 ),正逻辑约定和负逻辑约定互为对偶关系,Electrical Function Table (电气功能表),Positive-Logic Convention,Negative-Logic Convention,Posit

19、ive-Logic (正逻辑)： F = AB,Negative-Logic (负逻辑)： F = A+B,The relationship of Positive-Logic Convention and Negative-Logic Convention are Duality (正逻辑约定和负逻辑约定互为对偶关系),Shannons expansion theorems(香农展开定理),香农展开定理主要用于证明等式或展开函数, 将函数展开一次可以使函数内部的变量数 从n个减少到n-1个.,Shannons expansion theorems,F=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.