[课件资料]第二章 逻辑代数基础

1,第二章逻辑代数基础,介绍分析数字电路逻辑功能的数学方法内容提要：逻辑代数的基本公式、常用公式和重要定理；逻辑函数及其表示方法；化简逻辑函数。,2,第二章复习要点基本概念：与、或、非、门电路、卡诺图、约束项、任意项、无关项基本方法：公式化简法、卡诺图化简法（与或式）与非与非式（与或式）或非或非式两套符号（国际、国标）,3,什么是逻辑？,请听一个故事.,什么是逻辑？,两工自烟囱出，一净一脏，谁会去洗澡呢？,事物间的因果关系,4,2.1概述,二值逻辑：用1位二进制数码的0和1表示一个事物的两种不同逻辑状态，如：是和非、真和伪、有和无、好和坏等；只有两种对立逻辑状态的逻辑关系称为二值逻辑。,逻辑代数（布尔代数）：进行逻辑运算的数学方法；英国数学家乔治.布尔首先提出；广泛用于开关电路和数字逻辑电路的分析与设计也称为开关代数或逻辑代数,逻辑变量：逻辑代数中用字母表示的变量；,5,乔治布尔GeorgeBoole，1815年11月1864年，爱尔兰数学家，哲学家。乔治布尔是一个皮匠的儿子，生于英格兰的林肯。由于家境贫寒，考虑过以牧师为业，但最终还是决定从教，而且不久就开办了自己的学校。1848年，布尔出版了TheMathematicalAnalysisofLogic。1849年。他被任命位于爱尔兰科克的皇后学院（现考克爱尔兰国立大学或UCC）的数学教授。1854年，他出版了TheLawsofThought，这是他最著名的著作。1864年，布尔死于肺炎，肺炎是他在暴风雨天气中尽管已经湿淋淋了仍坚持上课引起的。,乔治布尔,19世纪最伟大的数学家,6,2.2逻辑代数的三种基本运算：与、或、非,1.与运算,与逻辑关系：决定事件的全部条件都满足时，事件才会发生,（正）逻辑赋值/状态赋值条件：1(开关闭合)；0(开关断开)；结果：1(灯亮)；0(不亮)；,Y=AB=AB=AandB=AA(AB)=A,证明：A(AB)=A(A+B)=AA+AB=AB,解释：上式说明，当A和一个乘积项的非相乘，且A为乘积项的因子时，则A这个因子可以消去。,证明：A(AB)=A(A+B)=AA+AB=A(1+B)=A,解释：上式说明，当A和一个乘积项的非相乘，且A为乘积项的因子时，其结果就等于A。,26,应用举例式(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的位置，则等式仍然成立。,27,2.4.2反演定理,应用:求已知逻辑式的反逻辑式,Y=A(B+C)+CD,Y=(A+BC)(C+D),=AC+AD+BCC+BCD=AC+AD+BCD,优先次序：先括号、然后乘、最后加不属于单个变量上的反号应保留不变,应用举例,规则:,28,2.4.3对偶定理,例如：证明式（17）A+BC=(A+B)(A+C)A+BC的对偶式：A(B+C)(A+B)(A+C)的对偶式：AB+AC因为：A(B+C)=AB+AC所以：式（17）得证。,对偶式:将逻辑式Y中的”+”换成”，”换成”+”，0换成1，1换成0，得到Y的对偶式，记做YD,对偶定理：若两逻辑式相等，则它们的对偶式也相等。,29,1和11，2和12，3和13，4和14，5和15，6和16，7和17，8和18互为对偶式,30,2.5逻辑函数及其表示方法,举重裁判电路：设有三个裁判，分别用A,B,C表示，其中A是主裁判。规定至少有两个裁判确认（其中必须包含主裁判）时，运动员的试举才算成功。当用Y表示举重结果时，Y与A,B,C的逻辑关系可表示为：,Y=A(B+C),2.5.1逻辑函数,Y=F(A,B,C,)-若以逻辑变量为输入，运算结果为输出，则输入变量值确定以后，输出的取值也随之而定。输入/输出之间是一种函数关系。,举重裁判电路,31,2.5.2逻辑函数的表示方法,常用的有五种：真值表；逻辑函数式；逻辑图；波形图；卡诺图；硬件描述语言。,一、真值表,举重裁判的真值表：,左侧是输入变量的所有取值组合，右侧是输出变量对应数值，即逻辑函数值。,当输入变量个数为n时，真值表共有2n行。,特点：描述逻辑问题方便；直观；但较繁琐。,32,二、逻辑函数式将输入/输出之间的逻辑关系用与/或/非的运算式表示就得到逻辑式。,举重裁判的函数式：Y=A(B+C),特点：便于运算、化简；便于画逻辑图；不便从逻辑问题直接得到。,三、逻辑(电路)图用逻辑图形符号表示逻辑运算关系，与逻辑电路的实现相对应。,举重裁判函数的逻辑图：,特点：便于用电路实现。,Y=A(B+C),举重裁判电路,33,五、各种表示方法间的相互转换,四、波形图,将输入变量每一种取值与对应的输出值按时间顺序排列起来，就得到波形图。主要用于描述时序逻辑。,举重裁判电路的波形图,34,各种表示方法间的相互转换：,真值表逻辑函数式例2.5.1：奇偶判别函数的真值表A=0,B=1,C=1使ABC=1A=1,B=0,C=1使ABC=1A=1,B=1,C=0使ABC=1这三种取值的任何一种都使Y=1,所以Y=ABC+ABC+ABC,35,真值表逻辑函数式,找出真值表中使Y=1的输入变量取值组合。每组输入变量取值对应一个乘积项，其中取值为1的写入原变量，取值为0的写入反变量。将取值为1的乘积项相加，得到Y的逻辑函数式。,逻辑函数式真值表,把输入变量取值的所有组合逐一代入逻辑式中求出Y，列表，即可得到真值表,例2.5.2,真值表逻辑函数式的一般方法,36,用图形符号代替逻辑式中的逻辑运算符号。按运算优先顺序将它们连接起来,逻辑函数式逻辑图,逻辑函数式逻辑图,37,1.从输入端到输出端逐级写出每个图形符号的输出逻辑式,逻辑图逻辑函数式,逻辑图逻辑函数式,38,波形图真值表,从波形图上找出每个时间段里输入变量与函数输出的取值；将这些输入、输出取值对应列表。,真值表波形图,将真值表中所有的输入变量与对应的输出变量取值依次排列，画成以时间为横轴的波形；,39,n变量逻辑函数中的最小项m：包含n个因子m是乘积项n个变量均以原变量和反变量的形式在m中出现一次,对于n变量函数有2n个最小项,“最小项之和”及“最大项之积”,2.5.3逻辑函数的两种标准形式,40,最小项举例：,两变量A,B的最小项三变量A,B,C的最小项,输入变量的每一组取值都使一个对应的最小项的值等于1,41,三变量最小项的编号：,42,最小项的性质,在输入变量任一取值下，有且仅有一个最小项的值为1。全体最小项之和为1。任何两个最小项之积为0。两个相邻的最小项之和可以合并，消去一对因子，只留下公共因子。相邻性：只有一个因子不同的两个最小项具有相邻性，例如：,43,逻辑函数的最小项之和形式：,例：,将给定的逻辑函数式化为若干乘积项之和的形式（积之和）；再利用基本公式将每个乘积项中缺少的因子补全。,44,逻辑函数的最小项之和形式：,例2.5.6：,45,最大项：,M是n个变量之和；n个变量均以原变量和反变量的形式在M中出现一次。如：两变量A,B的最大项,对于n变量函数2n个最大项,n变量逻辑函数中的最大项M：,46,最大项的性质,在输入变量任一取值下，有且仅有一个最大项的值为0；全体最大项之积为0；任何两个最大项之和为1；只有一个变量不同的最大项的乘积等于各相同变量之和。最大项和最小项之间存在如下关系：,最大项的编号：,48,三、逻辑函数的最大项之积形式,根据反演律,得：,49,2.5.4逻辑函数形式的变换,变换为与非-与非形式：与非门,与或式：与门/或门,与或非形式：,或非-或非形式？,50,2.6逻辑函数的化简方法,化简的目的：消去多余的乘积项；消去每个乘积项中多余的因子；常用的化简方法：公式化简法；卡诺图化简法；Q-M法（适用于编制计算机辅助分析程序）；,与或式使用最多，因此我们只讨论与或式的最简标准：,与项/乘积项数量最少；每个乘积项里的因子不能再减少。,51,2.6逻辑函数的化简方法,2.6.1公式化简法,逻辑函数式有多种形式，如与或式，或与式，与非与非式等等。,AB+AC与或式=(AB)(AC)与非与非式=(A+B)(A+C)或与式=(A+B)+(A+C)或非或非式=(AB+AC)与或非式,先与门后或门用与非门实现电路先或门后与门用或非门实现电路用与或非门实现电路,52,公式化简法的原理：反复使用逻辑代数的基本公式和常用公式消去函数式中多余的乘积项和多余的因子,常用方法：,并项法：,吸收法：,消项法：,消因子法：,配项法：,灵活、交替运用上述方法！,53,化简逻辑函数，例2.6.7：,根据A+AB=A，消去ABCD,根据A+AB=A+B，消去A(BC)中的(BC)因子,根据A+AB=A，消去AC和ABDE,根据AB+AC+BC=AB+AC，消去CD,54,1924生于纽约代表成果卡诺图1952年Yale大学博士.1952-1966，工作于贝尔实验室，54年提出著名的卡诺图1966-1993年工作于IBMAdjunctProf.PolytechnicofNYuntil1995E_mail:karnaugh_m,莫里斯卡诺（MauriceKarnaugh）,55,2.6.2卡诺图化简法,一、逻辑函数的卡诺图表示法,几何相邻=逻辑相邻,实质：将逻辑函数的最小项之和以图形的方式表示出来以2n个小方块分别代表n变量的全部最小项，将它们排列成矩阵，并使在逻辑上相邻的（只有一个变量不同）最小项在几何位置上也相邻地排列起来，就得到n变量最小项的卡诺图。,56,二变量卡诺图,四变量的卡诺图,表示最小项的卡诺图,三变量的卡诺图,几何相邻=逻辑相邻,相邻的两个最小项仅有一个变量是不同的,57,五变量的卡诺图,在几何位置上，将卡诺图看成是上下、左右闭合的图形,58,将函数表示为最小项之和的形式。,用卡诺图表示逻辑函数的方法，例2.6.8,59,在卡诺图上与这些最小项对应的位置上填入1，其余的位置填入0。,用卡诺图表示逻辑函数（续）,60,原理：具有相邻性的最小项可合并，消去不同因子。在卡诺图中，最小项的相邻性可以从图形中直观地反映出来。,二、用卡诺图化简逻辑函数（卡诺图化简法或图形化简法）,合并最小项的原则：两个相邻最小项可合并为一项，消去一对因子四个排成矩形的相邻最小项可合并为一项，消去两对因子八个相邻最小项可合并为一项，消去三对因子,61,如果有2n个最小项相邻并排列成一个矩形组，则它们可以合并为一项，并消去n对因子。合并后的结果中只包含公共因子。,红框合并2个最小项，对应与项ABC,相对于最小项少1(n)个变量,蓝（绿）框合并4个最小项，对应与项AB（AC）少2(n)个变量。,紫框合并8个最小项，对应与项A少3(n)个变量。,几何相邻和逻辑相邻一致！,62,1,1,1,1,1,1,图中黑框对应与项ABD。,图中蓝框对应与项AD。,图中红框对应与项BD。,1,1,图中紫框对应与项D。,63,例2.6.10：,A,BC,卡诺图化简法的步骤,用卡诺图表示逻辑函数,64,A,BC,卡诺图化简法的步骤（续）,找出可以合并的最小项并用线圈出,例2.6.10：,A,BC,65,A,BC,卡诺图化简法的步骤（续）,选取化简后的乘积项,例：,A,BC,化简结果不唯一,66,选取的乘积项应包含函数式中所有的最小项，即覆盖图中所有的1。乘积项的数目最少，即圈成的矩形最少。每个乘积项包含的因子最少，即圈成的矩形最大。,选取乘积项的原则,67,卡诺图化简法的示例,用卡诺图化简法将下式化为最简与或逻辑式,AB,CD,合并0？,可重复使用最小项,例2.6.11：,68,2.7具有无关项的逻辑函数及其化简,2.7.1无关项,无关项：约束项和任意项的总称。,1.约束项:恒等于0的最小项,例如，用A,B,C分别表示一台电动机的正转、反转和停止的命令，A=1表示正转，B=1表示反转，C=1表示停止。则，表示正转、反转和停止工作状态的逻辑函数可写成：,000,011,101,110,111五个值不可能出现，则称ABC,ABC,ABC,ABC,ABC为约束项；在真值表和卡诺图中都用X表示。,Y1=ABC(正转)Y2=ABC(反转)Y3=ABC(停止),约束条件：,69,2.任意项:是最小项,若使其值为1时,函数值可为0也可为1,并不影响电路的功能,则称该为任意项。,令Y4表示电路自动切断供电，那么这时Y1,Y2和Y3等于1还是0已无关紧要。,000,011,101,110,111五个值出现与否对Y1,Y2和Y3没有影响，则称ABC,ABC,ABC,ABC,ABC为Y1,Y2和Y3的任意项；在真值表和卡诺图中都用X表示。,70,1.Y(ABCD)=m1+m7+m8,约束条件为:,m3+m5+m9+m10+m12+m14+m15=0,Y(ABCD)=AD+AD,2.Y=ACD+ABCD+ABCD,约束条件为:AB+AC=0,Y=AD+BD+CD,注意:被圈进去的约束项的值为1,未圈进去的约束项的值为0。,71,2.7.2无关项在化简逻辑函数中的应用,合理地利用无关项，可得更简单的化简结果。加入的无关项应与函数式中尽可能多的最小项具有逻辑相邻性。从卡诺图上直观地看，加入无关项的目的是为矩形组合最大，矩形组合数最少。,72,AB,CD,化简具有约束的逻辑函数，例2.7.1：,约束条件：,73,AB,CD,74,AB,CD,75,AB,CD,化简具有无关项的逻辑函数，例2.7.2：,76,本章小结,介绍分析数字电路逻辑功能的数学方法内容提要：逻辑代数的基本公式、常用公式和重要定理；逻辑函数及其表示方法；逻辑函数的化简方法。,77,作业：2.2（2）2.3（a）2.5（1）2.6（b)2.82.10(2)2.11(3)(5),2.