第3章_逻辑代数

1、第第3 3章章 逻辑代数逻辑代数 1.逻辑代数逻辑代数 数字电路是由逻辑门等单元电路构成的逻辑系统，实现输入逻辑变量与输出逻辑变量之间的某种逻辑关系。 分析和设计这种电路的数学工具是逻辑代数，它是描述客观事物逻辑关系的一种数学方法。 英国数学家乔治布尔率先提出，故亦称为布尔代数。2.学习本章目的学习本章目的 掌握掌握逻辑运算的规律和逻辑函数的简化方法。第第3 3章章 逻辑代数逻辑代数3.1 3.1 逻辑代数的基本定律逻辑代数的基本定律3.2 3.2 逻辑运算的基本规则逻辑运算的基本规则3.3 3.3 逻辑函数的代数法化简逻辑函数的代数法化简3.4 3.4 逻辑函数的卡诺图化简逻辑函数的卡诺图化

2、简3.5 3.5 具有无关项的逻辑函数化简具有无关项的逻辑函数化简3.1 逻辑代数的基本定律逻辑代数的基本定律表3.1.1 基本、复合逻辑运算和逻辑运算顺序ABY BAYAY 1与：2或：3非：BA,1.单个逻辑变量的非运算“-”，如2.逻辑与“ ”；3.异或“”、同或“ ”；4.逻辑或“+”。基本逻辑运算常用复合逻辑运算运算顺序1.与非：2.或非：3.异或：4.同或：Y=A B5.与或非BAYBAYCDABYABY ；6.使用括号“（ ）”可改变运算顺序。CDAB5.表达式的非运算“-”，如与或非 中的表达式AB+CD。3.1.1逻辑代数定理逻辑代数定理 逻辑表达式：逻辑常量及逻辑变量之间的

