Digital-electronics 简明教程

Simplifications of Boolean Algebra

What is a Karnaugh Map (K-Map)?

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

K-Map is a graphical tool used for simplifying Boolean expressions represented in their standard form to obtain their minimal form.

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

The K-Map is basically a graph or chart that composed of an arrangement of adjacent cells or squares, where each cell represents a particular combination of variables of the function either in sum or product form.

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

The number of cells in the K-Map depends upon number of variables in the Boolean function, i.e., K-map has 2n adjacent cells, where n is the number of variables in the Boolean expression. Therefore, the number of cells in a 2 variable K-map are 4 (22), in 3 variable KMap, the number of cells are 8 (23), in 4 variable K-map, the number of cells are 16 (24), and so on.

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

However, we can use the K Map for any number of variables. But, for simplifying Boolean functions in variables more than 5, it becomes tedious.

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

Now, let us discuss the procedure of simplifying a Boolean expression using K-Map.

Steps to Simplify a Boolean Expression using K Map

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

The following steps are involving in simplification of a given Boolean expression by using K-Map −

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

Step 1 − Select a K-Map as per the number of variables in the given Boolean function.

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

Step 2 − Identify the minterms (in SOP form) or maxterms (in POS form).

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

Step 3 − For SOP (Sum of Products) Form, put 1s in cells of the K-Map with respect to the minterms of given function. Read the K-Map as follows −

  1. Read the K-map for 1s which are not adjacent to any other 1. These 1s are the isolated minterms, thus they are to be read as they are, because they cannot be combine in groups.

  2. Read the K-map for 1s which are adjacent only one other 1. Combine such minterms in 2-squares.

  3. Read the K-map for quads (4-squares), octets (8-squares), and so on of adjacent 1s even if they have some 1s which are already combined in other groups. The only thing to remember that they must geometrically form a rectangle or a square.

  4. Read the K-map for any 1s that have not been grouped yet and group them into bigger squares or rectangles if possible.

  5. Finally, obtain product terms of all the groups, and then sum up them to form the minimal SOP expression.

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

For POS (Product of Sums) Form, put 0s in cells of the K-Map with respect to the maxterms of given function. Read the K-Map as follows −

  1. Read the K-map for 0s which are not adjacent to any other 0. These 0s are the isolated maxterms, thus they are to be read as they are, because they cannot be combine in groups.

  2. Read the K-map for 0s which are adjacent only one other 0. Combine such maxterms in 2-squares.

  3. Read the K-map for quads (4-squares), octets (8-squares), and so on of adjacent 0s even if they have some 0s which are already combined in other groups. The only thing to remember that they must geometrically form a rectangle or a square.

  4. Read the K-map for any 0s that have not been combined yet and combine them into bigger squares or rectangles if possible.

  5. Finally, obtain sum terms of all the groups, and then product them to form the minimal POS expression.

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

Let us understand this procedure of simplifying Boolean expression using K-map with the help of some solved examples.

Example 1

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

Simplify the following 3-variable Boolean function in SOP form using K-Map.

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

Solution

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

The K-Map representation of the given Boolean function is shown in Figure-1.

k map representation

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

The simplification of this K-map is done as per the following steps −

  1. There are no isolated 1s.

  2. The minterm m1 forms a 4-square with minterms m3, m5, and m7. Make it and read it as R.

  3. The minterm m0 forms a 2-square with the minterm m1. Make it and read it as $\mathrm{\bar{P} \: \bar{Q}}$

  4. Write all the product terms in SOP form.

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

Thus, the simplified SOP expression is,

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

Example 2

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

Simplify the following 3-variable Boolean function in POS form using K-Map.

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

Solution

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

The POS K-map representation of the given Boolean function is shown in Figure-2.

pos k map representation

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

The simplification of this POS K-map is done as per the following steps −

  1. The maxterm M1 has no adjacency. Thus, keep it as it is and read it as $\mathrm{(A \: + \: B \: + \: \bar{C})}$.

  2. The maxterm M2 has only one adjacency M6. Hence, expand the maxterm M2 into a 2-square with the maxterm M6 and read the 2-square as $\mathrm{(\bar{B} \: + \: C)}$.

  3. The maxterm M4 also has only one adjacency M6. Hence, expand the maxterm M4 into a 2-square with the maxterm M6 and read the 2-square as $\mathrm{(\bar{A} \: + \: C)}$.

  4. Write all the sum terms in POS form.

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

Therefore, the simplified POS expression is,

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

Example 3

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

Simplify the following 4-variable Boolean function in SOP form to obtain the minimal SOP expression.

\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 of the given Boolean function is shown in Figure-3.

sop k map representation

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

The simplification of this SOP K-map is done as per the following steps −

  1. There are no isolated 1s.

  2. The minterm m1 has three adjacencies m3, m5, and m7. So expand m1 into a 4-square with minterms m3, m5, and m7, and read the 4-square as $\mathrm{\bar{A}D}$.

  3. The minterm m5 has three adjacencies m7, m13, and m15. Expand m5 into a 4-square with minterms m7, m13, and m15, and read the 4-square as BD.

  4. The minterm m6 also has three adjacencies m7, m14, and m15. Expand m6 into a 4- square with minterms m7, m14, and m15, and read the 4-square as BC.

  5. The minterm m10 has only one adjacency m14. Expand m10 into a 2-square with minterm m14 and read the 2-square as $\mathrm{AC\bar{D}}$.

  6. The minterm m0 also has only one adjacency m1. Expand m0 into a 2-square with minterm m1 and read the 2-square as $\mathrm{\bar{A}\bar{B}\bar{C}}$.

  7. Write all the product terms in SOP form.

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

Hence, the simplified SOP expression is,

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

Conclusion

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

In this way, we can simplify a given Boolean expression using K-map to obtain the minimal expression. Try solving the following tutorial problems for better understanding.

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

Q. 1 − Simplify the following 3-variable Boolean function in SOP form to obtain its minimal expression.

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

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

*Q. 2 * − Simplify the following 4-variable Boolean function in SOP form to obtain the minimal Boolean expression.

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