논리학, 그 여섯 번째 이야기 | 여러 가지 추론 규칙 ( Various Inference Rules )

이번 글에서는 여러 가지 추론 규칙에 대해 다룰 것이다. 긴말하지 않고 바로 본론으로 들어가자.

 

Inference Rules

$\mathscr{B}$, $\mathscr{C}$, $\mathscr{D}$가 모두 wff일 때 다음은 모두 참이다. 1. 이중부정의 제거 (Double Negation Elimination; DNE) $$\vdash \neg \neg \mathscr{B} \Rightarrow \mathscr{B}$$ 2. 이중부정의 도입 (Double Negation Introduction; DNI) $$\vdash \mathscr{B} \Rightarrow \neg \neg \mathscr{B}$$ 3. 대우법칙 (Equivalence of Contrapositives; Contrapositives) $$ \neg \mathscr{C} \Rightarrow \neg \mathscr{B} \vdash \mathscr{B} \Rightarrow \mathscr{C} $$ 4. 가언적 삼단논법 (Hypothetical Syllogism; HS) $$ \mathscr{B} \Rightarrow \mathscr{C}, \mathscr{C} \Rightarrow \mathscr{D} \vdash \mathscr{B} \Rightarrow \mathscr{D} $$ 5. 선언적 삼단논법 (Disjunctive Syllogism; DS) $$ \mathscr{B} \lor \mathscr{C}, \neg \mathscr{B} \vdash \mathscr{C} $$ 6. 연언 소거 (Conjunction Elimination; CE) $$ \mathscr{B} \land \mathscr{C} \vdash \mathscr{B} $$ $$ \mathscr{B} \land \mathscr{C} \vdash \mathscr{C} $$ 7. 연언 도입 (Conjunction Introduction; CI) $$ \mathscr{B}, \mathscr{C} \vdash \mathscr{B} \land \mathscr{C} $$ 8. 선언 소거 (Disjunction Elimination; DE) $$ \mathscr{B} \Rightarrow \mathscr{D}, \mathscr{C} \Rightarrow \mathscr{D}, \mathscr{B} \lor \mathscr{C} \vdash \mathscr{D} $$ 9. 선언 도입 (Disjunction Introduction; DI) $$ \mathscr{B} \vdash \mathscr{B} \lor \mathscr{C} \\ \mathscr{C} \vdash \mathscr{B} \lor \mathscr{C} $$ 10. 전건 긍정 (Modus Ponens; MP) $$ \mathscr{B} \Rightarrow \mathscr{C}, \mathscr{B} \vdash \mathscr{C} $$ 11. 후건 부정 (Modus Tollens; MT) $$ \mathscr{B} \Rightarrow \mathscr{C}, \neg \mathscr{C} \vdash \neg \mathscr{B} $$

 

Proof.

증명은 다음과 같다.

[1], [2] 이 둘은 이 글에서 증명하였다.

 

[3] 이는 이 글에서 증명하였다.

 

[4] 이는 이 글에서 증명하였다.

 

[5] $\mathscr{B} \lor \mathscr{C}$의 정의가 $\neg \mathscr{B} \Rightarrow \mathscr{C}$이므로 MP에 의해 자명하다.

 

[6] $\mathscr{B} \land \mathscr{C}$의 정의가 $\neg \left( \mathscr{B} \Rightarrow \neg \mathscr{C} \right)$이므로 $\mathscr{B} \land \mathscr{C} \vdash \mathscr{C}$임을 다음과 같이 증명할 수 있다.

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

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

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

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

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

$\blacksquare$

 

[7] $\mathscr{B}, \mathscr{C} \vdash \mathscr{B} \land \mathscr{C}$를 증명하기에 앞서, $\mathscr{B}, \mathscr{C}, \mathscr{B} \Rightarrow \neg \mathscr{C} \vdash \neg \left( \mathscr{B} \Rightarrow \mathscr{B} \right)$임을 보이자.

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

따라서 $\mathscr{B}, \mathscr{C}, \mathscr{B} \Rightarrow \neg \mathscr{C} \vdash \neg \left( \mathscr{B} \Rightarrow \mathscr{B} \right)$이다. 여기에 연역 정리를 적용하면, $\mathscr{B}, \mathscr{C} \vdash \left( \mathscr{B} \Rightarrow \neg \mathscr{C} \right) \Rightarrow \neg \left( \mathscr{B} \Rightarrow \mathscr{B} \right)$임을 알 수 있다. 이제 이 사실을 이용하여 $\mathscr{B}, \mathscr{C} \vdash \neg \left( \mathscr{B} \Rightarrow \neg \mathscr{C} \right)$임을 보이자.

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

