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

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

 

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

 

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

 

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

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

 

Proof.

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

 

$$ \begin{array}{rll} 1. & \mathscr{B} & \text{Hyp} \\ 2. & \mathscr{B} \Rightarrow \mathscr{C} & \text{Hyp} \\ 3. & \mathscr{C} & \text{1, 2, }\href{https://chocobear.tistory.com/151}{\color{#006DD7}{\text{MP}}} \\ 4. & \mathscr{C} \Rightarrow \mathscr{D} & \text{Hyp} \\ \hline \therefore & \mathscr{D} & \text{3, 4, MP} \end{array} $$

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

$\blacksquare$

 

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

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

 

Theorem 2.

$\mathscr{B}$, $\mathscr{C}$, $\mathscr{D}$가 wff라고 하자. 그러면 $\mathscr{B} \Rightarrow \left( \mathscr{C} \Rightarrow \mathscr{D} \right), \mathscr{C} \vdash \mathscr{B} \Rightarrow \mathscr{D}$이다.

 

Proof.

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

 

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

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

$\blacksquare$