逻辑代数及其应用.ppt

《逻辑代数及其应用.ppt》由会员分享，可在线阅读，更多相关《逻辑代数及其应用.ppt（62页珍藏版）》请在三一办公上搜索。

1、第2章 逻辑代数及其应用,南京信息工程大学信息与控制学院,2.1 概述,为什么学习本章内容？,例：100人的表决会议，每人有权选择“赞同”、“反对”或者“弃权”，根据与会人员的表决情况决定议案是否通过，即最后的结果有两个，要么“通过”，要么“不通过”。主要规则如下：1）无弃权票情况下，多数人赞同则通过，否则不通过；2）有10票及以上弃权票情况下，无论如何都不通过议案；,组委会要求：设计一套复杂的表决电路，每个人面前有三个按钮分别代表“赞同”“反对”“弃权”，按下按钮后会自动发出一个最终表决通过与否的信号。,学完本章即可为该项工作奠定基础！,2023/9/16,3,2.1 概述,在数字电路中，主

2、要研究的是电路的输入输出之间的逻辑关系，因此数字电路又称逻辑电路，其研究工具是逻辑代数（布尔代数或开关代数-1849年）。,逻辑变量为进行逻辑推理，引入逻辑变量，以代表事物的两种逻辑状态；,逻辑：事物间的因果关系。,二值逻辑只有两种对立逻辑状态的逻辑关系称为二值逻辑。题目 答对、答错；考试 通过、不通过；开关 闭合、不闭合；灯 亮、不亮；,不论因还是果，都分别有两种情况，这两种“情况”就是“逻辑状态”,不再表示数量的大小，只代表两种不同的状态;,逻辑变量用字母表示，如因可以用x表示，果可以用Y表示；,不论X还是Y，取值只有0和1;,2023/9/16,4,2.2 逻辑代数的三种基本运算,与（A

3、ND）、或（OR）、非（NOT）,1）逻辑与（与运算）：假设条件（A，B）与事件Y存在因果关系，如果仅当上述条件（A，B）均满足时，事件（Y）才发生，则这种因果关系为逻辑与。,A、B都闭合，灯才亮。,以开关 闭合为条件，以 灯亮为结果,条件都满足，结果才发生。,2023/9/16,5,2）或逻辑（或运算）：当决定事件（Y）发生的各种条件(A，B，)中，只要有一个或多个条件满足，事件（Y）就发生。,只要有一个条件满足，结果就发生。,2.2 逻辑代数的三种基本运算,以开关 闭合为条件，以 灯亮为结果,只要有一个开关闭合，灯就亮。,2023/9/16,6,3）非逻辑（非运算）：条件事件A满足时，事件

4、Y不发生；条件A不满足，事件Y反而发生。,2.2 逻辑代数的三种基本运算,开关闭合，灯就不亮；,以开关 闭合为条件，以 灯亮为结果,条件满足，结果就不发生；,以A、B作为开关的状态，Y作为灯的状态，并人为约定：1）开关闭合：1；开关断开：02）灯亮：1；灯灭：0,逻辑真值表truth table,2.2 逻辑代数的三种基本运算,+,YA,+,7,与、或、非等逻辑功能可以通过电路实现，相应的电路单元分别称为：与门（and gate）、或门(or gate)和非门(not gate)。,与、或、非-基本逻辑单元，组合后可以表达任意逻辑关系。,与非、或非、异或等 简单的复合逻辑单元,2.2 逻辑代数

5、的三种基本运算,8,2023/9/16,9,(a)与非运算：逻辑表达式为：,2.2 逻辑代数的三种基本运算-几种常用复合逻辑运算,CD4011,10,(b)或非运算：逻辑表达式为：,2.2 逻辑代数的三种基本运算-几种常用复合逻辑运算,2023/9/16,11,(c)异或运算,同0，异1,2.2 逻辑代数的三种基本运算-几种常用复合逻辑运算,2023/9/16,12,(d)同或运算,AB,同1，异0,2.2 逻辑代数的三种基本运算-几种常用复合逻辑运算,2023/9/16,13,(e)与或非运算：逻辑表达式为,2.2 逻辑代数的三种基本运算-几种常用复合逻辑运算,2023/9/16,14,2.

