奎因-麦克拉斯基表格法

---

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

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

这种表格方法对于通过重复使用以下布尔恒等式来获取素蕴涵项非常有用。

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

Quine-McCluskey 表格法的流程

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

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

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

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

步骤 4 - 制定素蕴含表。它由行和列的集合组成。素蕴涵项可以按行放置，最小项可以按列放置。将“1”放入与每个素蕴涵项中涵盖的最小项相对应的单元格中。

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

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

例子

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

给定的布尔函数采用最小项之和的形式。它有 4 个变量 W、X、Y 和 Z。给定的最小项是 2、6、8、9、10、11、14 和 15。这些最小项的升序基于它们中存在的项数。二进制等效值为 2、8、6、9、10、11、14 和 15。下表显示了这些最小术语及其等效的二进制表示形式。

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

与相邻组仅在一位位置上不同的最小项被合并。该不同的位用该符号“-”表示。在本例中，存在三组，每组包含两个最小项的组合。下表显示了相邻组中最小术语对的可能合并。

仅一位位置不同的连续的最小项对组被合并。该不同的位用该符号“-”表示。在本例中，有两组，每组包含四个最小项的组合。在这里，这些 4 分钟术语的组合在两行中可用。因此，我们可以删除重复的行。删除冗余行后的缩减表如下所示。

不可能进一步合并来自相邻组的最小项的组合，因为它们在不止一位位置上不同。上表中有三行。因此，每一行都会给出一个素蕴涵项。因此，素蕴涵项是 YZ'、WX' 和 WY。

素蕴含表如下所示。

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

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

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

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

在这个示例问题中，我们得到了三个素蕴涵项，并且这三个素蕴涵项都是必不可少的。因此，简化的布尔函数为

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