命題計算の完全性定理

体系 $H$ については，次の事実が知られている:

定理7(命題計算の妥当性)

$\vdash_H \cal A$ ならば$\cal A$ が恒真論理式である。 $\Box$ この定理は，命題計算の体系についての妥当性と呼ばれるものである。

妥当性の証明

$\vdash_H \cal A$が成立すれば$\cal A$が恒真論理式であることを示そう。

$\vdash_H \cal A$が成り立つとすると， 系$H$の「証明」である論理式の列

$${\cal A}_1,{\cal A}_2, \cdots,{\cal A}_n$$

があって，$\cal A$は最後の${\cal A}_n$と一致しているものとしてよい。 各${\cal A}_i$は

(1).

公理系の各公理の形の論理式である。この場合，各公理は恒真論理式 であるから${\cal A}_i$は恒真論理式である。

(2).

論理式 ${\cal A}_i$ の前に論理式 ${\cal A}_j$と${\cal A}_k$ $(j,k<i)$があり，${\cal A}_k$は ${\cal A}_j \Rightarrow {\cal A}_i$ の 形をしている。 $i$より前の論理式は恒真論理式であると仮定すると， ${\cal A}_j$と ${\cal A}_j \Rightarrow {\cal A}_i$が真理値$T$しかとらないから真理値表

${\cal A}_j$	${\cal A}_i$	${\cal A}_j \Rightarrow {\cal A}_i$
$F$	$F$	$T$
$F$	$T$	$T$
$T$	$F$	$F$
$T$	$T$	$T$

から明らかなように${\cal A}_i$の真理値は$T$しか取り得ない。 すなわち${\cal A}_i$は恒真論理式である。$\Box$

定理8(命題計算の無矛盾性)

命題論理の公理系${\bf H}$は無矛盾である。 すなわち

$$\vdash_H {\cal A} \qquad \vdash_H \lnot {\cal A}$$

となるような論理式は存在しない。 $\Box$ この定理は，命題計算の体系についての無矛盾性と呼ばれるものである。

無矛盾性の証明

公理系${\bf H}$が矛盾すれば 定理6により任意の論理式${\cal C}$が証明可能である。 従って，${\cal C}$は定理7により恒真論理式である。 しかるに，${\bf H}$の命題変数$X$は論理式ではあるが恒真論理式 ではない。$\Box$

定理9(命題計算の完全性定理)

$\cal A$ が恒真論理式であることの必要十分条件は， $\vdash_H \cal A$ が成立することである。$\Box$ この定理は，命題計算の体系についての完全性定理(completeness theorem)と呼ばれるものである。

完全性定理の証明

$\vdash_H \cal A$が成立すれば$\cal A$が恒真論理式であることは 妥当性の定理で既に証明済みである。 逆に$\cal A$が恒真論理式であるときに， $\vdash_H \cal A$が成立することをいうには次の補題が必要になる。

補題

$\cal A$が命題変数 $X_1,X_2,\cdots,X_n$から構成される論理式とする。 命題変数 $X_1,X_2,\cdots,X_n$に真理値$T,F$をふり当て，そのふり当てに対し$\cal A$の真理値が$T$である場合

$$\delta X_1,\delta X_2,\cdots \delta X_n \vdash_H \cal A$$

$\cal A$の真理値が$F$である場合

$$\delta X_1,\delta X_2,\cdots \delta X_n \vdash_H \cal \lnot A$$

である。ただし，$\delta X_i$は$X_i$に対する真理値のふり当てが$T$の場合$X_i$，$F$の場合は$\lnot X_i$とする。$\Box$

定理9の証明の続き

恒真論理式$\cal A$が命題変数 $X_1,X_2,\cdots,X_n$から構成されるものとする。 命題変数 $X_1,X_2,\cdots,X_n$に真理値$T,F$をどのようにふり当てても， $\cal A$の真理値は常に$T$である。

命題変数 $X_1,X_2,\cdots,X_n$に真理値$T,F$どのようにふり当てるしかたは $2^n$通りある。これを辞書式順序で全て列挙し[補題]を適用すると

