논리학, 그 열 번째 이야기 | 명제논리에서의 건전성 정리와 완전성 정리 ( Soundness Theorem and Completeness Theorem for Propositional Logic )

이번 글에서는 이론의 성질인 완전성과 건전성에 대해 이야기해보려고 한다. 완전성과 건전성은 형식 체계의 성질로, 형식 체계가 굳이 이를 만족할 필요는 없지만, 완전성과 건전성을 만족하는 보통은 완전성과 건전성을 만족하는 형식 체계를 사용한다. 완전성과 건전성은 다음과 같이 정의한다.

 

Definition 1.

구문론적 귀결 관계인 $\vdash$와 의미론적 귀결 관계인 $\models$를 포함하는 형식 체계가 있다고 하자. 이러한 형식 체계의 임의의 wff의 집합 $G$와 wff $\mathscr{C}$에 대하여 $G \vdash \mathscr{C}$가 $G \models \mathscr{C}$를 함의한다면, 이 형식 체계가 건전 (Sound)하다고 한다. 또한, 이 역이 성립하는 형식 체계를 완전 (Complete)하다고 한다. 즉, wff의 집합 $G$와 wff $\mathscr{C}$에 대하여 $G \models \mathscr{C}$가 $G \vdash \mathscr{C}$를 함의하는 형식 체계를 완전하다고 한다.

 

위의 정의에서 등장한 $\vdash$와 $\models$는 앞선 글들에서 소개했던 $\vdash$와 $\models$와 같은 맥락의 개념으로, 명제논리에서의 정의보다 더 일반화시킨 개념이라고 생각하면 된다.

 

명제논리는 위의 완전성과 건전성이 모두 성립한다. 다음 정리를 보자.

 

Theorem 1. 명제논리에서의 건전성 정리 ( Soundness Theorem for Propositional Logic )

명제논리는 건전성이 성립한다. 즉, wff의 집합 $\Sigma$와 wff $\mathscr{C}$에 대하여 $\Sigma \vdash \mathscr{C}$라면 $\Sigma \models \mathscr{C}$이다.

 

Proof.

$\Sigma \vdash \mathscr{C}$이므로 $\Sigma$로부터의 $\mathscr{C}$의 증명 $\mathscr{B}_1, \mathscr{B}_2, \cdots, \mathscr{B}_n$이 존재한다.

그러면 임의의 $1 \leq i \leq n$에 대하여 $\mathscr{B}_i$는 다음 중 하나이다.

a) $\mathscr{B}_i$는 명제논리의 공리이다.

b) $\mathscr{B}_i$는 $\Sigma$의 원소이다.

c) $\mathscr{B}_j = \left( \mathscr{B}_k \Rightarrow \mathscr{B}_i \right)$인 $1 \leq j,k < i$가 존재한다.

이제 귀납법을 통해 임의의 $1 \leq k \leq n$에 대하여 $\Sigma \models \mathscr{B}_k$임을 보일 것이다.

$k=1$인 경우를 살펴보자.

$\mathscr{B}_1$은 명제논리의 공리이거나 $\Sigma$의 원소이다. 따라서 $\mathscr{B}_1$은 항진명제이며, $\Sigma \models \mathscr{B}_1$임은 자명하다.

이제 $1 \leq i \leq k$인 모든 $i$에 대하여 $\Sigma \models \mathscr{B}_i$라고 가정하고 $\mathscr{B}_{k+1}$을 고려하자.

만약 $\mathscr{B}_{k+1}$이 명제논리의 공리라면, 이 글의 Theorem 3에 의해 $\Sigma \models \mathscr{B}_{k+1}$이다.

만약 $\mathscr{B}_{k+1} \in \Sigma$라면 $\Sigma \models \mathscr{B}_{k+1}$임이 자명하다.

만약 $\mathscr{B}_i = \left( \mathscr{B}_j \Rightarrow \mathscr{B}_{k+1} \right)$인 $1 \leq i,j \leq k$가 존재한다면, boolean interpretation $v$의 확장 $\bar{v}$의 정의에 의해 $\bar{v}(\mathscr{B}_i) = \bar{v}(\mathscr{B}_j) = \mathbf{T}$이면 $\bar{v}(\mathscr{B}_{k+1}) = \mathbf{T}$이다. 그런데, 귀납가정에 의해 $\Sigma \models \mathscr{B}_i$이고 $\Sigma \models \mathscr{B}_j$이므로 $\Sigma \models \mathscr{B}_{k+1}$이다.

