清华大学数电2逻辑代数.ppt

1、1,第二章 逻辑代数基础,第一节 概述,逻辑代数的产生：,1849年英国数学家乔治.布尔(George Boole)首先提出，用来描述客观事务逻辑关系的数学方法称为布尔代数。,后来被广泛用于开关电路和数字逻辑电路的分析与设计，所以也称为开关代数或逻辑代数。,逻辑代数中用字母表示变量逻辑变量，每个逻辑变量的取值只有两种可能0和1。它们也是逻辑代数中仅有的两个常数。0和1只表示两种不同的逻辑状态，不表示数量大小。,本章重点：,用逻辑代数公式化简逻辑函数；,用卡诺图化简逻辑函数。,【题2.10】 （1） 【题2.15】（2）,(4) ,(6) ,(10) 【题2.18】 （1）,(5),(7) 【题

2、2.22】（2） ,(3) 【题2.23】（3）,(4) 。,2,第二节 逻辑代数的三种基本运算,一、三种基本运算与、或、非（反）,1.与运算,可用开关图来说明：,该图代表的逻辑关系是：决定事件的全部条件都满足时，事件才发生这就是与逻辑关系。,用1表示开关接通，1表示灯亮，可得如下真值表：,在函数式中，用. 表示与运算，记作,Y=A.B 或Y=AB,逻辑符号：,只有输入全为1时，输出才为1,它们都有集成门电路与之对应。,3,2.或运算,该图代表的逻辑关系是：决定事件的全部条件至少有一个满足时，事件就发生这就是或逻辑关系。,输入有一个为1时，输出就为1,在函数式中，用 表示或运算，记做,Y=AB

