[工学]第二章逻辑代数基础.ppt

第 二 章 逻 辑 代 数 基 础,目 录,2.1 概述 2.2 逻辑代数中的三种基本运算 2.3 逻辑代数的基本公式和常用公式 2.4 逻辑代数的基本定理 2.5 逻辑函数及其表示方法 2.6 逻辑函数的化简方法 2.7 具有无关项的逻辑函数及其化简,本章重点和难点,逻辑代数的基本公式、常用公式 逻辑代数重要定理 逻辑函数及其表示方法 化简逻辑函数的方法,返回,2.1 概述,1、基本概念,逻辑：事物的因果关系,逻辑运算：当0和1表示逻辑状态时，两个二进制数码按照某种特定的因果关系进行的运算，逻辑运算使用的数学工具是逻辑代数。,逻辑代数：与普通代数不同之处是逻辑代数中的变量只有0和1两个可取值，它们分别用来表示完全两个对立的逻辑状态，在逻辑代数中，有与、或、非三种基本的逻辑运算。,逻辑运算的描述方式:逻辑代数表达式、真值表、逻辑图、卡诺图、波形图和硬件描述语言（HDL) 等。,返回,2.2 逻辑代数中的三种基本运算,与（AND）,或（OR）,非（NOT）,(a),(b),(c),图(a)中，A、B同时闭合，指示灯亮； 图(b)中，A、B任一个闭合，指示灯亮； 图(c)中，A闭合，指示灯灭，A断开，指示灯亮。,返回,以A=1表示开关A闭合，A=0表示开关A断开； 以Y=1表示灯亮，Y=0表示灯不亮； 三种电路的因果关系不同：,返回,逻辑与(逻辑相乘),特点：条件同时具备，结果发生 逻辑表达式：Y=A AND B = A&B=AB=AB,逻辑与真值表,图形符号,返回,规则：有0为0，全1为1,功能表,逻辑或(逻辑相加),特点：条件之一具备，结果发生 逻辑表达式：Y= A OR B = A+B,逻辑或真值表,图形符号,返回,规则：有1为1，全0为0,功能表,逻辑非(逻辑求反),特点：条件不具备，结果发生,逻辑表达式：Y=A=NOT A,逻辑非真值表,图形符号,返回,规则：取反,功能表,逻辑表达式：,几种常用的复合逻辑运算,1、与非,逻辑与非真值表,图形符号,规则：相同取反，不同取高,返回,2、或非,逻辑表达式：,逻辑或非真值表,图形符号,规则：相同取反，不同取低,返回,3、异或,逻辑表达式：,逻辑异或真值表,图形符号,规则：相同取低，不同取高,返回,Y= A B=AB+AB,4、同或,逻辑表达式：,逻辑同或真值表,图形符号,规则：相同取高，不同取低,返回,5、与或非,逻辑表达式：,图形符号,返回,(1) 10100011和00001111相与：,例1：求下列逻辑运算结果。,(2) 10101100和00001111相或：,00000011,10101111,(3) 10101100的非运算：,01010011,(4) 10101100和00001111异或：,10100011,(6) 10101100和00001111与非：,11110011,(5) 10101100和00001111同或：,01011100,返回,（1）写出10100101与11110000的加法运算结果以及逻辑与、逻辑或、逻辑异或和逻辑与非的结果。,思考题1,（2）写出10101010的逻辑非运算结果。,返回,2.3 逻辑代数的基本公式和常用公式,1、基本公式,返回,其中：,(1)、(2)、(11)、(12)称 “01”律，给出了变量与常量间的运算规则；,(5)、(15)称“交换”律， (6)、(16)称“结合”律， (7)、(17)称“分配”律，是和普通代数相似的定律。,(4)、(14)称“互补”律， (3)、(13)称“重叠”律， (8)、(18)称“反演”律，是特殊定律；,(9)称“还原”律， (10)是对0和1的求反运算。,返回,例2：请对公式（17）进行证明,解1：,右边=(A+B)(A+C),=A+AB+AC+BC,=A(1+B+C)+BC,=A+BC=左边,返回,公式推演法,解2：,真值表法,A+BC,(A+B)(A+C),=,返回,2、若干常用公式,返回,例3：证明A + A B = A,证明：,返回,说明：在两个乘积项相加时，若其中一项以另一项为因子，则该项是多余的，可以删去。,原变量吸收公式,例4：证明A + AB = A+B,证明：,说明：两个乘积项相加时，如果一项取反后是另一项的因子，则此因子是多余的，可以消去。,反变量吸收公式,返回,例5：证明AB + AB = A,证明：,说明：两个乘积项相加时，若它们分别包含B和B两个因子而其他因子相同，则两项定能合并，且可将B和B两个因子消去。,互反变量吸收公式,返回,例6：证明A(A+B) = A,证明：,说明：变量A和包含A的和相乘时，其结果等于A，即可以将和消掉。,返回,例7：证明AB+AC+BC=AB+AC,证明：,说明：若两个乘积项中分别包含A和A两个因子，而这两个乘积项的其余因子组成第三个乘积项时，则第三个乘积项是多余的，可以消去。,混合变量吸收公式,可以导出：AB+AC+BCD=AB+AC,返回,返回,例8：证明A(AB)=AB,证明：,说明：当A和一个乘积项的非相乘，且A为乘积项的因子时，则A这个因子可以消去。,例9：证明A(AB)=A,证明：,说明：当A和一个乘积项的非相乘，且A为乘积项的因子时，其结果就等于A。,返回,2.4 逻辑代数的基本定理,2.4.1 代入定理,在任何一个包含A的逻辑等式中，若以另外一个逻辑式代入式中A的位置，则等式依然成立。,含义：,返回,例10：用代入定理证明式（17）适用于多变量的情况。,A+BC = (A+B)(A+C),A+B(CD) = (A+B)(A+CD),= (A+B)(A+C)(A+D),解：,例11：用代入定理证明德.摩根定理也适用于多变量的情况。,解：,二变量的德.摩根定理为,(A B) = A+ B,(A+ B) = AB,将(B+C)代入等式(2)中B的位置,(1),(2),将(BC)代入等式(1)中B的位置,(A+(B+C)=A(B+C)=A B C,(A(BC)=A+(BC)=A+B+C,返回,注意：对复杂逻辑式进行运算时，需遵守与普通代数一样的运算优先顺序，即先算括号里的内容，其次算乘法，最后算加法。,2.4.2 反演定理,对于任意一个逻辑式Y，若将其中所有的：,则:得到的结果就是Y。,含义：,运算规则：,遵循“先括号，然后乘，最后加”的运算优先次序； 不属于单个变量的上的反号保留不变。,返回,运用：,为求取已知逻辑式的反逻辑式提供方便。,例12：已知Y=A(B+C)+CD，用反演定理求Y。,解：,根据反演定理可以写出,已知：,返回,德.摩根定律则是反演定理的一个特例。,n变量逻辑函数反演律：,Y=A1+A2+A3+.+An,Y= (A1+A2+A3+.+An),= A1 A2 A3An,则：,例13：若Y=(AB+C)+D)+C，用反演定理求Y。,解：,已知:,Y=(AB+C)+D)+C,根据反演定理可以写出:,Y=( A + B ) C ) D ) C,返回,2.4.3 对偶定理,含义：,若两逻辑式相等，则它们的对偶式也相等。,对于任意一个逻辑式Y，若将其中的：,得到一个新的逻辑式YD，称为Y的对偶式，或者说Y与YD互为对偶式。,如：,Y=A(B+C),Y=(AB+CD),Y=AB+(C+D),则：,YD=A+BC,YD=(A+B)(C+D),YD=(A+B)(CD),返回,运用：证明两个逻辑式相等。,例14：证明恒等式A+BC=(A+B)(A+C),解：,运用对偶定理来证明,A+BC = A (B+C) = AB+AC,(A+B) (A+C) = AB+AC,返回,证明等式的方法：,真值表法 基本公式推导法 基本定理(代入定理、反演定理、对偶定理),例15：证明A+BC=AC+AB+BC+ACD,解：,右=AC+AB+BC+ACD,=AC(1+D)+AB+BC,=AC +AB+BC,=A(C+B)+BC,=A(BC)+BC,=(A+BC)(BC)+BC),=A+BC,德.摩根定律,分配律,结合律,返回,例16：证明ABC+ABC+ABC=AB+AC,解：,左= ABC+ABC+ABC+ABC,=AB(C+C)+ABC+ABC,=AB(C+C)+AC(B+B),=AB+AC,返回,注： 在二值逻辑中，输入/输出都只有两种取值0/1。,2.5 逻辑函数及其表示方法,2.5.1 逻辑函数,若以逻辑变量为输入，运算结果为输出，则输入变量值确定以后，输出的取值也随之而定。即：输入/输出之间是一种函数关系。,含义：,Y=F (A,B,C,),返回,如：举重裁判电路。,比赛规则规定：在一名主裁判和两名副裁判中，必须有两人以上（必须包括主裁判）认定运动员的动作合格，试举才算成功。主裁判掌握着开关A，两名副裁判掌握开关B和C。运动员举起杠铃，裁判认为动作合格就合上开关，否则不合。,指示灯Y是开关A、B、C的二值逻辑函数：,Y=F(A，B，C),返回,逻辑真值表 逻辑函数式（逻辑式或函数式） 逻辑图 波形图 卡诺图 硬件描述语言,2.5.2 逻辑函数的表示方法,各种表示方法之间可以相互转换。,返回,1、逻辑真值表,将输入变量所有的取值下对应的输出值找出来，列成表格，即可得到真值表。,返回,n个变量，则为2n个组合。,如：楼道开关示意图,开关状态表,A、B: 向上1 向下-0 L : 亮-1; 灭-0,确定变量、函数，并赋值,开关: 变量 A、B 灯 : 函数 L,返回,例17：试列出之前举重裁判电路的逻辑真值表。,1 - 开关闭合,0 - 开关断开,1 - 灯亮,0 - 灯灭,返回,2、逻辑函数式,将输入/输出之间的逻辑关系用与/或/非的运算式表示就得到逻辑代数式，即逻辑函数式。,表示方法：,(1)找出真值表中使Y=1的输入变量组合；,(2)每组输入变量组合对应一个乘积项（“与”运算） 其中：1-原变量，0-反变量；,(3)将这些乘积项相加（“或运算”），则得Y。,返回,法一：由真值表写逻辑函数式,法二：直接根据电路功能的要求和与、或的逻辑定义得Y。,例18 ：用法一将下图所示真值表转换为逻辑函数式。,返回,例19：写出举重裁判电路的逻辑函数式。,法1：,Y=ABC+ABC+ABC,=ABC+ABC+ABC+ABC,=AB(C+C)+ABC+ABC,=AB(C+C)+AC(B+B),=AB+AC,=A(B+C),解：,法2：,“B、C至少有一个合上”，表示为(B+C),“同时还要求合上A”，则应写作A(B+C),所以，逻辑函数式：Y=A(B+C),返回,3、逻辑图,将逻辑函数式中各变量之间的与、或、非等逻辑关系用图形符号表示出来，就可以画出表示函数关系的逻辑图。,返回,如：,则：,4、波形图,将逻辑函数输入变量每一种可能出现的取值与对应的输出值按时间顺序排列起来画成时间波形，其中0表示低电平，1表示高电平。,如：,返回,5、各种表示方法间的相互转换,(1)真值表与逻辑函数式的相互转换,找出真值表中使Y=1的输入变量组合；,每组输入变量组合对应一个乘积项（“与”运算） 其中：1-原变量，0-反变量；,将这些乘积项相加（“或运算”），则得Y。,把输入变量取值的所有组合逐个代入逻辑式中求出函数值，列表。,返回,例20：已知一个奇偶判别函数的真值表如左下图所示，试写出它的逻辑函数式。,解：,A=0,B=1,C=1使Y=1,A=1,B=0,C=1使Y=1,A=1,B=1,C=0使Y=1,且：Y = ABC=1,且：Y = ABC=1,且：Y = ABC =1,返回,Y=ABC+ABC+ABC,所以：,例21：已知逻辑函数Y=A+BC+ABC，求它对应的真值表。,解：,将A、B、C各种取值逐一代入Y式中计算，将计算结果列表。,返回,(2) 逻辑函数式与逻辑图的相互转换,用逻辑图形符号代替逻辑函数式中的逻辑运算符号并按运算优先顺序将它们连接起来，就得到所求逻辑图。,从逻辑图的输入端到输出端逐级写出每个图形符号的输出逻辑式，可在输出端得到所求逻辑函数式。,返回,例22：已知逻辑函数为Y=(AB+BC)+ABC，画出对应的逻辑图。,对应的逻辑图为：,解：,Y=(AB+BC)+ABC,返回,例23：已知函数的逻辑图如下图所示，试求它的逻辑函数式。,逻辑图为：,解：,逻辑函数式为：,返回,(3) 波形图与真值表的相互转换,从波形图上找出每个时间段里输入变量与函数输出的取值，然后将这些输入、输出取值对应列表，就得到所求真值表。,将真值表中所有的输入变量与对应的输出变量取值依次排列画成以时间为横轴的波形，就得到所求波形图。,返回,例24：见书p34。,例25：已知A、B、C三个变量，当它们取值包含奇数个1时，输出变量Y为1，否则输出均为0，试求该逻辑函数真值表、逻辑函数式和逻辑图，并由A、B、C波形画出Y波形。,解：,(1)真值表为,返回,(2)逻辑函数式为,Y=ABC+ABC+ABC+ABC,=A(BC+BC)+A(BC+BC),返回,(3)逻辑图为,返回,(4)波形图,见书p34,2.5.3 逻辑函数的两种标准形式,两种标准形式,最小项之和,最大项之积,返回,1、最小项,(1) 含义：,在n变量逻辑函数中，m为包含n个因子的乘积项，而且这n个变量均以原变量或反变量的形式在m中出现一次，称m为该组变量的最小项。,返回,两变量A, B的最小项,三变量A,B,C的最小项,例如：,4个,8个,对于n变量函数，有2n个最小项。,所以：,同时，输入变量的每一组取值都使一个对应的最小项的值等于1。(详见下表),三变量最小项的编号表,返回,同理，4个变量的16个最小项记作m0m15。,(2) 最小项性质,对于任意一个最小项，只有一组变量取值使得它的值为1； 对于变量的任一组取值，全体最小项之和为1 ； 对于变量的任一组取值，任何两个最小项之积为0 ； 两个相邻的最小项之和可以合并，消去一对因子，只留下公共因子。,两个最小项只有一个因子不同，称这两个最小项具有相邻性。,相邻：,如：,ABC与ABC具有相邻性,所以：,返回,2、最大项,(1) 含义：,在n变量逻辑函数中，若M为n个变量之和，而且这n个变量均以原变量或反变量的形式在M中出现一次，称M为该组变量的最大项。,两变量A, B的最大项,三变量A,B,C的最大项,例如：,4个,8个,返回,对于n变量函数，有2n个最大项。,所以：,同时，输入变量的每一组取值都使一个对应的最大项的值等于0。(详见下表),三变量最大项编号表,同理，4个变量的16个最小项记作m0m15。,返回,(2) 最大项性质,在输入变量任一取值下，有且仅有一个最大项的值为0； 全体最大项之积为0； 任何两个最大项之和为1； 只有一个变量不同的最大项的乘积等于各相同变量之和。,如：,A+B+C与A+B+C两个最大项只有一个变量不同,所以：,返回,3、逻辑函数的最小项之和形式,将给定的逻辑函数式化为若干乘积项之和的形式（亦称“积之和”形式），然后利用基本公式A+A=1将每个乘积项中缺少的因子补全，这样就可以将与或的形式化为最小项之和的标准形式。,例如：,已知Y(A,B,C)=ABC+BC，求其最小项之和的形式。,则可化为：,返回,例26：已知Y=AB+BC+ABC，求其最小项之和的形式。,解：,Y=AB+BC+ABC,=AB(C+C)+BC(A+A)+ABC,=ABC+ABC+ABC+ABC+ABC,=m5+m4+m6+m2+m7,返回,例27：已知Y=ABCD+ACD+AC，求其最小项之和的形式。,解：,Y=ABCD+ACD+AC,=ABCD+ACD(B+B)+AC(B+B)(D+D),=ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD,=m9+m7+m3+m15+m14+m11+m10,返回,思考题2,已知：Y=ABCD+BCD+BC，求其展开为最小项之和的形式。,返回,4、逻辑函数的最大项之积形式,将给定的逻辑函数式化为若干多项式的或与形式（亦称“和之积”形式），然后利用基本公式AA=0将每个多项式中缺少的变量补全，这样就可以将函数式的或与的形式化为最大项之积的标准形式。,例如：,已知Y(A,B,C)=AB+AC，化为最大项之积的形式。,则可化为：,Y=AB+AC,=(AB+A)(AB+C),=(A+A)(B+A)(A+C)(B+C),=(A+B)(A+C)(B+C),返回,=(A+B+CC)(A+BB+C)(AA+B+C),=(A+B+C)(A+B+C)(A+B+C)(A+B+C)(A+B+C)(A+B+C),=(A+B+C)(A+B+C)(A+B+C) (A+B+C),=M0 M1 M4 M6,Y=(A+B)(A+C)(B+C),返回,2.5.4 逻辑函数形式的变换,任何一个逻辑函数Y都遵守公式Y+Y=1,又因为全部最小项之和恒等于1，所以不包含在Y中的那些最小项之和就是Y。,之前的内容中，可以通过运算将给定的与或形式或或与形式逻辑函数式变换为最小项之和或最大项之积的形式。,如果在实际运算中，受到器件的限制，只能用与或非或其他功能的门电路来实现逻辑函数式，就需要用到逻辑函数形式的变换。,变换要点：,返回,例：见书p38。,2.6 逻辑函数的化简法,化简方法：,公式化简法,适用于编制计算机辅助分析程序的Q-M法。,卡诺图化简法,返回,根据化简后的表达式构成的逻辑电路简单，可节省器 件，降低成本，提高工作的可靠性。,化简意义：,化简标准(最简的与或表达式),乘积项的个数最少(与门的个数少）; 每个乘积项中包含的变量数最少（与门的输入端个数少）。,化简后使电路简单，可靠性提高。,返回,2.6.1 公式化简法,反复应用逻辑代数的基本公式和常用公式，消去函数式中多余的乘积项和多余的因子。,原理：,方法：,合并项法,AB+AB=A,吸收法,消项法,配项法,其他常用公式,A+AB=A,A+AB=(A+A)(A+B)=A+B,A+A=1,A+A=A,AA=0,A+BC=(A+B)(A+C),(A+B)=AB,(AB)=A+B,返回,AB+AC=AB+AC+BC,注意：,(1)A、B、C都可以是复杂逻辑式,(2)一般将表达式转化为“与或”形式,返回,例28：写出下列逻辑函数式的化简结果。,(1) Y1=AB+(A+C)B+AC,(2) Y2=AB+BC+AB+AC,(3) Y3=AB+AC+BC+AD,(4) Y4=ABCD+ABD+BCD+ABC+BD+BC,解：,(1) Y1=AB+(A+C)B+AC,=AB+(AC)B+AC,=AB+(AC)+AC)(AC+B),=AB+AC+B,=(A+B)(B+B)+AC,=A+B+AC,=A+B,返回,解：,(2) Y2=AB+BC+AB+AC,=AB+BC+AC+AB+AC,=AB+BC+AB+AC+AC,=AB+BC+AB+A,=A+BC+AB,=(A+A)(A+B)+BC,=A+B+BC,=A+B,返回,另解：,(2) Y2=AB+BC+AB+AC,=AB+B(A+C)+AC,=AB+B(AC)+AC,=AB+(AC+B)(AC+(AC),=AB+AC+B,=(A+B)(B+B)+AC,=A+B+AC,=A(1+C)+B,=A+B,返回,解：,(3) Y3=AB+AC+BC+AD,=A(B+C)+BC+AD,=A(B+C)+BC+AD,=A(BC)+BC+AD,=A(BC)+BC+AD,=A+BC+AD,=A+D+BC,返回,解：,(4) Y4=ABCD+ABD+BCD+ABC+BD+BC,=ABC+ABD+BCD+BD+BC,=ABC+BD+BCD+BC,=B(AC+C)+B(D+CD),=B(A+C)+B(D+C),=AB+BC+BD+BC,=AB+BD+B,=AB+B,=B,返回,2.6.2 卡诺图化简法,1、逻辑函数的卡诺图表示法,实质：,将逻辑函数的最小项之和以图形的方式表示出来。,以2n个小方块分别代表n变量的所有最小项，并将它们排列成矩阵，而且使几何位置相邻的两个最小项在逻辑上也是相邻的（只有一个变量不同），就得到表示n变量全部最小项的卡诺图。,方法：,几何相邻性,逻辑相邻性,返回,二变量的卡诺图,三变量的卡诺图,四变量的卡诺图,返回,五变量的卡诺图,图形两侧标注的0和1表示使对应小方格内的最小项为1的变量取值，同时，这些0和1组成的二进制数所对应的十进制数大小也就是对应的最小项的编号。,返回,方法：逻辑函数包含有哪几个最小项，就在卡诺图相对应的方格内填1，其余各方格填0。,例如画出逻辑函数 的卡诺图,根据最小项逻辑表达式画卡诺图,。,1,0,0,0,1,返回,用卡诺图表示逻辑函数的方法：,1、将逻辑函数化为最小项表达式； 2、填写卡诺图。,例29：用卡诺图表示逻辑函数：Y=AB+ABC+AC,解：,(1) 将逻辑函数化为最小项表达式,Y=AB+ABC+AC,=AB(C+C)+ABC+AC(B+B),=ABC+ABC+ABC+ABC+ABC,(2) 填写卡诺图。,。,1,1,1,1,1,返回,0,0,0,0,0,例30：画出下式的卡诺图,解：,(1)将逻辑函数化为最小项表达式,(2)填写卡诺图,Y=(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D),Y=(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D),Y=ABCD+ABCD+ABCD+ABCD+ABCD,返回,2、用卡诺图化简逻辑函数,依据：具有相邻性的最小项可合并，消去不同因子。,在卡诺图中，最小项的相邻性可以从图形中直观地反映出来。,返回,3、若八个最小项相邻并排列成一个矩形组， 则可合并为一项并消去三个变量。,合并最小项的原则：,1、若两个最小项相邻， 则可合并为一项并消去一个变量。,2、若四个最小项相邻并排列成一个矩形组， 则可合并为一项并消去两个变量。,即：如果有2n个最小项相邻并排列成一个矩形组，则他们可以合并为一项，并消去n个变量，合并后的结果中仅包含这些最小项的公共因子。,返回,卡诺图化简法的步骤：,将函数化为最小项之和的形式； 画出表示该逻辑函数的卡诺图； 找出可以合并的最小项； 选取化简后的乘积项；,选取原则：,化简后的乘积项应包含函数式的所有最小项，即覆盖图中所有的1。,乘积项的数目最少，即圈成的矩形最少。,每个乘积项因子最少，即圈成的矩形最大。,返回,画包围圈时应遵循的原则：,包围圈内的方格数一定是2n个，且包围圈必须呈矩形。,循环相邻特性包括上下底相邻，左右边相邻和四角相邻。,同一方格可以被不同的包围圈重复包围多次，但新增的包围圈中一定要有原有包围圈未曾包围的方格。,一个包围圈的方格数要尽可能多,包围圈的数目要可能少。,返回,例31：用卡诺图化简,1,1,1,1,1,1,1,1,1,1,L=CD+BC+ABC+ACD+BCD,返回,例32：用卡诺图化简,圈0,圈1,返回,L=B+C+D,L=BCD,L=B+C+D,例33：,Y=AC+AC+BC+BC,解：,=AC(B+B)+AC(B+B)+BC(A+A)+BC(A+A),=ABC+ABC+ABC+ABC+ABC+ABC,A,BC,返回,法一：,用卡诺图化简该逻辑代数式。,A,BC,返回,法二：,结论：卡诺图化简结果并不一定具有唯一性，但应满足最简与-或标准。,返回,例34：,用卡诺图化简该逻辑代数式。,解：,先将上式化为最小项之和的形式。,Y=ABC+ABD+ACD+CD+ABC+ACD,=ABC(D+D)+ABD(C+C)+ACD(B+B)+CD(A+A)(B+B)+ABC(D+D)+ACD(B+B),=ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD,返回,AB,CD,卡诺图法一：,返回,AB,CD,卡诺图法二：,返