ブール関数 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

   主項をすべて列挙する。 隣接する最小項（ちょうど 1 ビットだけ異なるもの）をまとめ、極大なグループだけを残すと、7 個の主項が得られる。

   $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)$

   どのグループもセルは 2 個しかない。この最小項の集合から 4 個を選んでカルノー図の正方形をなすものが存在しないので、$4$ セルのまとまりはどこにも作れない。

3. 3

   必須の項を特定する。 最小項 $m_5$ を覆うのは $A'BC'D$ だけ、$m_{15}$ を覆うのは $ABCD$ だけなので、この 2 つの完全な最小項は必須であり、必ず現れなければならない。同様に $m_6$ は $A'CD'$ にしか現れず、$m_9$ は $AB'C'$ にしか、$m_{12}$ は $AC'D'$ にしか現れない——さらに 3 個の必須主項である。

4. 4

   残りを覆う。 必須の 5 項 $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'$ でも拾うことができ、どちらもサイズは 2 なので、同じコストの最簡被覆がちょうど 2 通り存在する。

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$）はこの集合の中に隣接する項をもたないので、図のまとめ方によらず 4 リテラルの積項のまま残るのである。