Digital-electronics 简明教程

Simplifications of Boolean Algebra

What is a Karnaugh Map (K-Map)?

K-Map 是一个图形工具，用于简化用标准形式表示的布尔表达式以获得其极小形式。

卡诺图基本上是一个图形或图表，由相邻单元格或方块的排列组成，其中每个单元格代表函数变量的特定组合，以求和形式或乘积形式表示。

卡诺图中的单元格数量取决于布尔函数中的变量数量，即，卡诺图有 2n 个相邻单元格，其中 n 是布尔表达式中变量的数量。因此，2 变量卡诺图中的单元格数量为 4（22），在 3 变量卡诺图中，单元格数量为 8（23），在 4 变量卡诺图中，单元格数量为 16（24），依此类推。

但是，我们可以对任意数量的变量使用卡诺图。但是，对于简化变量多于 5 的布尔函数，它变得很繁琐。

现在，让我们讨论使用卡诺图简化布尔表达式的过程。

Steps to Simplify a Boolean Expression using K Map

以下步骤涉及使用卡诺图简化给定的布尔表达式 −

Step 1 − 根据给定布尔函数中的变量数量选择一个卡诺图。

Step 2 − 识别最小项（以 SOP 形式表示）或最大项（以 POS 形式表示）。

Step 3 − For SOP (Sum of Products) Form ，根据给定函数的最小项，在卡诺图的单元格中放入 1。按照如下方式解读卡诺图 −

  1. 针对与任何其他 1 不相邻的 1 来解读卡诺图。这些 1 是孤立最小项，因此必须按原样解读，因为它们不能成组组合。

  2. 针对仅与另一个 1 相邻的 1 来解读卡诺图。将这些最小项组合成 2 平方。

  3. 针对相邻 1 的四边形（4 平方）、八边形（8 平方）等等来解读卡诺图，即使它们已经有一些组合成其他组的 1。需要记住的唯一事情是它们必须在几何上形成一个矩形或一个正方形。

  4. 针对尚未分组的任何 1 来解读卡诺图，并尽可能将它们分组到更大的正方形或矩形中。

  5. 最后，获得所有组的产品项，然后将它们相加形成最小的 SOP 表达式。

For POS (Product of Sums) Form ，将 0 放置在 K-Map 的单元格中，相对于给定函数的最大项。读取 K-Map 如下：

  1. 读取不与其他任何 0 相邻的 0 的 K-map。这些 0 是孤立的最大项，因此它们应按原样读取，因为它们无法组合成组。

  2. 读取仅与一个其他 0 相邻的 K-map 中的 0。将此类最大项组合到 2 平方格中。

  3. 读取 0 的四联体（4 平方格）、八联体（8 平方格），依此类推，即使它们有一些 0 已组合到其他组中。唯一需要记住的是它们必须在几何上形成一个矩形或正方形。

  4. 读取任何尚未组合的 0 的 K-map，并在可能的情况下将它们组合成更大的正方形或矩形。

  5. 最后，获得所有组的和项，然后将它们相乘以形成最小的 POS 表达式。

让我们借助一些已解决的示例了解使用 K-map 简化布尔表达式的这个过程。

Example 1

使用 K-Map 以 SOP 形式化简以下 3 变量布尔函数。

\mathrm{F(P, \: Q, \:R) \: = \: \sum m ( 0, \: 1, \: 3, \: 5, \: 7)}

Solution

给定布尔函数的 K-Map 表示如下图 1 所示。

k map representation

此 K-map 的化简按以下步骤进行：

  1. 没有孤立的 1。

  2. 最大项 m1 与最大项 m3、m5 和 m7 形成一个 4 平方格。创建它并将其读为 R。

  3. 最大项 m0 与最大项 m1 形成一个 2 平方格。创建它并将其读为 $\mathrm{\bar{P} \: \bar{Q}}$

  4. 将所有乘积项写成 SOP 形式。

因此，简化的 SOP 表达式为：

