이산수학 - 2. 증명

1. 증명의 정의

공리: 별도의 증명없이 참으로 이용되는 명제

정의: 논의의 대상을 보편화하기 위해 사용하는 용어 또는 기호의 의미를 확실하게 규정한 문장이나 식

정리: 공리와 정의를 통해 참으로 확인된 명제

증명: 하나의 명제가 참임을 확인하는 과정

 

 

2. 직접증명법 

함수 p→q가 참이 됨을 증명하는 방법

 

3. 간접증명법

함수 p→q를 다양한 형태로 변형하여 증명

 

대우증명법: p→q가 ~q→~p와 동치임을 증명

모순증명법: p→q가 ~p∨q와 동치임을 이용하여 증명 

반례증명법: 모순이 되는 예를 찾아 증명

존재증명법: 참이되는 예를 찾아 증명

 

 

4. 수학적 귀납법

자연수 n에 대한 명제 p(n)이 모든 자연수 n에 대해 만족하는 것을 다음 세단계 과정으로 증명하는 방법

(1) 기본가정: p(논의영역의 초기값)이 참 임을 증명

(2) 귀납가정: 임의의 k에 대해 p(k)가 참이라고 가정

(3) 귀납단계: 기본가정과 귀납가정을 이용해 k+1에 대해 p(k+1)이 참임을 증명