《数字电子技术基础》第3章 逻辑代数

1、第第3 3章章 逻辑代数逻辑代数3.1 3.1 逻辑代数的基本定律逻辑代数的基本定律3.2 3.2 逻辑运算的基本规则逻辑运算的基本规则3.3 3.3 逻辑函数的代数法化简逻辑函数的代数法化简3.4 3.4 逻辑函数的卡诺图化简逻辑函数的卡诺图化简3.5 3.5 具有无关项的逻辑函数化简具有无关项的逻辑函数化简2.学习本章目的：学习本章目的：掌握掌握逻辑运算的规律和 逻辑函数的简化方法。第第3 3章章 逻辑代数逻辑代数 1.逻辑代数的定义：逻辑代数的定义： 描述客观事物逻辑关系的描述客观事物逻辑关系的一种一种数学数学(方法方法)表达式。表达式。 （由英国数学家乔治布尔率先提出，故亦称为布尔代数

2、布尔代数）。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+C)9反演律10非非律证明方法

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

5、（A+B）=A吸收式吸收式223合并式4配项式1配项式256AABAABAA7BAABABABAA证明常用恒等式的方法：证明常用恒等式的方法：用基本定理导出或枚举法用基本定理导出或枚举法 AABBABAAB1)(BCAACAABBCCAAB)(证明：例3.1.4 证明配项式： 。证明：CAABBCCAAB例3.1.3 证明合并式： 。ABAAB)1 ()1 (BCACABCAABBCAABCCAAB)(BAAABAA证明：例3.1.2证明吸收式： 。BABAABABA)(1如果两项如果两项分别包含分别包含A和和 ，而其余的因子，而其余的因子相乘为第相乘为第3项项，则，则第第3项是多余的。项是多

6、余的。A如果如果一项一项的反是另一项的的反是另一项的因子，则此因子是多余的。因子，则此因子是多余的。注意1：由于逻辑代数中没有逻辑减法及逻辑除法，故初等代数由于逻辑代数中没有逻辑减法及逻辑除法，故初等代数中的移项规则（移加作减，移乘作除）这里不适用中的移项规则（移加作减，移乘作除）这里不适用。注意注意2: 定理和恒等式反映的是逻辑关系定理和恒等式反映的是逻辑关系, , 不是数量之间的关系。不是数量之间的关系。 3.2 3.2 逻辑运算的基本规则逻辑运算的基本规则3.2.1 代入规则代入规则1.定义：在任何一个逻辑等式中，用一个逻辑函数代替等式在任何一个逻辑等式中，用一个逻辑函数代替等式两边的某

7、一逻辑变量后，新的等式仍然成立，这个规则称为两边的某一逻辑变量后，新的等式仍然成立，这个规则称为代入规则代入规则。BAAB例3.2.1 在 中，用BC代替等式两边的B，求新等式。2.作用：将逻辑代数的基本定理（表3.1.2）和常用恒等式（表3.1.4）推广到多变量的情况。CBABCAABC右边左边解：CBAABC得3.2.2 反演规则反演规则1.定义：在任何一个逻辑函数在任何一个逻辑函数Y中，同时进行下述中，同时进行下述3种变换（称种变换（称为反演变换）后为反演变换）后产生的新函数就是原函数产生的新函数就是原函数Y的反函数的反函数：注意：不属于单个变量上的反号应该保留反号应该保留，并保持原表达

8、式中变量间的运算顺序运算顺序添加括号（）。2.作用：求反函数。AAY)01 (解：解：()()YA B B CD解：解： 例3.2.2 已知 ，求 )(DCBABY?Y例3.2.3 已知Y=A+01，求 。Y(1)所有的“”换成“+”， “+”换成“”；(3)所有的原变量换成反变量，反变量换成原变量。(2) 所有的“0”换成“1”，“1”换成“0”；3.2.3 对偶规则对偶规则注意：必须保持原表达式中变量间的运算顺序。1.定义：在一个逻辑表达式Y中，同时进行下述变换后产生的新表达式称为原式Y的对偶式Y，这种变换称为对偶变换 ：（1）所有的“”换成“+”， “+”换成“”；（2）所有的“0”换成

9、“1”， “1”换成“0”, 0BAAL例如，表3.1.2和表3.1.4同一行的等式，互为对偶式。1)(BAAL2.作用：使要证明和要记忆的公式减少了一半。3.3 3.3 逻辑函数的代数法化简逻辑函数的代数法化简与或式：乘积项之和BCBAY3.3.13.3.1最简的标准最简的标准1.1.逻辑函数的逻辑函数的5 5种表达式和相互转换种表达式和相互转换与或非式CBBA或与式：和项之积)(CBBA与非与非式BCBA或非或非式CBBA与或式转换为或与式：与或式转换为或与式：a.a.在最简与或式的基础上，取反。在最简与或式的基础上，取反。b.b.在反函数最简与或式的基础上，用反演规则，直接写出在反函数最

10、简与或式的基础上，用反演规则，直接写出最简或与式。最简或与式。BCBAY+=例CBBACBCABACBBAY+=+=)+)(+(=)(CBBACBBACBBAYY在最简与或式上，在最简与或式上，2次取反。次取反。在最简或与式上，在最简或与式上，2次取反。次取反。在最简或非或非式上，在最简或非或非式上，利用反演规则得利用反演规则得。21),(非最简与或式非最简与或式最简与或式BCAABCBAABBCACBAY同一种类型的表达式中，形式有不同，但最简的形式形式是唯一的。例如在与或表达式中（1）乘积项的个数最少；）乘积项的个数最少；2.2.最简与或表达式的标准：最简与或表达式的标准：（2）在满足（）

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

12、CCAAB利用 ，消去BC项。例如：4、消因法、消因法BABAAA利用 ，消去因子 。例如：)( BACBAC5、配项法、配项法ABCBCACBAYCBAACBCCBABACBCBBABAY)()(1 AAAAA利用 ， ，等公式，在原式中增加项，然后再化简。1 AA（1）利用 ，配项化简 代数法化简逻辑函数时，必须综合使用上述技巧、逻辑代数代数法化简逻辑函数时，必须综合使用上述技巧、逻辑代数定理和恒等式，才能有效地化简逻辑函数。定理和恒等式，才能有效地化简逻辑函数。)() 1()1 (BBCACBACBACBACBACBCBABCABACACBBAAAA（2）利用 ，配项化简)()(ABCB

13、CABCACBABCBABCBA3.4 3.4 逻辑函数的卡诺图化简逻辑函数的卡诺图化简3.4.1 逻辑函数标准表达式逻辑函数标准表达式化简的理论基础：化简的理论基础：标准表达式、最小项和最大项1.标准与或式标准与或式每个乘积项都包含函数的全部变量的特殊与或式每个乘积项都包含函数的全部变量的特殊与或式称为称为标准与或表达式。标准与或表达式。BCACBAY),(BCACBACBACABABC一般与或式BCAACCBBA)()(标准与或式最小项：最小项：标准与或式中每一个乘积项都包含函数标准与或式中每一个乘积项都包含函数Y Y的全部变量，的全部变量，每个变量以原每个变量以原变量或反变量因子仅出现一

14、次。变量或反变量因子仅出现一次。 最小项最小项 把原变量用把原变量用1 1替代，反变量用替代，反变量用0 0替代，按一定的变量排列顺替代，按一定的变量排列顺序构成的序构成的二进制数二进制数就是最小项的就是最小项的编号编号，通常转换为十进制数。，通常转换为十进制数。最小项的编号方法：最小项的编号方法：n个变量的逻辑函数有个变量的逻辑函数有2n个最小项。个最小项。常用常用mi 或或m( i )表示，表示，i是最小项的编号。是最小项的编号。CBA（101）2 =(5)10，记作m5或m(5)。ABCCABCBACBABCACBACBACBA,如如3变量的最小项变量的最小项 2n 238CBAm 0C

15、BAm 2CABm 6ABCm 7表3.4.1 Y(A,B,C)=A+BC三变量全部最小项的真值表ABCY=A+BC000100000000001010000000010001000000011000100001100000010001101000001001110000000101111000000011CBAm 5CBAm 4BCAm 3CBAm 1下P26p22最小项的性质最小项的性质：对于任意一个最小项，只有一组变量取值使其为1，其它组取值使其为0。 为1 的取值组合是最小项的编号。n个变量的最小项有n个相邻项，且两相邻最小项之和等于它们的相同变量之积。12 , 2 , 1 , 0,

16、0njijimm不同的两个最小项之积恒为0，即全部最小项之和恒为1，即1120iimn逻辑相邻逻辑相邻:仅有一个变量不同的2个最小项称为逻辑相邻最小项，简称相邻项。例如，3变量最小项ABC的相邻项是 、 和 。BCACBACAB两相邻最小项之和等于它们的相同变量之积。ABCABABCACCBAABC最小项一般表达式：最小项一般表达式： 3变量表达式： (由表3.4.1的最后一列得）120765432103)(11111000),(iiimmYmmmmmmmmBCACBAYn变量表达式：使mi=1的变量取值组合对应的函数值iiimmYCBAYn120)(),(最小项最小项 反函数表达式：iiim

17、mYCBAYn120)(),(即任意反函数的标准与或式是函数值为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，即使最大项为1、0的取值组合的二进制数值是最大项的编号。12 , 2 , 1 , 0, 10njijij

19、iMMmm全部最大项之积恒为0，即仅有一个变量不同的2个最大项称为最大项，简称相邻项。01120120nniiiiMmBACBACBA)( n个变量的最大项有n个相邻项，且两相邻最大项之积等于它们的相同变量之和。 两相邻最大项之积等于它们的相同变量之和。例如， CBACBACBA例如，3变量最大项A+B+C的相邻项是 、 和 。例如： BACBACBA)(逻辑相邻：最大项一般表达式： 由式（3.4.3）得)()(),(),(120120iiiiiimmYmmYCBAYCBAYnn)(),(120iiiMmYCBAYn即任意逻辑函数的标准即任意逻辑函数的标准或与式或与式是函数值为是函数值为0 0

20、所对应的所对应的最大项之积。最大项之积。 例如，在表3.4.1中的最后一列，)()(),(210CBACBACBAMMMBCACBAY。与式（3.4.4）相同P193实际问题的逻辑函数例3.4.1 一楼梯间照明电路如下图所示。双控开关A和B一个装在楼上，一个装在楼下。楼下时开灯，上楼后则可关灯，反之亦然。表3.4.2楼梯间照明电路真值表 由此列出真值表3.4.2。ABY001010100111所以，最小项表达式220V50Hz12ABY图3.4.1楼梯间照明电路12解：解：（1）列真值表）列真值表 设灯亮Y=1，灯灭Y=0； A或B=1表示拨向1位；A或B=0表示2位。ABBABABAmmYB

21、AYiii1001)(),(1202BAABY=1对应的最小项是 、 ；Y=0对应的最小项是 、 。BABA)3 , 0(mABBA（2）写最小项表达式）写最小项表达式)()2 , 1 ()2 , 1 ()2 , 1 ()3 , 0(),(BABAMmmmBAY（3）写最大项表达式）写最大项表达式由实际逻辑问题导出逻辑函数的方法是：（1）根据命题导出真值表；（2）由真值表导出标准表达式；（3）化简。（2）标准或与式（最大项表达式）是函数值为0所对应的最大项之积。由真值表导出标准表达式的方法是（1）标准与或式（最小项表达式）是函数值为1所对应的最小项之和。（4）画逻辑图。3.4.2 逻辑函数的卡

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

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

24、）卡诺图ABCD1DCABDCABCDBACDBA1312113mmmm111方法一：转换为最小项表达式方法二：方法二：由表达式直接填入由表达式直接填入CBACBAY),(1 ：例 ABC 00 01 11 10 0 1 1 1 1 1 1ABCBCABCBAY),(2：例 ABC 00 01 11 10 0 11BCAB111（2）由真值表画卡诺图ABCY00000010010001111000101111011111 在卡诺图中，使逻辑函数值为的最小项填入；使逻辑在卡诺图中，使逻辑函数值为的最小项填入；使逻辑函数值为的最小项填入，为了直观和简洁，通常不填写。函数值为的最小项填入，为了直观和

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

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

27、量。2化简的步骤化简的步骤(1)(1)画出逻辑函数的卡诺图（画出逻辑函数的卡诺图（2 2n n个方格）个方格）(2)(2)画卡诺圈画卡诺圈卡诺圈越少越好（因一个卡诺圈代表一个与项）；卡诺圈越少越好（因一个卡诺圈代表一个与项）；卡诺圈内值为卡诺圈内值为1 1的方格越多越好（因圈越大消去的变量越多，的方格越多越好（因圈越大消去的变量越多，与项包含的变量越少与项包含的变量越少）。）。卡诺圈可以交迭，但每个卡诺圈必须至少有与其它卡诺圈卡诺圈可以交迭，但每个卡诺圈必须至少有与其它卡诺圈不同的、值为不同的、值为1 1的方格。的方格。(3)(3)求求每个卡诺圈的公共变量之积（与项）并相加每个卡诺圈的公共变量

28、之积（与项）并相加，得到最简，得到最简的与或表达式。的与或表达式。卡诺圈：卡诺圈：在卡诺图中，把在卡诺图中，把2 2n n个值为个值为1 1的相邻的方格画成一个圈。的相邻的方格画成一个圈。例3.4.4化简函数(A,B,C,D)=m(0,1,2,5,6,7,14,15)。解：解：在画卡诺圈时，注意到卡诺图的对称相邻特性，可以想象将两边粘连，上下粘连。000111100011101111111110CDAB000111100011101111111110CDAB（ a ）（ b ）因图（a）的卡诺圈比图（b）的多，所以图(b)是正确的卡诺圈。由图（b）,函数Y的最简与或式为DBADCABCYBCD

29、CADBA解：例例3.4.53.4.5已知逻辑函数Y(A,B,C,D)=m(0,1,2,8,9,10,11,13,15)，求函数Y的最简与或式；反函数的最简与或式；函数Y的最简或与式。CD0001111000111011111101111ABCD0001111000111011111101111ABY的最简与或式；DBCBADYADDBCB反函数的最简与或式；CDADBBAYDBBACDAY的最简或与式。)()(DCADBBACDADBBAYY对反函数 求反，可获得函数Y的最简或与式Y3.3.反函数的最简与或式再取反可反函数的最简与或式再取反可求函数求函数Y Y的最简或与式。的最简或与式。结论

30、： 1.1.圈圈1 1可求函数的最简与或式。可求函数的最简与或式。2.2.圈圈0 0可求反函数的最简与或式。可求反函数的最简与或式。3.5 具有无关项的逻辑函数化简3.5.1 无关项概念约束项和任意项统称为无关项约束项和任意项统称为无关项 例如：用二变量例如：用二变量ABAB控制一台电梯；控制一台电梯； AB=00AB=00电梯停；电梯停；AB=01AB=01电梯下电梯下降；降； AB=10AB=10电梯上升。而电梯上升。而AB=11AB=11是不允许的取值组合，因为任是不允许的取值组合，因为任何时刻一台电梯不能同时上行和下行。这个逻辑问题的约束何时刻一台电梯不能同时上行和下行。这个逻辑问题的

31、约束方程为方程为AB=0AB=0，即允许的取值组合满足约束方程，即允许的取值组合满足约束方程，而不允许的，而不允许的1.约束项约束项在在n n个变量的逻辑函数中，如果对变量的每个取值组合（共个变量的逻辑函数中，如果对变量的每个取值组合（共有有2 2n n个取值组合），函数均有确定的值（个取值组合），函数均有确定的值（0 0或或1 1）与之对应，则）与之对应，则称这样的函数为称这样的函数为确定的逻辑函数确定的逻辑函数，否则，称为，否则，称为不完全确定的逻不完全确定的逻辑函数或具有无关项的逻辑函数。辑函数或具有无关项的逻辑函数。对某些逻辑问题，自变量的一些特定对某些逻辑问题，自变量的一些特定取值组

32、合是不允许出现取值组合是不允许出现的，函数的取值无定义，它可能是的，函数的取值无定义，它可能是0 0，也可能是，也可能是1 1。对应于这些特。对应于这些特定的取值组合，值为定的取值组合，值为1 1的最小项称为约束项。的最小项称为约束项。 无关项在真值表和卡诺图中用无关项在真值表和卡诺图中用 “ “ ” 或或“d”d”表示。表示。2. 任意项任意项例如，将例如，将8421BCD8421BCD码转换为余码转换为余3 3码，其真值表为表码，其真值表为表3.4.33.4.3。当变量当变量ABCDABCD取值为取值为00000000、10011001时，有确定的余时，有确定的余3 3码码00110011、11001100与之对应。当非与之对应。当非8421BCD 10108421BCD 1010、11111111出出现时，并不影响现时，并不影响8421BCD8421BCD码转换为余码转换为余3 3码的功能，所以，码的功能，所以，WXYZWXYZ的的取值无关紧要。取值无关紧要。对某些逻辑问题，对应于自变量的一些特定对某些逻辑问题，对应于自变量的一些特定取值组合，函取值组合，函数的取值无关紧要，对逻辑功能没有任何影响数的取值无关紧要，对