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

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

 

Definition 1.

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

 

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

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

 

Definition 2.

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

 

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

 

Theorem 1.

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

 

Proof.

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

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

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

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

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

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

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

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

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

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

$◼$