따라서 임의의 $1 \leq i \leq n$에 대하여 $\Sigma \models \mathscr{B}_i$이며, 이때, $\mathscr{B}_1, \mathscr{B}_2, \cdots, \mathscr{B}_n$이 $\Sigma$로부터의 $\mathscr{C}$의 증명이므로 $\mathscr{B}_n = \mathscr{C}$이다. 따라서 $\Sigma \models \mathscr{C}$이다.

$\blacksquare$

 

이제 명제논리가 건전하다는 사실을 알게 되었으니 명제논리가 완전하다는 것을 증명할 차례이다. 명제논리가 완전하다는 것을 보이기에 앞서 다음 보조정리를 하나 확인하자.

 

Lemma 1.

$\mathscr{B}$가 wwf라고 하고 원자명제 $B_1, B_2, \cdots, B_n$가 $\mathscr{B}$를 구성한다고 하자. 이때, 주어진 boolean interpretation $v$에 대하여 $B'_k$를 $v(B_k) = \mathbf{T}$일 때에는 $B_k$로, $v(B_k) = \mathbf{F}$일 때에는 $\neg B_k$로 정의하고 $\mathscr{B}'$ 역시 같은 방식으로 정의하자. 그러면 $B'_1, B'_2, \cdots, B'_n \vdash \mathscr{B}'$이다.

 

Proof.

이에 대한 증명은 $\mathscr{B}$에 등장하는 $\neg$와 $\Rightarrow$의 개수인 $n$에 대한 수학적 귀납법으로 이루어질 것이다.

먼저, $n=0$인 경우, $\mathscr{B}$는 단순한 원자명제 $B_1$이다. 이때, $B_1 \vdash B_1$이고 $\neg B_1 \vdash \neg B_1$임은 자명하므로 $n=0$인 경우에 대해서는 보조정리가 성립한다.

이제 $j < n$인 모든 $j$에 대하여 보조정리가 성립한다고 가정하자. 그러면 $\mathscr{B}$는 $\neg \mathscr{C}$이거나 $\mathscr{C} \Rightarrow \mathscr{D}$이다.

 

먼저 $\mathscr{B}$가 $\neg \mathscr{C}$인 경우를 살펴보자.

만약 $\bar{v}(\mathscr{C}) = \mathbf{T}$라면, $\bar{v}(\mathscr{B}) = \mathbf{F}$이다. 따라서 $\mathscr{C}'$는 $\mathscr{C}$이고, $\mathscr{B}'$는 $\neg \mathscr{B}$이다. 여기에 귀납가정을 적용하면 $B'_1, B'_2, \cdots, B'_n \vdash \mathscr{C}$를 얻을 수 있다. 이때, $\mathscr{B}'$는 $\neg \neg \mathscr{C}$이고, DNE에 의해 $\mathscr{C} \vdash \neg \neg \mathscr{C}$이므로 $B'_1, B'_2, \cdots, B'_n \vdash \mathscr{B}'$이다.

만약 $\bar{v}(\mathscr{C}) = \mathbf{F}$라면, $\bar{v}(\mathscr{B}) = \mathbf{T}$이다. 따라서 $\mathscr{C}'$는 $\neg \mathscr{C}$이고, $\mathscr{B}'$는 $\mathscr{B}$이다. 여기에 귀납가정을 적용하면 $B'_1, B'_2, \cdots, B'_n \vdash \neg \mathscr{C}$를 얻을 수 있다. 이때, $\neg \mathscr{C}$는 $\mathscr{B}' = \mathscr{B}$이므로 $B'_1, B'_2, \cdots, B'_n \vdash \mathscr{B}'$이다.

 

이제 $\mathscr{B}$가 $\mathscr{C} \Rightarrow \mathscr{D}$인 경우를 살펴보자.

