논리학, 그 여덟 번째 이야기 | 명제논리에서의 치환 ( Substitution in Propositional Logic )

이번 글에서는 명제논리에서의 치환에 대해 다룰 것이다. 일단 치환에 대해 정의하기에 앞서 다음 정의를 보자.

 

Definition 1.

wff $\mathscr{A}$에 대하여 $\mathscr{B}$가 $\mathscr{A}$의 부분문자열이라고 하자. 만약 $\mathscr{B}$ 역시 wff라면 $\mathscr{B}$를 $\mathscr{A}$의 Subformula라고 한다.

 

이해를 돕기 위해 예를 들자면, wff $\mathscr{A} = \neg \left( \left( \mathcal{p} \Rightarrow \mathcal{q} \right) \Rightarrow \neg \mathcal{r} \right)$에 대하여 $\mathscr{B} = \left( \mathcal{p} \Rightarrow \mathcal{q} \right) \Rightarrow \neg \mathcal{r}$와 $\mathscr{C} = \Rightarrow \neg \mathcal{r}$은 모두 $\mathscr{A}$의 부분문자열이지만, $\mathscr{B}$는 $\mathscr{A}$의 subformula이고 $\mathscr{C}$는 $\mathscr{A}$의 subformula가 아니다.

명제논리에서의 치환은 다음과 같이 정의된다.

 

Definition 2.

wff $\mathscr{C}$가 wff $\mathscr{B}$의 subformula라고 하자. 이때, $\mathscr{B}$에서 $\mathscr{C}$의 위치에 $\mathscr{C}$ 대신 wff $\mathscr{C}'$를 집어넣어서 만들어진 새로운 wff를 $\mathscr{B} \left[ \mathscr{C}' / \mathscr{C} \right]$와 같이 나타내며, 이를 $\mathscr{B}$에서 $\mathscr{C}$를 $\mathscr{C}'$로 치환한 wff라고 한다.

 

이렇게 정의된 치환에 대하여 다음 정리가 성립한다.

 

Theorem 1.

$\mathscr{B}$, $\mathscr{C}$, $\mathscr{C}'$이 모두 wff이고 $\mathscr{C}$가 $\mathscr{B}$의 subformula라고 하자. 만약 $\mathscr{C}$와 $\mathscr{C}'$이 Tautologically Equivalent하다면 $\mathscr{B}' = \mathscr{B} \left[ \mathscr{C}' / \mathscr{C} \right]$와 $\mathscr{B}$가 tautologically equivalent하다.

 

Proof.

임의의 Boolean Interpretation $v$를 생각하자. 그러면 $\mathscr{C}$와 $\mathscr{C}'$가 tautologically equivalent하므로 $\bar{v}(\mathscr{C}) = \bar{v}(\mathscr{C}')$라는 것을 기억해 두자.

만약 위의 조건 아래에서 $\bar{v}(\mathscr{B}) = \bar{v}(\mathscr{B}')$임을 보인다면 $v$의 선택이 임의적이므로 정리가 증명된다.

이를 수학적 귀납법을 이용하여 보일 것이다.

$n(\mathscr{B})$를 $\mathscr{C}$를 subformula로 가지는 $\mathscr{B}$의 subformula의 개수로 정의할 때, $n(\mathscr{B})$에 대한 귀납법을 생각하자.

먼저, $n(\mathscr{B}) = 1$일 때를 생각하자. 만일 $n(\mathscr{B}) = 1$이라면, $\mathscr{B} = \mathscr{C}$이다. 따라서 $\mathscr{B}' = \mathscr{C}'$임을 즉시 알 수 있고, $\bar{v}(\mathscr{C}) = \bar{v}(\mathscr{C}')$임으로부터 $\bar{v}(\mathscr{B}) = \bar{v}(\mathscr{B}')$임이 자명하다.

$n(\mathscr{B}) \leq n$인 모든 경우에 대하여 정리가 성립한다고 가정하고 $n(\mathscr{B}) = n+1$일 때에도 성립함을 보이자.

그러면 $\mathscr{B} = \neg \mathscr{B}_1$인 경우와 $\mathscr{B} = \mathscr{B}_1 \Rightarrow \mathscr{B}_2$인 경우의 두 가지 경우로 상황을 나눠서 생각할 수 있다.

만약 $\mathscr{B} = \neg \mathscr{B}_1$이라면, $n(\mathscr{B}_1) = n$이므로 귀납가정에 의해 $\bar{v}(\mathscr{B}_1 \left[ \mathscr{C}' / \mathscr{C} \right]) = \bar{v}(\mathscr{B}_1)$이다. 따라서 $\bar{v}$의 정의와 $\mathscr{B} \left[ \mathscr{C}' / \mathscr{C} \right] = \neg \mathscr{B}_1 \left[ \mathscr{C}' / \mathscr{C} \right]$라는 사실으로부터 $\bar{v}(\mathscr{B} \left[ \mathscr{C}' / \mathscr{C} \right]) = \bar{v}(\mathscr{B})$임을 얻을 수 있다.

만약 $\mathscr{B} = \mathscr{B}_1 \Rightarrow \mathscr{B}_2$라면, $\mathscr{B} \left[ \mathscr{C}' / \mathscr{C} \right] = \mathscr{B}_1 \left[ \mathscr{C}' / \mathscr{C} \right] \Rightarrow \mathscr{B}_2 \left[ \mathscr{C}' / \mathscr{C} \right]$임을 자명하게 알 수 있다. 이때, $n(\mathscr{B}_1), n(\mathscr{B}_2) \leq n$임이 자명하므로 귀납가정에 의해 $\bar{v}(\mathscr{B}_1 \left[ \mathscr{C}' / \mathscr{C} \right]) = \bar{v}(\mathscr{B}_1)$, $\bar{v}(\mathscr{B}_2 \left[ \mathscr{C}' / \mathscr{C} \right]) = \bar{v}(\mathscr{B}_2)$이다. 따라서 $\bar{v}$의 정의에 의해 $\bar{v}(\mathscr{B} \left[ \mathscr{C}' / \mathscr{C} \right]) = \bar{v}(\mathscr{B})$이다.

따라서 수학적 귀납법에 의해 $n(\mathscr{B})$에 관계없이 $\bar{v}(\mathscr{B}) = \bar{v}(\mathscr{B}')$이며, 이로 인해 $\mathscr{B}$와 $\mathscr{B}'$는 tautologically equivalent하다.

$\blacksquare$