ch2逻辑代数基础

1、第二章第二章 逻辑代数基础逻辑代数基础2.1 概述概述n基本概念基本概念逻辑：逻辑： 事物的因果关系事物的因果关系逻辑运算的数学基础：逻辑运算的数学基础： 逻辑代数逻辑代数在二值逻辑中的变量取值：在二值逻辑中的变量取值： 0/10/1在正逻辑中：在正逻辑中：1 1 表示条件具备、开关接通、高电平等。表示条件具备、开关接通、高电平等。 0 0 表示条件不具备、开关断开、低电平等。表示条件不具备、开关断开、低电平等。逻辑代数逻辑代数开关代数开关代数布尔代数。布尔代数。用来解决数字逻辑电路的分析与设计问题。用来解决数字逻辑电路的分析与设计问题。参与逻辑运算的变量叫逻辑变量，用字母参与逻辑运算的变量叫

2、逻辑变量，用字母A A，B B表示。每个变量的取值非表示。每个变量的取值非0 0 即即1 1。 0 0、1 1不表不表示数的大小，而是代表两种不同的逻辑状态。示数的大小，而是代表两种不同的逻辑状态。2.2 逻辑代数中的三种基本运算逻辑代数中的三种基本运算 与与（AND） 或或（OR） 非非（NOT）以以A=1表示开关表示开关A合上，合上，A=0 0表示开关表示开关A断开；断开；以以Y=1 1表示灯亮，表示灯亮，Y=0 0表示灯不亮；表示灯不亮；三种电路的因果关系不同：三种电路的因果关系不同：与与n条件同时具备，结果发生条件同时具备，结果发生nY=A AND B = A&B=AB=ABA

3、 BY0 000 101 001 11或或n条件之一具备，结果发生条件之一具备，结果发生nY= A OR B = A+BA BY0 000 111 011 11非非n条件不具备，结果发生条件不具备，结果发生n ANOTY AA Y0 110几种常用的复合逻辑运算几种常用的复合逻辑运算n与非与非 或非或非 与或非与或非几种常用的复合逻辑运算几种常用的复合逻辑运算n异或异或nY= A BA BY0 000 111 011 10几种常用的复合逻辑运算几种常用的复合逻辑运算n同或同或nY= A BA BY0 010 101 001 112.3.1 基本公式基本公式2.3.2 常用公式常用公式2.3 逻

4、辑代数的基本公式和常用公式逻辑代数的基本公式和常用公式2.3.1 基本公式基本公式n根据与、或、非的定义，得表根据与、或、非的定义，得表2.3.1的布尔恒等式的布尔恒等式序号公 式序号公 式10 1 = 0; 0= 110 A = 0111 + A= 121 A = A120 + A = A3A A = A13A + A = A4A A= 014A + A = 15A B = B A15A +B = B + A6A (B C) = (A B) C16A + (B +C) = (A + B) + C7A (B +C) = A B + A C17A + B C = (A +B)(A +C)8(A

5、B) = A + B18(A+ B) = AB9(A ) = A证明方法：推演证明方法：推演 真值真值表表公式（公式（17）的证明）的证明（公式推演法）：（公式推演法）：左右BCABCCBABCACABACABA)()(1公式（公式（17）的证明（真值表法）：）的证明（真值表法）：ABCBCA+BCA+BA+C（A+B）(A+C)00000000001000100100010001111111100011111010111111001111111111112.3.2 若干常用公式若干常用公式序 号公 式21A + A B = A22A +A B = A + B23A B + A B = A24

6、A ( A + B) = A25A B + A C + B C = A B + A CA B + A C + B CD = A B + A C26A (AB) = A B ; A (AB) = A 2.4 逻辑代数的基本定理逻辑代数的基本定理n2.4.1 代入定理代入定理 -在任何一个包含在任何一个包含A的逻辑等式中，的逻辑等式中，若以另外一个逻辑式代入式中若以另外一个逻辑式代入式中A的位置，的位置，则等式依然成立。则等式依然成立。代入规则的意义在于扩代入规则的意义在于扩大等式的应用范围。大等式的应用范围。2.4.1 代入定理代入定理n应用举例：应用举例： 式（式（17） A+BC = (A+

7、B)(A+C) A+B(CD) = (A+B)(A+CD)= (A+B)(A+C)(A+D)2.4.1 代入定理代入定理n应用举例：应用举例： 式式 （8）CBABCACBABCBBABA)()()(代入以2.4 逻辑代数的基本定理逻辑代数的基本定理n2.4.2 反演定理反演定理 -对任一逻辑式对任一逻辑式原变量反变量反变量原变量，0110YY变换顺序变换顺序 先括号，先括号，然后乘，最后加然后乘，最后加不属于单个变量上不属于单个变量上的反号保留不变的反号保留不变反演规则的意义在于：反演规则的意义在于： 利用它可以比较容易地利用它可以比较容易地求出一个逻辑函数的反。求出一个逻辑函数的反。2.4

8、.2 反演定理反演定理n应用举例：应用举例：CDCBAY)(DCBDACBCADCCBAY)(CDCABY)() ) )(CDCBAY课堂练习课堂练习)()()()()()(EBECDBCABYDBACYDCBDBCDCBAYBEDCABYn2.4.3 对偶定理对偶定理0110，DYY 对偶规则对偶规则 则指当某个逻辑恒等式成立则指当某个逻辑恒等式成立时，其对偶式也一定成立。时，其对偶式也一定成立。 -对任一逻辑式对任一逻辑式 利用对偶规则可以使利用对偶规则可以使要证明的公式数目减少一要证明的公式数目减少一半。半。2.4.3 对偶定理对偶定理n应用举例：应用举例：CDCBAY)(CDCABY)

