논리학, 그 일곱 번째 이야기 | 명제논리의 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}$를 생각하자. 그러면 다음을 만족하는 함수 $\bar{v} : \mathrm{S} \to \{ \mathbf{T}, \mathbf{F} \}$를 $v$의 확장이라고 한다. 1) 모든 $\varphi \in \mathrm{A}$에 대하여 $\bar{v}(\varphi) = v(\varphi)$ 2) 모든 wff $\mathscr{B}$에 대하여 $\bar{v}(\neg \mathscr{B}) = \begin{cases} \mathbf{T} & \mbox{ if } \bar{v}(\mathscr{B}) = \mathbf{F} \\ \mathbf{F} & \mbox{ if } \bar{v}(\mathscr{B}) = \mathbf{T} \end{cases}$ 3) 모든 wff $\mathscr{B}$, $\mathscr{C}$에 대하여 $\bar{v}(\mathscr{B} \Rightarrow \mathscr{C}) = \begin{cases} \mathbf{F} & \mbox{ if } \bar{v}(\mathscr{B}) = \mathbf{T} \mbox{ and } \bar{v}(\mathscr{C}) = \mathbf{F} \\ \mathbf{T} & \mbox{ otherwise } \end{cases}$

 

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

 

Theorem 1.

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

 

Proof.

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

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

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

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

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

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

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

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

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

$\blacksquare$

 

Theorem 2.

$L$의 boolean interpretation $v$가 주어졌다고 하자. 그러면 $v$의 확장 $\bar{v}$와 wff $\mathscr{B}$, $\mathscr{C}$에 대하여 다음이 성립한다. 1) $\bar{v}(\mathscr{B} \lor \mathscr{C}) = \begin{cases} \mathbf{F} \mbox{ if } \bar{v}(\mathscr{B}) = \mathbf{F} \mbox{ and } \bar{v}(\mathscr{C}) = \mathbf{F} \\ \mathbf{T} \mbox{ otherwise } \end{cases}$ 2) $\bar{v}(\mathscr{B} \land \mathscr{C}) = \begin{cases} \mathbf{T} \mbox{ if } \bar{v}(\mathscr{B}) = \mathbf{T} \mbox{ and } \bar{v}(\mathscr{C}) = \mathbf{T} \\ \mathbf{F} \mbox{ otherwise } \end{cases}$ 3) $\bar{v}(\mathscr{B} \Leftrightarrow \mathscr{C}) = \begin{cases} \mathbf{T} \mbox{ if } \bar{v}(\mathscr{B}) = \bar{v}(\mathscr{C}) \\ \mathbf{F} \mbox{ otherwise } \end{cases}$

 

위 정리는 $\lor$, $\land$, $\Leftrightarrow$의 정의와 $\bar{v}$의 정의에 의해 자명하므로 따로 증명을 서술하지는 않겠다.

 

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

 

Definition 3.

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

 

Definition 4.

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

 

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

 

Proposition 1.

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

 

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

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

 

Proposition 2.

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

 

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

다음 정리를 보자.

 

Theorem 3.

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

 

Proof.

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

$\bar{v} \left( \mathscr{B} \Rightarrow \left( \mathscr{C} \Rightarrow \mathscr{B} \right) \right) = \mathbf{T}$

$\bar{v} \left( \left( \mathscr{B} \Rightarrow \left( \mathscr{C} \Rightarrow \mathscr{D} \right) \right) \Rightarrow \left( \left( \mathscr{B} \Rightarrow \mathscr{C} \right) \Rightarrow \left( \mathscr{B} \Rightarrow \mathscr{D} \right) \right) \right) = \mathbf{T}$

$\bar{v} \left( \left( \neg \mathscr{C} \Rightarrow \neg \mathscr{B} \right) \Rightarrow \left( \left( \neg \mathscr{C} \Rightarrow \mathscr{B} \right) \Rightarrow \mathscr{C} \right) \right) = \mathbf{T}$

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

$\blacksquare$