논리학, 그 일곱 번째 이야기 | 명제논리의 Boolean Interpretation ( Boolean Interpretation for Propositional Logic )

이번 글에서는 명제논리에서의 명제에 진리값을 부여할 것이다. 즉, 어떤 명제에 대해 해당 명제가 참인지, 거짓인지를 판단해주는 함수에 대해 소개할 것이다. 앞으로의 글에서 진리값 $\mathbf{T}$는 $True$를, $\mathbf{F}$는 $False$를 나타낼 것이다. 그러면 이제 다음 정의를 보자.

 

Definition 1.

명제논리 $L$의 원자명제의 집합 $\mathrm{A}$를 생각하자. 그러면 다음 함수 $v$를 $L$의 Boolean Interpretation이라고 한다. $$v:\mathrm{A}\to \{\mathbf{T},\mathbf{F}\}$$

 

위 정의를 통해 명제논리 $L$의 원자명제에 진리값을 부여할 수 있다. 하지만, 이것만으로는 큰 의미를 가지지 않는데, 위의 정의만으로는 $L$의 대부분의 wff에는 진리값을 부여할 수 없기 때문이다. 따라서 다음 정의가 추가적으로 필요하다.

 

Definition 2.

명제논리 $L$에서 모든 wff의 집합 $\mathrm{S}$를 생각하자. 그러면 다음을 만족하는 함수 $\overline{v}:\mathrm{S}\to \{\mathbf{T},\mathbf{F}\}$를 $v$의 확장이라고 한다. 1) 모든 $\phi \in \mathrm{A}$에 대하여 $\overline{v}(\phi )=v(\phi )$ 2) 모든 wff $\mathcal{B}$에 대하여 $\overline{v}(\mathrm{\neg }\mathcal{B})=\{\begin{array}{ll}\mathbf{T}& \text{ if }\overline{v}(\mathcal{B})=\mathbf{F}\\ \mathbf{F}& \text{ if }\overline{v}(\mathcal{B})=\mathbf{T}\end{array}$ 3) 모든 wff $\mathcal{B}$, $\mathcal{C}$에 대하여 $\overline{v}(\mathcal{B}\Rightarrow \mathcal{C})=\{\begin{array}{ll}\mathbf{F}& \text{ if }\overline{v}(\mathcal{B})=\mathbf{T}\text{ and }\overline{v}(\mathcal{C})=\mathbf{F}\\ \mathbf{T}& \text{ otherwise }\end{array}$

 

이제 다음 정리를 살펴보자.

 

Theorem 1.

명제논리 $L$의 boolean interpretation $v$가 주어졌다고 하자. 그러면 $v$의 확장 $\overline{v}$는 잘 정의된다. 즉, 그러한 함수 $\overline{v}:\mathrm{S}\to \{\mathbf{T},\mathbf{F}\}$가 유일하게 존재한다.

 

Proof.

이 정리의 증명은 임의의 wff $\mathbf{B}$에 대하여 $\overline{v}(\mathbf{B})$의 값이 유일하게 결정됨을 보이면 충분하다. 이는 wff $\mathbf{B}$의 길이에 대한 귀납법을 통해 증명할 수 있다. 먼저 $\mathbf{B}$의 길이가 1인 wff의 경우를 보자.

길이가 1인 wff $\mathbf{B}$는 원자명제 뿐이다. 따라서 $\overline{v}(\mathbf{B})=v(\mathbf{B})$으로 $\overline{v}(\mathbf{B})$가 유일하게 결정된다.

이제 길이가 $k$ 이하인 모든 wff에 대하여 $\overline{v}$의 값이 유일하게 결정된다고 가정하자.

길이가 $k+1$인 wff $\mathcal{B}$에 대하여 $\overline{v}$의 값이 유일하게 결정된다면 수학적 귀납법에 의해 증명이 완결된다. $\mathcal{B}$의 길이가 $k+1$이라면 wff의 정의에 의해 다음의 두 가지 경우 중 하나이다.

a) $\mathcal{B}=\mathrm{\neg }\mathcal{C}$인 wff $\mathcal{C}$가 존재한다.