3、逻辑运算式称为逻逻辑常量及逻辑变量之间的逻辑运算式称为逻 辑表达式。辑表达式。 如果如果2 2 个逻辑表达式恒等，则构成逻辑恒等式。逻辑代数个逻辑表达式恒等，则构成逻辑恒等式。逻辑代数的基本定理常用恒等式表达。的基本定理常用恒等式表达。表3.1.2 逻辑代数基本定理10 01BAABBABAAA53序号名称恒等式01自等律A+0=AA1=A20-1律A+1=1A0=0重叠律A+A=AAA=A4互补律1 AA0 AA吸收律A+AB=AA(A+B)=A6交换律A+B=B+AAB=BA7结合律(A+B)+C=A+(B+C)(AB)C=A(BC)8分配律A(B+C)=AB+ACA+BC=(A+B)(A

4、+C)9反演律10非非律P10证明方法：枚举法枚举法-按基本逻辑运算（与、或、非）的定按基本逻辑运算（与、或、非）的定 义义列出真值表列出真值表进行逻辑运算。进行逻辑运算。 BAAB例3.1 证明反演律（亦称为摩根定理） 。BAAB解：解：将变量的各种取值组合分别代入等式的左边和右边进行计算，列出真值表如表3.1.3。由表可知： 。ABBABAAB表3.1.3证明AB00011011111011103.1.4 常用恒等式常用恒等式BABAAABBAA)(ABAABABABA)(CAABBCCAAB)()()(CABACBCABACAABBCDCAAB)()()(CABADCBCABA序号名称恒

5、 等 式 1吸收式1A+AB=AA（A+B）=A吸收式吸收式223合并式4配项式1配项式256AABAABAA7BAABABABAA证明常用恒等式的方法：证明常用恒等式的方法：用基本定理导出或枚举法用基本定理导出或枚举法 AABBABAAB1)(BCAACAABBCCAAB)(证明：例3.3 证明配项式： 。证明：CAABBCCAAB例3.2 证明合并式： 。ABAAB)1 ()1 (BCACABCAABBCAABCCAAB)(BAAABAA证明：例3.2-1 证明吸收式： 。BABAABABA)(1注意1：由于逻辑代数中没有逻辑减法及逻辑除法，故初等代数由于逻辑代数中没有逻辑减法及逻辑除法，

6、故初等代数中的移项规则（移加作减，移乘作除）这里不适用中的移项规则（移加作减，移乘作除）这里不适用。注意注意2: 定理和恒等式反映的是逻辑关系定理和恒等式反映的是逻辑关系, , 不是数量之间的关系。不是数量之间的关系。 3.2 3.2 逻辑运算的基本规则逻辑运算的基本规则3.2.1 代入规则代入规则1.规则：在任何一个逻辑等式中，用一个逻辑函数代替等式在任何一个逻辑等式中，用一个逻辑函数代替等式两边的某一逻辑变量后，新的等式仍然成立，这个规则称为两边的某一逻辑变量后，新的等式仍然成立，这个规则称为代入规则。代入规则。BAAB例3.4 在 中，用BC代替等式两边的B，求新等式。2.作用：将逻辑代

7、数的基本定理（表3.1.2）和常用恒等式（表3.1.4）推广到多变量的情况。CBABCAABC右边左边解：CBAABC得P7P53.2.2 反演规则反演规则1.规则：在任何一个逻辑函数在任何一个逻辑函数Y中，同时进行下述中，同时进行下述3种变换（称种变换（称为反演变换）后为反演变换）后产生的新函数就是原函数产生的新函数就是原函数Y的反函数的反函数：注意：不属于单个变量上的反号应该保留反号应该保留，并保持原表达式中变量间的运算顺序运算顺序添加括号（）。2.作用：求反函数。AAY)01 (解：解：)(DCBBAY解：解： 例3.5 已知 ， 求 )(DCBABY?Y例3.6 已知Y=A+01，求

8、。Y(1)所有的“”换成“+”， “+”换成“”；(3)所有的原变量换成反变量，反变量换成原变量。(2) 所有的“0”换成“1”，“1”换成“0”；3.2.3 对偶规则对偶规则注意：必须保持原表达式中变量间的运算顺序。1.对偶式：在一个逻辑表达式Y中，同时进行下述变换后产生的新表达式称为原式Y的对偶式Y: （1）所有的“”换成“+”， “+”换成“”；（2）所有的“0”换成“1”， “1”换成“0”, 0BAAL例如，表3.1.2和表3.1.4同一行的等式，互为对偶式。1)(BAAL3.作用：使要证明和要记忆的公式减少了一半。P72.对偶规则：任意一个恒等式两边同时作对偶变换导出仍然成立的对偶

9、恒等式。例如， A(B+C)=AB+ACA+BC=(A+B)(A+C)3.3 3.3 逻辑函数的代数法化简逻辑函数的代数法化简与或式：乘积项之和BCBAY3.3.13.3.1最简的标准最简的标准1.1.逻辑函数的逻辑函数的5 5种表达式和相互转换种表达式和相互转换21),(非最简与或式非最简与或式最简与或式BCAABCBAABBCACBAY例如：同一种类型的表达式中，形式有不同，但最简的形式形式是唯一的。例如在与或表达式中与或非式CBBA或与式：和项之积)(CBBA与非与非式BCBA或非或非式CBBA（1）乘积项的个数最少；）乘积项的个数最少；2.2.最简与或表达式的标准：最简与或表达式的标准

10、：（2）在满足（）在满足（1）的条件下，每个乘积项中变量的个数最少。）的条件下，每个乘积项中变量的个数最少。 代数法化简，亦称为公式法化简，就是用逻辑代数的定理就是用逻辑代数的定理和恒等式，对逻辑函数进行化简，求最简与或表达式。和恒等式，对逻辑函数进行化简，求最简与或表达式。3.3.2 3.3.2 代数法化简代数法化简 CDBCDAABAACDABAACDBAY)()(1. 并项法并项法利用 ，将两项合并为一项，并消去一个变量。例如：1 AA2. 吸收法吸收法BADCBABAY)(利用A+AB=A,消去AB项。 例如：CBACCBBAACCBBAACYDEABCABCDEABCY3 .消项法消

11、项法CAABBCCAAB利用 ，消去BC项。例如：4.消因法消因法BABAAA利用 ，消去因子 。例如：如果两项如果两项分别包含分别包含A和和 ，而其余的，而其余的因子因子相乘为第相乘为第3项项，则则第第3项是多余的。项是多余的。A)( BACBAC如果如果一项一项的反是另一项的的反是另一项的因子，则此因子是多余的。因子，则此因子是多余的。5. 配项法配项法ABCBCACBAYCBAACBCCBABACBCBBABAY)()(1 AAAAA利用 ， ，等公式，在原式中增加项，然后再化简。1 AA（1） 利用 ，配项化简 代数法化简逻辑函数时，必须综合使用上述技巧、逻辑代数代数法化简逻辑函数时，

12、必须综合使用上述技巧、逻辑代数定理和恒等式，才能有效地化简逻辑函数。定理和恒等式，才能有效地化简逻辑函数。)() 1()1 (BBCACBACBACBACBACBCBABCABACACBBAAAA（2） 利用 ，配项化简)()(ABCBCABCACBABCBABCBA3.4 3.4 逻辑函数的卡诺图化简逻辑函数的卡诺图化简3.4.1 逻辑函数标准表达式逻辑函数标准表达式化简的理论基础：化简的理论基础：标准表达式、最小项和最大项1.标准与或式标准与或式 每个乘积项都包含函数的每个乘积项都包含函数的全部变量全部变量的特殊与或式称为的特殊与或式称为标准与或表达式。标准与或表达式。BCACBAY),(

13、BCACBACBACABABC一般与或式BCAACCBBA)()(标准与或式最小项：最小项：标准与或式中每一个乘积项都包含函数标准与或式中每一个乘积项都包含函数Y Y的全部变量，的全部变量，每个变量以原每个变量以原变量或反变量因子仅出现一次。变量或反变量因子仅出现一次。 最小项最小项代数法可以化简任意的逻辑函数，但是否达到最简却较难判断。卡诺图法可以直观、简便地得到最简逻辑表达式 标准式：标准与或式，标准或与式。 把原变量用把原变量用1 1替代，反变量用替代，反变量用0 0替代，按一定的变量排列顺替代，按一定的变量排列顺序构成的序构成的二进制数二进制数就是最小项的就是最小项的编号编号，通常转换

14、为十进制数。，通常转换为十进制数。最小项的编号方法：最小项的编号方法：n个变量的逻辑函数有个变量的逻辑函数有2n个最小项。个最小项。常用常用mi 或或m( i )表示，表示，i是最小项的编号。是最小项的编号。CBA（101)2 =(5)10，记作m5或m(5)。ABCCABCBACBABCACBACBACBA,如如3变量的最小项变量的最小项 2n 238CBAm 0CBAm 2CABm 6ABCm 7表3.4.1 三变量全部最小项的真值表Y(A,B,C)=A+BCABCY=A+BC000100000000001010000000010001000000011000100001100000010