9、()()(DCBCAYDCDCBAYD) (n2.5.1 逻辑函数逻辑函数nY=F(A,B,C,) -若以逻辑变量为输入，运算结果为输若以逻辑变量为输入，运算结果为输出，则输入变量值确定以后，输出的取值出，则输入变量值确定以后，输出的取值也随之而定。输入也随之而定。输入/输出之间是一种函数关输出之间是一种函数关系。系。 注：在二值逻辑中，输入注：在二值逻辑中，输入/输出都只有两种取值输出都只有两种取值0/1。2.5 逻辑函数及其表示方法逻辑函数及其表示方法各种表示方法之间可以相互转换2.5.2 逻辑函数的表示方法逻辑函数的表示方法n 真值表真值表输入变量输入变量A B C输出输出Y1 Y2 遍

10、历所有可能的输入遍历所有可能的输入变量的取值组合变量的取值组合输出对应的取值输出对应的取值n逻辑式逻辑式 将输入将输入/输出之间的逻辑关系用输出之间的逻辑关系用与与/ /或或/ /非非的运算的运算式表示就得到逻辑式。式表示就得到逻辑式。n逻辑图逻辑图 用逻辑图形符号表示逻辑运算关系，与逻辑电路用逻辑图形符号表示逻辑运算关系，与逻辑电路的实现相对应。的实现相对应。n 波形图波形图 将输入变量所有取值可能与对应输出按时间顺序排将输入变量所有取值可能与对应输出按时间顺序排列起来画成时间波形。列起来画成时间波形。n卡诺图卡诺图nEDA中的描述方式中的描述方式 HDL (Hardware Descrip

11、tion Language) VHDL (Very High Speed Integrated Circuit ) Verilog HDL 。 举例：举重裁判电路举例：举重裁判电路ABCF000001001011100110111011断断“0”0”合合“1”1”亮亮“1”1”灭灭“0”0”C C开，开，F F灭灭0000C C合，合，A A、B B中中有一个合，有一个合，F F亮亮11C C合，合，A A、B B均均断，断，F F灭灭0逻辑函数式逻辑函数式 挑出函数值为挑出函数值为1 1的项的项1 101111101111 每个函数值为每个函数值为1 1的输入变量取值组合写成一个的输入变量取

12、值组合写成一个乘积项乘积项 这些乘积项作这些乘积项作逻辑加逻辑加输入变量取值为输入变量取值为1 1用原变量表示用原变量表示; ;反之，则用反变量表示反之，则用反变量表示ABC、ABC、ABCF= ABC+ABC+ABC逻辑图逻辑图F= ABC+ABC+ABC乘积项乘积项用用与门与门实现，实现，和项和项用用或门或门实现实现波形图波形图0 01 10 00 01 11 10 00 01 11 11 11 1CBAY)(ACB各种表现形式的相互转换：各种表现形式的相互转换：n真值表真值表 逻辑式逻辑式例：奇偶判别函数的真值表例：奇偶判别函数的真值表nA=0,B=1,C=1使使 ABC=1nA=1,B

13、=0,C=1使使 ABC=1nA=1,B=1,C=0使使 ABC =1这三种取值的任何一种都使这三种取值的任何一种都使Y=1,所以所以 Y= ? AB CY00000010010001111000101111011110n真值表真值表 逻辑式：逻辑式：1.找出真值表中使找出真值表中使 Y=1 的输入变量取值组合。的输入变量取值组合。2.每组输入变量取值对应一个乘积项，其中取每组输入变量取值对应一个乘积项，其中取值为值为1的写原变量，取值为的写原变量，取值为0的写反变量。的写反变量。3.将这些变量相加即得将这些变量相加即得 Y。4.把输入变量取值的所有组合逐个代入逻辑式把输入变量取值的所有组合逐

14、个代入逻辑式中求出中求出Y，列表，列表课堂练习：A B CY0 0 00 0 00 00 0 10 0 11 10 1 00 1 00 00 1 10 1 10 01 0 01 0 01 11 0 11 0 11 11 1 01 1 00 01 1 11 1 11 1A B CY0 0 00 0 01 10 0 10 0 11 10 1 00 1 00 00 1 10 1 11 11 0 01 0 00 01 0 11 0 11 11 1 01 1 00 01 1 11 1 10 0n逻辑式逻辑式 逻辑图逻辑图 用图形符号代替逻辑式中的逻辑运算符。用图形符号代替逻辑式中的逻辑运算符。)(CBA

15、Y课堂练习)()(DBACYBEDCABYn逻辑式逻辑式 逻辑图逻辑图1. 用图形符号代替逻辑式中的逻辑运算符。用图形符号代替逻辑式中的逻辑运算符。2. 从输入到输出逐级写出每个图形符号对应从输入到输出逐级写出每个图形符号对应的逻辑运算式。的逻辑运算式。 )( BAB)(BAA) )()(BABABABABABABABABA )()()(课堂练习&C1A1 1 1B&1 1 Y&C1A1 1 B=1=1 Y&n波形图波形图 真值表真值表ABYABY000011101110最小项最小项 m：nm是乘积项是乘积项n包含包含n个因子个因子nn个变量均以原变量和反变量的

16、形式在个变量均以原变量和反变量的形式在m中出中出现一次现一次2.5.3 逻辑函数的两种标准形式逻辑函数的两种标准形式 最小项最小项之和、之和、最大项最大项之积之积最小项举例：最小项举例：n两变量两变量A, B的最小项的最小项n三变量三变量A,B,C的最小项的最小项）4个（22ABBABABA,）8个（32ABCCABCBACBABCACBACBACBA,最小项的编号：最小项的编号：最小项最小项取值取值对应对应编号编号A B C 十进制数十进制数0 0 00 0 0 0m00 0 10 0 1 1m10 1 00 1 0 2m20 1 10 1 1 3m31 0 01 0 0 4m41 0 11

17、 0 1 5m51 1 01 1 0 6m61 1 11 1 1 7m7ABCCABCBACBABCACBACBACBA最小项的性质最小项的性质n在输入变量任一取值下，有且仅有一个最小项的在输入变量任一取值下，有且仅有一个最小项的值为值为1。n全体最小项之和为全体最小项之和为1 。n任何两个最小项之积为任何两个最小项之积为0 。n两个两个相邻相邻的最小项之和可以的最小项之和可以合并合并，消去一对因子，消去一对因子，只留下公共因子。只留下公共因子。 -相邻相邻：仅一个变量不同的最小项：仅一个变量不同的最小项 如如 BACCBABCACBABCACBA)(与逻辑函数最小项之和的形式：逻辑函数最小项

18、之和的形式：n例：例：),()(),(763mBCAABCCABAABCCABBCCABCBAY利用公式利用公式可将任何一个函数化为可将任何一个函数化为1 AA im逻辑函数最小项之和的形式：逻辑函数最小项之和的形式：n例：例：DCBAACDBAADCBCDBDDCBDBCAADCBACBDBCDCBADCBAY)()(.)()(),(逻辑函数最小项之和的形式：逻辑函数最小项之和的形式：n例：例：DCBAACDBAADCBCDBDDCBDBCAADCBACBDBCDCBADCBAY)()(.)()(),(逻辑函数最小项之和的形式：逻辑函数最小项之和的形式：n例：例：DCBAACDBAADCBC

19、DBDDCBDBCAADCBACBDBCDCBADCBAY)()(.)()(),(逻辑函数最小项之和的形式：逻辑函数最小项之和的形式：n例：例：DCBAACDBAADCBCDBDDCBDBCAADCBACBDBCDCBADCBAY)()(.)()(),(最大项：最大项：nM是相加项；是相加项；n包含包含n个因子。个因子。nn个变量均以原变量和反变量的形式在个变量均以原变量和反变量的形式在M中出现一次。中出现一次。n如：两变量如：两变量A, B的最大项的最大项）4个（22BABABABA,最大项的性质最大项的性质n在输入变量任一取值下，有且仅有一个最大项的在输入变量任一取值下，有且仅有一个最大项

20、的值为值为0 0；n全体最大项之积为全体最大项之积为0 0；n任何两个最大项之和为任何两个最大项之和为1 1；n只有一个变量不同的最大项的乘积等于各相同变只有一个变量不同的最大项的乘积等于各相同变量之和。量之和。最大项的编号：最大项的编号：最大项最大项取值取值对应对应编编 号号A B C十进制数十进制数1 1 11 1 17M71 1 01 1 06M61 0 11 0 15M51 0 01 0 04M40 1 10 1 13M30 1 00 1 02M20 0 10 0 11M10 0 00 0 00M0CBACBACBACBACBACBACBACBA imYikkmYikkmY)(kikk

21、ikMmY2.6 逻辑函数的化简法逻辑函数的化简法n逻辑函数的最简形式逻辑函数的最简形式 最简最简与或与或 -包含的乘积项已经最少，每个乘积项的因包含的乘积项已经最少，每个乘积项的因子也最少，称为最简的子也最少，称为最简的与与- -或或逻辑式。逻辑式。CBACYACDCBABCY21函数的简化依据函数的简化依据 逻辑电路所用门的数量少逻辑电路所用门的数量少 每个门的输入端个数少每个门的输入端个数少 逻辑电路构成级数少逻辑电路构成级数少 逻辑电路保证能可靠地工作逻辑电路保证能可靠地工作降低成本降低成本提高电路的工作提高电路的工作速度和可靠性速度和可靠性方法：方法： 并项：并项： 利用利用ABAA

22、B将两项并为一项，将两项并为一项，且消去一个变量且消去一个变量B B 消项：消项： 利用利用A + AB = AA + AB = A消去多余的项消去多余的项ABAB 配项：利用配项：利用CAABBCCAAB和互补律、和互补律、重叠律先增添项，再消去多余项重叠律先增添项，再消去多余项BCBC 消元：利用消元：利用BABAA消去多余变量消去多余变量A A0111010AAAAAAAAAAA eee1000101AAAA AAAAAAA 关于变量和常量关系的公式关于变量和常量关系的公式0-1律互补律交换律交换律ABBAABBAeeABBAA BB A结合律结合律()()()()ABCABCABCAB

23、 CABCABCABCABCeeee分配律分配律()()()()()()()A BCABACA BCABABCAB ACABCABACACee重叠律重叠律AAAA AA10AAAAeABA BABABABABABABee反演律反演律(摩根定理)调换律调换律ABCACBBCAABCACBBCA若，则，若，则，eeeABABABABABABeeeCBDBDAACF例：试简化函数例：试简化函数解：解：CBDBDAACF利用反演律利用反演律)BA(DCBACABDCBAC配项加配项加ABABABDABCBAC消因律消因律DABCBAC消项消项ABABDCBAC2.6.1公式化简法公式化简法n反复应用基

24、本公式和常用公式，消去多余的反复应用基本公式和常用公式，消去多余的乘积项和多余的因子。乘积项和多余的因子。 例：例： DBCBADCDBCBADEBAADCDBCBACDEBACBADCDBCBACCBADEBADBCACBADCDBCBACY )()()(2.6.1公式化简法公式化简法n反复应用基本公式和常用公式，消去多余的反复应用基本公式和常用公式，消去多余的乘积项和多余的因子。乘积项和多余的因子。 例：例： DBCBADCDBCBADEBAADCDBCBACDEBACBADCDBCBACCBADEBADBCACBADCDBCBACY)()()(2.6.1公式化简法公式化简法n反复应用基本

25、公式和常用公式，消去多余的反复应用基本公式和常用公式，消去多余的乘积项和多余的因子。乘积项和多余的因子。 例：例： DBCBADCDBCBADEBAADCDBCBACDEBACBADCDBCBACCBADEBADBCACBADCDBCBACY)()()(2.6.1公式化简法公式化简法n反复应用基本公式和常用公式，消去多余的反复应用基本公式和常用公式，消去多余的乘积项和多余的因子。乘积项和多余的因子。 例：例： DBCBADCDBCBADEBAADCDBCBACDEBACBADCDBCBACCBADEBADBCACBADCDBCBACY)()()(2.6.1公式化简法公式化简法n反复应用基本公式

26、和常用公式，消去多余的反复应用基本公式和常用公式，消去多余的乘积项和多余的因子。乘积项和多余的因子。 例：例： DBCBADCDBCBADEBAADCDBCBACDEBACBADCDBCBACCBADEBADBCACBADCDBCBACY)()()(2.6.2 卡诺图化简法卡诺图化简法 逻辑函数的卡诺图表示法逻辑函数的卡诺图表示法n实质：将逻辑函数的最小项之和以图形的方式实质：将逻辑函数的最小项之和以图形的方式表示出来表示出来n以以2n个小方块分别代表个小方块分别代表 n 变量的所有最小项，变量的所有最小项，并将它们排列成矩阵，而且使并将它们排列成矩阵，而且使几何位置相邻几何位置相邻的的两个最

27、小项在两个最小项在逻辑上也是相邻的逻辑上也是相邻的（只有一个变（只有一个变量不同），就得到表示量不同），就得到表示n变量全部最小项的卡变量全部最小项的卡诺图。诺图。 表示最小项的卡诺图表示最小项的卡诺图n二变量卡诺图二变量卡诺图 三三变量的卡诺图变量的卡诺图n4变量的卡诺图变量的卡诺图表示最小项的卡诺图表示最小项的卡诺图n二变量卡诺图二变量卡诺图 三三变量的卡诺图变量的卡诺图n4变量的卡诺图变量的卡诺图表示最小项的卡诺图表示最小项的卡诺图n二变量卡诺图二变量卡诺图 三三变量的卡诺图变量的卡诺图n4变量的卡诺图变量的卡诺图n五变量的卡诺图五变量的卡诺图用卡诺图表示逻辑函数用卡诺图表示逻辑函数1.

28、将函数表示为最小项之和的形式将函数表示为最小项之和的形式 。2.在卡诺图上与这些最小项对应的位置上添入在卡诺图上与这些最小项对应的位置上添入1，其余地方添其余地方添0。 im用卡诺图表示逻辑函数用卡诺图表示逻辑函数),()()(),CDDCDCCDBADBACCDCBABADBADCBADCBAY例：例：用卡诺图表示逻辑函数用卡诺图表示逻辑函数 用卡诺图化简函数用卡诺图化简函数n依据：具有相邻性的最小项可合并，消去依据：具有相邻性的最小项可合并，消去不同因子。不同因子。 n在卡诺图中，最小项的相邻性可以从图形在卡诺图中，最小项的相邻性可以从图形中直观地反映出来。中直观

