증명
- 논리적 법칙을 이용하여 주어진 가정으로부터 결론을 유도해내는 추론의 한 방법
- 어떠한 명제나 논증이 적절하고 타당한지를 입증하는 작업이다.
연역법(deduction): 주어진 사실들과 공리(axioms)들에 입각하여 추론(inference)을 통해 새로운 사실을 도출하는 것
귀납법(induction): 관찰과 실험에 기반한 가설을 귀납 추론을 통하여 일반적인 규칙을 입증하는 것
수학적 귀납법(mathematical induction): 명제 이 사실이라고 할 때 의 경우에도 성립한다는 것을 보이는 것
1. 기초 단계(basis): 출발점이 되는 명제
2. 귀납 가정(inductive assumption): 이 참이라고 가정한다.
- 귀납 단계(inductive step): 의 경우에도 성립한다는 것을 보이는 단계(귀납 가정에 입각하여)
모순 증명법(proof by contradiction): 기존의 전통적인 방법으로는 문제를 쉽게 증명할 수 없는 경우에 유용하며 귀류법이라고도 한다.
- 주어진 문제의 명제를 일단 부정하고 논리를 전개하여 그것이 모순됨을 보임으로써 본래의 명제가 사실임을 증명하는 방법
- p→q 와 ~(p∧(~q)) 가 동치 이므로 p∧(~q)가 참이라고 하고 모순이 유도되면 원래의 명제가 참인 것을 증명하게 된다.
직접 증명법(direct proof): 통상 주어진 유용한 정보로부터 추론을 통해 결론에 도달할 수 있도록 유도하는 증명법.
- 명제 p→q의 직접 증명은 p의 값이 참일 때 q도 참임을 보이는 증명 방법
대우 증명법(contra positive proof): p→q 와 ~q→~p가 대우 관계로서 논리적 동치가 됨을 이용한다.
- ~q→~p가 참인 것을 증명함으로 p→q가 참인 것을 보여주는 증명 방법
존재 증명법(existence proof): P(x)를 x라는 변수를 가지는 명제 라고 할 때. P(x)가 참인 x가 적어도 하나가 존재한다는 것을 보이는 증명 방법.
- '∃x such that P(x)'를 보이는 것
반례 증명법(proof by counter-example): 어떤 명제가 참 또는 거짓임을 입증하기가 어려운 경우, 주어진 명제에서 모순이 되는 간단한 하나의 예를 보임으로 써 증명하는 방법
- ∀xP(x)가 거짓임을 보이기 위해 ~ ∀xP(x)와 동치인 ∃x~P(x)에서 P(x)를 만족하지 않는 x가 적어도 하나 존재함을 보이면 된다.
- 이때 x를 반례(counter example) 이라고 한다.
필요충분조건 증명법(if and only if proof): 주어진 명제의 동치를 통하여 증명하는데 (p ↔ q)를 증명하기 위해 '만약 p이면 q이다.'와 '만약 q이면 p이다.'를 증명한다.
