把布林函數 F = A′B′C′D′ + A′B′CD′ + A′BC′D + A′BCD′ + AB′C′D′ + AB′C′D + ABC′D′ + ABCD 化簡成最簡的積之和形式。

Step-by-step solution

1. 1

   先把式子轉成最小項清單。 把每個乘積項讀成 $4$ 位元的樣式 $ABCD$（帶撇號的文字代表 $0$）：

   $A'B'C'D' = m_0, \ A'B'CD' = m_2, \ A'BC'D = m_5, \ A'BCD' = m_6$

   $AB'C'D' = m_8, \ AB'C'D = m_9, \ ABC'D' = m_{12}, \ ABCD = m_{15}$

   於是

   $F = \Sigma m(0, 2, 5, 6, 8, 9, 12, 15)$

   起始成本是 $8$ 個乘積項、$32$ 個文字。

2. 2

   列出所有主要蘊涵項。 把相鄰的最小項（恰好差一個位元的那些）合併，只保留最大的群組，得到七個主要蘊涵項：

   $A'B'D'\,(0,2), \quad A'CD'\,(2,6), \quad B'C'D'\,(0,8), \quad AC'D'\,(8,12)$

   $AB'C'\,(8,9), \quad A'BC'D\,(5), \quad ABCD\,(15)$

   每個群組都只含兩格 —— 整張圖上沒有任何 $4$ 格的方塊，因為這些最小項裡任何四個都湊不成卡諾圖上的一個方塊。

3. 3

   找出必要的項。 最小項 $m_5$ 只被 $A'BC'D$ 蓋到，$m_{15}$ 只被 $ABCD$ 蓋到，所以這兩個完整的最小項是必要的，非出現不可。同樣地，$m_6$ 只出現在 $A'CD'$ 裡、$m_9$ 只出現在 $AB'C'$ 裡、$m_{12}$ 只出現在 $AC'D'$ 裡 —— 這又是三個必要的主要蘊涵項。

4. 4

   把剩下的蓋起來。 這五個必要項 $A'BC'D$、$ABCD$、$A'CD'$、$AB'C'$、$AC'D'$ 合起來蓋住了 $\{2,5,6,8,9,12,15\}$，只剩下 $m_0$。它可以由 $A'B'D'$ 或 $B'C'D'$ 任一個接手，兩者大小都是二，所以恰好存在兩組成本相同的最簡覆蓋。

5. 5

   寫出最簡的積之和。 選 $A'B'D'$：

   $F = A'B'D' + A'CD' + A'BC'D + AB'C' + AC'D' + ABCD$

   另一組同樣最簡的寫法是把 $A'B'D'$ 換成 $B'C'D'$。無論哪一種，成本都是 $6$ 個乘積項、$20$ 個文字，比原本的 $8$ 個乘積項、$32$ 個文字要精簡。

6. 6

   用完整真值表驗證。 把化簡後的式子在全部 $16$ 種輸入組合上求值，結果恰好在 $\{0,2,5,6,8,9,12,15\}$ 上是 $1$、其餘都是 $0$。化簡幅度之所以有限，原因出在結構上：像 $m_5$（$0101$）與 $m_{15}$（$1111$）這種最小項在集合裡沒有鄰居，所以無論怎麼分組，它們都只能以完整的四文字乘積項留下來。