논리학, 그 네 번째 이야기 | 대우법칙의 증명 ( The Proof of the Equivalence of Contrapositives )

이번 글에서는 대우법칙과 그 증명에 대해 소개할 것이다. 먼저, 대우법칙이 무엇인지 살펴보자. 대우법칙이란 다음과 같은 추론규칙을 말한다.

 

$\mathcal{B}$와 $\mathcal{C}$가 wff라면, $\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B}⊢\mathcal{B}\Rightarrow \mathcal{C}$이다.

 

또한, 추후 포스팅할 이중부정의 제거를 사용하면 $\mathcal{B}$와 $\mathcal{C}$가 wff라면 $\mathcal{B}\Rightarrow \mathcal{C}⊢\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B}$라는 사실도 도출할 수 있다. 이제 대우법칙의 증명을 살펴보자. 대우법칙은 다음과 같이 증명할 수 있다.

 

Theorem 1. 대우법칙 ( The Equivalence of Contrapositives )

$\mathcal{B}$와 $\mathcal{C}$가 wff라면, $\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B}⊢\mathcal{B}\Rightarrow \mathcal{C}$이고 $\mathcal{B}\Rightarrow \mathcal{C}⊢\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B}$이다.

 

Proof.

먼저 $\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B}⊢\mathcal{B}\Rightarrow \mathcal{C}$임을 보이자.

 

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

 

따라서 $\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B}⊢\mathcal{B}\Rightarrow \mathcal{C}$이다.

이제 $\mathcal{B}\Rightarrow \mathcal{C}⊢\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B}$임을 보이자.

 

$$\begin{array}{rll}1.& \mathcal{B}\Rightarrow \mathcal{C}& \text{Hyp}\\ 2.& \mathrm{\neg }\mathrm{\neg }\mathcal{B}\Rightarrow \mathcal{B}& \text{DNE}\\ 3.& \mathrm{\neg }\mathrm{\neg }\mathcal{B}\Rightarrow \mathcal{C}& \text{1, 2, HS}\\ 4.& \mathcal{C}\Rightarrow \mathrm{\neg }\mathrm{\neg }\mathcal{C}& \text{DNI}\\ 5.& \mathrm{\neg }\mathrm{\neg }\mathcal{B}\Rightarrow \mathrm{\neg }\mathrm{\neg }\mathcal{C}& \text{3, 4, HS}\\ 6.& (\mathrm{\neg }\mathrm{\neg }\mathcal{B}\Rightarrow \mathrm{\neg }\mathrm{\neg }\mathcal{C})\Rightarrow (\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B})& \mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B}⊢\mathcal{B}\Rightarrow \mathcal{C}\text{, }\text{Deduction Thm}\\ \therefore & \mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B}& \text{5, 6, HS}\end{array}$$

 

따라서 $\mathcal{B}\Rightarrow \mathcal{C}⊢\mathrm{\neg }\mathcal{C}\Rightarrow \mathrm{\neg }\mathcal{B}$이다.

$◼$