逻辑电路的分析和设计-1.ppt

第二章 逻辑电路中的代数基础,Algebraic Methods for the Analysis and Synthesis of Logic Circuit,George Boole,乔治布尔（George Boole，1815年1864年）是皮匠的儿子，1815年11月生于英格兰的林肯郡。由于家境贫寒，布尔不得不在协助养家的同时为自己能受教育而奋斗，不管怎么说，他成了19世纪最重要的数学家之一。尽管他考虑过以牧师为业，但最终还是决定从教，而且不久就开办了自己的学校。在备课的时候，布尔不满意当时的数学课本，便决定阅读伟大数学家的论文。在阅读伟大的法国数学家拉格朗日的论文时，布尔有了变分方面的新发现。变分是数学分析的分支，它处理的是寻求优化某些参数的曲线和曲面。 1848年，布尔出版了The Mathematical Analysis of Logic，这是它对符号逻辑诸多贡献中的第一次。1849年。他被任命位于爱尔兰科克的皇後学院的数学教授。1854年，他出版了The Laws of Thought，这是他最著名的著作。在这本书中布尔介绍了现在以他的名字命名的布尔代数。布尔撰写了微分方程和差分方程的课本，这些课本在英国一直使用到19世纪末。布尔在1855年结婚，他的妻子使皇後校园一位希腊文教授的侄女。1864年，布尔死于肺炎，肺炎是他在暴风雨天气中尽管已经湿淋淋的了仍坚持上课引起的。,主要内容,布尔代数基础 Fundamentals of Boolean Algebra 开关函数与开关电路 Switching Functions 开关电路 Switching Circuits 组合电路分析 Analysis of Combinational Circuits 组合逻辑电路综合 Synthesis of Combinational Logic Circuits 应用 Applications 逻辑电路的计算机辅助设计 Computer-Aided Design of Logic Circuits,1.布尔代数基础 Fundamentals of Boolean Algebra,基本定义 对偶规则 反演规则 基本定理 一些例子,1849,GEORGE BOOLE提出 逻辑思维处理的形式描述,公设1 定义 Postulates 1. Definition 布尔代数是一个封闭的代数系统,该系统包括一个 由两个或两个以上的元素组成的集合K,以及两种 操作,和+:满足: a,b K有a bK&a+b K.,基本公设 Basic Postulates,A Boolean algebra is a closed algebraic system containing a set K of two or more elements and the two operators. And +;alternatively ,for every a and b in set K, ab belongs to K and a+b belongs to K(+ is called OR and is called AND),公设2: 1元, 0元的存在性(existence): 具有唯一的元素1K,0K,使得,a K, (1) a + 0 = a (2) a 1 = a 其中,0、1分别称为或与操作的单位元(identity element)。,公设4: + 与 满足结合律(associativity)： a,b,cK, (1) a + ( b + c ) = ( a + b ) + c (2) a (b c) = (a b) c,公设3: + 与 满足交换律(commutativity)： a, bK, (1) a +b = b + a (2) a b = b a,基本公设 Basic Postulates,公设5: 满足 + 对 以及 对 + 的分配律(distributivity): a,b,c K, (1) a + (b c) = (a + b) ( a + c) (2) a (b + c) = a b + a c,基本公设 Basic Postulates,对偶原理 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 valid 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 F),对偶规则,对偶原理,举例,a+(bc)=(a+b)(a+c) a (b+c)=a b+a c,逻辑表达式:由逻辑变量,逻辑值与逻 辑操作(+, )组成的表达式.,对偶原理 Duality,操作的顺序,a+a=a a.a=a,1.重叠律,对偶规则,基本定理 1 Fundamental Theorems of Boolean Algebra,a+1=1 a 0=0,对偶规则,基本定理2,基本定理3、4、5,基本定理6、7,基本定理8,基本定理,基本定理9,运算符,+，或 ，与，这个符号也可以被省略 ，异或 AB = AB + AB ，同或 AB = AB + AB AB= AB,异或的定理,用文氏图(ven diagram) 来理解逻辑定理,与逻辑,或逻辑,非逻辑,用文氏图(ven diagram) 来理解逻辑定理,与对异或的 分配律成立,用文氏图(ven diagram) 来理解逻辑定理,思考:或对异或 是否具有类似 的分配律?,用文氏图(ven diagram) 来理解逻辑定理,开关代数(switching algebra): 当布尔代数中的集合K=0,1时,又称为开关代数,开关函数(switching function): F(X1,X2,X3,.,Xn),其定义域和值域=0,1.,F1(X1,X2,X3,.,Xn)= F2(X1,X2,X3,.,Xn) X1,X2,X3,.,Xn 0,1的一组值,都有F1=F2,2. 开关函数与开关电路,开关函数中的3个重要规则,（1） 代入规则： 在任何一个逻辑等式中，如将等式两边所有出现某一变量的地方都用同一函数式替代，则等式仍然成立。这个规则就是代入规则。代入规则扩大了逻辑等式的应用范围。,开关函数中的3个重要规则,（2）对偶规则(principle of duality) ： 将某一逻辑表达式中的换成+、+换成 ；0换成1，1换成0，就得到一个新的表达式。这个新的表达式就是原表达式的对偶式。如果两个逻辑式相等，则它们的对偶式也相等。这就是对偶规则。,开关函数中的3个重要规则,（3）反演规则(又称为香农定理)(Shannons Theorem) ： 如将某一逻辑式中的换成+、+换成 ；0换成1，1换成0 ；原变量换成反变量，反变量换成原变量，则所得到的逻辑表达式称为原式的反演式。这种变换方法称为反演规则。利用反演规则可以比较容易地求出一个函数的反函数。,开关函数中的3个重要规则,注意 (1)在运用反演规则或对偶规则的时候，要保持运算的优先级一致性。 (2) 在运用反演规则（香农定理）时，不是一个变量上的反号不能变动。也就是，只改变单个变量。原变反，反变原。,对所有可能的输入组合,求出其相应的函数值.将所有可能 的输入组合与其对应的函数值用表格的形式表现出来.该 表称为真值表.,真值表(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,书中 P93,Table 2.4(b) 有 错误！,真值表 Truth Tables表示,开关函数的真值表表示举例,SOP ：Sum Of Products 积之和,POS： Pruduct Of Sums 和之积,2.2.2开关函数的代数形式,F(A,B,C)=AB+AC+BC,积之和(SOP),和之积(POS),F(A,B,C)=(A+B)(A+C)(B+C),开关函数的代数形式,范式 Canonical Forms,1, 分为 SOP 和 POS两种 2, 对于其中的每一种, 范式的意义是使得任何一个逻辑表达式都有唯一的标准形式. 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) 对于任一个最小项, 只有唯一的一组变量取值使其为1;,(2) 对于任两个最小项, 其积为0;,(3) 所有最小项之和为1;,(4) 将最小项对应的n位二进制的数值(原变量为1, 非变量为0) 记作其下标i, 该项记作mi;,(5) 清一色由最小项之和组成的范式称为积之和范式 (canonical sum of products)(canonical SOP),最小项的性质,最小项范式,一个积项称为一个最小项:若对于每个函数变量, 该积项或者包含该变量或者包含改变量的反变量.,若一个布尔函数表示为最小项之和的形式,成为 最小项范式.每个最小项表示为一个二进制数: 原变量表示为1,补变量表示为0.,开关函数的代数形式:范式 Canonical Forms,f(A,B,C)=ABC+ABC+ABC+ABC =m1 + m3 + m5 + m6,例:将下列函数表示为最小项形式,最小项范式 Canonical SOP 举例,最大项(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) 所有最大项之积为0;,(4) 将最大项对应的n位二进制(原变量为0, 非变量为1)的数值 记作其下标i, 该项记作Mi,(5) 清一色由最大项之积组成的范式称为和之积范式 (canonical product of sums)(canonical POS),最大项的性质,若一个布尔函数表示为最大项之和的形式,称为 最大项范式.每个最大项表示为一个二进制数: 原变量表示为0, 反变量表示为1.,最大项范式 Canonical POS,最大项范式,一个和项称为一个最大项:若对于每个函数变量, 该和项或者包含该变量或者包含改变量的反变量.,最大项范式举例,= M1 M3 M5 = M(1,3,5),例：将下列函数式转换成最小项范式和最大项范式。,最小项范式,最大项范式,范式 Canonical Forms 举例,最小项范式的生成,列出真值表,取出值为1的行,原始表达式F(A,B,C),F(A,B,C) = m(0,2,4),最大项范式与最小项范式的关系,最大项范式的生成,列出真值表,取出值为0的行,原始表达式F(A,B,C),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),结论：逻辑代数式F的最大项范式与最小项范式的下标“互补”。,最大项范式与最小项范式举例,两个思路：代数式法；真值表法,结论：逻辑代数式F的最大项范式与(F非)的最小项范式下标相同；同理， F的最小项范式与(F非)的最大项范式下标相同,最大项与最小项关系总结,（1）构成最小项时，1代表原变量，0代表反变量。 （2）构成最大项时，0代表原变量，1代表反变量。 （3）一个逻辑表达式的最小项范式的下标和最大项范式的下标互补。 （4）对某一个下标（任意一个），其最小项和最大项互补。,最大项范式与最小项范式,代数式法常见的扩展思路：,P168 2.20, 2.21,课堂练习：范式的推导,Applications-1,A burglar(盗窃) alarm for a bank is designed so that it senses four 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 each line:,A,B,C,D,保险箱控制开关,有锁橱柜内保险箱下的压力感应器,电子钟,橱柜的锁,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 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