6、3 基本公式和若干导出公式,1.基本公式,根据与、或、非的定义，得表的逻辑代数的基本公式,证明方法：真值表,2023/9/16,15,式(8a)和(8b)是著名的德摩根(De Morgan)定理，亦称反演律，在逻辑化简和变换中经常要用到这一对公式。,例：用真值表法证明公式（8a）：(A B)=A+B,同理可证明公式（8b）。,16,2.常用的导出公式,证明方法：推导 真值表,谢 谢！,17,2023/9/16,18,2.4 逻辑代数的基本定理,1）代入定理：在任意一个包含变量A的等式中，若用任何一个逻辑 式 代替等式中的A，则等式仍然成立。,应用举例：(AB)=A+B，如果将“B”换为“BC”

7、,(A(BC)=A+(BC)=A+B+C,2023/9/16,19,应用举例,2）反演定理：对于任意一个逻辑式Y，若将其中所有的“与”换成“或”，“或”换成“与”，并且将所有逻辑变量和常量取反，则得到的结果是Y。,意义：为求取已知逻辑式的反提供了方便。,步骤及注意事项：a）先括号，再乘，最后加；b)不属于单个变量上的反号应保留；,例：已知 Y=A(B+C)+CD，求Y 已知Y=(AB+C)+D)+C 求Y,Y=A(B+C)+CD,(C+D),BC,(A+BC),.,+,A,(C+D),.,Y=(AB+C)+D)+C,C,.,(?),(AB+C)+D,?,D,.,(?),(A+B)C)D,(A+

8、B)C)D)C,(A+B).C,a）先括号，再乘，最后加；b)不属于单个变量上的反号应保留；,3）对偶定理：,两逻辑式相等，则对应的对偶式也成立。,对偶式：对于任意逻辑式Y，将“.”与“+”互换，“1”与“0”互换，则得到对偶式YD。,意义：欲证明逻辑式成立，可以先证明两边的对偶式相等。-有时候相应的对偶式相等更容易证明。,证明：A+BC=(A+B)(A+C),A(B+C),AB+AC,=,2023/9/16,23,2.5 逻辑函数及其描述方法,逻辑函数：,如果以逻辑变量作为输入，以运算结果作为输出，当输入变量的取值确定之后，输出的取值便随之而定。输出与输入之间的函数关系称为逻辑函数（Logi

9、cal Function）。Y=F(A,B,C,),逻辑函数表示方法：,常用逻辑函数的表示方法有：逻辑真值表（真值表）、逻辑函数式（逻辑式或函数式）、逻辑图、波形图、卡诺图及硬件描述语言。它们之间可以相互转换。,输入变量及输出的取值都只有0、1两种状态，所以这里讨论的都是二值逻辑函数。,2023/9/16,24,2.5.1 逻辑函数的几种表示方法,例：一举重裁判电路，A为主裁判，B、C为两位副裁判。只有主裁判通过以及两位副裁判当中的一位或全部通过，举重成绩有效，否则无效。,a.真值表描述逻辑函数,2023/9/16,25,解：设A、B、C闭合用“1”表示，断开用“0”表示；Y亮用“1”表示，灯

10、灭用“0”表示。得到函数表示形式：,真值表,2023/9/16,26,2023/9/16,26,b.逻辑图描述逻辑函数,用逻辑图形符号连接起来表示逻辑函数，得到的连接图，称为逻辑图。,2023/9/16,27,2023/9/16,27,将输入变量所有可能的取值与对应的输出按时间顺序依次排列起来画成的时间波形，称为函数的波形图。,c.波形图描述逻辑函数,2023/9/16,28,2.5.2 逻辑函数描述方法之间的相互转换,a.逻辑函数式&真值表,例：给出逻辑函数的真值表，试写出它的逻辑函数式。,1)真值表逻辑式,方法：将真值表中为1的项相或。,2023/9/16,南京信息工程大学信息与控制学院_

