명제논리의 기초(5) - 연역추론

 

명제논리의 기초(4)에 나타난 추론규칙들을 전제로 해서 여러 가지 것들을 증명하겠습니다.

 

1. p→q ≡ ~q→~p (대우명제)

 

 p→q ≡ ~p∨q

        ≡ q∨~p

        ≡ ~(~q)∨~p

  ≡ ~q→ ~p

 

 

2. (p→q) ∧ p ⇒ q (Modus Ponens)

 

(p→q) ∧ p ≡ (~p∨q)∧ p

                ≡ (~p∧p)∨(q∧ p)

                ≡ c∨(q∧ p)

                ≡ (q∧ p)

                ⇒ q

 

 

3. p→q  ≡ (p∧~q) → c  (reduction to absurdity. 귀류법)

           

 p→q ≡ ~p∨q

        ≡ (~p∨q)∨c

        ≡ ~(p∧~q)∨c

        ≡ (p∧~q) → c

 

3의 경우, 귀류법을 정당화해주는 논리적 장치입니다. p가 전제이고 q가 결론일 때, p이고 ~q이면 모순이 된다는 것이 귀류법의 취지이죠.

 

 

4. (p→r)∨(q→s) ≡ (p∧q)→(r∨s)

 

(p→r)∨(q→s) ≡ (~p∨r)∨(~q∨s)

                     ≡ (~p∨~q)∨(r∨s)

                     ≡ ~(p∧q)∨(r∨s)

   ≡ (p∧q) → (r∨s)

 

 

5. (p→q) ∧ (p→~q) ≡ ~p

 

(p→q) ∧ (p→~q) ≡ (~p∨q)∧(~p∨~q)

                          ≡ ~p∨(q∧~q)

                          ≡ ~p∨c

                          ≡ ~p

 

6. (p→q) ∧ (~p→q) ≡ q   (dilemma. 양도논법)

 

(p→q) ∧ (~p→q) ≡ (~p∨q)∧(p∨q)

  ≡ q∨(~p∧p)

  ≡ q∨c

  ≡ q

 

 

6번 식은 수학에서 많이 쓰이는 논증법입니다. p를 가정해도 q가 나오고, ~p를 가정해도 q가 나온다면, 항상 q가 나온다는 의미입니다.