논리학, 그 열세 번째 이야기 | 명제논리에서의 Unique Readability Theorem ( Unique Readability Theorem for Propositional Logic )

이번 글에서는 명제논리에서의 unique readability theorem에 대해 다룰 것이다. Unique readability theorem은 쉽게 말하자면 임의의 wff는 그 구조가 유일하게 결정된다는 것이다. 즉, 그 어떤 wff도 서로 다른 두 의미로 해석될 수 없다는 것이 unique readability theorem의 요지이다. 이 정리를 증명하기 위해서는 다음과 같은 보조정리들이 필요하다. 다음을 보자.

 

Lemma 1.

임의의 wff는 왼쪽 괄호 $\left(\right.$와 오른쪽 괄호 $\left.\right)$의 개수가 같다.

 

Proof.

왼쪽 괄호 $\left(\right.$와 오른쪽 괄호 $\left.\right)$의 개수가 같은 wff의 집합을 $S$라고 하자.

먼저 원자명제의 경우를 살펴보면, 원자명제는 괄호가 전혀 없으므로 왼쪽 괄호 $\left( \right.$와 오른쪽 괄호 $\left. \right)$의 개수가 같다. 즉, 임의의 원자명제는 $S$의 원소이다.

만약 두 wff $\mathcal{B}$와 $\mathcal{C}$의 왼쪽 괄호 $\left( \right.$와 오른쪽 괄호 $\left. \right)$의 개수가 각각 같다면 $\left( \neg \mathcal{B} \right)$와 $\left( \mathcal{B} \Rightarrow \mathcal{C} \right)$ 모두 왼쪽 괄호 $\left( \right.$와 오른쪽 괄호 $\left. \right)$의 개수가 같다.

즉, $S$는 두 연결사 $\Rightarrow$와 $\neg$에 대하여 닫혀 있다.

따라서 귀납법에 의해 모든 wff는 왼쪽 괄호 $\left(\right.$와 오른쪽 괄호 $\left.\right)$의 개수가 같다.

$\blacksquare$

 

다음 보조정리를 보기 전에 한 가지 간단한 개념을 정의하고 넘어가자.

 

Definition 1. Proper Initial Segment

wff $\mathcal{B}$가 주어졌다고 하자. 만약 어떤 논리식 $\mathcal{B}_0$가 $\mathcal{B}$의 첫 몇 글자라면 $\mathcal{B}_0$을 Initial Segment라고 한다. 예를 들어, 논리식 $\left( \mathrm{A} \Rightarrow \right.$는 wff $\left( \mathrm{A} \Rightarrow \mathrm{B} \right)$의 initial segment이다. wff $\mathcal{B}$의 initial segment 중 $\mathcal{B}$가 아닌 것들을 $\mathcal{B}$의 Proper Initial Segment라고 한다.

 

Lemma 2.

임의의 wff의 proper initial segment는 왼쪽 괄호 $\left(\right.$로 시작한다. 따라서 임의의 wff의 proper initial segment는 언제나 왼쪽 괄호 $\left(\right.$의 개수가 오른쪽 괄호 $\left.\right)$의 개수보다 많다.

 

Proof.

모든 proper initial segment가 왼쪽 괄호 $\left(\right.$의 개수가 오른쪽 괄호 $\left.\right)$의 개수보다 많은 wff의 집합을 $S$라고 하자. 이제 $S$가 모든 wff의 집합임을 보이면 보조정리가 증명된다.

먼저 원자명제의 경우를 살펴보면, 원자명제는 proper initial segment가 없으므로 모든 원자명제는 $S$의 원소이다.

 

이제 $S$가 연결사 $\neg$에 대하여 닫혀있음을 보이자.

$\mathcal{B} \in S$라고 하면, wff $\left( \neg \mathcal{B} \right)$의 proper initial segment는 다음 4가지 중 하나이다.

1) $\left(\right.$

2) $\left( \neg \right.$

3) $\left( \neg \mathcal{B}_0 \right.$, $\mathcal{B}_0$는 $\mathcal{B}$의 proper initial segment.

4) $\left( \neg \mathcal{B} \right.$

그런데, 1), 2)는 자명하게 왼쪽 괄호 $\left(\right.$가 오른쪽 괄호 $\left.\right)$보다 많으며, 3)은 $\mathcal{B} \in S$라는 가정에 의해 왼쪽 괄호 $\left(\right.$가 오른쪽 괄호 $\left.\right)$보다 많고, 4)는 Lemma 1에 의해 왼쪽 괄호 $\left(\right.$가 오른쪽 괄호 $\left.\right)$보다 많다.

즉, $\left( \neg \mathcal{B} \right) \in S$이며, 이는 곧 $S$가 연결사 $\neg$에 대하여 닫혀있음을 의미한다.

 

이제 $S$가 연결사 $\Rightarrow$에 대하여 닫혀있음을 보이자.

