数据结构C语言版》严蔚敏第二章逻辑代数基础.ppt

《数据结构C语言版》严蔚敏第二章逻辑代数基础.ppt》由会员分享，可在线阅读，更多相关《数据结构C语言版》严蔚敏第二章逻辑代数基础.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、（2-1）第二章第二章 逻辑代数基础逻辑代数基础数字电路数字电路（2-2）1.2.1 逻辑代数与基本逻辑关系逻辑代数与基本逻辑关系在数字电路中，我们要研究的是电路在数字电路中，我们要研究的是电路的输入输出之间的逻辑关系，所以数字电的输入输出之间的逻辑关系，所以数字电路又称路又称逻辑电路逻辑电路，相应的研究工具是，相应的研究工具是逻辑逻辑代数（布尔代数）代数（布尔代数）。在逻辑代数中，逻辑函数的变量只能在逻辑代数中，逻辑函数的变量只能取两个值（取两个值（二值变量二值变量），即），即0和和1，中间值，中间值没有意义，这里的没有意义，这里的0和和1只表示两个对立的只表示两个对立的逻辑状态，如电位的低

2、高（逻辑状态，如电位的低高（0表示低电位，表示低电位，1表示高电位）、开关的开合等。表示高电位）、开关的开合等。1.2 逻辑代数及运算规则逻辑代数及运算规则（2-3）（1）“与与”逻辑逻辑A、B、C条件都具备时，事件条件都具备时，事件F才发生。才发生。基本逻辑关系：基本逻辑关系：EFABC逻辑符号逻辑符号（2-4）F=ABC逻辑式逻辑式逻辑乘法逻辑乘法逻辑与逻辑与AFBC00001000010011000010101001101111真值表真值表（2-5）（2）“或或”逻辑逻辑A、B、C只有一个条件具备时，事件只有一个条件具备时，事件F就就发生。发生。逻辑符号逻辑符号AEFBC（2-6）F=A

3、+B+C逻辑式逻辑式逻辑加法逻辑加法逻辑或逻辑或AFBC00001001010111010011101101111111真值表真值表（2-7）（3）“非非”逻辑逻辑A条件具备时条件具备时，事件，事件F不发生；不发生；A不具备不具备时，事件时，事件F发生。发生。逻辑符号逻辑符号AEFR（2-8）逻辑式逻辑式逻辑非逻辑非逻辑反逻辑反真值表真值表AF0110（2-9）（4）几种常用的逻辑关系）几种常用的逻辑关系“与与”、“或或”、“非非”是三种基本的是三种基本的逻辑关系，任何其它的逻辑关系都可以以逻辑关系，任何其它的逻辑关系都可以以它们为基础表示。它们为基础表示。与非：与非：条件条件A、B都具备，都

4、具备，则则F 不发生。不发生。（2-10）或非：或非：条件条件A、B任任一一具备，具备，则则F不不 发生。发生。异或：异或：条件条件A、B有有一个具一个具备，另一个不备，另一个不具备则具备则F 发生。发生。（2-11）（5）几种基本的逻辑运算）几种基本的逻辑运算 从三种基本的逻辑关系出发，我们可从三种基本的逻辑关系出发，我们可以得到以下逻辑运算结果：以得到以下逻辑运算结果：0 0=0 1=1 0=01 1=10+0=00+1=1+0=1+1=1（2-12）1.2.2 逻辑代数的基本定律逻辑代数的基本定律一、基本运算规则一、基本运算规则(0-1律律)A+0=A A+1=1 A 0=0 A=0 A

5、 1=A（2-13）二、基本代数规律二、基本代数规律交换律交换律结合律结合律分配律分配律A+B=B+AA B=B AA+(B+C)=(A+B)+C=(A+C)+BA(B C)=(A B)CA(B+C)=A B+A CA+B C=(A+B)(A+C)普通代普通代数不适数不适用用!（2-14）三、吸收规则（吸收律）三、吸收规则（吸收律）1.原变量的吸收：原变量的吸收：A+AB=A证明：证明：A+AB=A(1+B)=A1=A利用运算规则可以对逻辑式进行化简。利用运算规则可以对逻辑式进行化简。例如：例如：被吸收被吸收（2-15）2.反变量的吸收：反变量的吸收：证明：证明：例如：例如：DCBCADCBC

