使用布林代數化簡

---

---

什麼是卡諾圖 (K-Map)？

卡諾圖 (K-Map) 是一種圖形工具，用於簡化以標準形式表示的布林表示式，以獲得其最小形式。

卡諾圖基本上是一個圖表，由相鄰的單元格或方塊組成，每個單元格代表函式變數的特定組合，以和式或積式表示。

卡諾圖中單元格的數量取決於布林函式中變數的數量，即，K-map 有 2ⁿ 個相鄰單元格，其中 n 是布林表示式中變數的數量。因此，2變數卡諾圖中的單元格數量為 4 (2²)，3變數卡諾圖中的單元格數量為 8 (2³)，4變數卡諾圖中的單元格數量為 16 (2⁴)，依此類推。

但是，我們可以對任意數量的變數使用卡諾圖。但是，對於簡化超過 5 個變數的布林函式，它會變得繁瑣。

現在，讓我們討論使用卡諾圖簡化布林表示式的過程。

使用卡諾圖簡化布林表示式的步驟

使用卡諾圖簡化給定布林表示式涉及以下步驟：

步驟 1 - 根據給定布林函式中變數的數量選擇卡諾圖。

步驟 2 - 識別最小項（在 SOP 形式中）或最大項（在 POS 形式中）。

步驟 3 - 對於SOP（積之和）形式，根據給定函式的最小項在卡諾圖的單元格中放入 1。讀取卡諾圖如下：

• 讀取卡諾圖中與任何其他 1 不相鄰的 1。這些 1 是孤立的最小項，因此需要按原樣讀取，因為它們不能組合成組。
• 讀取卡諾圖中僅與另一個 1 相鄰的 1。將此類最小項組合成 2-方塊。
• 讀取卡諾圖中相鄰 1 的四元組（4-方塊）、八元組（8-方塊）等等，即使它們有一些 1 已經在其他組中組合。唯一需要注意的是，它們必須幾何地形成矩形或正方形。
• 讀取卡諾圖中尚未分組的任何 1，如果可能，將它們分組到更大的正方形或矩形中。
• 最後，獲得所有組的乘積項，然後將它們加起來形成最小的 SOP 表示式。

對於POS（和之積）形式，根據給定函式的最大項在卡諾圖的單元格中放入 0。讀取卡諾圖如下：

• 讀取卡諾圖中與任何其他 0 不相鄰的 0。這些 0 是孤立的最大項，因此需要按原樣讀取，因為它們不能組合成組。
• 讀取卡諾圖中僅與另一個 0 相鄰的 0。將此類最大項組合成 2-方塊。
• 讀取卡諾圖中相鄰 0 的四元組（4-方塊）、八元組（8-方塊）等等，即使它們有一些 0 已經在其他組中組合。唯一需要注意的是，它們必須幾何地形成矩形或正方形。
• 讀取卡諾圖中尚未組合的任何 0，如果可能，將它們組合到更大的正方形或矩形中。
• 最後，獲得所有組的和項，然後將它們相乘形成最小的 POS 表示式。

讓我們藉助一些已解決的示例來了解使用卡諾圖簡化布林表示式的過程。

示例 1

使用卡諾圖簡化以下 SOP 形式的 3 變數布林函式。

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

解答

給定布林函式的卡諾圖表示如圖 1 所示。

根據以下步驟簡化此卡諾圖：

• 沒有孤立的 1。
• 最小項 m₁ 與最小項 m₃、m₅ 和 m₇ 形成一個 4-方塊。將其組合並讀取為 R。
• 最小項 m₀ 與最小項 m₁ 形成一個 2-方塊。將其組合並讀取為 $\mathrm{\bar{P} \: \bar{Q}}$
• 以 SOP 形式編寫所有乘積項。

因此，簡化的 SOP 表示式為：

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

示例 2

使用卡諾圖簡化以下 POS 形式的 3 變數布林函式。

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

解答

給定布林函式的 POS 卡諾圖表示如圖 2 所示。

根據以下步驟簡化此 POS 卡諾圖：

• 最大項 M₁ 沒有相鄰項。因此，按原樣保留它並將其讀取為 $\mathrm{(A \: + \: B \: + \: \bar{C})}$.
• 最大項 M₂ 只有一個相鄰項 M₆。因此，將最大項 M₂ 擴充套件為與最大項 M₆ 的 2-方塊，並將 2-方塊讀取為 $\mathrm{(\bar{B} \: + \: C)}$。
• 最大項 M₄ 也只有一個相鄰項 M₆。因此，將最大項 M₄ 擴充套件為與最大項 M₆ 的 2-方塊，並將 2-方塊讀取為 $\mathrm{(\bar{A} \: + \: C)}$。
• 以 POS 形式編寫所有和項。

因此，簡化的 POS 表示式為：

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

示例 3

簡化以下 SOP 形式的 4 變數布林函式以獲得最小的 SOP 表示式。

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

解答

給定布林函式的 SOP 卡諾圖表示如圖 3 所示。

根據以下步驟簡化此 SOP 卡諾圖：

• 沒有孤立的 1。
• 最小項 m₁ 有三個相鄰項 m₃、m₅ 和 m₇。因此，將 m₁ 擴充套件為與最小項 m₃、m₅ 和 m₇ 的 4-方塊，並將 4-方塊讀取為 $\mathrm{\bar{A}D}$。
• 最小項 m₅ 有三個相鄰項 m₇、m₁₃ 和 m₁₅。將 m₅ 擴充套件為與最小項 m₇、m₁₃ 和 m₁₅ 的 4-方塊，並將 4-方塊讀取為 BD。
• 最小項 m₆ 也具有三個相鄰項 m₇、m₁₄ 和 m₁₅。將 m₆ 擴充套件為與最小項 m₇、m₁₄ 和 m₁₅ 的 4-方塊，並將 4-方塊讀取為 BC。
• 最小項 m₁₀ 只有一個相鄰項 m₁₄。將 m₁₀ 擴充套件為與最小項 m₁₄ 的 2-方塊，並將 2-方塊讀取為 $\mathrm{AC\bar{D}}$。
• 最小項 m₀ 也只有一個相鄰項 m₁。將 m₀ 擴充套件為與最小項 m₁ 的 2-方塊，並將 2-方塊讀取為 $\mathrm{\bar{A}\bar{B}\bar{C}}$。
• 以 SOP 形式編寫所有乘積項。

因此，簡化的 SOP 表示式為：

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

結論

透過這種方法，我們可以使用卡諾圖（K-map）簡化給定的布林表示式，得到最小表示式。嘗試解決以下練習題以更好地理解。

題 1 − 將以下三變數布林函式化簡為SOP形式，得到其最小表示式。

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

題 2 − 將以下四變數布林函式化簡為SOP形式，得到其最小布爾表示式。

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