4.1 증명의 방법론

4.2.1 수학적 귀납법

수학적 귀납법 : 자연수에 관한 명제 P(n)이 모든 자연수에 대해 성립함을 보이는 증명법
약한 수학적 귀납법
- 다음을 증명한다고 가정하자. n >= a 인 모든 정수에서 P(n)이 참이다.
- 기초 단계(basis) : P(a)가 참임을 보인다.
- 귀납 단계(inductive step) : k >= a 인 모든 정수에 대해 P(k)가 참임을 가정하고 P(k+1)이 참인지를 보인다.
- 귀납 가정(inductive hypothesis/assumption) : k >= a 인 임의 정수 k에 대해 P(k)가 참이라 가정하는 것
- 기초 단계와 귀납 단계를 모두 만족하면 n >= a 인 모든 정수에서 P(n)이 참이다.
강한 수학적 귀납법
- P(n)이 정수 n에 대해 정의되는 명제이고 a ⇐ b 를 만족하는 정수 a, b를 가정하자.
- 기초 단계(basis) : P(a), P(a+1), … , P(b) 가 전부 참임을 보인다.
- 귀납 단계(inductive step) : k >= b 인 k 에 대해 만약 a 부터 k 까지의 모든 정수 i 에 대해 P(i)가 참임을 가정하고 P(k+1)이 참임을 보인다.
- 기초 단계와 귀납 단계를 모두 만족하면 n >= a 인 모든 정수에서 P(n)이 참이다.

모순 증명법(귀류법) : 주어진 명제를 부정해 놓고 논리를 전개하여, 그것이 모순됨을 보임으로써 본래의 명제가 사실임을 증명하는 방법이다.
- 참, 가 참이니 를 거짓이라 가정하고 논리를 전개해 모순됨을 보인다.

직접 증명법 : 주어진 유용한 정보로부터 추론을 통해 목적하는 결론에 도달할 수 있도록 유도하는 증명법
- 의 직접 증명. 논리적으로 p가 참일 때 q도 참임을 보이는 증명 방법이다.

대우 증명법 : 명제의 대우 관계로서 논리적 동치가 됨을 이용해 증명하는 방법
- 와 가 대우 관계이고, 가 참임을 증명함으로써 가 참이 되는 것을 보여주는 증명 방법이다.

존재 증명법 : p(x)를 x라는 변수를 가지는 명제라고 할 때, p(x)가 참인 x가 적어도 하나가 존재한다는 것을 보이는 증명 방법이다.
- 를 보이는 것이다.

반례 증명법 : 어떤 명제가 참 또는 거짓임을 입증하기가 상당히 어려운 경우, 주어진 명제에서 모순이 되는 간단한 하나의 예를 보임으로써 비교적 쉽게 증명할 수 있는 방법이다.
- 가 거짓임을 보이기 위해 과 동치인 에서 p(x)를 만족하지 않는 x가 적어도 하나 존재함을 보이면 된다.