逻辑电路的分析和设计1

1、第二章第二章 逻辑逻辑电路中电路中 的的代数代数基础基础 George Boole 乔治乔治布尔布尔（George Boole，1815年1864年）是皮匠的儿子，1815年11月生于 英格兰的林肯郡。由于家境贫寒，布尔不得不在协助养家的同时为自己能受教育 而奋斗，不管怎么说，他成了19世纪最重要的数学家之一。尽管他考虑过以牧师 为业，但最终还是决定从教，而且不久就开办了自己的学校。在备课的时候，布 尔不满意当时的数学课本，便决定阅读伟大数学家的论文。在阅读伟大的法国数 学家拉格朗日的论文时，布尔有了变分方面的新发现。变分是数学分析的分支， 它处理的是寻求优化某些参数的曲线和曲面。 1848年

2、，布尔出版了The Mathematical Analysis of Logic，这是它对符号 逻辑诸多贡献中的第一次。1849年。他被任命位于爱尔兰科克的皇後学院的数学 教授。1854年，他出版了The Laws of Thought， 这是他最著名的著作。在这本书中布尔介绍了现在以他的名字命 名的布尔代数。布尔撰写了微分方程和差分方程的课本，这些课本在英 国一直使用到19世纪末。布尔在1855年结婚，他的妻子使皇後校园一位希腊文 教授的侄女。1864年，布尔死于肺炎，肺炎是他在暴风雨天气中尽管已经湿淋淋 的了仍坚持上课引起的。 主要内容 1.布尔代数基础布尔代数基础 Fundamental

3、s of Boolean Algebra 基本公设 Basic Postulates 。 基本公设 Basic Postulates 基本公设 Basic Postulates a K, 唯一的唯一的a K,使得使得: (1) a +a = 1 (2) a a=0 对偶原理 Duality The principle of duality is a very important concept in Boolean algebra. Briefly stated, the principle of duality pronounces that, if an expression is val

4、id in Boolean algebra, the dual of the expression is also valid. The dual expresion is found(建立) by replacing all + operators with , all operator with +, all ones with zeros , and all zeros with ones. 对偶规则对偶规则 F: 0 1 + F: 1 0 + 举例举例 a+(bc)=(a+b)(a+c) a (b+c)=a b+a c 逻辑表达式逻辑表达式:由逻辑变量由逻辑变量,逻辑值与逻逻辑值与逻

5、辑操作辑操作(+, )组成的表达式组成的表达式. 对偶原理 Duality 操作的顺序操作的顺序 a+a=a a.a=a 1.重叠律重叠律 证明证明: a+a=(a+a).1 =(a+a).(a+a) =a+a.a =a+0 =a 对偶规则对偶规则 证明证明: a.a=a.a+0=a.a+a.a=a.(a+a)=a.1=a 基本定理 1 Fundamental Theorems of Boolean Algebra a+1=1 a 0=0 对偶规则对偶规则 基本定理2 证明证明: a+1=(a + 1) 1 =1 (a + 1) =(a+a)(a+1) =a+a1 =a+a=1 证明证明: a

6、0=a(aa)=(aa)a=aa=0 a+ab=a a(a+b)=a 证明证明: a+ab=a.1+ab=a.(1+b)=a.1=a a(a+b)=(a+0)(a+b)=a+0.b=a+0=a 基本定理3、4、5 a = a a与与 a 互补互补 a a = 0 a + a = 1 证明证明: a+ab=(a+a)(a+b)=1(a+b)=a+b a(a+b)=aa+ab=0+ab=ab a+ab=a+b a(a+b)=ab ab+ab=a (a+b)(a+b)=a 证明证明: ab+ab=a(b+b)=a.1=a (a+b)(a+b)=a+(bb)=a+0=a ab+abc=ab+ac (a

7、+b)(a+b+c)=(a+b)(a+c) 证明证明: ab+abc=(ab+abc)+abc=ab+(abc+abc)=ab+ac (a+b)(a+b+c)=(a+b)(a+b+c)(a+b+c) =(a+b)(a+b+c)(a+b+c)=(a+b)(a+c)(b+b) =(a+b)(a+c) 基本定理6、7 DeMorgan定理定理: (1)a+b=a.b (2)a.b=a+b (a+b)(a.b)=0 (a+b)+a.b=1 a+b=a.b 基本定理8 ?想一想，为什么想一想，为什么 (a+b)(a.b)=0 (a+b)+a.b=1 a+b=a.b abcd.z=a+b+c+d+.z a

