2.5 卡诺图的化简
当合并卡诺图中的方格时，一定要确保包含了函数全部的最小项。同时，我们必须避免其最小项已经被其他函数项包含的冗余项，这样可以使优化了的函数所包含的函数项最少。在这一节，我们将介绍一种有助于卡诺图化简的方法步骤，同时还将介绍和之积表达式的优化和不完全确定函数的优化。
2.5.1 质主蕴涵项
如果我们引入“蕴涵项”“主蕴涵项”和“质主蕴涵项”的概念，那么合并卡诺图中方格的过程会变得更加系统化。如果函数对某个乘积项的每一个最小项都取值为1，则这个乘积项是函数的一个蕴涵项（implicant）。可以清楚地看到，卡诺图中所有由1方格组成的矩形都对应着蕴涵项。如果从蕴涵项P中移去任何一个变量，所得的乘积项不再是函数的蕴涵项，则这样的P称为主蕴涵项（prime implicant）。在n变量函数的卡诺图中，主蕴涵项集合对应着所有由2m（m＝0，1，…，n）个1方格构成的多个矩形，每个矩形包含了尽可能多的1方格。
如果函数的某个最小项只包含在一个主蕴涵项中，则这个主蕴涵项是必需的。因此，如果一个1方格仅存在于表示某个主蕴涵项的一个矩形内，则这样的主蕴涵项是必要的（essential）。如图2-14c中，函数项AC和AC是必要主蕴涵项（又称质主蕴涵项—译者注），函数项AB和BC是非必要主蕴涵项（又称非质主蕴涵项—译者注）。
函数的主蕴涵项可以从卡诺图中获得，它是由2m（m＝0，1，…，n）个1方格构成的一个最大的矩形。这意味着如果卡诺图中有一个1方格不与其他任何1方格相邻，则这个1方格就是一个主蕴涵项；如果两个相邻的1方格形成了一个表示主蕴涵项的矩形，则这两个1方格不在一个包含了4个或更多个1方格的矩形中；如果不被8个或更多个1方格所构成的矩形所包含，则由4个1方格形成的矩形是一个主蕴涵项；等等。每个质主蕴涵项至少包括一个没有被任何其他主蕴涵项覆盖的方格。
利用卡诺图寻找函数优化表达式的一般步骤是：首先确定所有的主蕴涵项，然后对全部质主蕴涵项进行逻辑和，再加上其他一些主蕴涵项用来覆盖剩余的不被质主蕴涵项所包含的最小项。这个过程将在例题中阐述。
例2-10 使用主蕴涵项化简
考虑图2-17中所示的卡诺图。有三种可以将4个方格合并成矩形的方法，由这些组合得到的乘积项AD、BD、AB是函数的主蕴涵项，其中AD和BD是函数的质主蕴涵项，但AB却不是。这是因为最小项1和3仅被函数项AD覆盖，最小项12和14仅被函数项BD覆盖，但最小项4、5、6和7中的每一个都被两个主蕴涵项覆盖，其中一个是AB，所以函数项AB不是质主蕴涵项。事实上，一旦确定了主蕴涵项，AB就不需要了，因为所有的最小项都被这两个质主蕴涵项覆盖。图2-17所示函数优化后的表达式为
F＝AD＋BD ■例2-11 使用质主蕴涵项和非质主蕴涵项化简
第二个例子如图2-18所示。图2-18a所示的函数有7个最小项。如果我们尝试合并方格，就会发现有6个主蕴涵项。为了使函数的函数项最少，我们必须首先确定质主蕴涵项。如图2-18b灰色线部分所示，函数有4个质主蕴涵项。乘积项ABCD是质主蕴涵项，因为它是唯一覆盖最小项0的主蕴涵项。同样，乘积项BCD、ABC和ABC是质主蕴涵项，因为它们各自唯一覆盖了最小项5、12和10。最小项15被两个非质主蕴涵项覆盖。优化后的函数表达式由4个质主蕴涵项的逻辑和与一个覆盖了最小项15的主蕴涵项组成：
■
这样在卡诺图中识别质主蕴涵项的方法，说明质主蕴涵项一定会出现在函数的每一个积之和表达式中，并为我们提供了一个更为系统的方法来选择主蕴涵项。
2.5.2 非质主蕴涵项
除了使用所有的质主蕴涵项外，以下规则可以用来覆盖包含在非质主蕴涵项中函数剩余的最小项：
选择规则：尽可能地减少主蕴涵项的重叠。特别是在最后的表达式中，要确保所选择的主蕴涵项至少覆盖一个没有被其他主蕴涵项覆盖的最小项。
在通常情况下，尽管这样得不到最佳的表达式，但却是简化的和之积表达式。下面一个例子将说明选择规则的使用。
例2-12 使用选择规则来化简函数
为函数F(A, B, C, D)＝m(0, 1, 2, 4, 5, 10, 11, 13, 15)寻找一个简化的积之和表达式。
函数F的卡诺图如图2-19所示，所有的主蕴涵项都已给出。AC是唯一的质主蕴涵项。利用前面的选择规则，我们可以按图中给出的顺序为积之和式选择剩余的主蕴涵项。注意，选择主蕴涵项1和2是为了使覆盖的最小项不重叠。主蕴涵项3（ABD）和主蕴涵项BCD都覆盖了余下的最小项0010，随意选择主蕴涵项3来覆盖这个最小项，最后的积之和表达式是：
F(A, B, C, D)＝AC＋ABD＋ABC＋ABD
没有用到的主蕴涵项在图2-19中用黑线框标记。 ■
2.5.3 和之积优化
前面例子中通过卡诺图得到优化的布尔函数，都是采用积之和表达式，稍做修改就可以得到和之积的形式。
我们可以利用布尔函数的特性来得到优化的和之积表达式。卡诺图中的1方格代表函数的最小项，那些不包含在原函数中的最小项属于函数的非。因此，我们得知函数的非在卡诺图中由那些没有标记1的方格来表示。如果我们用0来标记这些方格并且适当合并成矩形，就可以得到函数非F的优化表达式，然后将F取反得到和之积形式的F。具体做法是对每个变量取反并求对偶式，如例2-13所示。
例2-13 化简和之积形式
化简下列布尔代数为和之积形式：
F(A, B, C, D)＝m(0, 1, 2, 5, 8, 9, 10)
图2-20所示卡诺图中标记为1的方格表示函数的最小项，标记为0的方格表示函数F取反后的最小项，而不是函数F的最小项。将标记为0的方格合并起来，我们可以得到简化的反函数：
F＝AB＋CD＋BD
取其对偶式并对F中的每个变量取反就可以得到F。F的和之积形式为：
F＝(A＋B)(C＋D)(B＋D) ■上面这个例子介绍了如何将最小项之和形式的函数化简为和之积形式的过程。如果函数表达式原本是最大项之积形式或者是和之积形式，这个过程也可以使用。记住，最大项的数字与函数取反后的最小项的数字相同，所以在卡诺图中可以用0标记最大项或函数的非。为了在卡诺图中标记一个用和之积形式表示的函数，我们可以对这个函数取反，找出要标记为0的方格。例如，对于函数
F＝(A＋B＋C)(B＋D)
在绘制卡诺图时可以先对其取反，
F＝ABC＋BD
然后将F的最小项所对应的方格标记为0，余下的方格都标记1。然后再合并1方格得到简化的积之和表达式，合并0方格并取反得到简化的和之积表达式。这样，对于任何绘制在卡诺图中的函数，我们都可以得到优化了的两种标准形式中的任意一种表示形式。
2.5.4 无关最小项
布尔函数的最小项确定了使函数取值为1的变量取值的所有组合，对其余的最小项函数的值为0。但是，这样的假设往往是无效的，因为在有些实际应用中，函数取值对某些变量取值组合来说是不确定的。这时会出现两种情况。第一种情况，某些输入组合根本不会出现，例如，用4位二进制对十进制数字进行编码时就有6种组合没有使用，也不会出现。第二种情况，某些输入组合会出现，但是我们并不关心这些输入组合会产生怎样的输出结果。对于这两种情况下的输入取值组合，函数输出结果均不确定。这种对于某些输入组合来说输出结果不确定的函数称为不完全确定函数（incompletely specified function）。在大多数应用中，我们并不关心对于那些不确定的最小项函数的值是多少。正因为这个原因，通常把这些函数中没有指定的最小项称为无关最小项（don抰-care condition），这些情况可以用于卡诺图以使函数得到进一步简化。
需要注意的是，一个无关最小项在卡诺图中不能用1标记，因为这会要求函数值对于这个最小项一直为1。同样，无关最小项用0标记就会要求函数值为0。为了与1和0区分，无关最小项通常用×来表示。这样一来，卡诺图方格中的×表示我们并不关心对于这个特殊的最小项，函数取值到底是0还是1。
选择卡诺图中相邻的方格来简化函数，无关最小项也许有用。当用1方格来简化函数F时，我们要包含那些可以使F的主蕴涵项最简单的无关最小项；当用0方格来简化函数F时，我们要包含那些可以使F的主蕴涵项最简单的无关最小项，不管这些无关最小项是否包含在F的主蕴涵项中。无论最终表达式的函数项中是否含有无关最小项，这两种情况相互之间没有任何关系。下面是对无关最小项处理的例子。
例2-14 用无关最小项进行化简
为了清楚地表述处理无关最小项的步骤，考虑下面不完全确定函数F，它有三个无关最小项d：
F(A, B, C, D)＝m(1, 3, 7, 11, 15)
d(A, B, C, D)＝m(0, 2, 5)
函数F的最小项组合使得函数的值为1，最小项d是无关最小项，卡诺图化简如图2-21所示。F的最小项用1标记，d的最小项则用×标记，其他的方格用0标记。为了获得函数积之和的简化形式，我们必须包括卡诺图中的5个1方格，但是可以将任何一个×包括或不包括进来，这取决于怎样做可以得到函数的最简形式。CD项在第3列包括4个最小项，余下的最小项方格0001和方格0011组合在一起成为一个三变量的函数项。然而，通过包括一个或两个相邻的×，我们可以将4个方格组合成一个矩形，得到一个两变量的函数项。在图2-21a部分，无关最小项0和2与1方格合并，得到化简后的函数
F＝CD＋AB
在图2-21b部分，无关最小项5与1方格合并，这时简化后的函数为
F＝CD＋AD
这两个表达式所表示的函数在代数中是不相等的，它们都包括原不完全确定函数中确定的最小项，但每个表达式却包括了不同的无关最小项。如果考虑的是不完全确定函数，那么这两个表达式都是可以接受的。唯一不同之处就是，对应无关最小项，函数F的取值不同。
对于图2-21中的函数也可以求得简化的和之积表达式。这时，使用组合0方格的方法将无关最小项0和2与0方格组合起来，得到优化后的反函数
F＝D＋AC
对函数F取反就可以得到优化的和之积表达式：
F＝D(A＋C) ■从前面介绍的例子可以看出，卡诺图中的无关最小项最初既可以认为是0，也可以认为是1，最后决定是0还是1取决于简化的过程。这样一来，对于原函数中的最小项和那些无关项，优化后函数的取值可能是0或1。因此，虽然开始时输出结果中可以包含×，但用特定方式实现时输出结果只能为0和1。
更多优化 补充材料介绍了如何选择主蕴涵项以便获得最优结果。另外，它还给出了一个用符号运算来产生主蕴涵项的方法，同时给出了用表格方法来选择主蕴涵项。补充材料还讨论了要为大电路找到真正的两级优化方法是不现实的，这是因为要产生全部主蕴涵项以及从大量的主蕴涵项中选择出可能的解决方案是困难的。补充材料给出了一个计算机算法，对于大电路它通常能够得到接近最优的两级解决方案，比用最优方法要快得多。