6、AA+=+被吸收被吸收（2-16）3.混合变量的吸收：混合变量的吸收：证明：证明：例如：例如：1吸收吸收吸收吸收（2-17）4.代入定理：代入定理：在任何一个包含在任何一个包含A的逻辑等式中，若的逻辑等式中，若以另外一个逻辑式代入式中以另外一个逻辑式代入式中A的位置，则的位置，则等式依然成立。等式依然成立。例如：例如：A+BA+BC C =(A+B)(A+=(A+B)(A+C C)A+B(A+B(CDCD)=(A+B)(A+)=(A+B)(A+CDCD)=(A+B)(A+=(A+B)(A+C C)(A+)(A+D D)（2-18）5.反演定理：反演定理：对任一逻辑式对任一逻辑式 变换顺序变换顺

7、序 先括号，先括号，然后乘，最后加然后乘，最后加 不属于单个变量的不属于单个变量的反号保留不变反号保留不变（2-19）例如：例如：（2-20）5.反演定理（特例）：反演定理（特例）：可以用列真值表的方法证明：可以用列真值表的方法证明：（2-21）6.对偶定理：对偶定理：Y YD公式公式 的对偶式为？的对偶式为？对任何一个逻辑式对任何一个逻辑式Y，若两逻辑式相等，则它们的对偶式也相等。若两逻辑式相等，则它们的对偶式也相等。（2-22）1.3.1 真值表：将输入、输出的所有可能真值表：将输入、输出的所有可能 状态一一对应地列出。状态一一对应地列出。设设A、B、C为输入变量，为输入变量，F为输出变量

8、。为输出变量。1.3 逻辑函数的表示法逻辑函数的表示法（2-23）n个变量可以有个变量可以有2n个组合，一个组合，一般按二进制的顺序，输出与输入般按二进制的顺序，输出与输入状态一一对应，列出所有可能的状态一一对应，列出所有可能的状态。状态。（2-24）1.3.2 逻辑函数式逻辑函数式把逻辑函数的输入、输出关系写成把逻辑函数的输入、输出关系写成与与、或或、非非等逻辑运算的组合式，即等逻辑运算的组合式，即逻辑代数式逻辑代数式，又称为，又称为逻辑函数式逻辑函数式，通常采用，通常采用“与或与或”的的形式。逻辑函数的两种标准形式：形式。逻辑函数的两种标准形式：最小项之和最小项之和 最大项之积最大项之积比

9、如：比如：F=(A+B+C)(A+B+C)(A+B+C)（2-25）若表达式的乘积项中包含了所有输入变若表达式的乘积项中包含了所有输入变量的原变量或反变量，则这一项称为量的原变量或反变量，则这一项称为最小最小项项，上式中每一项都是，上式中每一项都是最小项最小项。最小项最小项 m：m是乘积项是乘积项 包含包含n个因子个因子 n个变量均以原变量和反变量的形个变量均以原变量和反变量的形式在式在m中出现一次中出现一次（2-26）最小项举例最小项举例：两变量两变量A,B的最小项的最小项三变量三变量A,B,C的最小项的最小项（2-27）最小项的编号最小项的编号：最小项最小项取值取值对应对应编号编号A B

10、C 十进制数十进制数0 0 0 0m00 0 1 1m10 1 0 2m20 1 1 3m31 0 0 4m41 0 1 5m51 1 0 6m61 1 1 7m7（2-28）最小项的性质最小项的性质在输入变量任一取值下，有且仅有一个最小项的在输入变量任一取值下，有且仅有一个最小项的值为值为1 1。全体最小项之和为全体最小项之和为1 1。任何两个最小项之积为任何两个最小项之积为0 0。若两个最小项中只有一个变量以原、反状态相区若两个最小项中只有一个变量以原、反状态相区别，则称它们为别，则称它们为逻辑相邻逻辑相邻。两个相邻的最小项之和可以合并，消去一对因子，只两个相邻的最小项之和可以合并，消去一

11、对因子，只留下公共因子。留下公共因子。（2-29）逻辑相邻逻辑相邻逻辑相邻的项可以逻辑相邻的项可以合并，消去一个因子合并，消去一个因子（2-30）逻辑函数最小项之和的形式逻辑函数最小项之和的形式：例例：利用公式利用公式可将任何一个函数化为可将任何一个函数化为（2-31）逻辑函数最小项之和的形式逻辑函数最小项之和的形式：例例：利用公式利用公式可将任何一个函数化为可将任何一个函数化为（2-32）逻辑函数最小项之和的形式逻辑函数最小项之和的形式：例例：利用公式利用公式可将任何一个函数化为可将任何一个函数化为（2-33）1.3.3 卡诺图：卡诺图：将将n个输入变量的全部最小项用小方块个输入变量的全部最

12、小项用小方块阵列图表示，并且将逻辑相临的最小项放阵列图表示，并且将逻辑相临的最小项放在相临的几何位置上，所得到的阵列图就在相临的几何位置上，所得到的阵列图就是是n变量的变量的卡诺图卡诺图。卡诺图的每一个方块（最小项）代表卡诺图的每一个方块（最小项）代表一种输入组合，并且把对应的输入组合注一种输入组合，并且把对应的输入组合注明在阵列图的上方和左方。明在阵列图的上方和左方。（2-34）AB0101ABC0001111001两变量卡诺图两变量卡诺图三变量卡诺图三变量卡诺图（2-35）ABCD0001111000011110四变量卡诺图四变量卡诺图单元编号单元编号0010，对，对应于最小应于最小项：项

13、：ABCD=0100时函时函数取值数取值函数取函数取0、1均可，均可，称为称为无所无所谓状态谓状态（或任意（或任意状）状）。只有只有一项一项不同不同（2-36）约束项约束项任意项任意项逻辑函数中的无关项：约束项和任意项可逻辑函数中的无关项：约束项和任意项可以写入函数式，也可不包含在函数式中，以写入函数式，也可不包含在函数式中，因此统称为因此统称为无关项无关项。在逻辑函数中，值恒等于在逻辑函数中，值恒等于在逻辑函数中，值恒等于在逻辑函数中，值恒等于0 0的的的的最小项称为约束项最小项称为约束项最小项称为约束项最小项称为约束项函数值为函数值为函数值为函数值为1 1或为或为或为或为0 0不影响逻辑电

14、路不影响逻辑电路不影响逻辑电路不影响逻辑电路功能的最小项称为任意项功能的最小项称为任意项功能的最小项称为任意项功能的最小项称为任意项（2-37）有时为了方便，用二进制对应的十进制有时为了方便，用二进制对应的十进制表示单元编号。表示单元编号。ABC0001111001F(A,B,C)=(1,2,4,7)1,2,4,7单单元取元取1，其，其它取它取0（2-38）ABCD0001111000011110（2-39）1.3.4 逻辑图：逻辑图：把相应的逻辑关系用逻辑符号和把相应的逻辑关系用逻辑符号和连线表示出来。连线表示出来。（2-40）1.3.5 波形图：波形图：将输入变量所有取值可能与对应输出按将

15、输入变量所有取值可能与对应输出按时间顺序排列起来画成时间波形。时间顺序排列起来画成时间波形。（2-41）逻辑图逻辑图波形图波形图真值表真值表逻辑表达式逻辑表达式卡诺图卡诺图（2-42）1.4.1 利用逻辑代数的基本公式：利用逻辑代数的基本公式：例：例：反变量吸收反变量吸收提出提出AB=1提出提出A 1.4 逻辑函数的化简逻辑函数的化简（2-43）例：例：反演反演配项配项被吸收被吸收被吸收被吸收（2-44）AB=ACB=C?A+B=A+CB=C?请注意与普通代数的区别！请注意与普通代数的区别！（2-45）1.4.2 利用卡诺图化简：利用卡诺图化简：ABC0001111001（2-46）ABC00

16、01111001AB?（2-47）ABC0001111001ABBCF=AB+BC化简过程：化简过程：（2-48）利用卡诺图化简的规则：利用卡诺图化简的规则：（1）相临单元的个数是）相临单元的个数是2N个，并组成矩形个，并组成矩形时，可以合并。时，可以合并。ABCD0001 11 1000011110AD（2-49）ABCD0001 11 1000011110不是矩形不是矩形（2-50）（2）先找面积尽量大的组合进行化简，可以）先找面积尽量大的组合进行化简，可以 减少更多的因子，减少更多的因子，即圈成的矩形最大即圈成的矩形最大。（3）各最小项可以重复使用。）各最小项可以重复使用。（4）注意利用

17、无所谓状态，可以使结果大大）注意利用无所谓状态，可以使结果大大 简化。简化。（5）所有的）所有的1都要被圈过，都要被圈过，即覆盖图中所有 的1。（6）化简后的逻辑式是各化简项的逻辑和。）化简后的逻辑式是各化简项的逻辑和。（7）化简结果不唯一。）化简结果不唯一。（2-51）例：化简例：化简 F(A,B,C,D)=(0,2,3,5,6,8,9,10,11,12,13,14,15)ABCD0001 11 1000011110A（2-52）例：化简例：化简ABCD0001 11 1000011110ABD（2-53）例：已知真值表如图，用卡诺图化简。例：已知真值表如图，用卡诺图化简。101状态未给出，

18、即是无所谓状态。状态未给出，即是无所谓状态。（2-54）ABC0001111001化简时可以将无所谓状态当作化简时可以将无所谓状态当作1或或0，目的是得到最简结果。目的是得到最简结果。认为是认为是1AF=A（2-55）0001111000101111101ABCD例例（2-56）0001111000 01x001 0 x1011x0 xx10 1x0 xABCD（2-57）0001111000 01x001 0 x1011x0 xx10 1x0 xABCD（2-58）0001111000 000101 1x0111 xxxx10 10 xxABCD例例（2-59）第二章第二章 作业作业P62 2.15 (6)(7)(8)(9)(10)P63 2.19 (4)(5)2.20 (b)(d)P64 2.22 (3)(4)2.23 (3)(4)