8、+b+c+d+.+z=a.b.c.d.z 基本定理 ?想一想，为什么想一想，为什么 基本定理9 运算符 +，或 ，与，这个符号也可以被省略 ，异或 AB = AB + AB ，同或 AB = AB + AB AB= AB 异或的定理 AA=0AA=0 AA=1AA=1 A0=AA0=A A1=AA1=A AB=AB=AB1AB=AB=AB1 AB=BAAB=BA A(BC)=(AB)CA(BC)=(AB)C A A(BC)=(A(BC)=(AB)(AB)(AC)C) “与与”对对“异异 或或”的分配律的分配律 ABC=ABCABC=ABC 用文氏图(ven diagram) 来理解逻辑定理 与

9、逻辑与逻辑 或逻辑或逻辑 非逻辑非逻辑 异或逻辑异或逻辑AB = AB + ABAB = AB + AB 用文氏图(ven diagram) 来理解逻辑定理 与对异或的与对异或的 分配律成立分配律成立 用文氏图(ven diagram) 来理解逻辑定理 思考思考:或对异或或对异或 是否具有类似是否具有类似 的分配律的分配律? 用文氏图(ven diagram) 来理解逻辑定理 ?想一想想一想 2. 开关函数与开关电路 开关函数中的3个重要规则 （1） 代入规则： 在任何一个逻辑等式中，如将等式两边所有出 现某一变量的地方都用同一函数式替代，则等 式仍然成立。这个规则就是代入规则。代入规 则扩大

10、了逻辑等式的应用范围。 例如： A = (A + B)(A + B) 则有： A + B = (A + B + C)(A + B + C) 显然，这是用A+B代替了A, 用C代替了B 开关函数中的3个重要规则 （2）对偶规则(principle of duality) ： 将某一逻辑表达式中的换成+、+换成 ； 0换成1，1换成0，就得到一个新的表达式。这个 新的表达式就是原表达式的对偶式。如果两个逻 辑式相等，则它们的对偶式也相等。这就是对偶 规则。 例如： 则左边的对偶式为： 所以有： A + B = A B A + B A B 右边的对偶式为： A B = A + B 开关函数中的3个重

11、要规则 （3）反演规则(又称为香农定理)(Shannons Theorem) ： 如将某一逻辑式中的换成+、+换成 ；0 换成1，1换成0 ；原变量换成反变量，反变量换成 原变量，则所得到的逻辑表达式称为原式的反演式。 这种变换方法称为反演规则。利用反演规则可以比 较容易地求出一个函数的反函数。 例如： 其反演式为： A B = A + B A + B = A B 开关函数中的3个重要规则 注意 (1)在运用反演规则或对偶规则的时候，要保 持运算的优先级一致性。 (2) 在运用反演规则（香农定理）时，不是一个变量 上的反号不能变动。也就是，只改变单个变量。原 变反，反变原。 例如： 其左边的对

12、偶式为： A + BC = (A + B)(A + C) A (B + C) 而非： A B + C 真值表真值表(Truth Table)表示表示 A B C F(A,B,C) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 真值表真值表 Truth Tables表示表示 开关函数的真值表表示举例开关函数的真值表表示举例 F(a,b,c) = a b c + a b c + a b c + a b c 1, 分为 SOP 和 POS两种 2, 对于其中的每一种, 范式的意义是使 得任何一个逻辑表达式都有唯一的标准

13、 形式. 3, 对于 SOP而言, 范式由若干个最小项 之和形成 4, 同理,对于 POS 而言, 范式由若干个 最大项之积形成 什么是最小项什么是最小项? 最小项(min-terms): For a function of n variables, if a product term contains each of the n variables exactly one time in complemented of un-complemented form. This term is called minterm (1) 对于任一个最小项对于任一个最小项, 只有唯一的一组变量取值使其为只

14、有唯一的一组变量取值使其为1; (2) 对于任两个最小项对于任两个最小项, 其积为其积为0; (3) 所有最小项之和为所有最小项之和为1; (4) 将最小项对应的将最小项对应的n位二进制的数值位二进制的数值(原变量为原变量为1, 非变量为非变量为0) 记作其下标记作其下标i, 该项记作该项记作mi; (5) 清一色由最小项之和组成的范式称为积之和范式清一色由最小项之和组成的范式称为积之和范式 (canonical sum of products)(canonical SOP) 最小项的性质最小项的性质 mmmm m 1578 1 5 7 8( , , , ) m( , , , )13 56 最

15、大项(max-terms): For a function of n variables, if a sum term contains each of the n variables exactly one time in complemented of un-complemented form. This sum term is called maxterm 什么是最大项什么是最大项? (1) 对于任一个最大项对于任一个最大项, 只有唯一的一组变量取值使其为只有唯一的一组变量取值使其为0; (2) 对于任两个最大项对于任两个最大项, 其和为其和为1; (3) 所有最大项之积为所有最大项之积