$\mathcal{B}, \mathcal{C} \in S$라고 하면, wff $\left( \mathcal{B} \Rightarrow \mathcal{C} \right)$의 proper initial segment는 다음 6가지 중 하나이다.

1) $\left(\right.$

2) $\left( \mathcal{B}_0 \right.$, $\mathcal{B}_0$는 $\mathcal{B}$의 proper initial segment.

3) $\left( \mathcal{B} \right.$

4) $\left( \mathcal{B} \Rightarrow \right.$

5) $\left( \mathcal{B} \Rightarrow \mathcal{C}_0 \right.$, $\mathcal{C}_0$는 $\mathcal{C}$의 proper initial segment.

6) $\left( \mathcal{B} \Rightarrow \mathcal{C} \right.$

그런데, 1)은 자명하게 왼쪽 괄호 $\left(\right.$가 오른쪽 괄호 $\left.\right)$보다 많으며, 2), 3), 4), 5), 6)은 Lemma 1과 $\mathcal{B}, \mathcal{C} \in S$라는 가정에 의해 왼쪽 괄호 $\left( \right.$가 오른쪽 괄호 $\left. \right)$보다 많다.

즉, $\left( \mathcal{B} \Rightarrow \mathcal{C} \right) \in S$이며, 이는 곧 $S$가 연결사 $\Rightarrow$에 대하여 닫혀있음을 의미한다.

따라서 $S$는 귀납법에 의해 모든 wff의 집합과 같으며, 그러므로 보조정리가 증명된다.

$\blacksquare$

 

이제 unique readability theorem에 대해 이야기할 준비가 끝났다. 다음 정리를 보자.

 

Theorem 1. Unique Readability Theorem for Propositional Logic

wff의 집합 $S$는 원자명제의 집합 $\mathrm{A}$로부터 두 연결사 $\neg$와 $\Rightarrow$에 의해 freely generated 된다.

 

Proof.

모든 wff의 집합 $S$가 원자명제의 집합 $\mathrm{A}$로부터 두 연결사 $\neg$와 $\Rightarrow$에 의해 생성되었음은 자명하므로 원자명제의 집합 $\mathrm{A}$와 두 연결사의 치역 $I_\neg = \{ \left( \neg \mathcal{B} \right) \;|\; \mathcal{B} \in S \}$, $I_\Rightarrow = \{ \left( \mathcal{B} \Rightarrow \mathcal{C} \right) \;|\; \mathcal{B}, \mathcal{C} \in S \}$가 pairwise disjoint하고 두 연결사 $\neg$와 $\Rightarrow$가 단사임을 보이면 된다.

 

일단 집합 $\mathrm{A}$는 자명하게 $I_\neg$와도 서로소이며, $I_\Rightarrow$와도 서로소이다.

따라서 $I_\neg$와 $I_\Rightarrow$가 공통된 원소를 가지지 않음을 보이면 충분하다.

만약 어떤 세 wff $\mathcal{B}$, $\mathcal{C}$, $\mathcal{D}$에 대하여 $\left( \neg \mathcal{B} \right) = \left( \mathcal{C} \Rightarrow \mathcal{D} \right)$라면, $\mathcal{C}$는 $\neg$로 시작해야만 한다. 하지만 이는 Lemma 2에 모순이므로 그러한 세 wff는 존재하지 않는다. 즉, $I_\neg$와 $I_\Rightarrow$는 서로소이다.

 

이제 두 연결사 $\neg$와 $\Rightarrow$가 단사임을 보이자.

연결사 $\neg$가 단사임은 자명하므로 $\Rightarrow$가 단사임을 보이면 충분하다.

만약 어떤 네 wff $\mathcal{B}$, $\mathcal{C}$, $\mathcal{D}$, $\mathcal{E}$에 대하여 $\left( \mathcal{B} \Rightarrow \mathcal{C} \right) = \left( \mathcal{D} \Rightarrow \mathcal{E} \right)$라면, $\mathcal{B} \Rightarrow \mathcal{C} \left.\right) = \mathcal{D} \Rightarrow \mathcal{E} \left.\right)$임이 자명하다.

이때, $\mathcal{B} \neq \mathcal{D}$라면, 둘 중 하나가 다른 하나의 proper initial segment가 되며, 이는 Lemma 1과 Lemma 2에 모순임을 쉽게 알 수 있다. 따라서 $\mathcal{B} = \mathcal{D}$이며, 이는 곧 $\mathcal{C} = \mathcal{E}$임을 함의한다.

따라서 연결사 $\Rightarrow$는 단사이다.

 

위의 결과를 종합하면 wff의 집합 $S$가 원자명제의 집합 $\mathrm{A}$로부터 두 연결사 $\neg$와 $\Rightarrow$에 의해 freely generated 된다는 것을 알 수 있다.

$\blacksquare$