[第二章列表化简法.pptVIP

列表化简法 列表化简法是Quine-Mccluskey提出的一种系统化简法，故也称作Q-M法，也称作表格法。这种方法具有严格的算法，虽然其工作量大、方法繁琐，但便于计算机化简多变量逻辑函数。 列表化简法 Q-M法化简逻辑函数的步骤如下： 第一步，将函数表示成最小项表达式。 第二步，找出函数的全部质蕴涵项。 1、将n变量函数中的相邻最小项合并，消去相异的一个变量，得到(n-1)个变量的与项（蕴涵项）。 这时如果存在不能合并的最小项，它便是所寻找的部分质蕴涵项。 2、再将相邻的（n-1）个变量的与项合并，消去相异的一个变量，得到（n-2）个变量的与项（蕴涵项） ，这里如果存在不能合并的（n-1）个变量的与项，则它们也是所寻找的质蕴涵项。 如此进行下去，直到不能再合并为止。得全部的质蕴涵项。 列表化简法 第三步，找出函数的必要质蕴涵项。 先画出质蕴涵表，然后在表上找出仅属于一个质蕴涵项的最小项，则包含该最小项的质蕴涵项就是必要质蕴涵项。 第四步，找出函数的最小覆盖。 当第三步找出的必要质蕴涵项不能包含函数的全部最小项时，可以通过行、列消去法，找出最小覆盖的其他必要质蕴涵项。最小覆盖指包含函数的全部最小项的最小质蕴涵项集合。 列表化简法 用Q-M法化简函数 : 列表化简法 （1）找出全部质蕴涵项 ①做最小项分组表并找出不能合并者: 将最小项mi按变量取值表示成二进制数；其次，再根据这些二进制数中所包含1的个数从少到多的次序进行分组排队；最后，把含有1的个数相同的最小项划分成一组，组内按下标i的取值从小到大排列，如此制成最小项分组。 从含有1个数最少的那组开始，在相邻组内比较最小项，将只有一个变量值不同的两个最小项合并，消去一个变量，并在已合并的最小项的右边Pi栏内做记号“√”，表示该项已被合并。在不能合并的最小项的右边Pi栏内填入P1，则 就是所寻找的质蕴涵项。注意合并最小项只能处于相邻的两组内，而不能处于同组或隔组内。 列表化简法 列表化简法 ②做（n-1）个变量与项分组表并找出不能合并者: 在最小项合并过程中，用符号“—”表示被消去的变量，这样便得到若干个带有“—”的与项，或称作合并项。按照对最小项的分组方法，对带有“—”的与项进行分组。对相邻组中的“—”处于相同位置的那些与项进行合并，已合并的与项做记号“√”，并记入Pi栏；在不能合并的与项的Pi栏内记入P2和P3，则 也是质蕴涵项。 列表化简法 列表化简法 ③做（n-2）个变量与项分组表并找出不能合并者： 在（n-1）个变量与项合并过程中，也用符号“—”表示被消去的变量，这样便得到若干个带有两个“—”的与项。按照上述的分组方法，得到（n-2）个变量与项分组表。 由表可以看出，仅有的两（n-2）个变量与项不能再合并，在Pi栏内分别记入P4和P5，P4和P5就是最后所寻找的质蕴涵项。 列表化简法 列表化简法 ④列出全部质蕴涵项 由上述分析可得全部质蕴涵项： 列表化简法 （2）找出必要质蕴涵项 将函数的最小项和上述的质蕴涵项做序列表，并在质蕴涵项包含的最小项下面填入符号“×”,即做所谓质蕴涵表。 找出那些仅属于一个质蕴涵项的最小项，如m0仅属于P4；m5仅属于P5；m9仅属于P1；m10仅属于P2；m15仅属于P3；并在相应的×处加圆圈。 质蕴涵项P1～P5均包含一个不属于其他质蕴涵项的最小项，即它们均包含一个，所以它们均为必要质蕴涵项，并在其左边加“﹡”号。 列表化简法 列表化简法 （3）找出函数的最小覆盖 在上述的必要质蕴涵项P1～P5中，找出它们所包含的全部最小项，并在相应的最小项上面做记号“√” 。从表中可以看出，必要蕴涵项P1～P5包含函数的所有的最小项，也就是说，P1～P5构成了函数的最小覆盖，因此，函数的最简与或式为： 列表化简法 列表化简法 列表化简法 * 《数字逻辑电路》 吉林大学计算机科学与技术学院 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 《数字