b) $\mathcal{B}=\mathcal{C}\Rightarrow \mathcal{D}$인 wff $\mathcal{C}$와 $\mathcal{D}$가 존재한다.

첫 번째 경우부터 생각하자. 그러면 $\mathcal{C}$의 길이는 $k$이므로 귀납가정에 의해 $\overline{v}(\mathcal{C})$의 값은 유일하게 결정된다. 따라서 $\overline{v}(\mathcal{B})=\overline{V}(\mathrm{\neg }\mathcal{C})$로 $\overline{v}(\mathcal{B})$의 값이 유일하게 결정된다.

이제 두 번째 경우에 대해 생각해보자. 만약 $\mathcal{B}=\mathcal{C}\Rightarrow \mathcal{D}$라면 $\mathcal{C}$와 $\mathcal{D}$는 $\mathcal{B}$보다 길이가 짧다. 따라서 $\mathcal{C}$와 $\mathcal{D}$의 길이가 $k$ 이하이므로 귀납가정에 의해 $\overline{v}(\mathcal{C})$와 $\overline{b}(\mathcal{D})$의 값은 유일하게 결정된다. 따라서 $\overline{v}(\mathcal{B})=\overline{v}(\mathcal{C}\Rightarrow \mathcal{D})$로 $\overline{v}(\mathcal{B})$의 값이 유일하게 결정된다.

따라서 길이가 $k+1$인 모든 wff에 대하여 $\overline{v}$의 값이 유일하게 결정되며, 수학적 귀납법에 의해 정리가 증명된다.

$◼$

 

Theorem 2.

