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

第二章逻辑代数基础数字电路1.2.1逻辑代数与基本逻辑关系在数字电路中，我们要研究的是电路的输入输出之间的逻辑关系，所以数字电路又称逻辑电路，相应的研究工具是逻辑代数（布尔代数）。在逻辑代数中，逻辑函数的变量只能取两个值（二值变量），即0和1，中间值没有意义，这里的0和1只表示两个对立的逻辑状态，如电位的低高（0表示低电位，1表示高电位）、开关的开合等。§1.2逻辑代数及运算规则（1）“与”逻辑A、B、C条件都具备时，事件F才发生。基本逻辑关系：EFABC逻辑符号（2）“或”逻辑A、B、C只有一个条件具备时，事件F就发生。逻辑符号AEFBCF=A+B+C逻辑式逻辑加法逻辑或AFBC00001001010111010011101101111111真值表（3）“非”逻辑A条件具备时，事件F不发生；A不具备时，事件F发生。逻辑符号AEFR（4）几种常用的逻辑关系“与”、“或”、“非”是三种基本的逻辑关系，任何其它的逻辑关系都可以以它们为基础表示。与非：条件A、B都具备，则F不发生。或非：条件A、B任一具备，则F不发生。异或：条件A、B有一个具备，另一个不具备则F发生。（5）几种基本的逻辑运算从三种基本的逻辑关系出发，我们可以得到以下逻辑运算结果：0•0=0•1=1•0=01•1=10+0=00+1=1+0=1+1=1二、基本代数规律交换律结合律分配律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)普通代数不适用!三、吸收规则（吸收律）1.原变量的吸收：A+AB=A证明：A+AB=A(1+B)=A•1=A利用运算规则可以对逻辑式进行化简。例如：被吸收2.反变量的吸收：证明：例如：DCBCADCBCAA++=++被吸收4.代入定理：在任何一个包含A的逻辑等式中，若以另外一个逻辑式代入式中A的位置，则等式依然成立。例如：A+BC=(A+B)(A+C)A+B(CD)=(A+B)(A+CD) =(A+B)(A+C)(A+D)5.反演定理：对任一逻辑式

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

不属于单个变量的反号保留不变例如：6.对偶定理：YYD公式的对偶式为？对任何一个逻辑式Y，若两逻辑式相等，则它们的对偶式也相等。1.3.1真值表：将输入、输出的所有可能状态一一对应地列出。设A、B、C为输入变量，F为输出变量。§1.3逻辑函数的表示法

请注意n个变量可以有2n个组合，一般按二进制的顺序，输出与输入状态一一对应，列出所有可能的状态。若表达式的乘积项中包含了所有输入变量的原变量或反变量，则这一项称为最小项，上式中每一项都是最小项。最小项m：m是乘积项包含n个因子n个变量均以原变量和反变量的形式在m中出现一次最小项举例：两变量A,B的最小项三变量A,B,C的最小项逻辑相邻逻辑相邻的项可以合并，消去一个因子逻辑函数最小项之和的形式：例：利用公式可将任何一个函数化为逻辑函数最小项之和的形式：例：利用公式可将任何一个函数化为逻辑函数最小项之和的形式：例：利用公式可将任何一个函数化为1.3.3卡诺图：将n个输入变量的全部最小项用小方块阵列图表示，并且将逻辑相临的最小项放在相临的几何位置上，所得到的阵列图就是n变量的卡诺图。卡诺图的每一个方块（最小项）代表一种输入组合，并且把对应的输入组合注明在阵列图的上方和左方。AB0101ABC0001111001两变量卡诺图三变量卡诺图ABCD0001111000011110四变量卡诺图单元编号0010，对应于最小项：ABCD=0100时函数取值函数取0、1均可，称为无所谓状态（或任意状）。只有一项不同约束项任意项逻辑函数中的无关项：约束项和任意项可以写入函数式，也可不包含在函数式中，因此统称为无关项。在逻辑函数中，值恒等于0的最小项称为约束项函数值为1或为0不影响逻辑电路功能的最小项称为任意项有时为了方便，用二进制对应的十进制表示单元编号。ABC0001111001F(A,B,C)=(1,2,4,7)1,2,4,7单元取1，其它取0ABCD00011110000111101.3.4逻辑图：把相应的逻辑关系用逻辑符号和连线表示出来。1.3.5波形图：将输入变量所有取值可能与对应输出按时间顺序排列起来画成时间波形。逻辑图波形图真值表逻辑表达式卡诺图1.4.1利用逻辑代数的基本公式：例：反变量吸收提出AB=1提出A

§

1.4逻辑函数的化简例：反演配项被吸收被吸收？AB=ACB=C?A+B=A+CB=C?请注意与普通代数的区别！1.4.2利用卡诺图化简：ABC0001111001ABC0001111001AB?ABC0001111001ABBCF=AB+BC化简过程：利用卡诺图化简的规则：（1）相临单元的个数是2N个，并组成矩形时，可以合并。ABCD0001111000011110ADABCD0001111000011110不是矩形（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)ABCD0001111000011110A例：化简ABCD0001111000011110ABD例：已知真值表如图，用卡诺图化简。101状态未给出，即是无所谓状态。ABC0001111001化简时可以将无所谓状态当作1或0，目的是得到最简结果。认为是1AF=A0001111000101111101ABCD例000111100001x0010x1011x0xx101x0xABCD000111100001x0010x1011x0xx101x0xABCD00011110000001011x