11、钱承山,29,2023/9/16,29,逻辑式真值表,方法:将输入变量取值的所有组合状态逐一带入逻辑式求函数值,列成表即得真值表。,例：,0,1,1,1,1,1,1,0,2023/9/16,30,2023/9/16,30,b.逻辑式、逻辑图,方法:用图形符号代替逻辑式中的运算符号,并依照逻辑式中的运算优先顺序将这些图形符号连接起来就可以画出逻辑图.,1）逻辑式 逻辑图,2023/9/16,31,2023/9/16,31,2）逻辑图逻辑式,方法:从输入端到输出端逐级写出每个图形符号对应的逻辑式，即得到对应的逻辑函数式.,2023/9/16,32,c.波形图&真值表,1）真值表波形图,将ABC的取

12、值顺序按表中自上而下的顺序排列，即得到波形图。,2023/9/16,33,2)波形图真值表,0,1,1,0,0,1,0,1,2023/9/16,34,2.5.3 逻辑函数的标准形式,真值表,最小项m性质:m是乘积项；包含n个输入变量；n个输入变量都以原变量或反变量的形式在m中出现一次。,函数式,最小项：在n变量逻辑函数中，若m为包含n个因子的乘积项，而且这n个变量都以原变量或反变量的形式在m 中出现，且仅出现一次，则这个乘积项m称为该函数的一个标准乘积项，通常称为最小项。,1.最小项,2023/9/16,35,两变量A,B的最小项三变量A,B,C的最小项,最小项举例：,对于n变量函数有2n个最

13、小项,2023/9/16,36,最小项的编号：,2023/9/16,37,最小项的性质:,在输入变量任意取值下必对应一个最小项；输入变量确定后，仅有一个最小项的值为1；,任意两个最小项的乘积必为0；,全部最小项的和必为1；,2023/9/16,38,具有相邻性的两个最小项之和可以合并为一项，结果只保留公共因子。-相邻性：两个最小项之间仅有一个变量不同。,2.逻辑函数的最小项之和的形式,任何一个逻辑函数都可以表示成唯一的一组最小项之和，称为标准与或表达式，也称为最小项表达式。,1）将逻辑表达式展开成若干乘积项之和的形式；,2）利用AA1 基本公式将空缺的因子补全；,步骤：,2023/9/16,3

14、9,例,2023/9/16,40,例,2023/9/16,41,如果列出了函数的真值表，则只要将函数值为1的那些最小项相加，便是函数的最小项表达式。,谢 谢！,42,Y表示灯的状态：1 灯亮；0 灯灭；A、B、C代表三个开关的开、关状态：1 闭环；0 断开；,1）灯的 亮 与灭 与三个开关的开、关状态有关；,如何理解上式？,2）只要ABC=1，或者AC=1，Y就=1；,3）A可以等于0，也可以等于1，B和C同样，所以，ABC=1时必然意味着 A=1，B=1，且C=1，即A、B、C同时为1（三个开关同时闭合）；,4）A可以等于0，也可以等于1，C同样，所以，AC=1时必然意味着 A=0，且C=1

15、，即A=0，C=1 同时满足时即可令AC=1（开关1断开，开关3闭合）；,5）开关1、2、3同时闭合，或者开关1断开、3闭合情况下都能使灯亮；,6）只要1断开、3闭合灯就能亮，即此时灯亮与否已经与开关2的状态无关，即三个开关状态分别为 断、闭、闭时灯会亮，断、断、闭时也会亮；,与6）结论一致。,思考：为什么Y=F(A,B,C)一定可以写成最小项相加的形式？,2023/9/16,45,如果列出了函数的真值表，则只要将函数值为1的那些最小项相加，便是函数的最小项表达式。,2023/9/16,46,2.6 逻辑函数的化简方法,逻辑函数的最简形式最简与或：-逻辑函数式中乘积项最少，且每个乘积项所包含的