\mathrm{F \: = \: R \: + \: \bar{P}\bar{Q}}

Example 2

使用 K-map 以 POS 形式简化以下 3 变量布尔函数。

\mathrm{F(A, \: B, \: C) \: = \: \Pi \: M(1, \: 2, \: 4, \: 6)}

Solution

图 2 中显示了给定布尔函数的 POS K 地图表示。

pos k map representation

这个 POS K 地图的简化按下列步骤进行：

  1. 极大项 M1 没有邻接。因此，保持原样并将其读作 $\mathrm{(A \: + \: B \: + \: \bar{C})}$.

  2. 极大项 M2 只有一个邻接 M6。因此，将极大项 M2 展开为一个包含极大项 M6 的 2 平方，并将该 2 平方读作 $\mathrm{(\bar{B} \: + \: C)}$.

  3. 极大项 M4 也只有一个邻接 M6。因此，将极大项 M4 展开为一个包含极大项 M6 的 2 平方，并将该 2 平方读作 $\mathrm{(\bar{A} \: + \: C)}$.

  4. 以 POS 形式书写所有和式。

因此，简化的 POS 表达式为：

\mathrm{F \: = \: (A \: + \: B \: + \: \bar{C}) \: (\bar{B} \: + \: C) \: (\bar{A} \: + \: C)}

Example 3

简化下列 4 变量布尔函数的 SOP 形式，以获得极小 SOP 表达式。

\mathrm{F(A, \: B, \: C, \:D) \: = \: \sum \: m( 0,\: 1, \:3, \: 5, \: 7, \: 6, \: 10, \: 13, \: 14, \: 15)}

Solution

图 3 显示了给定布尔函数的 SOP K 地图表示。

sop k map representation

这个 SOP K 地图的简化按下列步骤进行：

  1. 没有孤立的 1。

  2. 极小项 m1 有 3 个邻接 m3、m5 和 m7。因此，将 m1 展开为一个包含极小项 m3、m5 和 m7 的 4 平方，并将该 4 平方读作 $\mathrm{\bar{A}D}$。

  3. 极小项 m5 有 3 个邻接 m7、m13 和 m15。将 m5 展开为一个包含极小项 m7、m13 和 m15 的 4 平方，并将该 4 平方读作 BD。

  4. 极小项 m6 也有 3 个邻接 m7、m14 和 m15。将 m6 展开为一个包含极小项 m7、m14 和 m15 的 4 平方，并将该 4 平方读作 BC。

  5. 极小项 m10 只有一个邻接 m14。将 m10 展开为一个包含极小项 m14 的 2 平方，并将该 2 平方读作 $\mathrm{AC\bar{D}}$。

  6. 极小项 m0 也只有一个邻接 m1。将 m0 展开为一个包含极小项 m1 的 2 平方，并将该 2 平方读作 $\mathrm{\bar{A}\bar{B}\bar{C}}$。

  7. 将所有乘积项写成 SOP 形式。

因此，简化的 SOP 表达式为：

\mathrm{F \: = \: \bar{A}D \: + \: BD \: + \: BC \: + \: AC\bar{D} \: + \: \bar{A}\bar{B}\bar{C}}

Conclusion

这样，我们可以使用 K 地图简化给定的布尔表达式，以获得极小表达式。尝试解决以下教程问题以获得更好的理解。

Q. 1 − 将以下 3 个变量布尔函数化简为 SOP 形式，以获得其极小表达式。

\mathrm{F(A, \: B, \: C) \: = \: \sum \: m(1, \: 2, \: 4, \: 5, \: 7)}

*Q. 2 *− 将以下 4 个变量布尔函数化简为 SOP 形式，以获得极小布尔表达式。

\mathrm{F(A, \: B, \: C, \: D) \: = \: \sum \: m(0, \: 1, \: 2, \: 4, \: 5, \: 7, \: 8, \: 9, \: 10, \: 12, \: 14, \: 15)}