数字逻辑 第二章逻辑代数基础

(第八讲第八讲)数 字 逻 辑第二章 逻辑代数基础 掌握逻辑代数的基本概念，学会用逻辑函描述逻辑问题的基本方法。掌握逻辑代数的公理、基本定理和重要规则；学会用代数法化简逻辑函数；熟练掌握用卡诺图化简逻辑函数。逻辑代数是一个由逻辑变量集K，常量0和1以及“与”、“或”、“非”3种基本运算构成的一个封闭的代数系统，记为L=K,+,-,0,1。它是一个二值代数系统。常量0和1表示真和假，无大小之分。该系统满足下列公理：2.1公理公理1交换律交换律 A+B=B+A,A B=B A公理公理2结合律结合律(A+B)+C=A+(B+C),(A B)C=A (B C)公理公理3分配律分配律 A+(B C)=(A+B)(B+C),A(B+C)=A B+A C公理公理401律律 A+0=A,A 1=A A+1=1,A 0=0，公理公理5互补律互补律 A+A=1,AA=0：仅取值0或取值1的变量。这里0和1无大小之分，实际上代表着矛盾的双方或事件的真假，例如开关的接通与断开，电压的高和底，信号的有和无，电灯的亮和灭等等。只要是两种稳定的物理状态，都可以用0和1这两种不同的逻辑值来表征。2.1.1如果决定某一事件发生的多个条件，只要有一个或一个以上的条件成立，事件便可发生，这种因果关系称之为或逻辑。在逻辑代数中，或逻辑关系用或运算描述。或运算又称逻辑加，其运算符为+或 ，两个变量的或运算可表示为:F=A+B 或者 F=AB读作F等于A或B,其中A、B是参加运算的两个逻辑变量，F为运算结果。意思是：只要A、B中有一个为1，则F为1；仅当A、B均为0时，F才为0。A B F0 0 00 1 11 0 11 1 1或运算表A+uBF由“或”运算的运算表可知“或”运算的法则为：0+0=01+0=10+1=11+1=1实现或运算的逻辑电路称为或门。如果决定某一事件的发生的多个条件必须同时具备，事件才能发生，这种因果关系称为与逻辑。逻辑代数中与逻辑关系用与运算描述。与运算又称逻辑乘，其运算符为或。两变量的与运算可表示为FA B 或者 F=AB读作F等于A与B，意思是若A B 均为1，则F为1；否则F为0。A B F0 0 00 1 01 0 01 1 1与运算表+uABF由“与”运算的运算表可知“与”运算法则为：0 0=01 0=00 1=01 1=1实现“与”运算的逻辑电路称为“与”门。如果某一事件的发生取决于条件的否定，则这种因果关系称为非逻辑。非逻辑用非运算描述。非运算又称求反运算，运算符为或.非运算可表示为F=A 或F=A读作F等于A非，意思是若A0，则F为1；反之，若A=1,则F为0。“非运算表由“非”运算的运算表可知“非”运算法则为：0 1 10A F0 11 0+uAF实现“非”运算的逻辑电路称为“非”门。设某一电路的输入逻辑变量为A1,A2,An,输出逻辑变量为F。如果当A1,A2,An 的值确定后，F的值就唯一地被定下来，则F称为A1,A2,An,的逻辑函数，记为F=f(A1,A2,An)逻辑电路的功能可由相应逻辑函数完全描述。与普通函数概念相比逻辑函数有如下特点：1）逻辑变量与逻辑函数的取值只有0和1；2）逻辑函数与逻辑变量的关系由“或”、“与”、“非”运算决定。2.1.2设有两个逻辑函数F1=f1(A1,A2,An)F2=f2(A1,A2,An)若对应于A1,A2,An的任何一组取值,F1 和F2的值都相同,则称函数F1和函数F2相等,记作F1=F2亦称函数F1与F2等价。由逻辑变量、常量和逻辑运算符构成的合法表达式。进行非运算可不加括号,如.等BA，A 与运算符一般可省略,AB可写成AB.可根据先与后或的顺序去括号,如：(AB)(CD)ABCD例：BABABAF),(逻辑表达式书写省略规则：2.1.3.的或非读作ABBA；非或读作BAAB 非；或读作BAAB 非；非读作BAA B 的与非；读作ABAB ；非与读作BAAB 非；与读作BAAB 真值表是一种由逻辑变量的所有可能取值组合及其对应的逻辑函数值所构成的表格.例如例如：函数 F=AB+AC 的真值表如右所示：A B C F0 0 000 0 110 1 000 1 111 0 011 0 111 1 001 1 10卡诺图是一种用图形描述逻辑函数的方法。000101 011 111 0 0 0 1 0 0 0 1 01 1 1 推论：1=0 0=12.2.1定理定理2(重叠律重叠律)AAAA A A 定理定理3(吸收律吸收律)AA BA A(A+B)A定理定理4(吸收律吸收律)AA BA+BA(A+B)A B定理定理5(对合律对合律)AA定理定理6(德摩根定理德摩根定理)ABABA B AB 定理定理7 AB+ABA(A+B)(A+B)A定理定理8(包含律包含律)AB+AC+BCAB+ACf(A1,A2,An)f(A1,A2,An)1任何一个含有变量A的逻辑等式，如果将所有出现A的位置都代之以同一个逻辑函数F，则等式仍然成立。例如例如：给定逻辑等式A(B+C)=AB+AC，若用A+BC代替A，则该等式仍然成立，即：(A+BC)(B+C)=(A+BC)B+(A+BC)C由公理5(A+A=1)同样有等式2.2.2F(A+B)(C+D)例如例如：已知FABCD，根据反演规可得到:如果将逻辑函数F中所有的 变成+,+变成 ,0变成1,1变成0,原变量变成反变量，反变量变成原变量，所得到的新函数是原函数的反函数F使用反演规则时,应注意保持原函式中运算符号的优先顺序不变。例如：例如：已知则),(EDCBAF)(EDCBAFEDCBAF如果将逻辑函数F中所有的 变成+,+变成 ,0变成1,1变成0,则所得到的新逻辑函数F的对偶式F。如果F是F的对偶式，则F也是F 的对偶式，即F与F互为对偶式。求某一函数F的对偶式时，同样要注意保持原函数的运算顺序不变。若两个逻辑函数F的G相等，则其对偶式F 和G 也相等。例:F=A+B+C F=A+B+C例:AB+AC+BC=AB+C 则(A+B)(A+C)(B+C)=(A+B)C吉林大学远程教育课件(第九讲第九讲)主讲人主讲人 ：魏魏 达达 学学 时：时：48数 字 逻 辑积之和表达式与和之积表达式.由若干个与项经或运算形成的CBAABBF表达式。例如：由若干个或项经与运算形成的表达)()(DBACBBAF式。例如：)(CDBADABF既不是与或表达式也不是或与表达式。而2.3.1如果一个具有n个变量的函数的积项包含全部n个变量,每个变量都以原变量或反变量形式出现,且仅出现一次，则这个积项被称为最小项。假如一个函数完全由最小项所组成,那么该函数表达式称为标准积之和表达式,即最小项之和.2.3.2变量的各组取值A B C000001010011100101110111对应的最小项及其编号最小项编 号CBA CBA CBA CBA CBA CBA CBA CBA om1m2m3m4m5m6m7m三变量函数的最小项：=m2+m3+m6+m7注意：变量的顺序.即n个变量的所有最小项之和恒等于1。所以 1120iimnABCCABBCACBACBAF),(因1),(),(2121nnAAAfAAAf因此，1202121),(),(niinnmAAAfAAAf而=m(2,3,6,7)ABCCABBCACBACBAF),(：例例如如最小项的性质：1）当函数以最小项之和形式表示时，可很容易列出函数及反函数的真值表（在真值表中，函数所包含的最小项填“1”）。2）当ji 时，0jimm。3）n变量的最小项有n个相邻项。相邻项：只有一个变量不同（以相反的形式出现）。一对相邻项可以消去一个变量。如果一个具有n个变量的函数的和项包含全部n个变量，每个变量都以原变量或反变量形式出现，且仅出现一次，则这个和项称为最大项。假如一个函数完全由最大项组成，那么这个函数表达式称为标准和之积表达式。变量的各组取值A B C000001010011100101110111对应的最大项及其编号最大项编 号CBACBACBACBACBACBACBACBAoM1M2M3M4M5M6M7M三变量函数的最大项：注意：变量顺序.与最小项类似，有0120iiMn)()()(),(CBACBACBACBACBAF5410MMMM例如：例如：)5,4,1,0(M0),(),(2121nnAAAfAAAf因iinnMAAAfAAAfn1202121),(),(而最大项的性质：1）当函数以最大项之积形式表示时，可很容易列出函数及反函数的真值表（在真值表中，函数所包含的最大项填“0”）。2）当ji 时，1jiMM。3）n变量的最大项有n个相邻项。相邻项：只有一个变量不同（以相反的形式出现）。一对相邻项可以消去一个变量。吉林大学远程教育课件(第十讲第十讲)主讲人主讲人 ：魏魏 达达 学学 时：时：48数 字 逻 辑 以最小项之和的形式表示的函数可以转换成最大项之积的形式，反之亦然。ABCCABBCACBACBAF),(：例例如如=m(2,3,6,7)F(A,B,C)=m(0,1,4,5)ABCCABBCACBAFF=(A+B+C)(A+B+C)(A+B+C)(A+B+C)5,4,1,0(MF(A,B,C)=m(0,1,4,5)7,6,3,2(M同理且有iiimMmMi 或即：最大项与最小项互补。例如：例如：M3=A+B+C=ABC=m3任何一个逻辑函数，总可以将其 转换成最小项之和及最大项之积的形式,常用代数转换法或真值表转换法.2.3.3用代数法求一个函数最小项之和的形式，一般分为两步：将函数表达式变换成一般的与或式.反复使用X=X(Y+Y)将非最小项的与 项 扩展为最小项。例例：将F(A,B,C)=(AB+BC)AB转换成最小项之和形式ABCBBACBAF),(1 、解：解：ABCBBAABCBBA)(ABBCCABA)()()(),(2AABCBBCACCBACBAF、)(CCABABCCBABCACBACBA CABABCBCAABCCABBCACBACBA F(A,B,C)=m0+m1+m3+m6+m7=m(0,1,3,6,7)类似地，用代数法求一个函数最大项之积的形式，也可分为两步：将函数表达式转换成一般或与式；如果给出的函数已经是与或式或者是或与式，则可直接进行第二步。：反复使用将非最大项的或项扩展成为最大项)(BABAA例：将F(A,B,C)=AB+AC转换成“最大项 之积的形式。解：1）F(A,B,C)=AB AC=(A+B)(A+C)2)F(A,B,C)=(A+B+CC)(A+BB+C)=(A+B+C)(A+B+C)(A+B+C)(A+B+C)F(A,B,C)=M1 M3 M6 M7=M(1,3,6,7)一个逻辑函数的真值表与它的最小项表达式和最大项表达式均存在一一对应的关系。函数F的最小项表达式由使F取值为1的全部最小项之和组成。函数F的最大项表达式由使F取值为0的全部最大项之积组成。表示成“最小项之和”将CBACAF例例：和最大项之积的形式。解：解：A B C F0 0 000 0 110 1 000 1 111 0 011 0 101 1 001 1 10CBABCACBAF(A,B,C)4,3,1(m)()(CBACBAF(A,B,C)()(CBACBA)(CBA)7,6,5,2,0(M 注意：任何一个逻辑函数的两种标准形式唯一.一般来说,逻辑函数表达式越简单,设计出来的电路也就越简单。把逻辑函数简化成最简形式称为逻辑函数的最小化,有三种常用的方法,即代数化简法、卡诺图化简法和列表化简法。2.4该方法运用逻辑代数的公理、定理和规则对逻辑函数进行推导、变换而进行化简，没有固定的步骤可以遵循，主要取决于对公理、定理和规则的熟练掌握及灵活运用的程度。有时很难判定结果是否为最简。2.4.1化简应满足的两个条件：1）表达式中与项的个数最少；2）在满足1）的前提下,每个与项中的变量个数最少。CDDACABCCAF简化例例：)()(DDACBCCAF解解：)()(DDDACCCBCACDACABCACDABCCA)(CDACDB)A(1DBDBCBCBCAABF简化例例：)(GFADEDBDBCBCBCBAF解：解：)(GFADE)(GFADEDBDBCBCBADBDBCBCBA)()(CCDBDBCBDDCBADCBDBCDBCBCDBDCBA CBDBDCA化简应满足的两个条件：化简应满足的两个条件：1）表达式中或项的个数最少；2）在满足1）的前提下,每个或项中的变量个数最少。例：F=(A+B)(A+B)(B+C)(B+C+D)解：F=(A+B)(A+B)(B+C)(B+C+D)=（A+B)(A+B)(B+C)=A(B+C)例：F=(A+B)(A+B)(B+C)(A+C)解：F=AB+AB+BC+AC=AB+AB+(B+A)C=AB+AB+ABC=AB+AB+CF=(F)=(A+B)(A+B)C吉林大学远程教育课件(第十一讲第十一讲)主讲人主讲人 ：魏魏 达达 学学 时：时：48数 字 逻 辑该方法简单、直观、容易掌握,当变量个数小于等于6时非常有效,在逻辑设计中得到广泛应用。n个变量的卡诺图是一种由2n个方格构成的图形,每一个方格表示逻辑函数的一个最小项,所有的最小项巧妙地排列成一种能清楚地反映它们相邻关系的方格阵列。因为任意一个逻辑函数都 可表示成最小项之和的形式,所以一个函数可用图形中若干方格构成的区域来表示。2.4.2mo m2m1 m3 0101ABAB 0101BA BABA ABBBAA二变量卡诺图mo m2 m6 m4m1 m3 m7 m500 01 11 1001ABC00 01 11 1001ABCCBA CBACABCBA CBA BCAABCCBA AACCBBB三变量卡诺图00 01 11 1000011110ABCDDCBA ACDCBA DCBA DCBA DCBA DCBA DCBA DCBA DCBA DCBA ABCDCDBADCBA DCBA DABCDCBADB 0 4 12 8 1 5 13 9 3 7 15 11 2 6 14 1000 01 11 1000011110ABCD四变量卡诺图：彼此只有一个变量不同，且这个不同变量互为反变量的两个最小 项(或与项)称为相邻最小项(或相邻与项).相邻最小项在卡诺图中有三种特征，即几何相邻、相对相邻和重叠相邻。卡诺图在构造上具有以下两个特点：卡诺图在构造上具有以下两个特点：1）n个变量的卡诺图由2n个小方格组成,每个小方格代表一个最小项。2）卡诺图上处在相邻、相对、相重位置的小方格所代表的最小项为相邻最小项。将逻辑函数所对应的最小项在卡诺图的相应方格中标以1，剩余方格标以0或不标。1、与或式的卡诺图表示.直接将表达式的与项或最小项所对应的方格标以1.00 01 11 1001ABC11111CBABCBACACBAF),(可表示为：例如：例如：2、其它形式函数的卡诺图表示要转换成与或式再在卡诺图上表示。吉林大学远程教育课件(第十二讲第十二讲)主讲人主讲人 ：魏魏 达达 学学 时：时：48数 字 逻 辑根据定理7有AB+AB=A,它表明两 个相邻与项或最小项可以合并为一项，这一项由两个与项中相同的变量组成，可以消去两个 与项中不同的变量。在卡诺图上把相邻最小项所对应的小方格圈在一起可进行合并，以达到用一个简单与项代替若干最小项的目的。这样的圈称为卡诺圈。0101AB1 1 0101AB1 1 0101AB1 11二变量卡诺图的典型合并情况00 01 11 1001ABC1 11 1AB 00 01 11 1001C1 1 1 11 1 1 101ABC00 01 11 10三变量卡诺图的典型合并情况100 01 11 1000011110ABCD111111100 01 11 1000011110ABCD1111111100 01 11 1000011110ABCD1111111111四变量卡诺图的典型合并情况一个卡诺圈中的小方格满足以下规律：一个卡诺圈中的小方格满足以下规律：1）卡诺圈中的小方格的数目为2m,m为整数且mn;3）2m个小方格可用(n-m)个变量的与项表示,该与项由这些最小项中的相同变量构成。2）2m个小方格含有m个不同变量和(n-m)个相同变量;4）当m=n时,卡诺圈包围整个卡诺图,可用1表示，即n个变量的全部最小项之和为1。蕴涵项：蕴涵项：与或式中的每一个与项称为函数的蕴涵项；质蕴涵项：质蕴涵项：不被其它蕴涵项所包含的蕴涵项；必要质蕴涵项：必要质蕴涵项：质蕴涵项中至少有一个最小项不被其它蕴涵项所包含。用卡诺图化简逻辑函数的一般步骤为：用卡诺图化简逻辑函数的一般步骤为：第一步：第一步：作出函数的卡诺图；第二步：第二步：在卡诺图上圈出函数的全部质蕴涵项；第三步：第三步：从全部质蕴涵项中找出所有必要质蕴涵项；第四步第四步：若全部必要质蕴涵项尚不能覆盖所有的1 方格，则需从剩余质蕴涵项中找出最简的所需质蕴涵项，使它和必要质蕴涵项一起构成函数的最小覆盖。例：例：用卡诺图化简逻辑涵数 F(A,B,C,D)=m(0,3,5,6,7,10,11,13,15)100 01 11 1000011110ABCD11111111解：解：1100 01 11 1000011110ABCD111111100 01 11 1000011110ABCD1*1111*1*1*1*1*CBABCACDBDDCBADCBAF ),(例：例：用卡诺图化简逻辑函数 F(A,B,C,D)=m(2,3,6,7,8,10,12)100 01 11 1000011110ABCD111111解：解：100 01 11 1000011110ABCD11111100 01 11 1000011110ABCD1*1111*1*1*1100 01 11 1000011110ABCD1*1*1*1*1DBADCACADCBAF ),(DCBDCACADCBAF),(或例：例：用卡诺图把逻辑函数 F(A,B,C,D)=M(3,4,6,7,11,12,13,14,15)化简成最简或与表达式。)15,14,13,12,11,7,6,4,3(),(MDCBAF解：解：15141312117643MMMMMMMMM15141312117643mmmmmmmmm)10,9,8,5,2,1,0(m100 01 11 1000011110ABCD00100101100100DBABCDDCBAF),(DBABCDDCBAF),()()(DBBADC1吉林大学远程教育课件(第十三讲第十三讲)主讲人主讲人 ：魏魏 达达 学学 时：时：48数 字 逻 辑一个逻辑函数,如果它的某些输入取值组合因受特殊原因制约而不会再现,或者虽然每种输入取值组合都可能出现,但此时函数取值为1还是为0无关紧要,那么这些输入取值组合所对应的最小项称为无关最小项。无关最小项可以随意加到函数表达式中，或不加到函数表达式中，并不影响函数的实际逻辑功能。2.4.4A B C DF0 0 0 0d0 0 0 1d0 0 1 0d0 0 1 110 1 0 010 1 0 110 1 1 000 1 1 101 0 0 001 0 0 101 0 1 011 0 1 111 1 0 011 1 0 1d1 1 1 0d1 1 1 1d100 01 11 1000011110ABCD11111),(DCBAFCBACDBDCBCBA：给定某电路的逻辑函数真值表如下，求F的最简与或式。解：1)不考虑无关最小项：1100 01 11 1000011110ABCD1111ddddddCBCBDCBAF),(2)考虑无关最小项：对于多输出逻辑函数，如果孤立地将单个输出一一化简，然后直接拼在一起，通常并不能保证整个电路最简，因为各个输出函数之间往往存在可供共享的部分。多输出逻辑函数化简的标准：多输出逻辑函数化简的标准：2）在满足上述条件的前提下，各不同与项中所含的变量总数最少。1）所有逻辑表达式包含的不同与项总数最小；：多输出函数.对应的卡诺图为100 01 11 1001ABC1 1F1100 01 11 1001ABC1 1F2CABACBAF),(1BCABCBAF),(2从多输出函数化简的观点来看，它们不是最佳的，应该是：CABBACBAF),(1CABBCCBAF),(2对应的卡诺图为100 01 11 1001ABC1 1F11 1100 01 11 1001ABCF2.21的共享部分和的其中FFABC