第2章 逻辑代数基础

1、第二章第二章 逻辑代数基础逻辑代数基础天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University吴森 讲师天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 内容提要 2.1 2.1 基本基本逻辑运算逻辑运算 2.2 2.2 逻辑代数的

2、基本公式和定理逻辑代数的基本公式和定理 2.3 2.3 逻辑函数的表示方法逻辑函数的表示方法 2.4 2.4 逻辑函数的化简逻辑函数的化简天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 第一章 逻辑代数基础2.1 基本逻辑运算天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engin

3、eering, Tianjin University三三种种基本基本运算运算 2.1 基本逻辑运算 “0”、“1”表示两种对立的逻辑状态；只存在这两种状态的信号之间的因果关系称为二值逻辑；按照指定因果关系进行的推理即逻辑运算，逻辑运算的数学方法称为逻辑代数，又称布尔代数（George Boole）与（AND）或（OR）非（NOT）常见常见扩展扩展运算运算与非（NAND）或非（NOR）异或（Exclusive OR,xor）同或（Inclusive OR,xnor）复杂组合天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrumen

4、t & Opto-electronics Engineering, Tianjin University 2.1 基本逻辑运算一. “与”运算 当决定事件的所有条件都具备时事件才发生。功能表开关A开关B灯Y电源ABY断断灭断通灭通断灭通通亮真值表ABY000010100111逻辑函数表达式：Y=AB=ABABY&图形符号：逻辑乘与门天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.1 基本

5、逻辑运算二. “或”运算 当决定事件的所有条件中有一个或一个以上具备时事件就发生。逻辑函数表达式：Y=A+BABY1图形符号：逻辑加或门开关A开关B灯Y电源功能表ABY断断灭断通亮通断亮通通亮真值表ABY000011101111天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.1 基本逻辑运算三. “非”运算 决定事件的条件只有1个，当条件具备时事件不发生，条件不具备时事件发生。逻辑函数表达式：Y=A图形

6、符号：逻辑反非门功能表AY断亮通灭真值表AY0110开关A灯Y电源R（也可写成Y=A)AY1天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.1 基本逻辑运算四. 基本逻辑的常用扩展与非门Y=ABYAB&真值表ABABY0001010110011110真值表或非门Y=A+BYAB1ABA+BY0001011010101110天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 Scho

7、ol of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.1 基本逻辑运算四. 基本逻辑的常用扩展异或门YAB=1真值表ABY000011101110真值表同或门YAB=1ABY001010100111YABY= ABYABABYABAB天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.1 基本逻

8、辑运算IEEE符号AY国标符号AB&A1AB1YYYABABYYIEEE符号国标符号AB&AB=1AB1YYYABABYYYABAB=YABYA1&BCDYY=(AB+CD)天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 第二章 逻辑代数基础2.2 基本公式和定理天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrume

9、nt & Opto-electronics Engineering, Tianjin University 2.2 基本公式和定理一、基本公式一、基本公式0 0 A = 0 00 0，1 1律律0 0 + A = A1 1 A = A0 0，1 1律律1 1 + A= 1 1A A = A重叠律重叠律A + A = AA A= 0 0互补律互补律A + A = 1 1A B = B A交换律交换律A +B = B + AA (B C) = (A B) C结合律结合律A + (B +C) = (A + B) + CA (B +C) = A B + A C分配率分配率A + B C = (

10、A +B)(A +C)(A B) = A + B反演律反演律(A+ B) = AB(A ) = A还原律还原律天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University证明公式：证明公式：A (B +C) = A B + A CABCA(B+C)ABACAB+AC00000000010000010000001100001000000101101111011011111111左 = 右枚举法真值表 2.2 基本公式和定理

