奎因-麦克拉斯基表法

---

---

本章将讨论使用也称为**奎因-麦克拉斯基方法**的表格方法化简布尔表达式。

奎因-麦克拉斯基方法在化简超过六个变量的布尔函数方面更有优势。这种化简技术克服了卡诺图在处理超过六个变量时的问题。

奎因-麦克拉斯基方法的另一个主要优点是它同样适用于手工计算和机器计算，因为它可以编程。

奎因-麦克拉斯基方法理论

奎因-麦克拉斯基方法是一种系统地化简复杂布尔表达式的技术。对于大量变量的布尔表达式化简，它成为了一种合适的方法。它也称为表格方法。

这种最小化技术基于对所有相邻项对重复使用组合定理（即，$\mathrm{XA \: + \: X\bar{A} \: = \: X}$，其中X是一组文字）。此过程给出了一组所有质蕴含项，从中我们可以选择一个最小和。

奎因-麦克拉斯基方法步骤

下面解释了使用奎因-麦克拉斯基方法化简布尔函数的分步过程：

**步骤1** - 列出给定布尔表达式的所有最小项。

**步骤2** - 对最小项分组。在此步骤中，我们根据最小项二进制形式中1的个数对所有最小项进行排列。例如，将所有没有1的最小项放在一起，所有只有一个1的最小项放在一起，依此类推。最小项中1的个数称为最小项的指标。将这些分组的最小项写在表的第1列中。

**步骤3** - 合并最小项。在此步骤中，将最低指标组的每个最小项与后续组中的每个最小项进行比较。只要可能，将相邻组中仅相差一位的两个最小项合并，并将不同的位替换为破折号（-）。这表示无关项。此外，在已与至少一个最小项合并的每个最小项前面放置一个勾号（✓）。重复此过程，直到完成所有可能的最小项组合。将所有组合的最小项写在表的第2列中。

**步骤4** - 以相同的方式比较和合并上述步骤中生成的最小项。在此步骤中，我们将合并仅相差一位且破折号位于相同位置的两个最小项。我们不能合并破折号位于不同位置的两个最小项。

将新生成的项写在第3列中，并在已在第2列中合并的每个项旁边放置一个勾号（✓）。使用第3列、第4列等中的项继续此过程，直到不再可能进行进一步的组合。最后，未组合的项称为**质蕴含项**。

**步骤5** - 列出所有质蕴含项并创建质蕴含项表。如果有任何无关项，则它不应出现在质蕴含项表中。

**步骤6** - 选择基本质蕴含项，即覆盖至少一个不被任何其他质蕴含项覆盖的最小项的质蕴含项。

**步骤7** - 合并基本质蕴含项以获得最终简化的表达式。

与奎因-麦克拉斯基方法相关的术语

在布尔表达式最小化奎因-麦克拉斯基方法中，使用多个术语来传达信息。下面定义了与奎因-麦克拉斯基方法相关的一些关键术语：

**最小项** - 最小项是布尔变量的组合，其中真值用1表示，假值用0表示。

**最大项** - 最大项是布尔变量的组合，其中真值用0表示，假值用1表示。

**指标** - 最小项中1的个数称为其指标。

**质蕴含项** - 不能与任何其他最小项组合的最小项称为质蕴含项。

**基本质蕴含项** - 覆盖至少一个不被任何其他质蕴含项覆盖的最小项的质蕴含项称为基本质蕴含项。

**质蕴含项表** - 显示布尔表达式质蕴含项和最小项之间关系的图形表示称为质蕴含项表。

**无关项** - 无关项是可以忽略的位或变量，用于函数的最小化。在奎因-麦克拉斯基方法中，它用破折号（-）表示。

这些是一些使用奎因-麦克拉斯基方法的基本重要术语。

现在让我们通过一个例子来了解奎因-麦克拉斯基方法在化简布尔函数中的应用。

基于奎因-麦克拉斯基方法的示例