29、地反映出来。n合并最小项的原则：合并最小项的原则：两个相邻最小项可合并为一项，消去一对因子两个相邻最小项可合并为一项，消去一对因子四个排成矩形的相邻最小项可合并为一项，消四个排成矩形的相邻最小项可合并为一项，消去两对因子去两对因子八个相邻最小项可合并为一项，消去三对因子八个相邻最小项可合并为一项，消去三对因子两个相邻最小项可合并为一项，两个相邻最小项可合并为一项，消去一对因子消去一对因子n化简步骤：化简步骤： -用卡诺图表示逻辑函数用卡诺图表示逻辑函数 -找出可合并的最小项找出可合并的最小项 -化简后的乘积项相加化简后的乘积项相加（项数最少，每项因子最少）（项数最少，每项因子最少） 用卡诺图化

30、简函数用卡诺图化简函数卡诺图化简的原则卡诺图化简的原则n化简后的乘积项应包含函数式的所有最小项，化简后的乘积项应包含函数式的所有最小项，即覆盖图中所有的即覆盖图中所有的1。n乘积项的数目最少，乘积项的数目最少，即圈成的矩形最少即圈成的矩形最少。n每个乘积项因子最少，每个乘积项因子最少，即圈成的矩形最大即圈成的矩形最大。例：例：CBCBCACACBAY),( 00 01 1 1 1 001ABC例：例：CBCBCACACBAY),( 00 01 1 1 1 00011111101CBCABAABC例：例：CBCBCACACBAY),( 00 01 1 1 1 00011111101ABCCBBA

31、CA例：例：CBCBCACACBAY),(CBCABACBBACA化化 简简 结结 果果 不不 唯唯 一一用卡诺图化简逻辑函数（1）画圈 相邻的 1 圈在一起，圈为矩形。 圈中 1 的个数为2n个 圈越大越好 所有的1必须圈完 1 可以重复圈，但每个圈中至少有一个未被圈过的1（2）合并最小项每个圈一项保留未变化的因子0100011110001110CDAB例：Y = AB + AC + BC + CDAB1111AC1111 BC1111CD1111Y = C + D + AB 最后将全部积项逻辑加即得最简与或表达式最后将全部积项逻辑加即得最简与或表达式0100011110001110CDAB

32、例：Y = A+ DY = ABC + ABD + CD +ABC + ACD + ACD111111111111例：Y = ABC + AB + AD + C + BD0100011110001110CDAB11111111111111Y = C+ D +B0100011110001110CDAB例：1111111Y = ABC D+ ABD + ACD +ABCDY = AC+ BD0100011110001110CDAB例：Y = A B C D+ A B C D +A B C D +A B C D + A B C D + A B C D1 111 1 1Y = BC+ BD例：Y =

33、M ( 5,7,13,15)0100011110001110CDAB0000 1 1 1 1 1 1 1 1 1 1 1 1Y = b + dn约束项约束项n任意项任意项n逻辑函数中的无关项：约束项和任意项可逻辑函数中的无关项：约束项和任意项可以写入函数式，也可不包含在函数式中，以写入函数式，也可不包含在函数式中，因此统称为无关项。因此统称为无关项。2.7具有无关项的逻辑函数及其化简具有无关项的逻辑函数及其化简2.7.1 约束项、任意项和逻辑函数式中的约束项、任意项和逻辑函数式中的无关项无关项AB（1）约束项约束：对输入变量所加的限制，这组变量叫做具有约束的变量例：水塔中装有两个水位检测传感器

34、，当水位高于传感器时，输出为1，否则为0，当水位高于A时，水位溢出报警器Y1输出为1，当水位低于B时，水位过低报警器Y2输出为1。 A B Y1 Y2 0 00 10 10 01 01 11 0约束项：不会出现的变量取值所对应的最小项 如果在输入变量的某些取值下，不管函数值是如果在输入变量的某些取值下，不管函数值是0 0还是还是1, 1,都不影响逻辑电路的功能；那末，在这些变量取值下，其都不影响逻辑电路的功能；那末，在这些变量取值下，其值等于值等于1 1的最小项称为任意项的最小项称为任意项. . 约束项和任意项统称为无关项约束项和任意项统称为无关项. . （2）任意项（3）无关项（4）无关项的表示无关项通常用无关项通常用d d ( (）表示。）表示。例：例：d d (m (m2 2，mm5 5，mm7 7） 约束项也可表示为约束项也可表示为 mm2 2mm5 5mm7 70 02.7.2 无关项在化简逻辑函数中无关项在化简逻辑函数中的应用的应用n合理地利用无关