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

第二章逻辑代数基础,数字电路,1.2.1逻辑代数与基本逻辑关系,在数字电路中，我们要研究的是电路的输入输出之间的逻辑关系，所以数字电路又称逻辑电路，相应的研究工具是逻辑代数（布尔代数）。,在逻辑代数中，逻辑函数的变量只能取两个值（二值变量），即0和1，中间值没有意义，这里的0和1只表示两个对立的逻辑状态，如电位的低高（0表示低电位，1表示高电位）、开关的开合等。,1.2逻辑代数及运算规则,（1）“与”逻辑,A、B、C条件都具备时，事件F才发生。,基本逻辑关系：,逻辑符号,F=ABC,逻辑式,真值表,（2）“或”逻辑,A、B、C只有一个条件具备时，事件F就发生。,逻辑符号,F=A+B+C,逻辑式,真值表,（3）“非”逻辑,A条件具备时，事件F不发生；A不具备时，事件F发生。,逻辑符号,逻辑式,真值表,A,F,0,1,1,0,（4）几种常用的逻辑关系,“与”、“或”、“非”是三种基本的逻辑关系，任何其它的逻辑关系都可以以它们为基础表示。,与非：条件A、B都具备，则F不发生。,或非：条件A、B任一具备，则F不发生。,异或：条件A、B有一个具备，另一个不具备则F发生。,（5）几种基本的逻辑运算,从三种基本的逻辑关系出发，我们可以得到以下逻辑运算结果：,00=01=10=0,11=1,0+0=0,0+1=1+0=1+1=1,1.2.2逻辑代数的基本定律,一、基本运算规则(0-1律),A+0=AA+1=1A0=0A=0A1=A,二、基本代数规律,交换律,结合律,分配律,A+B=B+A,AB=BA,A+(B+C)=(A+B)+C=(A+C)+B,A(BC)=(AB)C,A(B+C)=AB+AC,A+BC=(A+B)(A+C),三、吸收规则（吸收律）,1.原变量的吸收：,A+AB=A,证明：,A+AB=A(1+B)=A1=A,利用运算规则可以对逻辑式进行化简。,例如：,2.反变量的吸收：,证明：,例如：,3.混合变量的吸收：,证明：,例如：,4.代入定理：,在任何一个包含A的逻辑等式中，若以另外一个逻辑式代入式中A的位置，则等式依然成立。,5.反演定理：,对任一逻辑式,变换顺序先括号，然后乘，最后加,不属于单个变量的反号保留不变,例如：,5.反演定理（特例）：,可以用列真值表的方法证明：,6.对偶定理：,公式的对偶式为？,对任何一个逻辑式Y，,若两逻辑式相等，则它们的对偶式也相等。,1.3.1真值表：将输入、输出的所有可能状态一一对应地列出。,设A、B、C为输入变量，F为输出变量。,1.3逻辑函数的表示法,请注意,n个变量可以有2n个组合，一般按二进制的顺序，输出与输入状态一一对应，列出所有可能的状态。,1.3.2逻辑函数式,把逻辑函数的输入、输出关系写成与、或、非等逻辑运算的组合式，即逻辑代数式，又称为逻辑函数式，通常采用“与或”的形式。逻辑函数的两种标准形式：最小项之和最大项之积,若表达式的乘积项中包含了所有输入变量的原变量或反变量，则这一项称为最小项，上式中每一项都是最小项。,最小项m：m是乘积项包含n个因子n个变量均以原变量和反变量的形式在m中出现一次,最小项举例：,两变量A,B的最小项三变量A,B,C的最小项,最小项的编号：,最小项的性质,在输入变量任一取值下，有且仅有一个最小项的值为1。全体最小项之和为1。任何两个最小项之积为0。若两个最小项中只有一个变量以原、反状态相区别，则称它们为逻辑相邻。两个相邻的最小项之和可以合并，消去一对因子，只留下公共因子。,逻辑相邻的项可以合并，消去一个因子,逻辑函数最小项之和的形式：,例：,利用公式可将任何一个函数化为,逻辑函数最小项之和的形式：,例：,利用公式可将任何一个函数化为,逻辑函数最小项之和的形式：,例：,利用公式可将任何一个函数化为,1.3.3卡诺图：,将n个输入变量的全部最小项用小方块阵列图表示，并且将逻辑相临的最小项放在相临的几何位置上，所得到的阵列图就是n变量的卡诺图。,卡诺图的每一个方块（最小项）代表一种输入组合，并且把对应的输入组合注明在阵列图的上方和左方。,两变量卡诺图,三变量卡诺图,四变量卡诺图,函数取0、1均可，称为无所谓状态（或任意状）。,约束项任意项逻辑函数中的无关项：约束项和任意项可以写入函数式，也可不包含在函数式中，因此统称为无关项。,在逻辑函数中，值恒等于0的最小项称为约束项,函数值为1或为0不影响逻辑电路功能的最小项称为任意项,有时为了方便，用二进制对应的十进制表示单元编号。,F(A,B,C)=(1,2,4,7),1,2,4,7单元取1，其它取0,1.3.4逻辑图：,把相应的逻辑关系用逻辑符号和连线表示出来。,1.3.5波形图：,将输入变量所有取值可能与对应输出按时间顺序排列起来画成时间波形。,逻辑表达式,1.4.1利用逻辑代数的基本公式：,例：,1.4逻辑函数的化简,例：,反演,？,AB=AC,A+B=A+C,请注意与普通代数的区别！,1.4.2利用卡诺图化简：,AB,F=AB+BC,化简过程：,利用卡诺图化简的规则：,（1）相临单元的个数是2N个，并组成矩形时，可以合并。,（2）先找面积尽量大的组合进行化简，可以减少更多的因子，即圈成的矩形最大。,（3）各最小项可以重复使用。,（4）注意利用无所谓状态，可以使结果大大简化。,（5）所有的1都要被圈过，即覆盖图中所有的1。,（6）化简后的逻辑式是各化简项的逻辑和。,（7）化简结果不唯一。,例：化简,F(A,B,C,D)=(0,2,3,5,6,8,9,10,11,12,13,14,15),例：化简,例：已知真值表如图，用卡诺图化简。,化简时可以将无所谓状态当作1