使用奎因-麦克拉斯基技术化简以下布尔函数。

$$\mathrm{f(A, B,C,D) \: = \: \sum \: m(0,1,5,7,10,14)}$$

解答

下面解释了使用奎因-麦克拉斯基方法化简给定布尔函数的过程。

**步骤1** - 按1的个数升序对给定的最小项分组，并将它们的二进制形式写在第1列中。

**步骤2** - 比较和合并第1列的最小项。

我们可以看到，在两个相邻组之间，第2列中没有项可以与任何其他项合并。因此，它们都是质蕴含项。

**步骤3** - 创建质蕴含项表。

从质蕴含项表中可以看到，最小项m10和m14仅被S覆盖。因此，S是基本质蕴含项。还可以观察到，函数的其余最小项被P和R的最小质蕴含项集覆盖。

因此，最小表达式将是：

$$\mathrm{f_{min} \: = \: P \: + \: R \: + \: S \: = \: (000 \: − \: ) \: + \: (01 \: − \: 1) \: + \:(1 \: − \: 10)}$$

$$\mathrm{\Rightarrow f_{min} \: = \: \overline{ABC} \: + \: \overline{A}BD \: + \: AC\overline{D}}$$

这是给定布尔函数的最小布尔表达式，可以使用与门、或门和非门实现。

奎因-麦克拉斯基方法的优点

奎因-麦克拉斯基方法比其他最小化技术（如卡诺图）具有 several advantages。奎因-麦克拉斯基方法的一些主要优点如下：

• 奎因-麦克拉斯基方法提供了一个系统的最小化过程，以找到复杂布尔表达式的最小版本。
• 它可以应用于具有大量变量的布尔函数，而卡诺图技术在这种情况下变得不切实际。
• 它适用于手工计算和计算机计算。
• 奎因-麦克拉斯基方法基于系统的算法，有助于减少人为错误。
• 它也可以应用于具有“无关项”（don't care conditions）的布尔函数，即不完整的布尔函数。

奎因-麦克拉斯基方法的缺点

然而，奎因-麦克拉斯基方法是一种强大的简化技术，用于最小化布尔函数，比其他最小化技术具有 several advantages。

但是，它也有一些缺点，其中一些列在下面：

• 奎因-麦克拉斯基方法的主要缺点是计算复杂度。这是因为我们必须检查所有可能的最小项组合。
• 虽然对于大量变量，奎因-麦克拉斯基方法比卡诺图更好，但对于非常大量的变量（通常超过7个变量），它也变得不切实际。
• 奎因-麦克拉斯基方法涉及大量的 manual computation，这使得它既繁琐又容易出错。
• 奎因-麦克拉斯基方法对于某些类型的布尔函数效率不高。
• 由于奎因-麦克拉斯基方法采用算法方法而不是图形方法进行最小化，这使得它不那么直观。

奎因-麦克拉斯基方法的应用

奎因-麦克拉斯基方法是布尔代数中最有效的最小化技术之一。它提供了一种系统的方法来最小化具有大量变量的复杂布尔函数。奎因-麦克拉斯基方法的一些主要应用如下：

• 奎因-麦克拉斯基方法用于设计和优化数字电路和系统。它有助于减少数字电路中使用的逻辑门数量。
• 它也用于计算机编程中优化条件逻辑，以提高效率和速度。
• 在数字信号处理中，奎因-麦克拉斯基方法用于简化布尔表达式，以开发高效的处理算法。
• 奎因-麦克拉斯基方法用于设计高效的状态机。

结论

总之，奎因-麦克拉斯基方法是一种系统且算法化的简化复杂布尔表达式的方法。对于具有大量变量的布尔函数，它是一种有效的最小化技术。

奎因-麦克拉斯基方法的最大优点是它支持手工计算和机器计算，即它是可编程的。然而，这种方法涉及相对复杂的计算，这使得它很繁琐。