[이산수학] 증명법 (proof)

여러가지 증명 방법

이산수학 내에서 증명법은 크게 수학적 귀납법 / 직접 증명법 / 간접 증명법으로 나눌 수 있습니다.

수학적 귀납법(mathematical induction): 연역법의 일종으로, 주어진 사실들과 공리들에 입각해 추론을 통해 새로운 사실을 도출하는 것
직접 증명법(direct proof): 정의에 의해 혹은 이미 결과가 나온 내용을 토대로 논리적으로 명제를 직접 증명하는 것
간접 증명법(indirect proof): 모순, 대우, 논리적 동치 등을 이용해 간접적으로 결론이 참임을 이끌어 내 증명

 

수학적 귀납법

$P(n)$이 양의 정수 $n$에 의해 정의된다고 하자. $a$가 임의의 정수일 때, 다음의 두 명제가 참임을 가정한다.
1. $P(a)$는 참이다.
2. 모든 $k ≥ a$인 정수는 $P(k)$가 참이면 $P(k + 1)$도 참이다.
이 때 모든 정수 $n ≥ a, P(n)$이 성립한다.

 

직접 증명법

직접 증명법 (direct proof): 정의에 의해 혹은 이미 결과가 나온 내용을 토대로 논리적으로 명제를 직접 증명하는 것.

 

간접 증명법

간접 증명법(indirect proof): 모순, 대우, 논리적 동치 등을 이용해 간접적으로 결론이 참임을 이끌어 내 증명

 

모순 증명법

모순 증명법 (proof by contradiction)
1. 증명할 명제가 거짓이라고 가정한다. 즉, 명제의 부정이 참이라고 가정한다.
2. 논리적으로 모순임을 보인다.
3. 증명해야 할 명제를 참이라고 결론짓는다.

 

대우 증명법

대우 증명법 (proof by contraposition): $p → q$와 $\sim q → \space \sim p$가 대우 관계로서 논리적 동치가 되는 것을 이용해 $\sim q → \space \sim p$가 참인 것을 증명하는 것.

 

반례 증명법

반례 증명법 (proof by counterexample): 명제에서 모순이 되는 반례를 찾아 증명하는 것.

 

필요충분조건

필요충분조건 (if and only if): 필요조건과 충분조건을 모두 만족하면 동치가 되는 것을 이용해 주어진 명제가 동치됨을 증명.