《【教学课件】第二章逻辑代数基础.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章逻辑代数基础.ppt（44页珍藏版）》请在三一办公上搜索。
1、第二章 逻辑代数基础,2.1 概述,逻辑代数的产生：,1849年英国数学家乔治.布尔(George Boole)首先提出，用来描述客观事物逻辑关系的数学方法称为布尔代数。,后来被广泛用于开关电路和数字逻辑电路的分析与设计，所以也称为开关代数或逻辑代数，处理二值逻辑问题。,逻辑代数中用字母表示变量逻辑变量，每个逻辑变量的取值只有两种可能0和1。它们也是逻辑代数中仅有的两个常数。0和1只表示两种不同的逻辑状态，不表示数量大小。,本章重点：逻辑关系的数学表示方式；逻辑运算规则；用公式和卡诺图化简逻辑函数。,2.2 逻辑代数的三种基本运算,三种基本运算是：与、或、非（反）,1.与运算,该图代表的与逻辑
2、关系是：决定事件的全部条件都满足时，事件才会发生,逻辑赋值/状态赋值用1表示开关接通用1表示灯亮可得如下真值表：,Y=AB=AB=A and B=A&B,2.或运算,该图代表的或逻辑关系是：决定事件的全部条件只要有一个满足时，事件就会发生,Y=A+B=A or B,3.非逻辑,该图代表的非逻辑关系是：决定事件的条件满足时，事件反而不发生,A,A+B,AB,与 Y=A B 或 Y=A+B非,逻辑关系与集合概念的对应,4.一些常用的复合逻辑运算,用两个以上基本运算构成的逻辑运算。包括与非、或非、与或非、异或和同或运算。,与或非逻辑:,异或逻辑:,同或逻辑:,2.3 逻辑代数的基本公式和常用公式,2
3、.3.1 基本公式,返 回,公式（17）分配律证明（真值表法）,A+B C=(A+B)(A+C),2.3.2 若干常用公式,应用举例：式（17）A+BC=(A+B)(A+C)A+B(CD)=(A+B)(A+CD)=(A+B)(A+C)(A+D),2.4 逻辑代数的基本定理,2.4.1 代入定理,定理：在任何一个包含逻辑变量A的等式中，若以另外一个逻辑式代入式中所有A的位置，则等式仍然成立。,2.4.2 反演定理,应用:或去掉多个变量上的非号,要求运算前后对应变量运算顺序一致！否则，错！,+，10，AA,2.4.3 对偶定理,对偶式的定义：,例如：A(B+C)=AB+AC A+BC=(A+B)(
4、A+C),例如：,定义：对于任意一个逻辑式Y，若将其中所有的”+”和”交换，0和1交换，得到的结果就是Y的对偶式，记做YD，它们互为对偶式。,对偶定理：若两逻辑式相等，则它们的对偶式也相等。,这就从分配律的第一个公式直接推出第二个公式。,从对偶定理可看出，只要一个逻辑函数式的变量数不少于两个（含反变量），它就一定存在对偶式。,要求运算前后对应变量运算顺序一致！否则，错！,2.5 逻辑函数及其表示方法,事物间的因果关系是一种逻辑关系，也是函数关系，所以称为逻辑函数，具体说是二值逻辑函数。,如举重裁判的例子：设有三个裁判，分别用A,B,C表示，其中A是主裁判。规定至少有两个裁判确认（其中必须包含主
5、裁判）时，运动员的试举才算成功。当用Y表示举重结果时，Y与A,B,C的逻辑关系可表示为：,Y=A(B+C),2.5.1 逻辑函数,2.5.2 逻辑函数的表示方法,常用的有五种：真值表；逻辑函数式；逻辑图；波形图;卡诺图。,一、真值表,举重裁判的真值表：,左侧是输入变量的所有取值组合，右侧是输出变量对应数值是逻辑函数值。,当输入变量个数为n时，真值表共有2n行。,特点：描述逻辑问题方便；直观；但较繁琐。,二、函数式,举重裁判的函数式：Y=A(B+C),特点：便于运算、化简；便于画逻辑图；不便从逻辑问题直接得到。,三、逻辑(电路)图,举重裁判函数的逻辑图：,特点：便于用电路实现。,五、各种表示方法
6、间的相互转换,Y=A(B+C),四、波形图将输入变量所有取值可能与对应输出按时间顺序排列起来画成时间波形。主要用于描述时序逻辑,在黑板上练习,一、最小项和最大项,1.最小项,此时AB、A都不是最小项,m:min-term,2.5.3 逻辑函数式的两种标准形式,逻辑函数式的两种标准形式分别是标准与或式（乘项之和、SOP-Sum Of Product）和标准或与式（和项之积、POS-Product Of Sum），我们重点介绍标准与或式及相关的最小项。,2.最小项的性质：,（1）对应输入变量的任何取值，都会有一个最小项，且仅有一个 最小项的值为1；,（2）全体最小项之和为1；,（3）任意两个最小项
7、之积为0；,（4）两个逻辑相邻的最小项之和可合并成一项，且消去一对因子.,两个与项（包括最小项）只有一个变量不相同，则称为逻辑相邻。,例：ABC和ABC是逻辑相邻的最小项，相加时，会消去变量C 即,ABC+ABC=AB,下面要介绍的卡诺图就是利用最小项的这一性质化简逻辑函数的。,标准与或式指最小项之和的表示形式。真值表求出逻辑函数的标准与或式。,ABC.ABC=0,以举重裁判逻辑为例。Y=1对应m5、m6、m7三个最小项，故有：,Y=ABC+ABC+ABC,简写成,Y=m5+m6+m7,或,将非标准形式化成标准形式规律：,Y=AB+AC,=AB(C+C)+AC(B+B),=ABC+ABC+AB
8、C,少1个变量，化成2个最小项之和；,少2个变量，化成4个最小项之和；,少n个变量，化成2n个最小项之和。,二、逻辑函数的最小项之和标准形式,标准与或式指最小项之和的表示形式。,3.最大项,三、逻辑函数的最大项之积标准形式,根据反演定理,得,2.6 逻辑函数的化简方法,2.6.1 公式化简法,逻辑函数式有多种形式，如与或式，或与式，与非与非式等等。,与或式使用最多，因此我们只讨论与或式的最简标准：,与项/乘积项数量最少；在满足1项的前提下，每个与项包含的变量个数最少。,AB+AC 与或式=(AB)(AC)与非与非式=(A+C)(A+B)或与式=(A+C)(A+B)或非或非式=(AB+AC)与或
9、非式,先与门后或门用与非门实现电路先或门后与门用或非门实现电路用与或非门实现电路,常用公式,3.Y=ABC+AC+B C,=ABC+(AB)C,=C,1.Y=AB+A(C+D)B,=AB,2.Y=AC+AD+CD,=AC+(AC)D,=AC+D,4.Y=AC+AD+(C+D),=AC+AD+CD,=AC+CD,5.Y=AB+AB+BC+BC,=AB+AB+BC+BC,+AC,=AB+BC+AC,或Y=AB+AB+BC+BC,+AC,=AB+BC+AC,化简结果不一定是唯一的！,1.A+AB=A+B,2.AB+AC+BC=AB+AC,常用公式,函数式中的任一与项都可重复使用，AAA,=AB+BC
10、,=ABC+ABC+ABC+ABC,1.Y=ABC+ABC+ABC,2.Y=(AB)C+CD)A,=(ABC+ABD+CD).A,=ACD,Y=AC+BC+BD+CD+A(B+C)+ABCD+ABDE,(BC),=BC+BD+A,当有长非号时，一般先化简非号下的式子，然后脱掉非号；但有时可先化去非号，再化简；应灵活运用。,3.,1.A+AB=A+B,2.A B+AC+BC=AB+AC,2.6.2 逻辑函数的卡诺图化简法,一、逻辑函数的卡诺图表示法,1.表示最小项的卡诺图,卡诺图是用来化简逻辑函数的。由英国工程师Karnaugh首先提出的，也称卡诺图为K图。,m0,m1,m3,m2,m6,m7,
11、m5,m4,ABC,ABC,ABC,ABC,ABC,三变量卡诺图,四变量卡诺图,D,A,ABCD,ABCD,ABCD,ABCD,五变量以上的卡诺图不作要求。,卡诺图上每个变量取1和取0的方格数各占总格数的一半。所以卡诺图还有另一种标法：,B,C,2.用卡诺图表示逻辑函数,显然，只要在每个小方格里填上函数值（0或1）即可。,具体操作还要分两种情况：,第一种，已知逻辑函数的真值表；,第二种，已知逻辑函数的函数式；,(1)已知真值表,真值表和卡诺图有一一对应关系，可直接填。如举重裁判：,我们已知道它的真值表中包含5，6，7号三个最小项，故,由于函数值只有0，1两种取值，故可将0省略。,0,0,0,0
12、,0,1,1,1,1)当已知最小项标准形式时，与1中情况相同。如:Y=m5+m6+m7,2)当已知一般与或式时，可将其化成最小项标准形式。如：,Y=AB+AC=AB(C+C)+AC(B+B)=ABC+ABC+ABC+ABC,=ABC+ABC+ABC,也可直接将每个与项填进卡诺图：,与项AB填入A、B都等于1的方格,即6号和7号最小项。,少1个变量的与项，在卡诺图上占2个相邻的小方格。,(2)已知函数式,我们在四变量卡诺图上作进一步研究。,1,1,1,1,与项AB少两个变量，用AB(C+C)(D+D)方法可得，它包含4个最小项，编号是12，13，14，15，它们组成一个矩形。,与项A少3个变量，
13、用A(B+B)(C+C)(D+D)方法可得，它包含8个最小项，编号是8，9，10，11，12，13，14，15，它们组成一个矩形。,结论:与项少n个变量，在卡诺图上占2n个的小方格，且组成矩形！,2.6.2 二、用卡诺图化简逻辑函数图形法化简,1.合并最小项的规律,与项少n个变量，在卡诺图上占2n个的小方格，且组成矩形。,反过来用：,卡诺图上合并组成矩形的2n或N个小方格，得到的与项少n个变量。,红框合并2个最小项，对应与项ABC,相对于最小项少1(n)个变量,篮（绿）框合并4个最小项，对应与项AB（AC）少2(n)个变量。,紫框合并8个最小项，对应与项A少3(n)个变量。,几何相邻和逻辑相邻
14、一致！,1,1,1,1,1,1,图中黑框对应与项ABD。,图中篮框对应与项AD。,图中红框对应与项BD。,1,1,图中紫框对应与项 D。,2.卡诺图化简的步骤,(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,最简与或式为：,Y=CD+AB+ABD,1可重复使用,要圈两个1,圈黑圈，得：Y=AB+BC+AC,圈篮圈，得：Y=AB+BC+AC,2.Y(A,B,C,D)=m1+m5+m6+m7+m11+
15、m12+m13+m15,显然，紫圈是多余的，所以，画完圈后注意检查。,当最简式不唯一时，画圈的方案也不唯一.,1.Y=AB+AB+BC+BC,两个例子：,Y=AD+BCD+ABC+ACD+ABD,=AB+BC+BD,Y=ACD+CD+AD+AB+ABC,这种情况可通过圈0求Y来解决：,Y=AD,Y=A+D,2.7 具有无关项的逻辑函数及其化简,2.7.1 无关项,无关项是约束项和任意项的总称。,1.约束项:取值组合不可能出现的最小项,例如，四舍五入函数:用A,B,C,D组成四位二进制数表示1位十进制数,当该数大于4时输出为1,1010 1111六个值不可能出现；即m10m15是约束项；在真值表
16、和卡诺图中都用X表示。,在函数式中约束项的表示方法：,m10+m11+m12+m13+m14+m15=0,d:dont cares,四舍五入函数表示为:,约束条件AB+AC=0,或,2.任意项:是最小项,若使其值为1时,函数值可为0也可为1,并不影响电路的功能,则称该为任意项。任意项很少遇到,这里不作讨论。,2.7.2 约束项在化简中的应用,举两个例子：,！注意：有约束项时，一定要用卡诺图化简。不要用公式法，除非变量太多，无法用卡诺图化简。,Y(ABCD)=m1+m7+m8,约束条件为:,m3+m5+m9+m10+m12+m14+m15=0,Y(ABCD)=AD+AD,Y=ACD+ABCD+A
17、BCD,约束条件为:AB+AC=0,Y=AD+BD+CD,注意:被圈进去的约束项的值为1,未圈进去的约束项的值为0。,习题解答,题2.10求最小项之和,(1)Y=ABC+AC+BC=ABC+ABC+ABC+ABC,题2.12用与非门组成逻辑图(4)Y=A(BC)+(AB)+AB+BC),题2.15化简,(4)Y=ABCD+ABD+ACD=AD(BC+B+C)=AD,(6)Y=AC(CD+AB)+BC(B+AD)+CE)=BC(B+AD)(C+E),=ABCDE,(10)Y=AC+ACD+ABEF+B(D E)+BCDE+BCDE+ABEF,=AC+AD+AEF+B(D E)+BC(D E),=
18、AC+AD+AEF+BDE+BDE,(2)Y=ABC+A+B+C=ABC+(ABC)=1,题2.18用卡诺图化简,(1)Y=ABC+ABD+CD+ABC+ACD+ACD,=(AD)=A+D,(5)Y=ABC+AB+AD+C+BD,=(BCD)=B+C+D,(7)Y(A,B,C,D)=(m0,m1,m2,m5,m8,m9,m10,m12,m14),=AD+BD+BC+ACD,题2.18用卡诺图化简,题2.22化简为最简与或式,(3)Y=CD(A B)+ABC+ACD约束条件:AB+CD=0,AB,CD,1,1,1,1,(2)Y=(A+C+D)+ABCD+ABCD约束条件:d(10,11,12,13,14,15),=AD+ACD+ABD=AD+ACD+BCD=AD+BCD+ABD答案不唯一,=B+AD+AC,Y=1所有最小项之和恒等于“1”,补充：,