11、天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University证明公式：证明公式：A +BC = (A + B )(A + C)推演法左右BCABCCBABCACABACABA)()(1 2.2 基本公式和定理天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin

12、University 2.2 基本公式和定理二二、常用其他公式、常用其他公式A + A B = AA +A B = A + BA B + A B = AA ( A + B) = AA B + A C + B C = A B + A CA B + A C + BCD = A B + A CA (AB) = A B ; A (AB) = A 天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University证明公式：证明公式：A

13、+ AB = A + B 右 = A + B = (A + A)(A + B)= A + AB = 左 证明公式：证明公式：AB + AC + BC = AB + AC 左 = AB + AC + BC = AB + AC + BC (A + A) = AB + ABC + AC + ACB = AB + AC = 右 证明公式：证明公式：AB + AC + BCD = AB + AC 左 = AB + AC + BCD = AB + AC + BC + BCD = AB + AC + BC = AB + AC = 右 证明公式：证明公式：A(AB) = AB 左 = A(AB) = A(A

14、+ B) = AB = 右 2.2 基本公式和定理天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University三、基本定理三、基本定理1. 代入定理 在任何一个包含A 的逻辑等式中，若以另外一个逻辑式代入式中A的位置，则等式依然成立。例：分配律公式 A (B + C) = AB+AC ，用C + D代替C 得:A B+(C+D) = AB+ A(C+D) = AB + AC + AD代入定理可以扩展所有基本公式或定律的应

15、用范围例：反演律公式 (A + B) = AB ，用B + C代替B 得:A+(B+C) = A(B+C) = ABC 2.2 基本公式和定理天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University2. 反演定理 对于任意逻辑表达式，按照以下方式变换可得到原函数的反函数。运算符“与”、“或”置换，“同或”、“异或”置换；变量、反变量置换；常量0、1置换。例：函数 Y=AB+CD的反演函数如下AB+CD(A+B)(C+

16、D)Y=(AB+CD)=(AB)(CD)=(A+B)(C+D)例：函数 Y=A(BC(DE)的反演函数如下A(BC(DE)A+(B+C+(D+E)= Y 括号不变，括号上的反号也不变 2.2 基本公式和定理天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University3. 对偶定理 两个相等逻辑式的对偶式也相等。任意逻辑表达式的对偶式可按照以下方式得到。运算符“与”、“或”置换，“同或” 、“异或”置换 ；常量0、1置换。

17、例：Y=AB+CD的对偶式如下AB+CD(A+B)(C+D)例： Y=A(BC(DE)的对偶式如下A(BC(DE)A+(B+C+(D+E) 对偶式不改变括号和反号 2.2 基本公式和定理天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University例：A+BCD = (A+B)(A+C)(A+D)A(B+C+D)(AB)+(AC)+(AD)用对偶定理证明=例：AB+AC+BC = AB+ACAB+AC+BC (A+B)(A

18、+C)(B+C) = AC+AB+BCAB+AC (A+B)(A+C) = AC+AB+BC (A+B)(A+C)(B+C) = (A+B)(A+C)AB+AC+BC = AB+ACA+BCD = (A+B)(A+C)(A+D) 2.2 基本公式和定理天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 第二章 逻辑代数基础2.3 逻辑函数的表示方法天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院

19、 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.3 逻辑函数的表示方法一一、逻辑函数、逻辑函数逻辑关系变量输入逻辑运算结果输出逻辑函数 Y=F(A,B,C)二二、表示方法、表示方法Y=A(B+C)YABC输 入输 出ABCY00000010010001101000101111011111YCBAtttt天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electron

20、ics Engineering, Tianjin University 2.3 逻辑函数的表示方法三三、逻辑函数的变换、逻辑函数的变换 同一个逻辑函数可以有不同的表达式，不同的表达式对应不同的逻辑电路。Y=(A(AB)+B(AB)=(A+B)(AB)=(AB)(AB)=AB+ABABYABYABYABY天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.3 逻辑函数的表示方法四四、逻辑函数的标准形式、逻辑函

21、数的标准形式逻辑函数标准形式最小项之和最大项之积最小项：在n变量逻辑函数中，若m为n个变量的乘积，且这n个变量均以原变量或反变量的形式在m中出现一次，则m为该组变量的最小项。例：n=2，m=AB、AB 最大项：在n变量逻辑函数中，若M为n个变量的和，且这n个变量均以原变量或反变量的形式在M中出现一次，则M为该组变量的最大项。例：n=2，M=A+B、A+B 例：n=2，Y=AB+AB例：n=2，Y=(A+B)(A+B)与-或或-与天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electroni

22、cs Engineering, Tianjin University 2.3 逻辑函数的表示方法最小项的特性：n变量逻辑函数总共有2n个最小项；任一最小项，只有一组变量取值使其值为1；任意两个最小项的乘积为0；全体最小项之和为1。取 值ABCABCABCABCABCABCABCABCABC0001000000000101000000010001000000110001000010000001000101000001001100000001011100000001天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument &am

23、p; Opto-electronics Engineering, Tianjin University 2.3 逻辑函数的表示方法 把与最小项对应的变量取值当成二进制数（原变量为1，反变量为0），与之相应的十进制数，就是该最小项的编号，用 mi 表示。A B CA B CA BCA BCAB CAB CABCABC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 1 234567m0m1m2m3m4m5m6m7天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-e

24、lectronics Engineering, Tianjin University 2.3 逻辑函数的表示方法 ( )YF A ,B ,CABA CABCABCA B CA BC3176mmmm m7 , 6 , 3 , 1()()YAB CCA C BB例： 写出下列函数的最小项标准式（与或式）：或m6m7m1m3 任何一个任何一个逻辑函数式的标准形式一定不可能是全部最小项之和。并且逻辑函数式的标准形式一定不可能是全部最小项之和。并且在化简之后一定不超过全部最小项个数的一半。在化简之后一定不超过全部最小项个数的一半。天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 Scho

25、ol of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.3 逻辑函数的表示方法例： 写出下列函数的最小项标准式（与或式）：CBADABY )( )( )(CBDABA DCBCABA )()()(AADCBBBCACCBA DCBADCBACBACBABCA DCBADCBADCBADCBA DCBADCBADBCABCDA m7m6m5m4m1m0m8 ) 8 , 7 , 6 , 5 , 4 , 1 , 0 (mm0与前面m0相重天津大学精密仪器与光电子工程学院天津大学精密仪器与光

26、电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 第二章 逻辑代数基础2.4 逻辑函数的化简天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简一一、逻辑函数的、逻辑函数的最最简简与与- -或或式式 在在若干个逻辑关系相同的与若干个逻辑关系相同的与- -或

27、表达式中，将其中包或表达式中，将其中包含的与项数最少，且每个与项中变量数最少的表达式称为含的与项数最少，且每个与项中变量数最少的表达式称为最简与最简与- -或或表达式。表达式。二二、公式化简法、公式化简法()LA BA BCD E FA B运用逻辑代数的基本定律和恒等式进行化运用逻辑代数的基本定律和恒等式进行化简。简。 天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简并项:YABCAB

28、CA BABA BB YABCAB CABCAB C()()A BCB CA BCB CA ()()A BCA BC例：例：ABABA 1A A天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简吸收:例：例：AABA EBDAABY EBDABA BA CDBCDAABY CDBAAB )( CDABAB AB BA BCDC BA BCAAY )( )()()(DC BA BCABCA

29、 BCA 例：天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简消去:例：BABAA CBCAABY CBAAB)( CABAB CAB ABCCBABABAY )()(BCBA CBB A )()(CBA CB A ACCABABA CBABA 例：天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument &

30、 Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简配项:例：例：CAABBCCAAB AB ABCACB 或BCCACACB BCCABA BCCABACBACBAY CBACBA BCCABA BA BCCACACBY 或BCCABACBACBA 冗余项冗余项1 AA天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化

31、简练习:EACDECBEDCBBEAACEY DCBACDCBBAACE ) (DCBEADEBECE DCBEADCBE )(DCBEADCBE DCBEAE DCBE DCBADBCE ) (天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简 要求要求对对所有公式所有公式熟练掌握熟练掌握； 无无一套一套完善完善流程流程可循，依赖可循，依赖于人于人的的经经验和验和灵活性灵活性； 不利于

32、不利于判断判断结果结果是否为最简式。是否为最简式。公式公式法法化简在使用中遇到的困难：化简在使用中遇到的困难：天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简三三、卡诺图（、卡诺图（ Karnaugh maps ）卡诺图即按格雷码排列的最小项方格图将n变量的全部最小项都用小方块表示，并使具有逻辑相邻的最小项几何相邻。逻辑相邻：两最小项只有一个变量互为反变量。几何相邻：相接 上下左右挨着

33、相对 同一行或列的两头相重 对折起来位置重合ABAABBBABABAAB二变量的卡诺图：4个最小项天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简ABC01000110111110逻辑不相邻逻辑相邻逻辑相邻m0m1m2m3m4m5m6m7ABCD0001111000011110CDE00011110000 001 011 010 110 111 101 100m0m1m2m3m4m5m

34、6m7m12m13m14m15m8m9m10m11m0m1m2m3m8m9m10m11m24m25m26m27m16m17m18m19m6m7m4m5m14m15m12m13m30m31m28m29m22m23m20m21几何相邻几何相邻几何相邻三变量卡诺图：8个最小项四变量卡诺图：16个最小项五变量卡诺图：32个最小项五个以上变量不适用卡诺图AB天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑

35、函数的化简用卡诺图表示逻辑函数1. 根据变量个数画出相应的卡诺图；2. 将函数化为最小项之和的形式；3. 在卡诺图上与这些最小项对应的位置填入 1 ，其余位置填 0 或不填。例：) (C B , A ,FY ACBCAB CBABCACABABC ABC010001111011110000利用卡诺图化简逻辑函数就是按一定规则对相邻的1进行合并与消去天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑

36、函数的化简卡诺图最小项合并规律 2N个相邻最小项合并可以消去N个因子，留下的是这些最小项中相同的部分。ABC01000111101111CBCBACBA BACBACBA ABCD00011110000111101111DCBDCBADCBA DBADCBADCBA 天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简ABCD00011110000111101111DC 1111CB AB

37、CD00011110000111101111BD1111DB 81240mmmm DCBADCABDCBADCBA DC 111023mmmm DCBADCBADCBADCBA CB 151375mmmm DCBADCBADCBADCBA BD 10820mmmm DCBADCBADCBADCBA DB 天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简ABCD0001111000011

38、1101111C 1111B ABCD00011110000111101111B1111D11111111天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简DABDADBA DBACDBADCBA BDABCDADCBA m0 m1 m3 m2 m4 m5 m7 m6 m12 m13 m15 m14 m8 m9 m11 m10 AB CD 00 01 11 10 00 01 11 10

39、ADABDDBA DADDA 天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简卡诺图化简逻辑函数步骤1. 根据逻辑函数填写卡诺图；2. 对相邻的1方格画包围圈，画圈原则如下：3. 对每个包围圈进行合并得到一个乘积项，各包围圈所得乘积项之和即是该逻辑函数的最简式。ABCD000111100001111011111111不正确的画圈每个圈都必须为矩形，且含有2n个1；先圈孤立1，再圈只有一

40、种合并方式的1，每个1都必须被圈上；圈内的1越多越好，圈的个数越少越好；不同的圈可包含相同的1，但每个圈中至少有一个不同的1.天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简利用图形法化简函数例： mF) 15 , 14 , 11 , 10 , 8 , 4 , 3 , 2 , 1 , 0 (解(1) 画函数的卡诺图ABCD00011110000111101111111111(2) 画包

41、围圈合并最小项(3) 写出最简与或表达式D BD C AACB AY 天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简利用图形法求下列函数的反函数的最简与或表达式例：ACBCABY 解(1) 画函数的卡诺图ABC010001111011110000(2) 合并函数值为0的最小项(3) 写出反函数的最简与或表达式CACBBAY 天津大学精密仪器与光电子工程学院天津大学精密仪器与光电子工程

42、学院 School of Precision Instrument & Opto-electronics Engineering, Tianjin University 2.4 逻辑函数的化简求下列函数的最简与或表达式例： 1 1 1 00 AB L 01 10 11 CD 11 00 00 01 10 011 1111111111110( , , ,)(0 3,5 7,8 11,1315)L A B C DmLDCBB 1 1 1 00 AB L 01 10 11 CD 11 00 00 01 10 011 1111111111110CD圈圈0LBCDLDCB圈圈1天津大学精密仪器与光电子工程