[이산수학#3] 증명

1. 기본사항

공리 : 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정, 별도의 증명 X 참으로 이용

증명 : 특정한 공리들을 가정, 제안된 명제가 참임을 입증

정리 : 공리로부터 증명된 명제

- 보조정리 : 정리를 증명하는 과정 중에 사용되는 증명된 명제

- 따름정리 : 정리로부터 쉽게 도출되는 부가적인 명제

 

2. 직접증명법 (연역법)

명제 변형 X 증명, 공리와 정의, 정리를 논리적으로 직접 연결하여 증명

ex) 파스칼 삼각형

 

3. 수학적 귀납법

자연수 n에 대한 명제의 성질을 증명

기본단계 => 귀납가정 => 귀납단계

기본단계 : n의 출발점에서 명제가 성립하는가 확인

귀납가정 : n = k 일 때, 명제가 성립한다고 가정

귀납단계 : n = k + 1 일 때도 명제가 성립함을 증명

 

4. 간접증명법

증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명

대우증명법 : P -> Q => ~Q -> ~P

모순증명법 : P -> Q 증명 시, ~P를 가정하면 모순 발생

-귀류법 : 오류로 귀착 , 배리법 : 이치에 어긋나게 됨

반례 증명법 : 전체 한정자가 포함된 명제가 거짓임을 증명

존재 증명법 : 존재 한정자가 포함된 명제가 참임을 증명

- 구성적 존재 증명법 : 명제함수를 증명할 때 P(x)를 참으로 만드는 x를 찾거나 찾는 과정

- 비구성적 존재 증명법 : 명제함수를 증명할 때 P(x)를 참으로 만드는 x를 찾지 않고 우회적으로 명제가 타당함을 보임

 

5. 다양한 증명방법

전수 증명법 : 명제에서 유도될 수 있는 경우의 수가 적을 때 일일이 모든 경우의 수를 조사

조합적 증명법 : 두 집합의 원소의 개수가 동일함을 증명

- 전단증명 : 원수가 n개인 집합 A와 원소가 m개인 집합 B를 찾은 후, 두 집합이 1:1 관계로 n = m임을 증명

- 중복산정 : 동일한 집합의 원소를 두 가지 방법으로 세어 결과가 n과 m이면 n = m임을 증명

 

컴퓨터 이용 증명법 : 증명하기 복잡한 경우 컴퓨터의 데이터 처리능력을 사용

ex)4색 정리