[이산수학] 증명, 직접증명법, 간접증명법, 수학적 귀납법

˚ 공리(Axion)

하나의 이론에서 증명 없이 참(T)이 되는 명제

ex) a=b면, a+c=b+c다.

˚ 정의(Definition)

 논의의 대상을 보편적인 것으로 하기 위해, 사용되는 용어 또는 기호의 의미를 확실하게 규정한 문장이나 식.

ex)한 내각의 크기가 직각인 삼각형을 직각삼각형이라 한다.

˚ 정리(Theorem)

공리와 정의를 통해 증명이 된 명제

ex) 피타고라스의 정리 : 직각삼각형은 빗변의 길이를 한 변으로 하는 정사각형의 넓이와

나머지 두 변의 길이를 각각 한변의 길이로 한 정사각형 두 개의 넓이의 합과 같다.

˚ 증명(proof)

어떤 명제가 참임을 확인하는 과정

 

˚ 직접증명법(Direct Proof)

명제를 변형하지 않고 함축명제 p→q가 T을 증명하는 방법이다.

예제) 모든 정수에 대해 짝수에서 홀수를 뺀 수가 홀수임을 증명하라.

풀이) p : x는 짝수다.

q : x에서 홀수 y를 뺀 수는 홀수다.

p→q : 짝수인 x에서 홀수인 y를 뺀 수는 홀수다.

정수 m,n이 있을 때, 짝수 x는 x=2m, 홀수 y는 y=2n+1 으로 표현할 수 있다.

x에서 y를 뺀 식을 표현하면 다음과 같다.

x - y = 2m - ( 2n + 1 ) = 2m - 2n - 1 = 2 ( m - n ) - 1

m-n을 변수 a로 치환하면, x-y=2a-1로 홀수가 된다.

∴ 명제 p→q "짝수인 x에서 홀수인 y를 뺀 수는 홀수다"는 참이다.

 

˚ 간접증명법(Indirect Proof)

직접 증명하지 않고, 간접으로 증명하는 방법으로, 대우증명법, 모순증명법, 반례증명법, 존재증명법이 있다.

1) 대우증명법(Proof by Conterposition)

함축명제 p→q와 ￢q→￢p가 동치임을 이용하여 증명하는 방법.

2) 모순증명법(Proof by Conteadiction)

함축명제 p→q와 ￢(p∧￢q)가 동치임을 이용하여 증명하는 방법.

3) 반례증명법(Proof by Counter-Example)

주어진 명제에 모순이 되는 예를 찾아 증명하는 방법.

4) 존재증명법(Existence Proof)

주어진 명제가 참이 되는 예를 찾아 증명하는 방법.

 

˚ 수학적 귀납법(Mathematical Induction)

자연수 n에 관한 명제 p(n)이 임의의 자연수에 대하여 만족하는 것을 세 단계의 과정으로 증명하는 방법이다.

1) 기본가정 : p(논의영역의 초깃값)가 성립한다.

2) 귀납가정 : 명제 p(k)가 성립한다면, p(k+1)도 성립한다고 가정한다.

3) 귀납단계 : 기본가정과 귀납가정을 이용해 p(n)이 성립함을 증명한다.

* 귀납이란? 여러 가지 특정 사실들로부터 일반적인 사실을 유도해내는 추론 방법