展開定理による加法標準形の導出

$$f(x_1, x_2, x_3, \ldots , x_n)$$ (9)

$$\sim x_1 \lor x_1 = 1$$ (10)

式(9)と1の論理積をとっても変わらない。

$$f(x_1, x_2, x_3, \ldots , x_n) = f(x_1, x_2, x_3, \ldots , x_n) \cdot 1$$

1を式(10)で置き換える。

$$f(x_1, x_2, x_3, \ldots , x_n) = f(x_1, x_2, x_3, \ldots , x_n)(\sim x_1 \lor x_1)$$

$$= \sim x_1 f(x_1, x_2, x_3, \ldots , x_n) \lor x_1 f(x_1, x_2, x_3, \ldots , x_n)$$

展開定理を適用すると次のようになる。

$$f(x_1, x_2, x_3, \ldots , x_n) = \sim x_1 f(0, x_2, x_3, \ldots , x_n)$$ (11)

$$\lor x_1 f(1, x_2, x_3, \ldots , x_n)$$ (12)

式(12)の右辺第1項の$f$を取り出す。

$$f(0, x_2, x_3, \ldots , x_n)$$ (13)

$$\sim x_2 \lor x_2 = 1$$ (14)

式(13)と1の論理積をとっても変わらない。

$$f(0, x_2, x_3, \ldots , x_n) = f(0, x_2, x_3, \ldots , x_n) \cdot 1$$

1を式(14)で置き換える。

$$f(0, x_2, x_3, \ldots , x_n) = f(0, x_2, x_3, \ldots , x_n)(\sim x_2 \lor x_2)$$

$$= \sim x_2 f(0, x_2, x_3, \ldots , x_n) \lor x_2 f(0, x_2, x_3, \ldots , x_n)$$

展開定理を適用すると次のようになる。

$$f(0, x_2, x_3, \ldots , x_n) = \sim x_2 f(0, 0, x_3, \ldots , x_n)$$ (15)

$$\lor x_2 f(0, 1, x_3, \ldots , x_n)$$ (16)

式(12)の右辺第2項の$f$を取り出す。

$$f(1, x_2, x_3, \ldots , x_n)$$ (17)

式(17)と1の論理積をとっても変わらない。

$$f(1, x_2, x_3, \ldots , x_n) = f(1, x_2, x_3, \ldots , x_n) \cdot 1$$

1を式(14)で置き換える。

$$f(1, x_2, x_3, \ldots , x_n) = f(1, x_2, x_3, \ldots , x_n)(\sim x_2 \lor x_2)$$

$$= \sim x_2 f(1, x_2, x_3, \ldots , x_n) \lor x_2 f(1, x_2, x_3, \ldots , x_n)$$

展開定理を適用すると次のようになる。

$$f(1, x_2, x_3, \ldots , x_n) = \sim x_2 f(1, 0, x_3, \ldots , x_n)$$ (18)

$$\lor x_2 f(1, 1, x_3, \ldots , x_n)$$ (19)

式(12)に式(16)と式(19)を代入す れば、次のようになる。

$$f(x_1, x_2, x_3, \ldots , x_n) = \sim x_1 \sim x_2 f(0, 0, x_3, \ldots , x_n)$$

$$\lor \sim x_1 x_2 f(0, 1, x_3, \ldots , x_n)$$

$$\lor x_1 \sim x_2 f(1, 0, x_3, \ldots , x_n)$$

$$\lor x_1 x_2 f(1, 1, x_3, \ldots , x_n)$$

この展開手続きを $x_3, x_4, \cdots, x_n$についても行えば、最終的に次のよ うな式が得られる。

$$f(x_1, x_2, x_3, \ldots , x_n) = \sim x_1 \sim x_2 \ldots \sim x_{n-1} \sim x_nf(0, 0, \ldots , 0, 0)$$

$$\lor \sim x_1 \sim x_2 \ldots \sim x_{n-1} x_n f(0, 0, \ldots , 0, 1)$$

$$\lor \sim x_1 \sim x_2 \ldots x_{n-1} \sim x_n f(0, 0, \ldots , 1, 0)$$

$$\lor \sim x_1 \sim x_2 \ldots x_{n-1} x_n f(0, 0, \ldots , 1, 1)$$

$$\vdots$$

$$\lor x_1 x_2 \ldots x_{n-1} x_n f(1, 1, \ldots , 1, 1)$$

これを略記した最小項と関数値で表せば次のようになる。

$$f(x_1, x_2, x_3, \ldots , x_n) = m_0 f_0$$

$$\lor m_1 f_1$$

$$\lor m_2 f_2$$

$$\lor m_3 f_3$$

$$\vdots$$

$$\lor m_{2^n-1} f_{2^n-1}$$

この略記した最小項と関数値の順序を入れ換えて整理するとつぎのような加法標 準形になる。

$$f(x_1, x_2, x_3, \ldots , x_n) = f_0 m_0 \lor f_1 m_1 \lor f_2 m_2 \lor \cdots \lor f_{2^n-1}m_{2^n-1}$$

$$= \bigvee_{i=0}^{2^n-1}f_i m_i$$