따라서 $\mathscr{B}, \mathscr{C} \vdash \neg \left( \mathscr{B} \Rightarrow \neg \mathscr{C} \right)$이다. 이때, 증명과정에서 사용된 DI는 아래에서 증명할 것이며, 아래 증명에는 CI를 사용하지 않으므로 순환논증이 아님을 확인할 수 있다.

$\blacksquare$

 

[8] $\mathscr{B} \lor \mathscr{C}$가 $\neg \mathscr{B} \Rightarrow \mathscr{C}$이므로 $\mathscr{B} \Rightarrow \mathscr{D}, \mathscr{C} \Rightarrow \mathscr{D}, \neg \mathscr{B} \Rightarrow \mathscr{C} \vdash \mathscr{D}$임을 보이면 충분하다. 이는 다음과 같이 보일 수 있다.

$$ \begin{array}{rll} 1. & \mathscr{C} \Rightarrow \mathscr{D} & \text{Hyp} \\ 2. & \neg \mathscr{B} \Rightarrow \mathscr{C} & \text{Hyp} \\ 3. & \neg \mathscr{B} \Rightarrow \mathscr{D} & \text{1, 2, HS} \\ 4. & \neg \mathscr{D} \Rightarrow \neg \neg \mathscr{B} & \text{3, Contrapositive} \\ 5. & \neg \neg \mathscr{B} \Rightarrow \mathscr{B} & \text{DNE} \\ 6. & \neg \mathscr{D} \Rightarrow \mathscr{B} & \text{4, 5, HS} \\ 7. & \mathscr{B} \Rightarrow \mathscr{D} & \text{Hyp} \\ 8. & \neg \mathscr{D} \Rightarrow \mathscr{D} & \text{6, 7, HS} \\ 9. & \neg \mathscr{D} \Rightarrow \neg \mathscr{D} & \vdash \mathscr{B} \Rightarrow \mathscr{B} \\ 10. & \left( \neg \mathscr{D} \Rightarrow \neg \mathscr{D} \right) \Rightarrow \left( \left( \neg \mathscr{D} \Rightarrow \mathscr{D} \right) \Rightarrow \mathscr{D} \right) & \href{https://chocobear.tistory.com/151}{\color{#006DD7}{\text{(A3)}}} \\ 11. & \left( \neg \mathscr{D} \Rightarrow \mathscr{D} \right) \Rightarrow \mathscr{D} & \text{9, 10, HS} \\ \hline \therefore & \mathscr{D} & \text{8, 11, HS} \end{array} $$

따라서 $\mathscr{B} \Rightarrow \mathscr{D}, \mathscr{C} \Rightarrow \mathscr{D}, \mathscr{B} \lor \mathscr{C} \vdash \mathscr{D}$이다.

$\blacksquare$

 

[9] $\mathscr{B} \lor \mathscr{C}$의 정의가 $\neg \mathscr{B} \Rightarrow \mathscr{C}$이므로 $\mathscr{B} \vdash \mathscr{B} \lor \mathscr{C}$임을 다음과 같이 보일 수 있다.

$$ \begin{array}{rll} 1. & \mathscr{B} & \text{Hyp} \\ 2. & \mathscr{B} \Rightarrow \left( \neg \mathscr{C} \Rightarrow \mathscr{B} \right) & \text{(A1)} \\ 3. & \neg \mathscr{C} \Rightarrow \mathscr{B} & \text{1, 2, HS} \\ 4. & \neg \mathscr{B} \Rightarrow \neg \neg \mathscr{B} & \text{3, Contrapositive} \\ 5. & \neg \neg \mathscr{C} \Rightarrow \mathscr{C} & \text{DNE} \\ \hline \therefore & \neg \mathscr{B} \Rightarrow \mathscr{C} & \text{4, 5, HS} \end{array} $$

따라서 $\mathscr{B} \vdash \mathscr{B} \lor \mathscr{C}$이다. 이제 $\mathscr{C} \vdash \mathscr{B} \lor \mathscr{C}$임을 보이자. 

일단, $\mathscr{C}, \neg \mathscr{B} \vdash \mathscr{C}$임은 자명하다. 따라서 연역 정리에 의해 $\mathscr{C} \vdash \neg \mathscr{B} \Rightarrow \mathscr{C}$이다.

$\blacksquare$

 

[10] 이는 이 글에서 언급한 것과 같이 명제논리에서는 증명 없이 받아들인다.

 

[11] 이는 다음과 같이 증명할 수 있다.

$$ \begin{array}{rll} 1. & \mathscr{B} \Rightarrow \mathscr{C} & \text{Hyp} \\ 2. & \neg \mathscr{C} \Rightarrow \neg \mathscr{B} & \text{1, Contrapositive} \\ 3. & \neg \mathscr{C} & \text{Hyp} \\ \hline \therefore & \neg \mathscr{B} & \text{2, 3, MP} \end{array} $$

$\blacksquare$

 

앞으로 위의 추론규칙들은 자주 쓰일 것이다. 또한, 위의 추론규칙들을 통해 아래의 몇 가지 따름정리들을 얻을 수 있다.

 

Corollary 1.

$\mathscr{B}$, $\mathscr{C}$, $\mathscr{D}$가 wff라고 하면, 아래는 모두 참이다. 1. 배중률 (Law of Excluded Middle) $$ \vdash \mathscr{B} \lor \neg \mathscr{B} $$ 2. 논리합의 교환법칙 (Commutative Law of Disjunction) $$ \mathscr{B} \lor \mathscr{C} \vdash \mathscr{C} \lor \mathscr{B} $$ 3. 논리합의 결합법칙 (Associative Law of Disjunction) $$ \left( \mathscr{B} \lor \mathscr{C} \right) \lor \mathscr{D} \vdash \mathscr{B} \lor \left( \mathscr{C} \lor \mathscr{D} \right) \\ \mathscr{B} \lor \left( \mathscr{C} \lor \mathscr{D} \right) \vdash \left( \mathscr{B} \lor \mathscr{C} \right) \lor \mathscr{D} $$ 4. 논리곱의 교환법칙 (Commutative Law of Conjunction) $$ \mathscr{B} \land \mathscr{C} \vdash \mathscr{C} \land \mathscr{B} $$ 5. 논리곱의 결합법칙 (Associative Law of Conjunction) $$ \left( \mathscr{B} \land \mathscr{C} \right) \land \mathscr{D} \vdash \mathscr{B} \land \left( \mathscr{C} \land \mathscr{D} \right) \\ \mathscr{B} \land \left( \mathscr{C} \land \mathscr{D} \right) \vdash \left( \mathscr{B} \land \mathscr{C} \right) \land \mathscr{D} $$ 6. 분배법칙 (Distributive Law) $$ \mathscr{B} \lor \left( \mathscr{C} \land \mathscr{D} \right) \vdash \left( \mathscr{B} \lor \mathscr{C} \right) \land \left( \mathscr{B} \lor \mathscr{D} \right) \\ \left( \mathscr{B} \lor \mathscr{C} \right) \land \left( \mathscr{B} \lor \mathscr{D} \right) \vdash \mathscr{B} \lor \left( \mathscr{C} \land \mathscr{D} \right) \\ \mathscr{B} \land \left( \mathscr{C} \lor \mathscr{D} \right) \vdash \left( \mathscr{B} \land \mathscr{C} \right) \lor \left( \mathscr{B} \land \mathscr{D} \right) \vdash \mathscr{B} \land \left( \mathscr{C} \lor \mathscr{D} \right) $$ 7. 드 모르간의 법칙 (De Morgan's Laws) $$ \neg \left( \mathscr{B} \land \mathscr{C} \right) \vdash \neg \mathscr{B} \lor \neg \mathscr{C} \\ \neg \left( \mathscr{B} \lor \mathscr{C} \right) \vdash \neg \mathscr{B} \land \neg \mathscr{C} $$ 8. 폭발 원리 (Principle of Explosion; $\bot \text{E}$) $$ \mathscr{B}, \neg \mathscr{B} \vdash \mathscr{C} $$ 9. 공허 참 (Vacuosly Truth) $$ \neg \mathscr{B} \vdash \mathscr{B} \Rightarrow \mathscr{C} $$

 

이에 대한 증명은 비교적 자명하므로 굳이 서술하지는 않겠다. 만약 명제논리에 익숙하지 않다면 연습문제 삼아 직접 증명해보는 것도 좋을 것이다. 또한, 논리합과 논리곱의 결합법칙으로부터 연산의 순서가 중요하지 않다는 사실을 알 수 있다. 따라서 3개 이상의 wff에 논리합 연산 또는 논리곱 연산을 적용할 때에는 $\mathscr{B}_1 \lor \mathscr{B}_2 \lor \cdots \lor \mathscr{B}_n$과 같이 나타내도 무방하다. 단, $\mathscr{B} \lor \mathscr{C} \land \mathscr{D}$와 같이 나타낼 수는 없음에 유의하라.