[이산수학] 증명

✔ 정의

공리(axiom)

어떤 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정으로, 별도의 증명 없이 참으로 이용되는 명제

증명(proof)

특정한 공리들을 가정하고, 그 가정하에 제안된 명제가 참임을 입증하는 작업

정리(theorem)

공리로부터 증명된 명제

1) 보조정리(lemma) : 정리를 증명하는 과정 중에 사용되는 증명된 명제

2) 따름정리(corollary) : 정리로부터 쉽게 도출되는 부가적인 명제

직접 증명법(direct proof)

공리와 정의 그리고 정리를 논리적으로 직접 연결하여 증명

다른 말로 연역법(deduction)이라고 함
* 연역법 : 이미 증명된 하나 또는 둘 이상의 명제를 전제로 하여 새로운 명제를 결론으로 이끌어내는 것
명제를 변형하지 않고 증명함

파스칼 삼각형(Pascal's triangle)

수학적 귀납법

자연수 n에 대한 명제의 성질을 증명하는데 유용함

3단계 과정
1. 기본단계(basis) : n의 출발점에서 명제가 성립하는가 확인
2. 귀납가정(inductive assumption) : n = k 일 때 명제가 성립한다고 가정
3. 귀납단계(inductive step) : n = k + 1 일 때도 명제가 성립함을 증명

1) 대우증명법(proof by transposition)

2) 모순증명법(proof by contradiction)

P → Q를 증명할 때 ~P를 가정하면 모순이 보임

3) 반례증명법

전체한정자가 사용된 명제가 거짓임을 증명

4) 구성적 존재증명법

명제함수 Ǝ𝑥P(𝑥)를 증명할 때 P(𝑥)를 참으로 만드는 𝑥를 찾거나 찾는 과정을 제시함

5) 비구성적 존재증명법

명제함수 Ǝ𝑥P(𝑥)를 증명할 때 P(𝑥)를 참으로 만드는 𝑥를 찾지않고 우회적으로 명제가 타당함을 보이는 방법

1) 전수증명법

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

2) 조합적 증명법

두 집합의 원소의 개수가 동일함을 증명할 때 사용됨

3) 컴퓨터를 이용한 증명

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