[이산수학] 증명

✔ 정의

공리(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) 조합적 증명법

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

1. 전단증명
   원소가 n개인 집합 A와 원소가 m개인 집합 B를 찾은 후, 두 집합이 일대일 관계임을 보여 n = m 임을 증명함
2. 중복산정
   동일한 집합의 원소를 두 가지 방법으로 센 다음, 그 결과가 각각 n과 m이라면 n = m 임을 증명함

3) 컴퓨터를 이용한 증명

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

• 4색 정리
  평면을 유한개의 부분으로 나누어 각 부분에 색을 칠할 때,
  서로 맞닿은 부분을 다른 색으로 칠한다면 네 가지 색으로 충분한다.