[이산수학] 증명

1. 증명 관련 기본 용어

1) 공리

어떤 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정으로 별도의 증명없이 참으로 이용되는 명제를 공리라고 합니다.

 

공리의 예로서는 아래 이론등이 있습니다.

1) 유클리드 기하학 : 두 점이 주어졌을 때 두점을 통과하는 직선을 그릴 수 있다.

2) 페아노의 공리 : 어떤 자연수도, 그 수의 다음 수가 존재한다.

3) 공리적 집합론 : 어떤 것도 포함되지 않는 집합이 존재한다.

2) 증명

특정한 공리들을 가정하고, 그 가정하에 제안된 명제가 참입을 입증하는 작업을 증명이라고 합니다.

3) 정리

공리로부터 증명된 명제를 정리라고 합니다.

이 정리에는 여러가지가 있습니다. 

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

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

 

2. 증명방법

1) 직접증명법

공리와 정의, 그리고 정리를 논리적으로 직접 연결하여 증명하는 방법입니다.

명제를 변형하지 않고 증명하는 방법입니다. 다른 말로 연역법이라고도 합니다.

주로 공리와 정의 이미 증명된 정리를 논리적으로 직접 연결해 증명하는 형식을 따릅니다.

 

연역법이란 이미 증명된 하나 또는 둘 이상의 명제를 전제로 하여 새로운 명제를 결론으로 이끌어내는 것입니다.

 

예제1)

문제)두 홀수의 합은 짝수임을 증명하라

증명)두 홀수를 x,y라고 하자.

        x = 2a + 1, y = 2b + 1 (단 a,b는 정수)

        x + y = 2(a+b+1)

        a+b+1은 정수이므로 정수의 두배는 짝수다. 따라서 x+y는 짝수가 된다.

 

예제2)

문제) 두 유리수의 합이 유리수임을 증명하라

증명) x,y를 유리수라고 하자

         x = a/b (단 a,b는 정수이고 b ≠ 0) y = c/d ( 단 c,d는 정수이고 d ≠ 0 )

         x + y = (ad+bc) / bd

        여기서 ad+bc, bd 모두 정수이면서 bd 는 0이 아니므로 두 유리수의 합은 유리수가 된다.

 

파스칼 삼각형

아래 그림과 같은 형태를 파스칼 삼각형이라고 합니다.

 

 

파스칼 삼각형을 증명하는 예제는 아래와 같습니다.

 

문제) n,k는 양의 정수이고 k<=n 이라고 가정하면 C(n+1,k) = C(n,k)+ C(n,k-1)이다.

증명) C(n,k) + C(n,k-1) = n! / k!(n-k)! + n! / (k-1)!(n-(k-1))! = n! / k!(n-k)! + n! / (k-1)!(n-k+1)!

                                     = (n-k+1)n! / (n-k+1)k!(n-k)! + kn! / k(k-1)!(n-k+1)!

                                     = ( (n-k+1)n!+kn!) / k! (n-k+1)! 

                                     = (n+1)n! / k!(n-k+1)!

                                     =  (n+1)! / k!((n+1)-k)! = C(n+1,k)

2) 수학적 귀납법

모든 자연수N에 대한 명제의 성질을 증명하는데 유용한 증명방법입니다.

순서는 아래 단계를 따릅니다.

1] 기본단계 : n의 출발점에서 명제가 성립하는가를 확인합니다.

2] 귀납과정 : n = k일때 명제가 성립한다고 가정합니다.

3] 귀납단계 : n = k+1 일때도 명제가 성립함을 증명합니다.

 

예제1)

문제) n이 자연수일 때 다음을 증명하시오

        1+2+3+4+...+n = n(n+1) / 2

증명) S(n)을 1+2+...+n = n(n+1) / 2라고 하자 

        1. 기본단계 : S(1)은 1 = 1(1+1)/2 이므로 성립

        2. 귀납과정 : S(k)가 참이라고 가정,  1+2+...+k = k(k+1) / 2를 참이라고 가정

        3. 귀납단계 : S(k+1) = 1+2+...+k + (k+1) = (k+1)((k+1)+1) / 2

                             S(k+1) = S(k) +(k+1)이므로 k(k+1)/2 +(k+1) = (k(k+1)+2(k+1))/2

                             = (k+1)(k+2)  / 2 = (k+1)((k+1)+1) /2

3) 간접증명법

증명해야할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법입니다.

이러한 간접증명법에는 대우 증명법, 모순 증명법, 반례증명법, 존재증명법 등이 있습니다.

 

1] 대우증명법: 대우를 사용하여 증명하는 방법입니다. 

예제)

문제) x^2이 홀수라면 x도 홀수임을 증명하시오

 

증명)

 

2] 모순증명법 : 모순증명법은  p이면 q이다를 증명할때 ~p를 가정하면 모순이 발생한다는 것을 보임으로써 증명하는 방법입니다. 모순증명법은 귀류법, 배리법 등이라고도 합니다.

 

예제)

(문제)√2가 유리수가 아님을 증명하시오

(증명) 

 

※서로소

두 수 사이의 관계에서 공통되는 약수가 최대 1이며 1밖에 없는 수

3] 반례증명법 :  전체한정자(∀)가 사용된 명제가 거짓임을 증명하는 방법입니다.

예제)

(문제) 모든 실수 a,b에 대해 a^2 = b^2이면 a=b이다가 거짓임을 증명하시오

(증명) a = 1, b= -1일 경우 a^2 = b^2이지만 a ≠ b 이다.

 

4] 존재증명법 : 존재한정자(∃)가 사용된 명제가 참임을 증명하는 방법입니다.

이러한 존재증명법에는 구성적 존재증명법과 비구성적 존재증명법이 있습니다.

 

구성적 존재증명법은 명제함수 ∃xP(x)를 증명할 때 P(x)를 참으로 만드는 x를 찾거나 찾는과정을 제시합니다.

예제)

(문제) a^b이 무리수가 되는 유리수 a,b가 존재함을 증명하시오

(증명) a=2, b=1/2라고 하자. 그러면 a^b = 2^(1/2) = √2가 된다. 따라서 문제가 참이다.

 

비구성적 존재증명법은 명제함수 ∃xP(x)를 증명할 때 P(x)를 참으로 만드는 x를 찾지 않고 우회적으로 명제가 타당함을 보이는 방법입니다.

 

예제)

(문제) a^b이 유리수가 되는 무리수 a,b가 존재함을 비구성적인 방법을 사용하여 증명하시오

(증명)

4) 기타 증명법

전수증명법, 조합적 증명법, 컴퓨터 이용한 증명법 등이 있습니다.

 

1] 전수증명법 : 명제에서 유도될 수 있는 경우의 수가 적을 때 모든 경우의 수를 조사하는 방법입니다.

2] 조합적 증명법 : 두 집합의 원소의 개수가 동일함을 증명할 때 사용합니다.

    조합적 증명법에는 전단증명과 중복산정이 있습니다.

    1. 전단증명 : 원소가 n개인 집합A와 원소가 m개인 집합 B를 찾은 후

                          두 집합이 일대일 관계임을 보여 n=m임을 증명하는 방법입니다.

     2. 중복산정 : 동일한 집합의 원소를 두가지 방법으로 센 다음, 그 결과가 각각 n, m이라면 n=m임을 증명하는 것입니다. 

 

3]컴퓨터를 이용한 증명 :  증명하기가 복잡한 경우, 컴퓨터의 데이터 처리능력을 이용하여 증명하는 방법입니다.

 

이러한 증명법에는 대표적인 것은 4색 정리입니다. 

 

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