《逻辑代数基础》doc版.doc

数字逻辑（毛法尧编著）教案 李澄举 面向21世纪教材 羆羀莂袆袂罿蒄蚈螈肈薇蒁肆肇芆蚇羂肆荿葿羈肆薁蚅袄肅芁薈螀肄莃螃聿肃蒅薆羅肂薇螂袁膁芇薄螇膁荿螀蚃膀蒂薃肁腿芁袈羇膈莄蚁袃膇蒆袆蝿膆薈虿肈膅芈蒂羄芅莀蚈袀芄蒃蒀螆芃膂蚆蚂节莅葿肀芁蒇螄羆芀蕿薇袂艿艿螂螈艿莁薅肇莈蒃螁羃莇薆薃衿莆芅蝿螅羂蒈薂螁羂薀袇肀羁芀蚀羆羀莂袆袂罿蒄蚈螈肈薇蒁肆肇芆蚇羂肆荿葿羈肆薁蚅袄肅芁薈螀肄莃螃聿肃蒅薆羅肂薇螂袁膁芇薄螇膁荿螀蚃膀蒂薃肁腿芁袈羇膈莄蚁袃膇蒆袆蝿膆薈虿肈膅芈蒂羄芅莀蚈袀芄蒃蒀螆芃膂蚆蚂节莅葿肀芁蒇螄羆芀蕿薇袂艿艿螂螈艿莁薅肇莈蒃螁羃莇薆薃衿莆芅蝿螅羂蒈薂螁羂薀袇肀羁芀蚀羆羀莂袆袂罿蒄蚈螈肈薇蒁肆肇芆蚇羂肆荿葿羈肆薁蚅袄肅芁薈螀肄莃螃聿肃蒅薆羅肂薇螂袁膁芇薄螇膁荿螀蚃膀蒂薃肁腿芁袈羇膈莄蚁袃膇蒆袆蝿膆薈虿肈膅芈蒂羄芅莀蚈袀芄蒃蒀螆芃膂蚆蚂节莅葿肀芁蒇螄羆芀蕿薇袂艿艿螂螈艿莁薅肇莈蒃螁羃莇薆薃衿莆芅蝿螅羂蒈薂螁羂薀袇肀羁芀蚀羆羀莂袆袂罿蒄蚈螈肈薇蒁肆肇芆蚇羂肆荿葿羈肆薁蚅袄肅芁薈螀肄莃螃聿肃蒅 第二章 逻辑代数基础教学重点：掌握逻辑代数的基本概念、定理和规则、逻辑函数的表示法、函数的卡诺图化简。教学难点：逻辑代数定理和规则的应用，各种逻辑表达式之间的转换方法。21逻辑代数的基本概念建立逻辑代数的概念，以区别普通代数，不能简单地把普通代数的规律照搬到逻辑代数中来。211 逻辑变量 逻辑代数中也用字母代表变量，但通常用一个字母代表一个变量。逻辑变量的取值只能是“0”或“1”，代表的是事物矛盾着的双方；判断事件的“真伪”和“是非”，无大小和正负之分。在数字系统中，代表开关的接通现断开，晶体管的导通与截止，电压的高(5V)低(0V)，信号的有无等。212 逻辑运算三种基本的逻辑运算：“或” 、“与”、 “非”。“或” 运算概念：着重因果关系。“或” 运算关系表达式：F=A+B 或者 F=AB。“或” 运算口诀：“有1出1”和“都0出0”。“与” 运算概念：着重因果关系。“与” 运算关系表达式：F=AB，或者 F=AB ，或者 F=AB。“或” 运算口诀：“有0出0”和“都1出1”。“非” 运算概念：着重因果关系。“非” 运算关系表达式：F=，或者 F= A。“非” 运算口诀：“反0出1”和“反1出0”。213 逻辑函数逻辑表达式：用基本逻辑运算符把逻辑变量连结起来的式子。逻辑函数：概念与普通代数一样，不过，在逻辑代数中，将自变量叫做输入变量，将因变量(函数)叫做输出变量。输入变量和输出变量(函数)的取值都只能是0或1；逻辑函数与输入变量之间的对应关系是由三种基本逻辑运算决定的。逻辑函数的相等：要求很严格，对应于输入变量的任何一组取值组合，两个函数的值都应该相同，这两个逻辑函数才相等。否则为不相等。例如：可用真值表验证两函数和是否相等。列表时，应将输入变量写在表的左边，输出变量写在表的右边。n个输入变量的2n个取值组合一个也不能漏，这要养成按000111递增的顺序填写的习惯。22逻辑代数的公理、定理及规则221逻辑代数的公理和基本定理1公理系统：如交换律、结合律、分配律、01律、互补律等共5个公理。其中应注意到加法也有分配律：。2基本定理：共有8个基本定理，其中每个定理中又有两个互为对偶式的定理，课文只证明其中一个。定理3可用来消去一个或项，定理4可用来消去一个因子，定理6是摩根定理，定理7用来将两个或项合并成一项，定理8用来消去冗余项。应用这些定理可将一个逻辑表达式简化。简化逻辑表达式在数字逻辑设计中有着重要意义，一方面它可以节约元件，降低成本；另一方面可以提高逻辑电路的可靠性。222逻辑代数的重要规则 1代入规则：用于从一个公式推导出更多的公式。 2反演规则：用于方便地求出一个函数的反函数。方法是：将函数表达式中的所有逻辑变量变反，并将“”和“”号互换、“0”和“1” 数字互换即得这个函数的反函数。 3对偶规则：用于方便地证明一个逻辑等式。方法是：将函数表达式中的所有的 “”和“”号互换、“0”和“1” 数字互换即得这个函数的对偶函数。将一个等式两边的逻辑表达式都变成对应的对偶式，这两个对偶式仍然相等。这在证明逻辑等式时十分有用。当一个逻辑等式较难证明时，往往用它们的对偶式来证明。23 逻辑函数表达式的形式与转换231 逻辑函数的表示法 1逻辑表达式：所谓“公式法”。由逻辑变量、常量和运算符号所构成的式子。2真值表：所谓“表格法”。一般用于不超过4变量的逻辑函数。因为如果有5变量的逻辑函数，这个真值表就应有2532行，随着变量数目增多，真值表的行数急剧增大。3卡诺图：所谓“图形法”。一般用于不超过6变量的逻辑函数，不同变量数的卡诺图形状不同。有时相同变量数的卡诺图形状也可设计成不同，这视方便而定。232 逻辑函数表达式的基本形式 两种基本形式：“积之和”表达式和“和之积” 表达式。“积之和”表达式即“与或”表达式；“和之积”表达式即“或与”表达式。233 逻辑函数表达式的标准形式 1最小项表达式：又称标准“与或”表达式。表达式中的每一个“与”项都是最小项。什么是“最小项”？什么是最小项表达式？最小项的性质：对于输入变量的每一种取值组合，只有一个最小项的值为1，其余的最小项的值皆为0。即最小项为1的几率最小。任何两个最小项的乘积为0。n个变量的所有2n个最小项之“和”恒为1。(或运算是“有1出1”)。一个逻辑函数可以有许多不同的“与或”表达式，但它的最小项表达式却是唯一的。最小项表达式的简化写法：F(A,B,C)=m(2,3,6,7)= m2m3 m6 m7,要注意输入变量写法的顺序。 2最大项表达式：又称标准“或与”表达式。表达式中的每一个因子项都是最大项。什么是“最大项”？什么是最大项表达式？最小项的性质：对于输入变量的每一种取值组合，只有一个最小项的值为0，其余的最小项的值皆为1。即最小项为1的几率最大。任何两个最小项的乘积为0。n个变量的所有2n个最小项之“积”恒为0。(与运算是“有0出0”)。一个逻辑函数可以有许多不同的“或与”表达式，但它的最大项表达式却是唯一的。最大项表达式的简化写法：F(A,B,C)=M(2,3,6,7)= M2M3M6M7,也要注意输入变量写法的顺序。 3两种标准形式之间的关系 最小项和最大项之间的关系：互补关系。即有Mi 或者 mi；如三个变量ABC的逻辑函数的一个最小项为，则234 逻辑函数表达式的转换 1代数转换法 代数转换法是利用逻辑代数的公理、定理和规则对函数表达式进行逻辑变换。应注意：变换出来的函数表达式是和原函数表达式相等的。转换成最小项表达式(标准“与或”表达式)的步骤：转换成一般“与或”表达式。将一般“与或”表达式中非最小项都扩展成最小项。例如三个变量ABC的逻辑函数表达式F=A +中，两项都是非最小项。第一项少B和C两个因子，第二项少一个A因子。缺少哪个因子就乘以这个因子的互补项之和。如A=A(B+)(C+)，=( A+)。展开即得各个最小项。转换成最大项表达式(标准“或与”表达式)的步骤：转换成一般“或与”表达式。将一般“或与”表达式中非最大项都扩展成最大项。例如F(A,B,C)=A +=(A+)(A+C) （应用加法的分配律），第一个因子缺少C，应加上这个变量的互补项之积C，第二个因子缺少B，应加上这个变量的互补项之积B，然后再分别应用加法分配律。如(A+)=(A+ C)=(A+ C)(A+)；(=M2M3)(A+C)= (A+C+ B) =(A + B+C)(A +C)；(=M0M2)故F(A,B,C)=A +=(A+ B + C) (A+ C)(A+)；(= M0M2M3)。 2真值表转换法 一个逻辑函数的真值表与它的“最小项之和”的形式有一一对应的关系。有了真值表，就可以方便快捷地写出这个逻辑函数的“最小项之和”的形式，以及“最大项之积”的形式。由真值表出逻辑函数的“最小项之和”的形式：取出函数值为1的那些最小项相加。由真值表出逻辑函数的“最大项之积”的形式：取出函数值为0的那些最大项相与。(参见P41表2.9真值表和P42表2.10真值表)24 逻辑函数的化简逻辑函数化简的必要性：逻辑函数是设计逻辑电路的依据。如果一个“与或”逻辑表达式的项数越少，每一个“与”项的变量数目越少，那么所设计的逻辑电路所用的元件就越少，复杂程度秒越低，成本就越便宜，并且可靠性越高。逻辑函数的最小化：把逻辑函数化简成最简形式。化简方法：2 代数化简法因技巧性强，故不作要求。必须指出：“或与”表达式的化简方法是：先将它的对偶式化成最简的“与与”表达式，然后再将它转化成对偶式。(“或与”表达式的对偶式是“或与”表达式，再求对偶式就是“或与”表达式)22 卡诺图化简法1. 卡诺图的构成形状：二变量卡诺图有22=4个小方格；三变量卡诺图有23=8个小方格；四变量卡诺图有24=16个小方格；一般4个小方格和16个小方格的卡诺图组成正方形；8个小方格的卡诺图组成长方形。(当然，也有五变量和六变量的卡诺图，它们有不同的设计方法) 坐标轴：也有横轴和纵轴。与普通代数中的平面直角坐标轴的称呼不太相同。下面的方法把坐标轴和变量联系起来记忆，可以方便学习。二变量(A,B)卡诺图的横轴称为A横轴，纵轴称为B纵轴；三变量(A,B,C)卡诺图的横轴称为AB横轴，纵轴称为C纵轴；四变量(A,B,C,D)卡诺图的横轴称为AB横轴，纵轴称为CD纵轴。坐标： 横坐标从左到右，纵坐标从上到下都按升序。 当坐标轴为一个变量时，升序为0，1。如A横轴，对应坐标为，A。余类推。 当坐标轴为二个变量时，升序为00，01，11，10。(注意：这种升序是二进制数00，01，10，11对应的格雷码)， 如AB横轴，对应坐标为，B，AB，A。余类推。 当坐标轴为三个变量时，升序为000，001，011，010，110，111，101，100。(注意：这种升序是二进制数000，001，010，011，100，101，110，111对应的格雷码)卡诺图中小方格的内容： 每一个小方格代表一个最小项。如同平面直角坐标系一样，平面上的每一个点的坐标是先横后列。例如四变量的卡诺图中，最小项m5对应的AB横轴坐标为01(即为B)，CD纵轴坐标为01(即为D)，故m5=BD。2. 逻辑函数在卡诺图上的表示若逻辑函数表达式是“最小项之和”的形式，如F(A,B,C)=m(2,3,6,7)= m2m3 m6 m7,则在直接在三变量卡诺图中对应m2、m3、m6、m7的小方格内填1，其余方格填0。填1的方格称为1方格，填0的方格称为0方格。一般不填0方格，以求图象清淅。若逻辑函数是“与或” 表达式，如F(A,B,C)= C+B +AC +BC在三变量卡诺图中，填C时，因只有一个横坐标，故应先在AB横轴上找出开始为0的坐标 (这个0对应着)：00和01的两列，然后在C纵轴上找出坐标为1的一列，这样就在卡诺图中找到了001和011的两个1方格。相当于C+BC=C。填B时，因只有横坐标，无纵坐标，故在AB横轴上找出坐标01后，在这一列的所有两个小方格内填1(即两个1方格)。相当于BC+B=B。填BC时，因只有一个横坐标B，故应先在AB横轴上找出第二个坐标为1的坐标 (这个1对应着B)的11和01的两列，然后在C纵轴上找出坐标为1的一列，这样就在卡诺图中找到了111和011的两个1方格。相当于ABC+BC=BC。填AC时，因它是最小项，故在AB横轴上找出坐标10后，然后在C纵轴上找出坐标为1的一列，就找到了101这个小方格。注意：如果在一个小方格内填了两个1，最后就以一个1代替。因1+1=1。这个例子告诉我们，用逻辑函数“与或” 表达式填图，不必先转化成最小项表达式，可以用这种方法直接填图，简化填图手续。3.卡诺图上最小项的合并卡诺图的一个重要应用就是把逻辑函数简化成最简“与或”表达式或者“或与”表达式。相邻的概念：几何相邻，逻辑相邻。两个相邻项(1方格)可以合并成一项，并且消去一个变量。四个相邻项(1方格)可以合并成一项，并且消去两个变量。八个相邻项(1方格)可以合并成一项，并且消去三个变量。十六个相邻项(1方格)可以合并成一项，并且消去四个变量。(若一个卡诺图中所有的方格都是1方格，则合并后变量全部消去，这项为1。)参看P50P51画圈的各种情况。说明圈里面1方格的个数一定要为2n个(n=0,1,2,3)，不能是3个、5个、6个、7个等等。4.用卡诺图化简逻辑函数用卡诺图一定能将逻辑函数化成最简的“与或”或者“或与”表达式。但最简的表达式不一定是唯一的。最简“与或”表达式的化简步骤：第一步：将逻辑函数填图。第二步：对卡诺图中的方格画卡诺圈。在满足合并条件下，卡诺圈应尽可能大；(一个卡诺圈对应一个“与”项，圈越大，这一项变量的个数就越少。)实际上，按照逻辑函数的代入规则，一个方格卡诺圈对应这个逻辑函数的一个子函数。在覆盖所有方格的前提下，卡诺圈的个数应尽可能小；(一个卡诺圈对应一个“与”项，圈的个数越少，逻辑函数的项数就越少。)每个方格可根据合并的需要被多个卡诺圈包含，但至少应被一个卡诺圈包含；每个卡诺圈中应至少有一个方格只被一个卡诺圈包含。否则会多出冗余项。第三步：将卡诺图上所有卡诺圈对应的“与”项相“或”，得到逻辑函数的最简“与或”表达式。例2.11用卡诺图化简逻辑函数F(A,B,C,)= m (2,3,4,7,10,11,13,15)参看P53图2.14。最简“与或”表达式为F(A,B,C,)=CD+C+ABD+B。例2.12用卡诺图化简逻辑函数F(A,B,C,)= +AC+B+ AB+C参看P53图2.15。 如图可见，有两种画圈方法，说明最简“与或”表达式不是唯一的。最简“与或”表达式为F(A,B,C,)=+BD+CD+AB 或者F(A,B,C,)=+BD+C+A最简“或与”表达式的化简步骤：第一步：将逻辑函数填图。第二步：对卡诺图中的0方格画卡诺圈。在满足合并条件下，卡诺圈应尽可能大；(一个卡诺圈对应一个“或”项，圈越大，这一项变量的个数就越少。)实际上，因一个1方格卡诺圈对应这个逻辑函数的一个子函数，故一个0方格卡诺圈就对应一个子函数的反函数。在覆盖所有0方格的前提下，卡诺圈的个数应尽可能小；(一个卡诺圈对应一个“或”项，圈的个数越少，逻辑函数的项数就越少。)每个0方格可根据合并的需要被多个卡诺圈包含，但至少应被一个卡诺圈包含；每个卡诺圈中应至少有一个方格只被一个卡诺圈包含。否则会多出冗余项。第三步：将卡诺图上所有卡诺圈对应的“或”项相“与”，得到逻辑函数的最简“或与”表达式。在写出0方格卡诺圈对应的“或”项时，应先写出这个0方格卡诺圈对应的子反函数“与”项，然后对它求反，即得子函数“或”项。例2.11 的最简“或与”表达式为：F = (B+C)(A+C+)(+C+D)(+D)。例2.13 用卡诺图求函数的最简或与表达式也是用上面的方法一气呵成。见P54 图2.16。23 逻辑函数化简中有关问题的考虑1包含无关最小项的逻辑函数的化简无关最小项的概念：在一个逻辑函数的所有最小项中，某些输入变量的取值组合(即某些最小项)，对应的输出变量(函数)根本不会出现，即没有对应的函数值。这时的函数值既可以看成1，又可以看成0，一般用d表示。无关最小项又叫任意项。例如，十进制数用4位二进制代码表示时，其16种组合中就有6种组合无十进制数码与之对应。例如8421