$$\begin{eqnarray*} &&X_1,X_2,\cdots , X_n \vdash_H \cal A \\ &&X_1,X_2,\cdots ... ... &&\lnot X_1,\lnot X_2,\cdots , \lnot X_n \vdash_H \cal A \\ \end{eqnarray*}$$

が得られる。最初の２式から演繹定理により

$$\begin{eqnarray*} &&X_1,X_2,\cdots , X_{n-1} \vdash X_n \Rightarrow \cal A \\ ... ..._1,X_2,\cdots , X_{n-1} \vdash \lnot X_n \Rightarrow \cal A \\ \end{eqnarray*}$$

これから公理$(5)$と，公理$(15)$を用いて；

$$X_1,X_2,\cdots , X_{n-1} \vdash_H \cal A$$

が得られる。すなわち$X_n$が消去された。同様にして順次に２式ずつ 同じ手順を繰り返せば，$X_n$が消去された$2^{n-1}$個の式を得る。この $2^{n-1}$個の式から$X_{n-1}$を２式ずつをとり同じ手順を繰り返すと$X_{n-1}$が 消去された$2^{n-2}$個の式を得る。 この手順を繰り返せば変数 $X_1,X_2,\cdots,X_n$が全て消去され，結局

$$\vdash_H \cal A$$

を得る。$\Box$

補題の証明

論理式$\cal A$がただ１つの命題変数$X$からなるとき 　　　　 　　　　$X$に対するふり当てが$T$のとき

$$X \vdash_H X$$

　　　　$F$のとき

$$\lnot X \vdash_H \lnot X$$

これは公理の$(1)$から容易に示される。

これ以外の場合は，$\cal A$は $\cal \lnot B,B \land C,B \lor C$の形をして いる。この場合，部分式$\cal B,C$については この補題が成り立つものとする。

$\cal A$ が$\cal \lnot B$である場合

$\cal A$の値が$T$のとき$\cal B$の値は$F$であるから

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \lnot \cal B$$

$\cal A$の値が$F$のとき$\cal B$の値は$T$であるから

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal B$$

　 $\cal B,\lnot B$はそれぞれ$\cal A$及び$\cal \lnot A$である。

$\cal A$ が$\cal B \lor C$である場合

$\cal A$の値が$T$のとき$\cal B,C$の少なくともどちらか一方の値は $T$であるから，$\cal B$の値が$T$としても一般性を失わない。このとき

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal B$$

が成り立っている。これと公理の$(3)$

$$\cal B \Rightarrow B \lor C$$

により

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal B \lor C$$

$\cal B \lor C$は$\cal A$に他ならない。

$\cal A$の値が$F$のとき$\cal B,C$の値はともに$F$でなければならない。 このとき

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal \lnot B$$

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal \lnot C$$

これに推論法則の「論理積」

$$\frac{\cal P,Q}{\cal P \land Q}$$

を用いて

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal \lnot B\land \lnot C$$

を得る。 $\cal \lnot B \land \lnot C$は $\cal \lnot A(=\lnot (B \lor C))$に他ならない。

$\cal A$ が $\cal B \land C$である場合

$\cal A$の値が$T$のとき$\cal B,C$の値はともに$T$でなければならない。 このとき

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal B$$

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal C$$

これに推論法則の「論理積」

$$\frac{\cal P,Q}{\cal P \land Q}$$

を用いて

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal B\land C$$

を得る。 $\cal B \land C$は$\cal A$に他ならない。

$\cal A$の値が$F$のとき$\cal B,C$の少なくともどちらか一方の値は $F$であるから，$\cal B$の値が$F$としても一般性を失わない。このとき

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal \lnot B$$

が成り立っている。これと公理の$(3)$

$$\cal P \Rightarrow P \lor Q$$

により

$$\delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H \cal \lnot B \lor \lnot C$$

$\cal \lnot B \lor \lnot C$は $\cal \lnot A=\lnot(B \land C)$に他ならない。 　

$\Box$