16、因子最少，则称为最简的与或逻辑式。,最简与或表达式,公式化简法,卡诺图化简法,2023/9/16,47,并项法：,吸收法：,A+AB=A,消项法：,消因子法：,配项法：,2.6.1 公式化简法,48,例：化简逻辑函数,解：,吸收法,2023/9/16,1）以2n个小方块分别代表 n 变量的所有最小项，并将它们排列成矩阵；,2.6.2 卡诺图化简法,具有相邻性的最小项相加可以化简为公共因子乘积的形式！,任何逻辑关系都可以写为最小项相加的形式！,写为最小项之和形式后：,n变量全部最小项的卡诺图（M.Karnaugh提出）。,2）使几何位置相邻的两个最小项在逻辑上也是相邻的（即只有一个变量不同）；,

17、任何逻辑关系都可以用卡诺图的形式表示！,2023/9/16,50,卡诺图的表示：,上下对折,左右对折均是逻辑相邻项.,2023/9/16,51,五变量的卡诺图,上下对折,左右对折均是逻辑相邻项.,2023/9/16,52,2.如何用卡诺图表示逻辑函数,(1)将函数表示为最小项之和的形式;(2)在最小项的卡诺图上与函数式中包含的最小项所对应位置上填入1，在其余的位置上填入0。,例：用卡诺图表示逻辑函数,2023/9/16,53,2.6.3 利用卡诺图化简逻辑表达式,依据：具有相邻性的最小项可合并，消去不同因子。优势：在卡诺图中，最小项的相邻性可以从图形中直观地反映 出来。,任何两个（21个）相邻

18、最小项，可以合并为一项，并消去一个变量。,合并最小项的原则,2023/9/16,54,合并最小项的原则,任何4个（22个）相邻的最小项，可以合并为一项，并消去2个变量。,2023/9/16,55,任何8个（23个）相邻最小项，可以合并为一项，并消去3个变量。,合并最小项的原则,2023/9/16,56,利用 AB+AB=A2个最小项合并，消去1个变量；4个最小项合并，消去2个变量；8个最小项合并，消去3个变量；2n个最小项合并，消去n个变量。,总结,2023/9/16,57,卡诺图化简法的步骤：,作出函数的卡诺图;画圈(将卡诺图中按矩形排列的 相邻的1圈成若干个相邻 组);写出最简与或表达式。

19、,画圈的原则,合并个数为2n；圈尽可能大，以使乘积项中含因子数最少；每个圈中至少有一个最小项仅被圈过一次，以免出现多余项。,2023/9/16,58,2.7 具有无关项的逻辑函数及其化简,2.7.1 约束项、任意项和逻辑函数式中的无关项,无 关 项,约束项：当限制某些输入变量的取值不能出现时，用它们对应的最小项恒等于0来表示。,任意项：在输入变量的某些取值下函数值是1还是0皆可，并不影响电路的功能。在这些变量的取值下，其值等于1的那些最小项称为任意项。,逻辑函数中的无关项：约束项和任意项可以写入函数式，也可不包含在函数式中，因此统称为无关项。,2023/9/16,59,合理地利用无关项，可得更简单的化简结果；加入无关项的目的是为了使矩形圈最大，矩形组合数最少,在卡诺图中用符号“”、“”或“d”表示无关项。在化简函数时即可以认为它是1，也可以认为它是0。,2023/9/16,60,2023/9/16,61,不利用无关项的化简结果为：,利用无关项的化简结果为：,2023/9/16,62,作业：题2.1(6)；题2.3；题2.5(2)；题2.7(b)；题2.8 题2.10(3),(4),(5)；题2.15(6)；题2.16(b)；题2.17(4)；题2.18(4);题2.20(a);题2.22(1);题2.23(1),