만약 $\bar{v}(\mathscr{C}) = \mathbf{F}$라면, $\bar{v}(\mathscr{B}) = \mathbf{T}$이다. 따라서 $\mathscr{C}'$는 $\neg \mathscr{C}$이고, $\mathscr{B}'$는 $\mathscr{B}$이다. 여기에 귀납가정을 적용하면 $B'_1, B'_2, \cdots, B'_n \vdash \neg \mathscr{C}$를 얻을 수 있다. 이때, $\neg \mathscr{C} \vdash \mathscr{C} \Rightarrow \mathscr{D}$이므로 $B'_1, B'_2, \cdots, B'_n \vdash \mathscr{B}'$이다. 만약 $\neg \mathscr{C} \vdash \mathscr{C} \Rightarrow \mathscr{D}$의 증명이 궁금하다면 아래의 '증명 보기'를 클릭하라.

 

$\neg \mathscr{C} \vdash \mathscr{C} \Rightarrow \mathscr{D}$는 다음과 같이 증명할 수 있다.

$$ \begin{array}{rll} 1. & \neg \mathscr{C} & \text{Hyp} \\ 2. & \mathscr{C} & \text{Hyp} \\ 3. & \mathscr{C} \Rightarrow \left( \neg \mathscr{D} \Rightarrow \mathscr{C} \right) & \href{https://chocobear.tistory.com/151}{\color{#006DD7}{\text{(A1)}}} \\ 4. & \neg \mathscr{C} \Rightarrow \left( \neg \mathscr{D} \Rightarrow \neg \mathscr{C} \right) & \text{(A1)} \\ 5. & \neg \mathscr{D} \Rightarrow \mathscr{C} & \text{1, 3, }\href{https://chocobear.tistory.com/156}{\color{#006DD7}{\text{MP}}} \\ 6. & \neg \mathscr{D} \Rightarrow \neg \mathscr{C} & \text{2, 4, MP} \\ 7. & \left( \neg \mathscr{D} \Rightarrow \neg \mathscr{C} \right) \Rightarrow \left( \left( \neg \mathscr{D} \Rightarrow \mathscr{C} \right) \Rightarrow \mathscr{D} \right) & \href{https://chocobear.tistory.com/151}{\color{#006DD7}{\text{(A3)}}} \\ 8. & \left( \neg \mathscr{D} \Rightarrow \mathscr{C} \right) \Rightarrow \mathscr{D} & \text{6, 7, MP} \\ \hline \therefore & \mathscr{D} & \text{5, 8, MP} \end{array} $$

따라서 연역 정리에 의해 $\neg \mathscr{C} \vdash \mathscr{C} \Rightarrow \mathscr{D}$이다.

$\blacksquare$

 

만약 $\bar{v}(\mathscr{D}) = \mathbf{T}$라면, $\bar{v}(\mathscr{B}) = \mathbf{T}$이다. 따라서 $\mathscr{D}'$는 $\mathscr{D}$이고, $\mathscr{B}'$는 $\mathscr{B}$이다. 여기에 귀납가정을 적용하면 $B'_1, B'_2, \cdots, B'_n \vdash \mathscr{D}$를 얻을 수 있다. 이때, $\mathscr{D} \vdash \mathscr{C} \Rightarrow \mathscr{D}$^[각주:1]이므로 $B'_1, B'_2, \cdots, B'_n \vdash \mathscr{B}'$이다.

만약 $\bar{v}(\mathscr{C}) = \mathbf{T}$이고 $\bar{v}(\mathscr{D}) = \mathbf{F}$라면, $\bar{v}(\mathscr{B}) = \mathbf{F}$이다. 따라서 $\mathscr{C}'$는 $\mathscr{C}$이고, $\mathscr{D}'$는 $\neg \mathscr{D}$이며, $\mathscr{B}'$는 $\neg \mathscr{B}$이다. 여기에 귀납가정을 적용하면 $B'_1, B'_2, \cdots, B'_n \vdash \mathscr{C}$와 $B'_1, B'_2, \cdots, B'_n \vdash \neg \mathscr{D}$를 얻을 수 있다. 이때, $\mathscr{C}, \neg \mathscr{D} \vdash \neg \left( \mathscr{C} \Rightarrow \mathscr{D} \right)$^[각주:2]이므로 $B'_1, B'_2, \cdots, B'_n \vdash \mathscr{B}'$이다.

 

따라서 $j<n$인 임의의 $j$에 대하여 보조정리가 성립하면 $n$에 대해서도 보조정리가 성립하며, 이로 인해 수학적 귀납법에 의해 보조정리가 증명된다.

$\blacksquare$

 

Theorem 2. 명제논리에서의 완전성 정리 (Completeness Theorem for Propositional Logic)

명제논리는 완전성이 성립한다. 즉, wff의 집합 $\Sigma$와 wff $\mathscr{C}$에 대하여 $\Sigma \models \mathscr{C}$이면 $\Sigma \vdash \mathscr{C}$이다.

 

Proof.

일단, $\Sigma \models \mathscr{C}$라면 명제논리에서의 콤팩트성 정리^[각주:3]에 의해 $\Sigma_0 \models \mathscr{C}$인 유한집합 $\Sigma_0 \subseteq \Sigma$가 존재한다.

$\Sigma_0 = \{ \mathscr{B}_1, \mathscr{B}_2, \cdots, \mathscr{B}_n \}$이라고 하면, 이 글의 Proposition 2에 의해 $\models \mathscr{B}_1 \Rightarrow \left( \mathscr{B}_2 \Rightarrow \cdots \Rightarrow \left( \mathscr{B}_n \Rightarrow \mathscr{C} \right) \right)$임을 알 수 있다. 편의상 $\mathscr{B}_1 \Rightarrow \left( \mathscr{B}_2 \Rightarrow \cdots \Rightarrow \left( \mathscr{B}_n \Rightarrow \mathscr{C} \right) \right)$를 $\mathscr{D}$로 나타내자.

이때, $\mathscr{B}_1, \mathscr{B}_2, \cdots, \mathscr{B}_n \in \Sigma$이므로 $\Sigma \vdash \mathscr{D}$임을 보이면 유한 번의 MP를 적용하여 $\Sigma \vdash \mathscr{C}$가 증명된다. 이때, $\mathscr{D}$를 구성하는 원자명제를 $D_1, D_2, \cdots, D_m$이라고 하자. 그러면 $\mathscr{D}$가 항진명제이므로 Lemma 1에 의해 $D'_1, D'_2, \cdots, D'_m \vdash \mathscr{D}$이다. 따라서 $v(D_m) = \mathbf{T}$가 되도록 boolean interpretation $v$를 선택하면 $D'_1, D'_2, \cdots, D'_{m-1}, D_m \vdash \mathscr{D}$를 얻을 수 있으며, $v(D_m) = \mathbf{F}$가 되도록 boolean interpretation $v$를 선택하면 $D'_1, D'_2, \cdots, D'_{m-1}, \neg D_m \vdash \mathscr{D}$를 얻는다. 따라서 연역정리에 의해 $D'_1, D'_2, \cdots, D'_{m-1} \vdash D_m \Rightarrow \mathscr{D}$와 $D'_1, D'_2, \cdots, D'_{m-1} \vdash \neg D_m \Rightarrow \mathscr{D}$를 얻을 수 있다. 이때, $D_m \Rightarrow \mathscr{D}, \neg D_m \Rightarrow \mathscr{D} \vdash \mathscr{D}$이므로^[각주:4] $D'_1, D'_2, \cdots, D'_{m-1} \vdash \mathscr{D}$이다. 방금 $D'_m$을 제거한 것과 똑같은 방법을 유한 번 적용하면 $\vdash \mathscr{D}$를 얻을 수 있으며, 따라서 정리가 증명된다.

$\blacksquare$

 

1. 이는 연역 정리에 의해 자명하다. [본문으로]
2. 이는 DI와 DN에 의해 자명하다. [본문으로]
3. 명제논리에서의 콤팩트성 정리를 소개한 글에서는 콤팩트성 정리의 따름정리라고 소개했지만, 일반적으로 두 정리 모두를 콤팩트성 정리라고 부른다 [본문으로]
4. 이는 배중률과 DE로부터 자명한 결과이다. [본문으로]