이산수학 3강 :: 공리, 증명, 정리, 증명법

이산수학 3강을 보며 배운내용

 

 

KEYWORDS

공리(axiom)

다른 명제를 증명하려고 사용되는 기본적인 가정

증명 없이 참으로 이용하는 명제

 

증명(proof)

특정 공리들을 가정하고,

가정하에 제안된 명제가 참인지 입증하는 작업

 

정리(theorem)

공리로부터 증명된 명제

 

 

증명 방법

• 직접 증명법
  공리, 정의 그리고 정리를 논리적으로 직접 연결
• 수학적 귀납법
  자연수 n에 대한 명제의 성징을 증명하는데 유용하다
  기본단계, 귀납가정, 귀납단계 이용
• 간접 증명법
  증명하기 쉽게 변형해서 증명
  예) 대우 증명법, 모순 증명법, 반례 증명법 등

 

 

직접 증명법(direct proof)

연역법(deduction)이라고도 한다

명제를 변형하지 않고 증명

주로 공리, 정의, 증명된 정리를 논리적으로 직접 증명한다

 

예) 두 유리수의 합이 유리수임을 증명

r과 s를 유리수라고 하자

r = a/b (단 a와 b는 정수 b != 0)

s= c/d (단 c와 d는 정수 d != 0)

 

r + s = a/b + c/d

=> ad + bc / bd

참이다, 정수끼리 더하고 나눠봐도 유리수

 

 

수학적 귀납법

모든 자연수 n에 대해 명제 증명하는데 유용하다

 

3단계 과정

1. 기본 단계(basis)
   n의 첫 번째 명제가 성립하는지 확인
   1부터 n까지면 1을 넣어보는 것
2. 귀납 가정(inductive assumption)
   n = k 일 때 명제가 성립한다고 가정
3. 귀납 단계(inductive step)
   n = k + 1 일 때도 명제의 성립을 증명

 

 

간접 증명법

직접 증명 어려울 때 사용

쉬운 형태로 변형해서 증명

 

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

P -> Q / ~Q -> ~P

 

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

귀류법, 배리법이라고도 한다

P -> Q 증명할 때

~ P를 가정하면 모순이 발생함을 보는 것

 

예) 자연수 k는 소수
모순: 소수 k는 완전수이다
k가 3일 때 약수는 1, 3
본인을 제외한 약수 1의 합으로 3이 될 수 없으니 완전수가 아니다

 

3. 반례증명법

한정자가 포함된 명제의 증명

전체한정자(∀)가 사용된 명제를 거짓으로 증명

존재한정자(∃)가 사용된 명제를 참임을 증명

 

4. 구성적 존재증명법

명제함수 ∃xP(x)를 증명할 때

P(x)를 참으로 만드는 x를 찾거나 찾는 과정을 제시