3、,逻辑符号：,真值表,4,3.非运算,该图代表的逻辑关系是：决定事件的条件满足时，事件不发生这就是非逻辑关系。,真值表,逻辑符号：,A,Y,在函数式中，用 表示，写成：,5,二、一些常用的复合逻辑运算,用两个以上基本运算构成的逻辑运算。包括与非、或非、与或非、异或和同或运算。和三个基本运算一样，它们都有集成门电路与之对应。,真值表：(除与或非运算外）,国内符号：,国外符号：,互为非逻辑关系,6,与或非逻辑,函数式形如：,Y= (AB + CD),逻辑符号：,A与B等于1，或者C与D等于1，Y等于0。,真值表：,异或的逻辑式：,同或的逻辑式：,Y=AB+AB,Y=A B + A B,7,第三节

4、逻辑代数的基本公式和常用公式,一、基本公式,关于常数之间的运算在真值表中已给出。下面的公式中都有变量：,0.A=0,1+A=1,1.A=A,0+A=A,A.A=A,A+A=A,A.B=B.A,AB=BA,交换律,A.(B.C )=(A.B).C,结合律,A(BC)=(AB)+C,A.(B+C )=A.B+AC,ABC=(AB)(A+C),分配律,摩根定理,我们用真值表证明分配律的第二个公式：,还原律,互补律,重叠律,8,其他公式的证明请同学自己完成。,ABC=(AB)(A+C),9,A + AB = A,证：左A(1+B)=A .1=A,吸收律1,吸收律2,证：左A(B+B)=A .1=A,A

5、 B+AC+BC = AB+AC,冗余项定理,推论：,=AB+AC+ABC+ABC=右,A (AB) =A B,A (AB) =A,证：,=A B+AC+B C =右,证：,左 A B+AC+BC(A+A),A B+AC+BCD = AB + AC,左(AB) ( A C),=(A+B)(A+C),摩根定理,证：左,二、若干常用公式,(A B+AC) = AB+AC,10,第四节 逻辑代数的基本定理,定理：在任何一个包含逻辑变量A的等式中，若以另外一个逻辑式代入式中所有A的位置，则等式仍然成立。,B用C.D代入，有,注：称A为原变量，A为反变量。,例如：将摩根定理 中,上式说明摩根定理可推广到

6、3个变量。当然也可推广到任意个变量。,二、反演定理,定理： 对于任意一个逻辑式Y，若将其中所有的 和交换，0和1交换， 原变量和反变量交换， 得到的结果就是Y。,一、代入定理,11,注意事项：,1.逻辑运算的优先顺序：括号，与，或, 异或。,2.多个变量上的非号的处理：可保持不变；也可用代入法处理。,例如：,已知：Y=A(B+C)+( CD),则：,或者，令E=CD 代入上式,所以：,12,三、对偶定理,对偶式的定义：,例如：,对偶定理：若两逻辑式相等，则它们的对偶式也相等。,在上面的例子中，根据分配律 Y=Z，再根据对偶定理有：,即 A+BC=(A+B)(A+C),这就从分配律的第一个公式直

7、接推出第二个公式。,从对偶定理可看出，只要一个逻辑函数式的变量数不少于两个（含反变量），它就一定存在对偶式。,定义： 对于任意一个逻辑式Y，若将其中所有的 和交换，0和1交换，得到的结果就是Y的对偶式，记做 。,很明显Y 也是 的对偶式。,Y=A(B+C) =A+BC,Z=AB+AC =(A+B)(A+C),13,第五节 逻辑函数及其表示方法,事务间的因果关系是一种逻辑关系，可用逻辑函数表示。,如：前面介绍的灯与开关间的逻辑关系。,又如举重裁判的例子：设有三个裁判，分别用A,B,C表示，其中A是主裁判。规定至少有两个裁判确认（其中必须包含主裁判）时，运动员的试举才算成功。当用Y表示举重结果时，

8、Y与A,B,C的逻辑关系可表示为：,Y=A(B+C),这就是一个逻辑函数的例子。,一、逻辑函数,又如，三变量多数表决逻辑。也是逻辑函数的例子。,二、逻辑函数的表示方法,常用的有五种：,真值表；逻辑函数式；逻辑图；卡诺图；波形图。,14,本节介绍四种，将卡诺图留在下节介绍。,1.真值表,举重裁判的真值表：,左侧是输入变量的所有取值，右侧是输出变量的值，即函数值。,当输入变量个数为n时，真值表共有2n行。,特点：,描述逻辑问题方便；,直观；,较繁琐。,2.函数式,举重裁判的函数式：Y=A(B+C),特点：,便于运算、化简；,便于画逻辑图；,不便从逻辑问题直接得到。,回22页,回24页,15,4.波

9、形图,举重裁判函数的逻辑图：,特点：,便于用电路实现。,A,Y,B,C,5.各种表示方法间的相互转换,真值表,函数式,逻辑图,黑箭头容易实现。篮箭头不能直接实现，可借助函数式实现。下面要重点介绍红箭头，即由真值表求函数式。,Y=A(B+C),见图2.5.3（举重）。,特点：,便于用仪器分析电路，如逻辑分析仪，计算机辅助分析。,波形图和真值表可直接转换。下面只研究真值表，函数式和逻辑图间的转换，,3.逻辑图,例:Y=AB+AB,逻辑式：,（2.5.2 五，1.真值表与逻辑函数式的相互转换，稍后讲 ）,16,（一）最小项,我们只介绍最小项。最大项不要求，留给同学自己看。,1.最小项的定义：,在n变

10、量逻辑函数中，若m为包含n个因子的与项，且这些变量均以原变量或反变量的形式出现一次，则称m为该组变量的最小项。,此时AB、A都不是最小项。,以三变量为例。,三、逻辑函数的两种标准形式,逻辑函数的两种标准形式分别是与或式和或与式，我们重点介绍与或式。首先，介绍最小项和最大项。,17,2.最小项的性质：,（1）对应输入变量的任何取值，都会有一个最小项，且仅有一个最小项的值为1；,（2）全体最小项之和为1；,（3）任意两个最小项之积为0；,（4）两个逻辑相邻的最小项之和可合并成一项，且消去一对因子。,定义：如两个最小项只有一个变量不相同，则称之为逻辑相邻。,例：,下面要介绍的卡诺图就是利用最小项的这

11、一性质化简逻辑函数的。,利用性质（1）可以从真值表求出逻辑函数的标准与或式。,关于最大项和逻辑函数的标准或与式留给同学自学。,ABC和 是逻辑相邻的最小项，当它们相加时，会消去变量C ：,18,（二）逻辑函数的最小项之和标准形式,操作方法：将函数值为1的行对应的最小项取出相加。,以举重裁判逻辑为例。Y=1对应m5、m6、m7三个最小项，固有：,简写成,Y(A,B,C)=m5+m6+m7,或,Y (A,B,C) =,或,将非标准形式化成标准形式：,Y=AB+AC,规律：,少1个变量，化成2个最小项之和；,少2个变量，化成4个最小项之和；,少n个变量，化成2n个最小项之和。,“逻辑函数形式的变换”

12、放到下节讲。（书上2.5,4节）,19,第六节 逻辑函数的化简方法,一、 逻辑函数式最简的标准,化简的意义：将逻辑函数化成最简形式便于在用电路实现时节省器件，而且其逻辑关系更明显。,逻辑函数式有多种形式，如与或式，或与式，与非与非式，或非或非式等等。不同的形式，可用不同的门电路实现。,AB+AC 与或式,=(AB)( AC) 与非与非式,两次取反,=A(B+C) 或与式,两次取反,与或式使用最多，因此我们只讨论与或式的最简标准：,1.包含的与项最少；,2.在满足1项的前提下，每个与项包含的变量个数最少。,或非或非式,逻辑函数形式 的变换,20,二、公式化简方法,我们通过一些例子说明如何应用这些

13、公式进行化简。,Y=ABC+AC+BC,=ABC+(A B) C,=C,Y=AB+A(C+D)B,=AB,1式,Y=AC+AD+CD,=AC+(AC) D,=AC+ D,2式,Y=AC+AD+(C+D),=AC+AD+C D,=AC+C D,3式,4式,吸收法,消因子法,并项法,消项法,Y=AB+AB+BC+BC,=AB+AB+BC +BC,+ AC,=AB+BC +AC,或,+ AC,=AB+BC +AC,本例说明最简式不一定是唯一的。,Y=AB+AB+BC+BC,常用公式,21,函数式中的任一与项都可重复使用：,=AB+BC,3式,=ABC+ABC+ABC+ABC,Y=ABC+ABC+AB

14、C,Y=(AB)C+CD) .A,=(ABC+CD) .A,=ACD,5式,Y=AC+BC+BD+CD+A(B+C)+ ABCD+ABDE,(BC),=BC+BD+A,注意：,1.当对复杂函数式取反时，应先化简该式子，然后脱掉非号。,2.要十分注意冗余项公式的应用。,常用公式,22,三. 逻辑函数的卡诺图化简法,（一）逻辑函数的卡诺图表示法,1.表示最小项的卡诺图,卡诺图是用来化简逻辑函数的。由英国工程师Karnaugh首先提出的。也称卡诺图为K图。,将真值表画成矩形表格。遵循的原则是逻辑相邻的最小项在卡诺图上对应的小方格要几何位置相邻。,几何位置相邻：1.有公共边；2.位置对称。,画法：,m