$L$의 boolean interpretation $v$가 주어졌다고 하자. 그러면 $v$의 확장 $\overline{v}$와 wff $\mathcal{B}$, $\mathcal{C}$에 대하여 다음이 성립한다. 1) $\overline{v}(\mathcal{B}\vee \mathcal{C})=\{\begin{array}{l}\mathbf{F}\text{ if }\overline{v}(\mathcal{B})=\mathbf{F}\text{ and }\overline{v}(\mathcal{C})=\mathbf{F}\\ \mathbf{T}\text{ otherwise }\end{array}$ 2) $\overline{v}(\mathcal{B}\wedge \mathcal{C})=\{\begin{array}{l}\mathbf{T}\text{ if }\overline{v}(\mathcal{B})=\mathbf{T}\text{ and }\overline{v}(\mathcal{C})=\mathbf{T}\\ \mathbf{F}\text{ otherwise }\end{array}$ 3) $\overline{v}(\mathcal{B}\iff \mathcal{C})=\{\begin{array}{l}\mathbf{T}\text{ if }\overline{v}(\mathcal{B})=\overline{v}(\mathcal{C})\\ \mathbf{F}\text{ otherwise }\end{array}$

 

위 정리는 $\vee$, $\wedge$, $\iff$의 정의와 $\overline{v}$의 정의에 의해 자명하므로 따로 증명을 서술하지는 않겠다.

 

이제 항진명제 (Tautology)와 모순명제 (Contradiction)에 대해 얘기해보려 한다. 그러기 위해서는 다음의 정의가 필요하다.

 

Definition 3.

$L$의 boolean interpretation $v$의 확장 $\overline{v}$에 대하여 $\overline{v}(\phi )=\mathbf{T}$일 때 $v$가 $\phi$를 만족한다 (Satisfy)고 하며, 이를 $v\models \phi$로 나타낸다.

 

Definition 4.

wff만을 원소로 가지는 집합 $\mathrm{\Sigma }$에 대하여 $\mathrm{\Sigma }$의 모든 원소를 만족하는 $L$의 boolean interpretation $v$에 대하여 언제나 $v$가 $\mathcal{C}$를 만족할 때, $\mathrm{\Sigma }$가 $\mathcal{C}$를 Tautologically Imply한다고 하며, 이를 $\mathrm{\Sigma }\models \mathcal{C}$와 같이 나타낸다. 또한, $\mathrm{\Sigma }$가 $\{{\mathcal{B}}_1,{\mathcal{B}}_2,\cdots ,{\mathcal{B}}_n\}$일 때 ${\mathcal{B}}_1,{\mathcal{B}}_2,\cdots ,{\mathcal{B}}_n\models \mathcal{C}$와 같이 나타낼 수 있으며, $\mathrm{\Sigma }$가 공집합인 경우, $\models \mathcal{C}$와 같이 나타낼 수 있다. 또한, $\models \mathcal{C}$인 경우 $\mathcal{C}$를 항진명제 (Tautology)라고 하며, 기호 $\mathrm{\top }$은 항진명제를 나타낸다. 이와 반대되는 개념으로 모든 boolean interpretation $v$에 대하여 $v$가 $\mathcal{C}$를 만족하지 않을 때, $\mathcal{C}$를 모순명제 (Contradiction)라고 하며, 기호 $\mathrm{\perp }$은 모순명제를 나타낸다. 추가적으로, 두 wff $\mathcal{B}$, $\mathcal{C}$에 대하여 $\mathcal{B}\models \mathcal{C}$이고 $\mathcal{C}\models \mathcal{B}$라면 $\mathcal{B}$와 $\mathcal{C}$가 Tautologically Equivalent하다고 한다.

 

또한, tautologically equivalent는 다음과 같은 성질을 가진다.

 

Proposition 1.

두 wff $\mathcal{B}$, $\mathcal{C}$가 tautologically equivalent한 것은 임의의 boolean interpretation $v$에 대하여 $\overline{v}(\mathcal{B})=\overline{v}(\mathcal{C})$가 성립하는 것과 논리적으로 동치이다.

 

이는 tautologically equivalent의 정의에 의해 자명하므로 굳이 증명을 서술하지는 않겠다.

추가적으로, $\models$는 다음과 같은 중요한 성질을 가지며, 이 역시 상당히 자명하므로 굳이 증명을 서술하지는 않겠다.

 

Proposition 2.

wff의 집합 $\mathrm{\Sigma }$와 wff $\mathcal{B}$, $\mathcal{C}$에 대하여 $\mathrm{\Sigma }\cup \{\mathcal{B}\}\models \mathcal{C}$이면 $\mathrm{\Sigma }\models \mathcal{B}\Rightarrow \mathcal{C}$가 성립한다.

 

또한, 한 가지 매우 중요한 사실이 있는데, 바로 명제논리의 공리가 항진명제라는 것이다.

다음 정리를 보자.

 

Theorem 3.

명제논리의 공리는 항진명제이다. 즉, 임의의 wff $\mathcal{B}$, $\mathcal{C}$, $\mathcal{D}$에 대하여 다음 세 명제는 언제나 항진명제이다. (A1) $\mathcal{B}\Rightarrow (\mathcal{C}\Rightarrow \mathcal{B})$ (A2) $(\mathcal{B}\Rightarrow (\mathcal{C}\Rightarrow \mathcal{D}))\Rightarrow ((\mathcal{B}\Rightarrow \mathcal{C})\Rightarrow (\mathcal{B}\Rightarrow \mathcal{D}))$ (A3) $(\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B})\Rightarrow ((\mathrm{\neg }\mathcal{C}\Rightarrow \mathcal{B})\Rightarrow \mathcal{C})$

 

Proof.

$\overline{v}(\mathcal{B})$, $\overline{v}(\mathcal{C})$, $\overline{v}(\mathcal{D})$의 값에 관계없이 언제나 다음이 성립한다.

$\overline{v}(\mathcal{B}\Rightarrow (\mathcal{C}\Rightarrow \mathcal{B}))=\mathbf{T}$

$\overline{v}((\mathcal{B}\Rightarrow (\mathcal{C}\Rightarrow \mathcal{D}))\Rightarrow ((\mathcal{B}\Rightarrow \mathcal{C})\Rightarrow (\mathcal{B}\Rightarrow \mathcal{D})))=\mathbf{T}$

$\overline{v}((\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B})\Rightarrow ((\mathrm{\neg }\mathcal{C}\Rightarrow \mathcal{B})\Rightarrow \mathcal{C}))=\mathbf{T}$

계산은 그리 어렵지 않으니 궁금하다면 직접 해보길 권장한다.

$◼$