선행학습 · PREREQUISITE
간접증명법
Indirect Proof
원문 : blog.naver.com/cki_math_lab/220730560771
간접증명법 (間接證明法, Indirect Proof)
추론의 타당성에서 보인 예들처럼 전제조건(가정)에서 직접 결론을 이끌어
내는 방법을 직접증명법(直接證明法, Direct Proof)이라 한다. 직접증명법을 사용하기 어려울 경우
간접증명법을 사용할 수 있다. 간접증명법에는 결론의 부정을 전제에 추가하여 모순을 이끌어 내는 방법인
배리법(背理法)이 많이 사용된다. 배리법은 귀류법으로 부르기도 한다.
간접증명법 사용의 예
추론 "그가 인문계열 학과를 다닌다면 그는 멋있는 인생을 살 것이다. 그가 자연계열 학과를 다닌다면 그는
취직을 잘 할 것이다. 그는 인문계열이나 자연계열 학과에 다닌다. 따라서 그는 멋있는 인생을 살거나 취직을
잘 할 것이다."의 타당성을 간접증명법으로 증명해보자.
p: 그는 인문계열 학과를 다닌다, q: 그는 멋있는 인생을 살 것이다, r: 그는 자연계열 학과를 다닌다, s: 그는 취직을 잘 할 것이다 라고 하면, 주어진 추론은 p→q, r→s, p∨r / ∴ q∨s 가 된다. 간접증명법으로 증명하자.
| ① | p→q | 가정 |
| ② | r→s | 가정 |
| ③ | p∨r / ∴ q∨s | 가정/결론 |
| ④ | ∼(q∨s) | 귀류법 (결론의 부정을 추가로 가정) |
| ⑤ | ∼q∧∼s | ④ 드모르간의 법칙 |
| ⑥ | ∼q | ⑤ 단순화 법칙 |
| ⑦ | ∼s | ⑤ 단순화 법칙 |
| ⑧ | ∼p | ①,⑥ 삼단부정법 |
| ⑨ | ∼r | ②,⑦ 삼단부정법 |
| ⑩ | r | ③,⑧ 선언지제거법1) |
| ⑪ | r∧∼r | ⑨,⑩ 논리곱 |
| ⑫ | c | ⑪ 모순명제 |
선언지제거법의 증명 (p∨q)∧∼p ⇒ q
| (p∨q)∧∼p | ≡ (p∧∼p)∨(q∧∼p) | ∵ 분배법칙 |
| ≡ c∨(q∧∼p) | ∵ 모순명제 | |
| ≡ (q∧∼p) | ∵ p∨c ⇔ p | |
| ⇒ q | ∵ 단순화법칙 |
- 1) 선언지제거법의 증명은 위 박스 참고.