16、为0; (4) 将最大项对应的将最大项对应的n位二进制位二进制(原变量为原变量为0, 非变量为非变量为1)的数值的数值 记作其下标记作其下标i, 该项记作该项记作Mi (5) 清一色由最大项之积组成的范式称为和之积范式清一色由最大项之积组成的范式称为和之积范式 (canonical product of sums)(canonical POS) 最大项的性质最大项的性质 最大项最大项 编码编码 表示表示 A+B+C 101 M5 A+B+C 011 M3 !小提示小提示 最小项用的是m, 原变量为1; 最大项用的是M, 原变量为0 F(A,B,C) = (A + B + C) (A + B +

17、 C) (A + B + C) = M1 M3 M5 = M(1,3,5) 001011 101 ABAf),( BAAB BBA ABAf )( ),( )( )*( ),( BABA BBA ABAf A B CF 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 0 原始表达式F(A,B,C) F(A,B,C) = m(0,2,4) 最大项范式与最小项范式的关系最大项范式与最小项范式的关系 原始表达式F(A,B,C) A B CF 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0

18、1 1 1 1 0 1 0 1 0 0 0 F(A,B,C) = M(1,3,5,6,7) 最大项范式与最小项范式的关系最大项范式与最小项范式的关系 最大项范式与最小项范式的关系最大项范式与最小项范式的关系 F(A,B,C) = M(1,3,5,6,7) 可见： F(A,B,C) = m(0,2,4) = ABC + ABC + ABC = (A+B+C) (A+B+C) (A+B+C) (A+B+C) (A+B+C) 结论：逻辑代数式F的最大项范式与最 小项范式的下标“互补”。 最大项范式与最小项范式举例最大项范式与最小项范式举例 已知函数 F(A,B,C) = AB + BC + ABC，

19、 求 F, F的最小项表达式和最大项表达式 两个思路：代数式法；真值表法 答案：F = m(2,3,5,6) = M(0,1,4,7) F= m(0,1,4,7) = M(2,3,5,6) 结论：逻辑代数式F的最大项范式与(F非)的 最小项范式下标相同；同理， F的最小项范 式与(F非)的最大项范式下标相同 最大项与最小项关系总结最大项与最小项关系总结 （1）构成最小项时，）构成最小项时，1代表原变量，代表原变量，0代表代表 反变量。反变量。 （2）构成最大项时，）构成最大项时，0代表原变量，代表原变量，1代表代表 反变量。反变量。 （3）一个逻辑表达式的最小项范式的下标）一个逻辑表达式的最小

20、项范式的下标 和最大项范式的下标互补。和最大项范式的下标互补。 （4）对某一个下标（任意一个），其最小）对某一个下标（任意一个），其最小 项和最大项互补。项和最大项互补。 最大项范式与最小项范式最大项范式与最小项范式 代数式法常见的扩展思路： （1）A = A1 = A (B + B) = AB + AB （2）A = A + 0 = A + BB = (A + B)(A + B) P168 2.20, 2.21 课堂练习：范式的推导 Applications-1 A burglar(盗窃) alarm for a bank is designed so that it senses four

21、 input signal lines. Line A is from the secret control switch, line B is from a pressure sensor under a steel safe(保险箱) in a locked closet(橱柜), line C is from a battery-powered clock, and line D is connected to a switch on the locked closet door. The following conditions produce a logic 1 voltage on

22、 each line: AB CD 保险箱控 制开关 有锁橱柜内保险箱 下的压力感应器 电子钟 橱柜的锁 AB CD 保险箱控 制开关 有锁橱柜内保险箱 下的压力感应器 电子钟 橱柜的锁 Applications-1 The following conditions produce a logic 1 voltage on each line: A: The control switch is closed. B:The safe is inits normal position in the closet. C:The clock is between 1000 and 1400 hours

23、 D:The closet door is closed. A:保险箱开关关上是1,打开是0 B:保险箱在原有位置的时候是1,被移走是0. C:电子钟在工作时间( 1000-1400 hours)是1,在非工作时间是0 D:橱柜的门被关上是1.打开是0 Applications-1 Write the equations of the control logic for the burglar alarm that prouces a logic 1(rings a bell) when the safe is moved and the control switch is closed, or when the closet is opened after banking hours, or when the closet is opened with the control switch open. AB CD 保险箱控 制开关 有锁橱柜内保险箱 下的压力感应器 电子钟 橱柜的锁 AB CD F(A,B,C,D)= A/B+/C/D+/A/D A D Applic