卡诺图法化简

第二章逻辑代数和函数化简数字系统逻辑设计DigitalSystemandLogicDesign主编：王维华、曲兆瑞山东大学出版社主讲人：李新山东大学计算机科学与技术学院计算机科学与技术学院2内容提要2.3代数法化简逻辑函数2.2基本定律、公式和规则2.1逻辑代数和逻辑门2.5多输出函数的化简2.4卡诺图法化简逻辑函数计算机科学与技术学院32.4逻辑函数的标准形式最小项及最小项表达式最大项卡诺图的结构逻辑函数的卡诺图表示用卡诺图法化简逻辑函数计算机科学与技术学院4逻辑函数的标准形式有“积之和”与“和之积”两种基本表达形式如是“积之和”的形式，又称“与－或”表达式；而则是“和之积”的形式，又称“或－与”表达式。CCBAABF))((CBBAFBAABAF),(BABAF),(基本表达式形式不是唯一的例如计算机科学与技术学院52.4.1最小项及最小项表达式1最小项(minterm)定义在一个具有n个变量的逻辑函数中，如果一个与项包含了所有n个的变量，而且每个变量都是以原变量或反变量的形式作为因子出现且仅出现一次，那么这样的与项就称为该逻辑函数的一个最小项。常用m表示最小项对于n个变量的全部最小项共有2n个。例如：2个变量A、B的最小项ABBABABA计算机科学与技术学院6例如，在三变量的逻辑函数F（A、B、C）中，它们组成的八个乘积项即、、、、、、、都符合最小项的定义。因此，我们把这八个与项称为三变量逻辑函数F（A、B、C）的最小项。除此之外，还有、等与项，都不满足最小项的定义，所以，都不是三变量逻辑函数F（A、B、C）的最小项。CBACBACBABCACBACBACABABCABCA计算机科学与技术学院7为了表达方便，人们通常用mi表示最小项，其下标i为最小项的编号。编号的方法是：最小项中的原变量取1，反变量取0，则最小项取值为一组二进制数，其对应的十进制数便为该最小项的编号。如三变量最小项对应的变量取值为100，它对应的十进制数为4，因此，最小项的编号为m4。其余最小项的编号以此类推。值得注意的是，在规定n变量最小项的编号时，对变量的排列顺序是重要的。例如，把记作m4。其中隐含了A是最高位，而C是最低位这一排列顺序。CBACBACBA最小项编号计算机科学与技术学院8ABCABC0001000000000101000000010001000000110001000000000001000101000001001100000001011100000001最小项编号m0m1m2m3m4m5m6m7CBACBABCACBACBACABCBA2最小项的性质（1）对于任意一个最小项，有且仅有一组变量取值使其值为1，而其余各种变量取值均使它的值为0。推论：不同最小项，使其值为1的变量取值也不相同。（2）对于变量的任意一组取值，任意两个不同最小项的乘积均为0。（3）对于变量的任意一组取值，全体最小项的和恒为1。计算机科学与技术学院9由最小项的逻辑或的形式构成的逻辑函数表达式称之为逻辑函数的最小项表达式，也称为标准与或表达式。如：BCACBACABCBAF),,(=m6+m4+m3又记为：)6,4,3(m)C,B,A(F这是一个三变量逻辑函数，其变量按（A，B，C）排列，函数本身由3个最小项构成。上述表达式即为逻辑函数的最小项之和的标准形式。3）最小项表达式计算机科学与技术学院104最大项最大项定义在一个具有n变量的逻辑函数中，如果一个或项包含了所有n个的变量，而且每个变量都是以原变量或反变量的形式作为一个因子仅出现一次，那么这样的或项就称为该逻辑函数的一个最大项。对于n个变量的全部最大项共有2n个。计算机科学与技术学院11例如，在三变量的逻辑函数F（A、B、C）中，它们组成的八个和项即CBACBACBACBACBACBACBACBA都符合最大项的定义。因此，我们把这八个或项称为三变量逻辑函数F（A、B、C）的最大项。除此之外，还有、等或项，都不满足最大项的定义，所以，都不是三变量逻辑函数F（A、B、C）的最大项。BACA计算机科学与技术学院12由最大项的逻辑与的形式所构成的逻辑函数表达式称之为逻辑函数的最大项之积的标准形式。如：))()((),,(CBACBACBACBAF=M1M3M4又记为：)4,3,1(),,(MCBAF是一个三变量逻辑函数，其变量按（A，B，C）排列，函数本身由3个最大项构成。上述表达式即为逻辑函数的最大项之积的标准形式。）最大项之积的标准形式计算机科学与技术学院13将逻辑函数展开为最小项表达式(1)利用公式1XX将函数展开为最小项表达式通过求解下面的例题来学习该方法的具体应用。例将函数)(),,(CABACBAF展开为最小项表达式。计算机科学与技术学院14解：)(),,(CABACBAF))((CABABCABCAABCA…………将函数式变换为一般“与－或”表达式)()(CCABCBBA…运用公式1XX变换为最小项之和的形式CABABCCBABCA=m1+m3+m6+m7=)7,6,3,1(m6713计算机科学与技术学院15同样，我们通过例题来学习该方法的具体步骤。例将函数展开为最小项之和的标准形式。BCACBCACBAF),,((2)利用真值表展开为两种标准形式计算机科学与技术学院16函数F的真值表ABCFABCF000100001101010110011111),,(CBAFm0+m3+m4+m6)6,4,3,0(m由表可知：BCACBCACBAF),,(10011010计算机科学与技术学院17结论：利用真值表求最小项之和标准形式的方法：观察真值表，找出函数F为1的各项，作函数对应这些项的最小项，对于输入变量为1，则取输入变量本身，若输入变量为0，则取其反变量，再取这些最小项之和，即为所求函数的最小项之和标准形式。ABCFABCF00010000110101011001111110011010=m0+m3+m4+m6BCACBCACBAF),,(计算机科学与技术学院18用代数的方法化简应使得逻辑函数式包含的项数以及变量数最少为原则；对于化简的结果，尤其较为复杂的结果，通常难于判断是否最简，因此我们还常常使用卡诺图的方法来化简逻辑函数。计算机科学与技术学院192.4.2卡诺图结构卡诺图是一种矩形方格图，图中的每个方格对应一个最小项，并且任意两个相邻方格所对应的最小项只有一个变量不同。卡诺图的每一个方块（最小项）代表一种输入组合，并且把对应的输入组合注明在阵列图的上方和左方。AB01010111输入变量计算机科学与技术学院20最小项:输入变量的每一种组合。1卡诺图的画法：（二输入变量）ABY001010101110AB01010110输出变量Y的值输入变量计算机科学与技术学院21卡诺图的画法（三输入变量）逻辑相邻：相邻单元输入变量的取值只能有一位不同。0100011110ABC00000111输入变量输出变量Y的值ABCY00000010010001101000101111011111计算机科学与技术学院22只有一位不同四输入变量卡诺图逻辑相邻计算机科学与技术学院23有时为了方便，用二进制对应的十进制表示单元格的编号。单元格的值用函数式表示。F(A,B,C)=(1,2,4,7)ABC000111100101324576ABC十进制数00000011010201131004101511061117ABC000111100101011010计算机科学与技术学院240132457612131514891110ABCD0001111000011110四变量卡诺图单元格的编号ABCD000001000120010300114010050101601107011181000ABCD91001101010111011121100131101141110151111计算机科学与技术学院263、真值表、卡诺图逻辑代数式方法:将真值表或卡诺图中为1的项相加,写成“与或式”。Y=AB+AB+AB真值表ABY001011101110AB01010111AB此逻辑代数式并非是最简单的形式，实际上此真值表是与非门的真值表，其逻辑代数式为Y=AB因此，有一个化简问题。ABAB计算机科学与技术学院27ABC000111100100100011ABCBCABCBCAABC卡诺图化简函数计算机科学与技术学院28ABCCBACBACBACBAF逻辑相邻CBCBACBA逻辑相邻的项可以合并，消去一个因子若两个最小项中只有一个变量以原、反状态相区别，则称它们为逻辑相邻。计算机科学与技术学院29ABC000111100100100011AB?计算机科学与技术学院30ABC000111100100100011ABBCF=AB+BC计算机科学与技术学院31ABCD00011110000100110001000100111110DCCBCBDCF边角也相邻计算机科学与技术学院32边角也相邻ABCD00011110000110010000000010011110DBDBF计算机科学与技术学院33ABCD00011110000100000100110010001110不是矩形计算机科学与技术学院34利用卡诺图化简的规则：（1）相邻单元的个数是2N个，并组成矩形时，可以合并。ABCD00011110000100000010011011101110AD计算机科学与技术学院35（2）先找面积尽量大的组合进行化简，可以减少更多的因子。（3）各最小项可以重复使用。（4）所有的1都被圈过后，化简结束。（5）化简后的逻辑式是各化简项的逻辑和。计算机科学与技术学院36例：化简F(A,B,C,D)=(0,2,3,5,6,8,9,10,11,12,13,14,15)ABCD00011110000110110101111111111110ADCCBDBDCBDCBDBCBDCAF计算机科学与技术学院37如何最简：圈的数目越少越简；圈内的最小项越多越简。特别注意：卡诺图中所有的1都必须圈到，不能合并的1必须单独画圈。YABC01000111101111100111上两式的内容不相同，但函数值一定相同。YABC01000111101111100111Y1=B+ABC+ACY1=C+A+BCAB将Y1=AC+AC+BC+BC化简为最简与或式。此例说明，一逻辑函数的化简结果可能不唯一。例：计算机科学与技术学院38Y2=例：将Y2=Σ(m0m2m4m6m8~m15)化简为最简与或式。Y2=ADY2=AD此例说明，为了使化简结果最简，可以重复利用最小项。=A+DY2ABCD000111100001111011111100001111111111Y2ABCD0001111000011110111100001111例：用圈0法化简Y2。解：若卡诺图中1的数目远远大于0的数目，可用圈0的方法。AD+计算机科学与技术学院392.4.5多变量函数的卡诺图化简多变量函数：多于4个变量的逻辑函数000001011010DEABC00011110110111101100轴AACDEBAEDABC115变量函数F(ABCDE)的卡诺图计算机科学与技术学院4010110100BBA00011110EFCD0001111010110100A2.4.5多变量函数的卡诺图化简FDECBADEFCBA116变量函数F(ABCDEF)的卡诺图相邻性不够直观分组操作困难6变量以上的卡诺图很少使用计算机科学与技术学院412.4.5多变量函数的卡诺图化简)31,27,25,24,19,17,16,15,13,12,9,8,3,1,0()(ABCDEP局部循环相邻对称循环相邻ECBBCDE111111111111111DC000001011010DEABC00011110110