논리학, 그 세 번째 이야기 | 추이법칙의 증명 ( The Proof of Law of Transitivity )

이번 글에서는 추이법칙을 증명할 것이다. 추이법칙이란, 다음과 같은 추론 규칙을 말한다.

 

$\mathcal{B}$, $\mathcal{C}$, $\mathcal{D}$가 wff라고 하자. 그러면 $\mathcal{B}\Rightarrow \mathcal{C},\mathcal{C}\Rightarrow \mathcal{D}⊢\mathcal{B}\Rightarrow \mathcal{D}$이다.

 

이를 증명하는 방식은 여러 가지 방식이 있지만, 이번 글에서는 증명을 간편하게 하기 위해 이전 글에서 소개했던 연역 정리를 사용하여 증명할 것이다. 그 증명은 다음과 같다.

 

Theorem 1. 추이법칙 ( Law of Transitivity )

$\mathcal{B}$, $\mathcal{C}$, $\mathcal{D}$가 wff라고 하자. 그러면 $\mathcal{B}\Rightarrow \mathcal{C},\mathcal{C}\Rightarrow \mathcal{D}⊢\mathcal{B}\Rightarrow \mathcal{D}$이다.

 

Proof.

먼저, $\mathcal{B}\Rightarrow \mathcal{C},\mathcal{C}\Rightarrow \mathcal{D},\mathcal{B}⊢\mathcal{D}$임을 증명하자. 이는 다음과 같이 증명할 수 있다.

 

$$\begin{array}{rll}1.& \mathcal{B}& \text{Hyp}\\ 2.& \mathcal{B}\Rightarrow \mathcal{C}& \text{Hyp}\\ 3.& \mathcal{C}& \text{1, 2, }\text{MP}\\ 4.& \mathcal{C}\Rightarrow \mathcal{D}& \text{Hyp}\\ \therefore & \mathcal{D}& \text{3, 4, MP}\end{array}$$

따라서 $\mathcal{B}\Rightarrow \mathcal{C},\mathcal{C}\Rightarrow \mathcal{D},\mathcal{B}⊢\mathcal{D}$이며, 연역 정리에 의해 $\mathcal{B}\Rightarrow \mathcal{C},\mathcal{C}\Rightarrow \mathcal{D}⊢\mathcal{B}\Rightarrow \mathcal{D}$이다.

$◼$

 

앞으로 위의 추이법칙은 HS (Hypothetical Syllogism; 가언적 삼단논법)로 줄여서 사용할 것이다.

추이법칙과 더불어서 자주 사용되는 추론 규칙으로는 아래와 같은 규칙이 있다.

 

Theorem 2.

$\mathcal{B}$, $\mathcal{C}$, $\mathcal{D}$가 wff라고 하자. 그러면 $\mathcal{B}\Rightarrow (\mathcal{C}\Rightarrow \mathcal{D}),\mathcal{C}⊢\mathcal{B}\Rightarrow \mathcal{D}$이다.

 

Proof.

이번에도 바로 증명하기보단 연역 정리를 이용하여 증명하는 편이 더 간단하다. 그러니 먼저 $\mathcal{B}\Rightarrow (\mathcal{C}\Rightarrow \mathcal{D}),\mathcal{C},\mathcal{B}⊢\mathcal{D}$임을 보이자.

 

$$\begin{array}{rll}1.& \mathcal{B}& \text{Hyp}\\ 2.& \mathcal{B}\Rightarrow (\mathcal{C}\Rightarrow \mathcal{D})& \text{Hyp}\\ 3.& \mathcal{C}\Rightarrow \mathcal{D}& \text{1, 2, MP}\\ 4.& \mathcal{C}& \text{Hyp}\\ \therefore & \mathcal{D}& \text{3, 4, MP}\end{array}$$

따라서 $\mathcal{B}\Rightarrow (\mathcal{C}\Rightarrow \mathcal{D}),\mathcal{C},\mathcal{B}⊢\mathcal{D}$이며, 연역 정리에 의해 $\mathcal{B}\Rightarrow (\mathcal{C}\Rightarrow \mathcal{D}),\mathcal{C}⊢\mathcal{B}\Rightarrow \mathcal{D}$이다.

$◼$