- toc {:toc}
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)이 참이다.
4.2.2 모순 증명법
- 모순 증명법(귀류법) : 주어진 명제를 부정해 놓고 논리를 전개하여, 그것이 모순됨을 보임으로써 본래의 명제가 사실임을 증명하는 방법이다.
참, 가 참이니 를 거짓이라 가정하고 논리를 전개해 모순됨을 보인다.
4.2.3 직접 증명법
- 직접 증명법 : 주어진 유용한 정보로부터 추론을 통해 목적하는 결론에 도달할 수 있도록 유도하는 증명법
의 직접 증명. 논리적으로 p가 참일 때 q도 참임을 보이는 증명 방법이다.
4.2.4 대우 증명법
- 대우 증명법 : 명제의 대우 관계로서 논리적 동치가 됨을 이용해 증명하는 방법
와 가 대우 관계이고, 가 참임을 증명함으로써 가 참이 되는 것을 보여주는 증명 방법이다.
4.2.5 존재 증명법
- 존재 증명법 : p(x)를 x라는 변수를 가지는 명제라고 할 때, p(x)가 참인 x가 적어도 하나가 존재한다는 것을 보이는 증명 방법이다.
를 보이는 것이다.
4.2.6 반례 증명법
- 반례 증명법 : 어떤 명제가 참 또는 거짓임을 입증하기가 상당히 어려운 경우, 주어진 명제에서 모순이 되는 간단한 하나의 예를 보임으로써 비교적 쉽게 증명할 수 있는 방법이다.
가 거짓임을 보이기 위해 과 동치인 에서 p(x)를 만족하지 않는 x가 적어도 하나 존재함을 보이면 된다.
4.2.7 필요충분조건 증명법
- 필요충분조건 증명법 : 주어진 명제의 동치를 통하여 증명한다.
를 증명하기 위해 와 를 보여 증명한다.
