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

第二章逻辑代数基础数字电路数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第1页!1.2.1逻辑代数与基本逻辑关系在数字电路中，我们要研究的是电路的输入输出之间的逻辑关系，所以数字电路又称逻辑电路，相应的研究工具是逻辑代数（布尔代数）。在逻辑代数中，逻辑函数的变量只能取两个值（二值变量），即0和1，中间值没有意义，这里的0和1只表示两个对立的逻辑状态，如电位的低高（0表示低电位，1表示高电位）、开关的开合等。§1.2逻辑代数及运算规则数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第2页!（1）“与”逻辑A、B、C条件都具备时，事件F才发生。基本逻辑关系：EFABC逻辑符号数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第3页!F=A•B•C逻辑式逻辑乘法逻辑与AFBC00001000010011000010101001101111真值表数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第4页!F=A+B+C逻辑式逻辑加法逻辑或AFBC00001001010111010011101101111111真值表数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第5页!逻辑式逻辑非逻辑反真值表AF0110数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第6页!或非：条件A、B任一具备，则F不发生。异或：条件A、B有一个具备，另一个不具备则F发生。数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第7页!1.2.2逻辑代数的基本定律一、基本运算规则(0-1律)A+0=AA+1=1A·0=0·A=0A·1=A数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第8页!三、吸收规则（吸收律）1.原变量的吸收：A+AB=A证明：A+AB=A(1+B)=A•1=A利用运算规则可以对逻辑式进行化简。例如：被吸收数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第9页!3.混合变量的吸收：证明：例如：1吸收吸收数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第10页!5.反演定理：对任一逻辑式

变换顺序先括号，然后乘，最后加

不属于单个变量的反号保留不变数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第11页!5.反演定理（特例）：可以用列真值表的方法证明：数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第12页!1.3.1真值表：将输入、输出的所有可能状态一一对应地列出。设A、B、C为输入变量，F为输出变量。§1.3逻辑函数的表示法

数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第13页!1.3.2逻辑函数式把逻辑函数的输入、输出关系写成与、或、非等逻辑运算的组合式，即逻辑代数式，又称为逻辑函数式，通常采用“与或”的形式。逻辑函数的两种标准形式：最小项之和

最大项之积比如：F=(A+B+C)(A’+B+C’)(A+B’+C’)数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第14页!最小项举例：两变量A,B的最小项三变量A,B,C的最小项数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第15页!最小项的性质在输入变量任一取值下，有且仅有一个最小项的值为1。全体最小项之和为1。任何两个最小项之积为0。若两个最小项中只有一个变量以原、反状态相区别，则称它们为逻辑相邻。两个相邻的最小项之和可以合并，消去一对因子，只留下公共因子。数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第16页!逻辑函数最小项之和的形式：例：利用公式可将任何一个函数化为数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第17页!逻辑函数最小项之和的形式：例：利用公式可将任何一个函数化为数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第18页!AB0101ABC0001111001两变量卡诺图三变量卡诺图数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第19页!约束项任意项逻辑函数中的无关项：约束项和任意项可以写入函数式，也可不包含在函数式中，因此统称为无关项。在逻辑函数中，值恒等于0的最小项称为约束项函数值为1或为0不影响逻辑电路功能的最小项称为任意项数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第20页!ABCD0001111000011110数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第21页!1.3.5波形图：将输入变量所有取值可能与对应输出按时间顺序排列起来画成时间波形。数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第22页!1.4.1利用逻辑代数的基本公式：例：反变量吸收提出AB=1提出A

§

1.4逻辑函数的化简数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第23页!？AB=ACB=C?A+B=A+CB=C?请注意与普通代数的区别！数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第24页!ABC0001111001AB?数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第25页!利用卡诺图化简的规则：（1）相临单元的个数是2N个，并组成矩形时，可以合并。ABCD0001111000011110AD数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第26页!（2）先找面积尽量大的组合进行化简，可以减少更多的因子，即圈成的矩形最大。（3）各最小项可以重复使用。（4）注意利用无所谓状态，可以使结果大大简化。（5）所有的1都要被圈过，即覆盖图中所有 的1

。（6）化简后的逻辑式是各化简项的逻辑和。（7）化简结果不唯一。数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第27页!例：化简ABCD0001111000011110ABD数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第28页!ABC0001111001化简时可以将无所谓状态当作1或0，目的是得到最简结果。认为是1AF=A数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第29页!000111100001x0010x1011x0xx101x0xABCD数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第30页!00011110000001011x0111xxxx1010xxABCD例数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第31页!（2）“或”逻辑A、B、C只有一个条件具备时，事件F就发生。逻辑符号AEFBC数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第32页!（3）“非”逻辑A条件具备时，事件F不发生；A不具备时，事件F发生。逻辑符号AEFR数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第33页!（4）几种常用的逻辑关系“与”、“或”、“非”是三种基本的逻辑关系，任何其它的逻辑关系都可以以它们为基础表示。与非：条件A、B都具备，则F不发生。数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第34页!（5）几种基本的逻辑运算从三种基本的逻辑关系出发，我们可以得到以下逻辑运算结果：0•0=0•1=1•0=01•1=10+0=00+1=1+0=1+1=1数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第35页!二、基本代数规律交换律结合律分配律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)普通代数不适用!数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第36页!2.反变量的吸收：证明：例如：DCBCADCBCAA++=++被吸收数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第37页!4.代入定理：在任何一个包含A的逻辑等式中，若以另外一个逻辑式代入式中A的位置，则等式依然成立。例如：A+BC=(A+B)(A+C)A+B(CD)=(A+B)(A+CD) =(A+B)(A+C)(A+D)数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第38页!例如：数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第39页!6.对偶定理：YYD公式的对偶式为？对任何一个逻辑式Y，若两逻辑式相等，则它们的对偶式也相等。数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第40页!请注意n个变量可以有2n个组合，一般按二进制的顺序，输出与输入状态一一对应，列出所有可能的状态。数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第41页!若表达式的乘积项中包含了所有输入变量的原变量或反变量，则这一项称为最小项，上式中每一项都是最小项。最小项m：m是乘积项包含n个因子n个变量均以原变量和反变量的形式在m中出现一次数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第42页!最小项的编号：最小项取值对应编号ABC十进制数0000m00011m10102m20113m31004m41015m51106m61117m7数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第43页!逻辑相邻逻辑相邻的项可以合并，消去一个因子数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第44页!逻辑函数最小项之和的形式：例：利用公式可将任何一个函数化为数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第45页!1.3.3卡诺图：将n个输入变量的全部最小项用小方块阵列图表示，并且将逻辑相临的最小项放在相临的几何位置上，所得到的阵列图就是n变量的卡诺图。卡诺图的每一个方块（最小项）代表一种输入组合，并且把对应的输入组合注明在阵列图的上方和左方。数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第46页!ABCD0001111000011110四变量卡诺图单元编号0010，对应于最小项：ABCD=0100时函数取值函数取0、1均可，称为无所谓状态（或任意状）。只有一项不同数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第47页!有时为了方便，用二进制对应的十进制表示单元编号。ABC0001111001F(A,B,C)=(1,2,4,7)1,2,4,7单元取1，其它取0数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第48页!1.3.4逻辑图：把相应的逻辑关系用逻辑符号和连线表示出来。数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第49页!逻辑图波形图真值表逻辑表达式卡诺图数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第50页!例：反演配项被吸收被吸收数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第51页!1.4.2利用卡诺图化简：ABC0001111001数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现在浏览的是第52页!ABC0001111001ABBCF=AB+BC化简过程：数据结构C语言版》严蔚敏第二章逻辑代数基础共59页，您现