15、001101000001001110000000101111000000011CBAm 5CBAm 4BCAm 3CBAm 1下P26P22最小项的性质最小项的性质：对于任意一个最小项，只有一组变量取值使其为对于任意一个最小项，只有一组变量取值使其为1，其它组取值使其为，其它组取值使其为 0。 为为1 的取值组合是最小项的编号。的取值组合是最小项的编号。12 , 2 , 1 , 0, 0njijimm不同的两个最小项之积恒为不同的两个最小项之积恒为0，即，即全部最小项之和恒为全部最小项之和恒为1，即，即1120iimn逻辑相邻逻辑相邻:仅有一个变量不同的2个最小项称为逻辑相邻最小项，简称相邻项

16、。例如，3变量最小项ABC的相邻项是 、 和 。BCACBACAB两相邻最小项之和等于它们的相同变量之积。ABCABABCACCBAABCn个变量的最小项有个变量的最小项有n个相邻项，且两相邻最小项之个相邻项，且两相邻最小项之和等于它们的相同变量之积。和等于它们的相同变量之积。最小项一般表达式：最小项一般表达式： 3变量表达式： (由表3.4.1的最后一列得）120765432103)(11111000),(iiimmYmmmmmmmmBCACBAYn变量表达式：使mi=1的变量取值组合对应的函数值iiimmYCBAYn120)(),(最小项最小项 反函数表达式：iiimmYCBAYn120)