15、0,m1,m3,m2,二变量,m0,m1,m3,m2,m6,m7,m5,m4,ABC,ABC,ABC,ABC,ABC,三变量,循环码,14页,23,四变量,m0,m1,m3,m2,m6,m7,m5,m4,m12,m13,m15,m14,m10,m11,m9,m8,D,A,五变量以上的卡诺图不作要求。,卡诺图上每个变量取1和取0的方格数各占总格数的一半。所以卡诺图还有另一种标法：,B,C,2.用卡诺图表示逻辑函数,显然，只要在每个小方格里填上函数值（0或1）即可。,具体操作还要分两种情况：,第一种，已知逻辑函数的真值表；,第二种，已知逻辑函数的函数式；,24,(1).已知真值表,真值表和卡诺图有

16、一一对应关系，可直接填。如举重裁判：,我们已知道它的真值表中包含5，6，7号三个最小项，故,由于函数值只有0，1两种取值，故可将0省略。,(2).已知函数式,当已知最小项标准形式时，与1中情况相同。如Y=m5+m6+m7,当已知一般与或式时，可将其化成最小项标准形式。如：,Y=AB+AC,=AB(C+C)+AC(B+B),=ABC+ABC+ABC,也可直接将每个与项填进卡诺图：,与项AB填入A、B都等于1的方格。,即6号和7号最小项。,与项AC填入A、C都等于1的方格。,即5号和7号最小项。,1,1,1,0,0,0,0,0,1,1,1,25,少1个变量的与项，在卡诺图上占2个相邻的小方格。,这

