Quine-McCluskey 表格方法

在上一章中，我们讨论了 K-map 方法，这是一种简化最多 5 个变量的布尔函数的便捷方法。但是，使用此方法很难简化具有 5 个以上变量的布尔函数。

Quine-McClukey 表格方法是一种基于素蕴涵项概念的表格方法。我们知道素蕴涵项是一个乘积（或和）项，它不能通过与给定布尔函数的任何其他乘积（或和）项组合来进一步减少。

此表格方法可用于通过重复使用以下布尔恒等式来获取素蕴涵项。

xy + xy' = x(y + y') = x.1 = x

Quine-McCluskey 表格方法的过程

按照以下步骤使用 Quine-McClukey 表格方法简化布尔函数。

步骤 1 − 按升序排列给定的最小项，并根据其二进制表示中存在的 1 的数量进行分组。因此，如果布尔函数中有'n'个布尔变量，或者最小项的二进制等价物中有'n'个位，则将有最多'n+1'个组。

步骤 2 − 比较连续组中存在的最小项。如果只有一位位置发生变化，则取这两个最小项的对。将此符号'_'放在不同的位位置，并保持其余位不变。

步骤 3 − 用新形成的项重复步骤 2，直到我们得到所有素蕴涵项。

步骤 4 − 制定素蕴涵项表。它由一组行和列组成。素蕴涵项可以按行放置，最小项可以按列放置。在每个素蕴涵项所涵盖的最小项对应的单元格中填入"1"。

步骤 5 − 通过观察每一列找到基本素蕴涵项。如果最小项仅由一个素蕴涵项涵盖，则它为基本素蕴涵项。这些基本素蕴涵项将成为简化布尔函数的一部分。

步骤 6 − 通过删除每个基本素蕴涵项的行以及与该基本素蕴涵项所涵盖的最小项对应的列来简化素蕴涵项表。对简化素蕴涵项表重复步骤 5。当给定布尔函数的所有最小项都结束时，停止此过程。

示例

让我们使用 Quine-McClukey 表格方法简化以下布尔函数，$f\left ( W,X,Y,Z ight )=\sum m\left ( 2,6,8,9,10,11,14,15 ight )$。

给定的布尔函数采用最小项总和形式。它有 4 个变量 W、X、Y 和Z。给定的最小项为 2、6、8、9、10、11、14 和 15。这些最小项基于其二进制等价物中存在的 1 的数量按升序排列，分别为 2、8、6、9、10、11、14 和 15。下表显示了这些最小项及其等价二进制表示。

根据二进制等价物中存在的 1 的数量，将给定的最小项分为 4 组。下表显示了相邻组中可能的 最小项合并。

与相邻组仅相差一位的最小项会被合并。相差的位用符号"-"表示。在本例中，有三个组，每个组包含两个最小项的组合。下表显示了相邻组中可能的最小项对合并。

将连续的最小项对组合并，这些组仅在一位位置上有所不同。不同的位用符号"-"表示。在这种情况下，有两个组，每个组包含四个最小项的组合。在这里，这 4 个最小项的组合在两行中可用。因此，我们可以删除重复的行。删除冗余行后的简化表如下所示。

无法进一步合并相邻组中的最小项组合，因为它们在多位位置上有所不同。上表有三行。因此，每行将给出一个素蕴涵项。因此，素蕴涵项为 YZ'、WX' 和 WY。

素蕴涵项表如下所示。

素蕴涵项按行放置，最小项按列放置。1 放置在素蕴涵项行和相应最小项列的公共单元格中。

最小项 2 和 6 仅由一个素蕴涵项 YZ' 覆盖。因此，它是一个 基本素蕴涵项。这将是简化布尔函数的一部分。现在，删除此素蕴涵项行和相应的最小项列。简化的素蕴涵项表如下所示。

最小项 8 和 9 仅由一个素蕴涵项 WX' 覆盖。因此，它是一个 基本素蕴涵项。这将是简化布尔函数的一部分。现在，删除此素蕴涵项行和相应的最小项列。简化的素蕴涵项表如下所示。

最小项 15 仅由一个素蕴涵项 WY 覆盖。因此，它是一个基本素蕴涵项。这将是简化布尔函数的一部分。

在这个示例问题中，我们得到了三个素蕴涵项，这三个都是基本素蕴涵项。因此，简化布尔函数是

f(W,X,Y,Z) = YZ' + WX' + WY。