[이산수학] 증명

증명

---

1. 공리(Axiom)

공리는 다른 정의나 정리를 통한 증명 없이 참으로 이용되는 명제이며, 이는 다른 정의나 정리들을 증명하기 위한 전제로 사용되는 가정입니다.

(예시) 유클리드 기하학의 공리
① 일직선 위의 점들 사이의 거리는 측정 가능하다.
② 임의의 선분은 무한히 연장 가능하다.
③ 모든 직각은 서로 동일하다.
④ 두 점이 주어졌을 때, 두 점을 통과하는 직선을 그릴 수 있다.
⑤ 모든 직선과 평행선에 대해 한 점에서 만나는 직선은 하나뿐이다.

 

2. 정리(Theorem)

정리란 증명된 명제를 의미합니다.

 

3. 증명(Proof)

증명은 이미 가정된 공리 하에 어떤 명제가 참임을 보이는 과정입니다,

 

3.1. 직접 증명법(Direct proof)

가정과 공리를 사용하여 명제의 변형 없이 논리적인 단계를 통해 직접 명제를 증명하는 방법입니다.

 

3.2. 간접 증명법(Indirect proof)

명제를 증명하기 쉬운 형태로 변형하여 원래의 명제를 증명하는 방법입니다.

• 반례법(Counterexample)
  반례를 제시하여 주어진 명제가 거짓임을 증명하는 방법.
• 대우증명법(Proof by Transposition)
  명제와 대우 관계인 명제를 증명하여 원래의 명제를 판별하는 방법.
• 모순증명법(Proof by Contradiction)
  주어진 명제의 참, 거짓을 가정하고 그 가정에서 모순이 발생하는 것을 보임으로 가정이 잘못되었음을 증명하는 방법.

 

3.3. 수학적 귀납법(Mathematical induction)

모든 자연수가 어떤 주어진 성질을 만족시킨다는 명제를 증명하는 방법입니다. 증명 과정은 다음과 같은 3단계 순서를 따르게 됩니다.

1. 기본단계
   n = 1이 참임을 증명.
2. 귀납가정
   n = k일 때, 명제가 성립한다고 가정. (k는 임의의 자연수)
3. 귀납단계
   n = k+1일 때에도 명제가 성립함을 증명.

(예시) n까지 자연수의 합 = n(n+1)/2
① n = 1일 때, 1 = 1(1+1)/2이기 때문에 참.
② n = k일 때, 1+2+...+k = k(k+1)/2라고 가정.
③ n = k+1일 때, 1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 (∵ ②이 참이라고 가정)

∴ 명제(n까지 자연수의 합 = n(n+1)/2)는 참이다.

 

3.4. 전수 증명법(Proof by Exhaustion)

가능한 모든 경우의 수를 모두 조사하여 명제를 증명하는 방법입니다. 경우의 수가 적을 때 유용합니다.