$n$変数式の標準形

$n$変数真理関数を表わす論理式についても，前節の$2$変数の方法を拡張して 次の定理のように標準形を作ることができる。 以下では，表現を簡単にするため

$$X_1 \land X_2 \land \cdots \land X_n を \bigwedge_{i=1}^n X_i$$ (1.14)

$$X_1 \lor X_2 \lor \cdots \lor X_n を \bigvee_{i=1}^n X_i$$ (1.15)

と書く。

定理2.2

$\phi$ を $n$ 変数真理関数とする。 $\{ (X_1,\cdots ,X_n)\vert \phi(X_1,\cdots ,X_n) = F \}$ を $\{ (\bar{\sigma}_{k1}, \bar{\sigma}_{k2},\cdots ,\bar{\sigma}_{kn})\vert k=1,2,\cdots ,m\}$ とし、

$$\bar{\sigma}_{ki}(X_i) = \left\{ \begin{array}{lc} X_i... ...}_{ki} = T のとき \end{array} \right. (i = 1,2,\cdots ,m)$$

とおけば、$\phi$の主$\bigwedge$標準形(principal disjunctivenormal form) による表現が与えられる。

$$\phi(X_1, \cdots ,X_n) =\bigwedge_{k=1}^m(\bigvee_{i=1}^n\bar{\sigma}_{ki}(X_i))$$ (1.16)

課題

主$\bigwedge$標準形が$\phi$ を表現する論理式であること、すなわち、

$$\phi(X_1,\cdots,X_n) = \bigwedge_{K=1}^m(\bigvee_{i=1}^n\bar{\sigma}_{ki}(X_i))$$

が成立することを示せ。

定理2.2と相対な次の定理も得られる:

定理2.3

$\phi$ を $n$ 変数真理関数とする。 $\{ (X_1,\cdots ,X_n)\vert \phi(X_1,\cdots ,X_n) = T \}$ を $\{ (\sigma_{k1}, \sigma_{k2},\cdots ,\sigma_{kn}\vert k=1,2,\cdots ,m\}$ とし、

$$\sigma_{ki}(X_i) = \left\{ \begin{array}{lc} X_i, & \s... ...a_{ki} = F のとき \end{array} \right. (i = 1,2,\cdots ,m)$$

とおけば、$\phi$の主$\lor$-標準形(principal conjunctive normal form)

$$\phi(X_1, \cdots ,X_n) = \bigvee_{k=1}^m(\bigwedge_{i=1}^n\sigma_{ki}(X_i))$$

が得られる。

主$\land$-標準形 を導くアルゴリズム

与えられた $\phi$ の真理表から、主$\land$-標準形 を導くアルゴ リズムを述べる。

$\phi$ の真理表

$$\begin{array}{\vert c\vert\vert c\vert} \hline X_1 \cdots... ... \\ \hline F \cdots F & v_{2^n} \\ \hline \end{array}$$

に対し、

(1).

$\phi$ の関数値 $v_j$ が $F$ である行に着目する。（定理の前提 から $m$ 行ある。）

(2).

(1) で着目した各行について、 $i=1,2,\cdots ,n$ に対し、$X_i$ の値が $T$ ならば $\neg X_i$ を、$F$ ならば $X_i$をつくってこれらを $\lor$ で結ぶ。（これにより、 $K=1,2,\cdots,m$ につい て、 $\bigvee_{i=1}^n \bar{\sigma}_{ki}(X_i)$ ができる。）

(3).

(2) でつくられた $m$ 個の各式を $\land$ で結ぶ。（これによって、 $\bigwedge_{K=1}^m(\bigvee_{i=1}^n\bar {\sigma}_{ki}(X_i))$ が得られる。）

課題

$$\phi(X_1,\cdots,X_n) = \bigvee_{K=1}^m(\bigwedge_{i=1}^n{\sigma}_{ki}(X_i))$$

が成立することを示せ。

定理3

全ての真理関数は $\lnot,\land,\lor$ の３種類の論理記号のみを用いた 論理式で表現できる。

証明

標準形の定理2.2,定理2.3から明らかである。

さらに以下の定理が成立つ。

定理4

(1)

全ての論理式（真理関数）は論理記号$\lnot,\land$のみを用いた論理式で表現できる。

(2)

全ての論理式（真理関数）は論理記号$\lnot,\lor$のみを用いた論理式で表現できる。

証明

$({\rm 1})$の証明：定理1.2の２重否定の法則 とドモルガンの法則を用いれば

$$X \lor Y = \neg \neg (X \lor Y) = \neg (\neg X \land \neg Y)$$

であるから$\lor$は$\neg$と$\land$によって表現できる。 このことと定理4から$({\rm 1})$が得られる。
$({\rm 2})$の証明：定理2.2のの２重否定の法則 とドモルガンの法則を用いれば

$$X \land Y = \neg \neg (X \land Y) = \neg (\neg X \lor \neg Y)$$

このことと定理4から$({\rm 2})$が得られる。
$\Box$