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

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

 

Inference Rules

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

 

Proof.

증명은 다음과 같다.

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

 

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

 

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

 

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

 

[6] $\mathcal{B}\wedge \mathcal{C}$의 정의가 $\mathrm{\neg }(\mathcal{B}\Rightarrow \mathrm{\neg }\mathcal{C})$이므로 $\mathcal{B}\wedge \mathcal{C}⊢\mathcal{C}$임을 다음과 같이 증명할 수 있다.

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

따라서 $\mathcal{B}\wedge \mathcal{C}⊢\mathcal{C}$이다.

이제 $\mathcal{B}\wedge \mathcal{C}⊢\mathcal{B}$임을 보이자.

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

따라서 $\mathcal{B}\wedge \mathcal{C}⊢\mathcal{B}$이다.

$◼$

 

[7] $\mathcal{B},\mathcal{C}⊢\mathcal{B}\wedge \mathcal{C}$를 증명하기에 앞서, $\mathcal{B},\mathcal{C},\mathcal{B}\Rightarrow \mathrm{\neg }\mathcal{C}⊢\mathrm{\neg }(\mathcal{B}\Rightarrow \mathcal{B})$임을 보이자.

$$\begin{array}{rll}1.& \mathcal{B}& \text{Hyp}\\ 2.& \mathcal{B}\Rightarrow \mathrm{\neg }\mathcal{C}& \text{Hyp}\\ 3.& \mathrm{\neg }\mathcal{C}& \text{1, 2, MP}\\ 4.& \mathcal{C}& \text{Hyp}\\ 5.& \mathcal{C}\vee \mathrm{\neg }(\mathcal{B}\Rightarrow \mathcal{B})& \text{4, DI}\\ \therefore & \mathrm{\neg }(\mathcal{B}\Rightarrow \mathcal{B})& \text{3, 5, DS}\end{array}$$

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

$$\begin{array}{rll}1.& (\mathcal{B}\Rightarrow \mathrm{\neg }\mathcal{C})\Rightarrow \mathrm{\neg }(\mathcal{B}\Rightarrow \mathcal{B})& \text{Above}\\ 2.& \mathrm{\neg }\mathrm{\neg }(\mathcal{B}\Rightarrow \mathcal{B})\Rightarrow \mathrm{\neg }(\mathcal{B}\Rightarrow \mathrm{\neg }\mathcal{C})& \text{1, Contrapositive}\\ 3.& (\mathcal{B}\Rightarrow \mathcal{B})\Rightarrow \mathrm{\neg }\mathrm{\neg }(\mathcal{B}\Rightarrow \mathcal{B})& \text{DNI}\\ 4.& (\mathcal{B}\Rightarrow \mathcal{B})\Rightarrow \mathrm{\neg }(\mathcal{B}\Rightarrow \mathrm{\neg }\mathcal{C})& \text{2, 3, HS}\\ 5.& \mathcal{B}\Rightarrow \mathcal{B}& ⊢\mathcal{B}\Rightarrow \mathcal{B}\\ \therefore & \mathrm{\neg }(\mathcal{B}\Rightarrow \mathcal{C})& \text{4, 5, MP}\end{array}$$

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

$◼$

 

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

$$\begin{array}{rll}1.& \mathcal{C}\Rightarrow \mathcal{D}& \text{Hyp}\\ 2.& \mathrm{\neg }\mathcal{B}\Rightarrow \mathcal{C}& \text{Hyp}\\ 3.& \mathrm{\neg }\mathcal{B}\Rightarrow \mathcal{D}& \text{1, 2, HS}\\ 4.& \mathrm{\neg }\mathcal{D}\Rightarrow \mathrm{\neg }\mathrm{\neg }\mathcal{B}& \text{3, Contrapositive}\\ 5.& \mathrm{\neg }\mathrm{\neg }\mathcal{B}\Rightarrow \mathcal{B}& \text{DNE}\\ 6.& \mathrm{\neg }\mathcal{D}\Rightarrow \mathcal{B}& \text{4, 5, HS}\\ 7.& \mathcal{B}\Rightarrow \mathcal{D}& \text{Hyp}\\ 8.& \mathrm{\neg }\mathcal{D}\Rightarrow \mathcal{D}& \text{6, 7, HS}\\ 9.& \mathrm{\neg }\mathcal{D}\Rightarrow \mathrm{\neg }\mathcal{D}& ⊢\mathcal{B}\Rightarrow \mathcal{B}\\ 10.& (\mathrm{\neg }\mathcal{D}\Rightarrow \mathrm{\neg }\mathcal{D})\Rightarrow ((\mathrm{\neg }\mathcal{D}\Rightarrow \mathcal{D})\Rightarrow \mathcal{D})& \text{(A3)}\\ 11.& (\mathrm{\neg }\mathcal{D}\Rightarrow \mathcal{D})\Rightarrow \mathcal{D}& \text{9, 10, HS}\\ \therefore & \mathcal{D}& \text{8, 11, HS}\end{array}$$

따라서 $\mathcal{B}\Rightarrow \mathcal{D},\mathcal{C}\Rightarrow \mathcal{D},\mathcal{B}\vee \mathcal{C}⊢\mathcal{D}$이다.

$◼$

 

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

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

따라서 $\mathcal{B}⊢\mathcal{B}\vee \mathcal{C}$이다. 이제 $\mathcal{C}⊢\mathcal{B}\vee \mathcal{C}$임을 보이자. 

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

$◼$

 

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

 

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

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

$◼$

 

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

 

Corollary 1.

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

 

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