제 2 절 간접증명법
앞 절에서 보인 예들처럼 전제조건에서 직접 결론을 이끌어 내는 방법을 직 접증명법(direct proof)이라 한다. 직접증명법을 사용하기 어려울 경우 간 접증명법(indirect proof)을 사용할 수 있다. 간접증명법에는 결론의 부정 을 전제에 추가하여 모순을 이끌어 내는 방법인 배리법(reductio ad absur- dum)이 많이 사용된다. 배리법은귀류법으로 부르기도 한다.
[[ 예 ]] 2.10 아래 추론의 타당성을 간접증명법으로 증명하여라.
그가 인문계열 학과를 다닌다면 그는 멋있는 인생을 살 것이다.
그가 자연계열 학과를 다닌다면 그는 취직을 잘 할 것이다.
그는 인문계열이나 자연계열 학과에 다닌다.
따라서 그는 멋있는 인생을 살거나 취직을 잘 할 것이다.
풀이. p : 그는 인문계열 학과를 다닌다.
q : 그는 멋있는 인생을 살 것이다.
r : 그는 자연계열 학과를 다닌다.
s : 그는 취직을 잘 할 것이다.
라고 하자. 그러면 주어진 추론은
p→ q r→ s p ∨ r /∴ q ∨ s
가 된다. 간접증명법으로 증명하자.
1. p→ q 2. r→ s 3. p ∨ r / ∴ q ∨ s
4. ∼ (q ∨ s) 간접증명 5. ∼ q ∧ ∼ s 4, De Morgan 6. ∼ q 5,단순화 7. ∼ s 5,단순화 8. ∼ p 1, 6,삼단부정법 9. ∼ r 2, 7,삼단부정법 10. r 3, 8,선언지제거 11. r∧ ∼ r 9, 10,논리곱
12. c 11
모순을 이끌어 냈으므로 배리법에 의해 주어진 추론은 타당하다.
[[ 예 ]] 2.11 다음 논증의 타당성을 간접증명법으로 증명하여라.
p ∨ q → r s→ p ∧ u q ∨ s/ ∴ r
풀이.
1. p ∨ q → r 2. s→ p ∧ u 3. q ∨ s/ ∴ r
4. ∼ r 간접증명법 5. ∼ (p ∨ q) 1, 4, 삼단부정법 6. ∼ p ∧ ∼ q 5, De Morgan 7. ∼ p 6,단순화 8. ∼ q 6,단순화 9. s 3, 8,선언지제거 10. p ∧ u 2, 9,삼단긍정법 11. p 10,단순화 12. p∧ ∼ p 7, 11,논리곱 13. c 12
결론을 부정하여 모순을 이끌어 내었으므로 배리법에 의해 위 논증은 타당하 다.