17、说明：,我们在四变量卡诺图上作进一步研究。,1,1,1,1,与项AB少两个变量，用AB(C+C)(D+D)方法可得，它包含4个最小项，编号是12，13，14，15，它们组成一个矩形。,易证明AD所占的4个格组成正方形。,1,1,1,1,与项A少3个变量，用A(B+B)(C+C)(D+D)方法可得，它包含8个最小项，编号是8，9，10，11，12，13，14，15，它们组成一个矩形。,结论：,与项少k个变量，在卡诺图上占2k个的小方格，且组成矩形。,将这个结论反过来用于化简，就是“合并最小项的规律”。,26,（二）用卡诺图化简逻辑函数,图形法,1.合并最小项的规律,与项少k个变量，在卡诺图上占2

18、k个的小方格，且组成矩形。,将：,反过来用：,在卡诺图上合并组成矩形的2k个小方格，得到的与项少k个变量。,红框合并2个最小项，对应与项ABC少1（k）个变量。,篮（绿）框合并4个最小项，对应与项AB（AC）少2（k）个变量。,紫框合并8个最小项，对应与项A少3（k）个变量。,注意：,a.只能合并2k个小方格；,b.边上方格的相邻性。,27,1,1,1,1,1,1,图中黑框对应与项A B D。,图中篮框对应与项A D。,图中红框对应与项B D。,1,1,图中紫框对应与项 D。,2.卡诺图化简法,由于每个与项在卡诺图上对应一个函数值为1 的矩形区，因此可用一个“圈”（也称为矩形组）将其包围。,将

19、 最简的原则与画圈对比：,(1). 用最少的圈（矩形组）覆盖所有的1，1可以重复使用；,对应每个圈最大；,(2). 与项中的变量最少,对应圈最少；,因此，化简的原则是：,(1). 与项最少,(2). 每一个圈（矩形组）覆盖2k个1，且k要取最大值；,逻辑函数的最简式有几个与项，就一定对应同样多的圈。,28,综上所述，化简的步骤是：,(1).将逻辑函数化成与或式，然后画出其卡诺图；,(2).按最简原则画出必要的圈；,(3).求出每个圈对应的与项，然后相加。,举例说明：,Y=(A+B)CD+(A+B)(A+B+C+D),=ACD+BCD+AB+ABCD,卡诺图为：,1,1,1,1,1,1,1,1,

20、用三个圈覆盖：,最简与或式为：,Y=CD+AB+ABD,1可重复使用,要圈两个1,当最简式不唯一时，画圈的方法也不唯一：,29,Y=AB+AB+BC+BC,1,1,1,1,1,1,卡诺图如右;,圈黑圈，得：,Y=AB+BC+CA,圈篮圈，得：,Y=AB+BC+CA,冗余项公式在这个卡诺图上看得非常清楚。,Y(A,B,C,D)=m1+m5+m6+m7+m11+m12+m13+m15,1,1,1,1,1,1,1,1,显然，紫圈是多余的。,避免画多余圈的方法：,1.画完圈后注意检查；,2.先圈只有一种方法可圈的1。,30,举两个例子：,Y=AD+BCD+ABC +ACD+A BD,1,1,=AB+BC+BD,Y=ACD+CD+AD+AB+ABC,1,1,这种情况可通过圈0求Y来解决：,Y=AD,Y=A+D,31,第七节 具有无关项的逻辑函数及