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

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

 

$\mathscr{B}$와 $\mathscr{C}$가 wff라면, $\neg \mathscr{C} \Rightarrow \neg \mathscr{B} \vdash \mathscr{B} \Rightarrow \mathscr{C}$이다.

 

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

 

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

$\mathscr{B}$와 $\mathscr{C}$가 wff라면, $\neg \mathscr{C} \Rightarrow \neg \mathscr{B} \vdash \mathscr{B} \Rightarrow \mathscr{C}$이고 $\mathscr{B} \Rightarrow \mathscr{C} \vdash \neg \mathscr{C} \Rightarrow \neg \mathscr{B}$이다.

 

Proof.

먼저 $\neg \mathscr{C} \Rightarrow \neg \mathscr{B} \vdash \mathscr{B} \Rightarrow \mathscr{C}$임을 보이자.

 

$$ \begin{array}{rll} 1. & \neg \mathscr{C} \Rightarrow \neg \mathscr{B} & \text{Hyp} \\ 2. & \left( \neg \mathscr{C} \Rightarrow \neg \mathscr{B} \right) \Rightarrow \left( \left( \neg \mathscr{C} \Rightarrow \mathscr{B} \right) \Rightarrow \mathscr{C} \right) & \href{https://chocobear.tistory.com/151}{\color{#006DD7}{\text{(A3)}}} \\ 3. & \left( \neg \mathscr{C} \Rightarrow \mathscr{B} \right) \Rightarrow \mathscr{C} & \text{1, 2, }\href{https://chocobear.tistory.com/151}{\color{#006DD7}{\text{MP}}} \\ 4. & \mathscr{B} \Rightarrow \left( \neg \mathscr{C} \Rightarrow \mathscr{B} \right) & \href{https://chocobear.tistory.com/151}{\color{#006DD7}{\text{(A1)}}} \\ \hline \therefore & \mathscr{B} \Rightarrow \mathscr{C} & \text{3, 4, }\href{https://chocobear.tistory.com/153}{\color{#006DD7}{\text{HS}}} \end{array}$$

 

따라서 $\neg \mathscr{C} \Rightarrow \neg \mathscr{B} \vdash \mathscr{B} \Rightarrow \mathscr{C}$이다.

이제 $\mathscr{B} \Rightarrow \mathscr{C} \vdash \neg \mathscr{C} \Rightarrow \neg \mathscr{B}$임을 보이자.

 

$$ \begin{array}{rll} 1. & \mathscr{B} \Rightarrow \mathscr{C} & \text{Hyp} \\ 2. & \neg \neg \mathscr{B} \Rightarrow \mathscr{B} & \href{https://chocobear.tistory.com/155}{\color{#006DD7}{\text{DNE}}} \\ 3. & \neg \neg \mathscr{B} \Rightarrow \mathscr{C} & \text{1, 2, HS} \\ 4. & \mathscr{C} \Rightarrow \neg \neg \mathscr{C} & \href{https://chocobear.tistory.com/155}{\color{#006DD7}{\text{DNI}}} \\ 5. & \neg \neg \mathscr{B} \Rightarrow \neg \neg \mathscr{C} & \text{3, 4, HS} \\ 6. & \left( \neg \neg \mathscr{B} \Rightarrow \neg \neg \mathscr{C} \right) \Rightarrow \left( \neg \mathscr{C} \Rightarrow \neg \mathscr{B} \right) & \neg \mathscr{C} \Rightarrow \neg \mathscr{B} \vdash \mathscr{B} \Rightarrow \mathscr{C} \text{, } \href{https://chocobear.tistory.com/152}{\color{#006DD7}{\text{Deduction Thm}}} \\ \hline \therefore & \neg \mathscr{C} \Rightarrow \neg \mathscr{B} & \text{5, 6, HS} \end{array} $$

 

따라서 $\mathscr{B} \Rightarrow \mathscr{C} \vdash \neg \mathscr{C} \Rightarrow \neg \mathscr{B}$이다.

$\blacksquare$