17、(),(即任意反函数的标准与或式是函数值为0所对应的最小项之和。（3.4.3）P192.标准或与式标准或与式 一般地，n个变量的逻辑函数有2n个最大项。例如，3变量的逻辑函数有23个最大项， 每个和项和项都包含函数的全部变量（以原或反变量出现）的或与式称为标准或与表达式。2)(1)(),(或与式或与式与或式CBBACCBACABABCACBAY 这种包含函数的全部变量的和项叫做最大项最大项，常用Mi或M(i)表示，i是最大项的编号。)(),(),(),()(),(),(),(CBACBACBACBACBACBACBACBA标准或与式)()(),(CBACBACBACBAY最大项的编号方法： 原

18、变量用原变量用0 0替换，反变量用替换，反变量用1 1替换替换，按一定变量排列顺序，按一定变量排列顺序构成的构成的2 2进制数就是最大项的编号，通常转换为十进制数。进制数就是最大项的编号，通常转换为十进制数。例如: (101)2=(5)10，记作M5或M(5)。相同编号的最大项和最小项互补，相同编号的最大项和最小项互补， 即即12, 2 , 1 , 0niiimM最大项的性质：对于任意一个最大项，只有变量的一组取值使其为0，其他组取值使其为1。使最大项为1的取值组合的二进制数值是最大项的编号。 )(CBA55,mCBACBACBAM例如全部最大项之积恒为0，即01120120nniiiiMmB

19、ACBACBA)( n个变量的最大项有n个相邻项，且两相邻最大项之积等于它们的相同变量之和。 两相邻最大项之积等于它们的相同变量之和。例如， CBACBACBA 例如，3变量最大项A+B+C的相邻项是：逻辑相邻：仅有一个变量不同的2个最大项称为逻辑相邻最大项，简称为相邻项。不同的两个最大项之和为1，即12 , 2 , 1 , 0, 10njijijiMMmm最大项一般表达式： )()(),(),(120120iiiiiimmYmmYCBAYCBAYnn)(),(120iiiMmYCBAYn即任意逻辑函数的标准或与式是函数值为即任意逻辑函数的标准或与式是函数值为0 0所对应的所对应的最大项之积。

20、最大项之积。 例如，在表3.4.1中的最后一列，)()(),(210CBACBACBAMMMBCACBAY。与式（3.4.4）相同P19iiimmYCBAYn120)(),(3实际问题的逻辑函数表3.4.2楼梯间照明电路真值表ABY001010100111所以，最小项表达式220V50Hz12ABY图3.4.1楼梯间照明电路12解：解：（1）列真值表）列真值表 设灯亮Y=1，灯灭Y=0； A或B=1表示拨向1位；A或B=0表示2位。ABBABABAmmYBAYiii1001)(),(1202BAABY=1对应的最小项是 、 ；Y=0对应的最小项是 、 。BABA)3 , 0(mABBA（2）写

21、最小项表达式）写最小项表达式例3.7 一楼梯间照明电路如下图所示。双控开关A和B一个装在楼上，一个装在楼下。楼下时开灯，上楼后则可关灯，反之亦然。)()2 , 1 ()2 , 1 ()2 , 1 ()3 , 0(),(BABAMmmmBAY（3） 写最大项表达式写最大项表达式由实际逻辑问题导出逻辑函数的方法是：（1）根据命题导出真值表；（2）由真值表导出标准表达式；（3）化简。（2）标准或与式（最大项表达式）是函数值为0所对应的最大项之积。由真值表导出标准表达式的方法是（1）标准与或式（最小项表达式）是函数值为1所对应的最小项之和。（4）画逻辑图。3.4.2 逻辑函数的卡诺图逻辑函数的卡诺图1

22、卡诺图的形成卡诺图的形成A0001111001图3.4.2 3变量卡诺图00011110000111100m1m3m2m4m5m7m6m12m13m15m14m8m9m11m10m0m1m3m2m4m5m7m6m图3.4.4变量卡诺图 边相邻（具有公共边）；或对称相邻。2个最小项的几何相邻循环码每个格代表每个格代表一个最小项一个最小项边相邻对称相邻对称相邻BCCDAB卡诺图就是用平面上相邻的方格表示函数的卡诺图就是用平面上相邻的方格表示函数的每一个最小项。几何上相邻的方格所代表的每一个最小项。几何上相邻的方格所代表的最小项在逻辑上也相邻。最小项在逻辑上也相邻。几何相邻的最小项是逻辑相邻的 ！0

23、m1m3m2m6m7m5m4m8m9m11m10m14m15m13m12m24m25m27m26m30m31m29m28m16m17m19m18m22m23m21m20m00000101101011011110110000011110CDAB图3.4.变量卡诺图2 逻辑函数的卡诺图逻辑函数的卡诺图 首先将逻辑函数转换为最小项表达式，然后，在卡诺图上函数包含的最小项所对应的小方格填入，在其他小方格填入。（也可不填写）。CABCDBDCBAY),(解：解：CABCDBDCBAY),(0001111000011110（1）由逻辑表达式画卡诺图ABCD1DCABDCABCDBACDBA1312113m

24、mmm111方法一：转换为最小项表达式例3.8 用卡诺图表示逻辑函数 任何确定的逻辑函数都可以表示为唯一的标准与或式。因此，可以用卡诺图表示逻辑函数。 方法二：方法二：由表达式直接填入由表达式直接填入CBACBAY),(1 ：例 ABC 00 01 11 10 0 1 1 1 1 1 1ABCBCABCBAY),(2：例 ABC 00 01 11 10 0 11BCAB11（2）由真值表画卡诺图ABCY00000010010001111000101111011111 在卡诺图中，使逻辑函数值为的最小项填入；使逻辑在卡诺图中，使逻辑函数值为的最小项填入；使逻辑函数值为的最小项填入，为了直观和简洁

25、，通常不填写。函数值为的最小项填入，为了直观和简洁，通常不填写。例3.4. 已知逻辑函数Y的真值表3.4.2 ，画出Y的卡诺图。解：解：a.由真值表可直接填入卡诺图7653),(mmmmABCCABCBABCACBAY表3.4.200011110011BCA111b.由真值表写标准表达式，填入卡诺图3.4.3逻辑函数的卡诺图化简逻辑函数的卡诺图化简1化简的依据化简的依据00011110000111100m1m3m2m4m5m7m6m12m13m15m14m8m9m11m10m图3.4.4变量卡诺图CDAB例：例： CBACBADDCBADCBADCBAmm1)(54CBCBADDADADACB

26、DCABDCABDCBADCBAmmmm1)(1312541 AAAA, 凡几何相邻的方格，对应的最小项逻辑上也相邻。而逻辑相邻的最小项求和时，可反复应用 的关系进行最小项合并，消去最小项中不同的变量（ ），保留公共变量（公因子）。公因子是卡诺图上最小项具有相同行列编码的变量之积。BBACDDACDCADCACDADCADCADCABABCDDABCDCABDCABBCDADBCADCBADCBAmmmmmmmm1)(151413127654相邻的相邻的2 2个方格合并，个方格合并，消去一个变量；消去一个变量；相邻的相邻的4 4个方格合并，个方格合并，消去消去2 2个变量；个变量；相邻的相邻的

27、8 8个方格合并，个方格合并，消去消去3 3个变量个变量。推广到一般情况： 两-两相邻的2n个方格合并，消去不同的n个变量，保留公共变量。 因为2n个方格合并时，提出公共变量（公因子）后，恰是余下的n个变量的全部最小项之和，其值恒为1。 公共变量是卡诺图上2n个最小项具有相同行列编码的变量之积。2化简的步骤化简的步骤(1)(1)画出逻辑函数的卡诺图（画出逻辑函数的卡诺图（2 2n n个方格）个方格）(2)(2)画卡诺圈画卡诺圈卡诺圈越少越好（因一个卡诺圈代表一个与项）；卡诺圈越少越好（因一个卡诺圈代表一个与项）；卡诺圈内值为卡诺圈内值为1 1的方格越多越好（因圈越大消去的变的方格越多越好（因圈

28、越大消去的变量越多，与项包含的变量越少量越多，与项包含的变量越少）。）。卡诺圈可以交迭，但每个卡诺圈必须至少有与其它卡诺圈可以交迭，但每个卡诺圈必须至少有与其它卡诺圈不同的、值为卡诺圈不同的、值为1 1的方格。的方格。(3)(3)求每个卡诺圈的公共变量之积（与项）并相加，得到最简求每个卡诺圈的公共变量之积（与项）并相加，得到最简的与或表达式。的与或表达式。卡诺圈：卡诺圈：把把2 2n n个值为个值为1 1的逻辑相邻的方格画成一个圈，的逻辑相邻的方格画成一个圈， 表示最小向求逻辑和。表示最小向求逻辑和。例3.10 化简函数(A,B,C,D)=m(0,1,2,5,6,7,14,15)。解：解：在画

29、卡诺圈时，注意到卡诺图的对称相邻特性，可以想象将两边粘连，上下粘连。000111100011101111111110CDAB000111100011101111111110CDAB（ a ）（ b ）因图（a）的卡诺圈比图（b）的多，所以图(b)是正确的卡诺圈。由图（b）,函数Y的最简与或式为DBADCABCYBCDCADBA解：例例3.113.11已知逻辑函数Y(A,B,C,D)=m(0,1,2,8,9,10,11,13,15)，求函数Y的最简与或式；反函数的最简与或式；函数Y的最简或与式。CD0001111000111011111101111ABCD00011110001110111111

30、01111ABY的最简与或式；DBCBADYADDBCB反函数的最简与或式；CDADBBAYDBBACDAY的最简或与式。)()(DCADBBACDADBBAYY对反函数 求反，可获得函数Y的最简或与式Y3.3.反函数的最简与或式再取反可反函数的最简与或式再取反可求函数求函数Y Y的最简或与式。的最简或与式。结论： 1.1.圈圈1 1可求函数的最简与或式。可求函数的最简与或式。2.2.圈圈0 0可求反函数的最简与或式。可求反函数的最简与或式。3.5 具有无关项的逻辑函数化简3.5.1 无关项概念对应于函数不确定的最小项称为无关项。对应于函数不确定的最小项称为无关项。约束项约束项和和任意项任意项

31、例如：用二变量例如：用二变量ABAB控制一台电梯；控制一台电梯； AB=00AB=00电梯停；电梯停；AB=01AB=01电梯下电梯下降；降； AB=10AB=10电梯上升。而电梯上升。而AB=11AB=11是不允许的取值组合，因为任是不允许的取值组合，因为任何时刻一台电梯不能同时上行和下行。这个逻辑问题的约束何时刻一台电梯不能同时上行和下行。这个逻辑问题的约束方程为方程为AB=0AB=0，即允许的取值组合满足约束方程，而不允许的，即允许的取值组合满足约束方程，而不允许的1.约束项约束项在在n n个变量的逻辑函数中，如果对变量的每个取值组合（共个变量的逻辑函数中，如果对变量的每个取值组合（共有

32、有2 2n n个取值组合），函数均有确定的值（个取值组合），函数均有确定的值（0 0或或1 1）与之对应，则）与之对应，则称这样的函数为称这样的函数为确定的逻辑函数确定的逻辑函数，否则，称为，否则，称为不完全确定的逻不完全确定的逻辑函数或具有无关项的逻辑函数。辑函数或具有无关项的逻辑函数。对某些逻辑问题，自变量的一些特定取值组合是不允许出现对某些逻辑问题，自变量的一些特定取值组合是不允许出现的，函数的取值无定义，它可能是的，函数的取值无定义，它可能是0 0，也可能是，也可能是1 1。对应于这些特。对应于这些特定的取值组合，值为定的取值组合，值为1 1的最小项称为约束项。的最小项称为约束项。 无

33、关项在真值表和卡诺图中用无关项在真值表和卡诺图中用 “ “ ” ” 或或“d”d”表示。表示。2. 任意项任意项例如，将例如，将8421BCD8421BCD码转换为余码转换为余3 3码，其真值表为表码，其真值表为表3.4.33.4.3。对某些逻辑问题，对应于自变量的一些特定取值组合，函对某些逻辑问题，对应于自变量的一些特定取值组合，函数的取值无关紧要，对逻辑功能没有任何影响。对应这些特定数的取值无关紧要，对逻辑功能没有任何影响。对应这些特定取值组合，值为取值组合，值为1 1的最小项称为任意项。的最小项称为任意项。 取值组合则不满足约束方程。最小项取值组合则不满足约束方程。最小项m m3 3 (=AB) (=AB)就是约束项。就是约束项。 当当10101010、11111111出现时，并不影响出现时，并不影响8421BCD8421BCD