[이산수학 - 3강] 증명

한국방송통신대학교 이산수학 강의 3강을 듣고 공부한 내용을 정리한 포스팅입니다.

3강의 학습목표

• 다양한 증명방법의 종류를 이해하고 때에 따라 적절한 증명방법을 선택할 수 있다.

• 기본단계와 귀납가정을 설계하고 귀답단계를 통해 주어진 명제가 타당함을 증명할 수 있다.
• 직접적으로 명제를 증명하기 어려울 때는 증명하기 쉬운 형태로 주어진 명제를 변경할 수 있다.
• 전수증명, 조합적 증명법, 컴퓨터를 이용한 증명방법을 이해하고 상황에 따라 증명방법을 사용할 수 있다.

- 증명의 기본

증명은 어떤 사실의 타당성을 입증하기 위해 사용된다. 주로 "P이면 Q이다", 즉 '전제가 참이면 결론도 참' 이라는 형식을 따르게 되는데 이때 전제로 사용되는 P가 참임을 증명하기 위해서는 다른 전제의 도움이 필요하다. 이렇게 계속 거슬러 올라가다보면 더 이상 증명할 필요가 없이 사실들을 만나게 되는 데 이를 '공리'라고 한다. 이를 바탕으로 '증명' 하고 '정리'를 얻는다.

 

공리 (axiom)

 

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

 

증명 (proof)

 

특정한 공리들을 가정하고, 그 가정하에 제안된 명제가 참임을 입증하는 작업

 

정리 (theorem)

 

공리로부터 증명된 명제. 이 때 정리를 증명하기 위한 과정에서 사용되는 명제는 보조 정리 (lemma) 라 하고, 정리로부터 쉽게 도출되는 부가적인 명제는 따름 정리 (corollary) 라고 한다.

- 직접 증명법

직접증명법 (direct proof - 연역법)

 

주로 공리와 정의, 그리고 이미 증명된 정리를 논리적으로 직접 연결해 증명하는 형식을 따르는 증명 방식을 직접 증명법이라고 한다. 연역법이라고도 불리운다.

 

예 ) 두 짝 수의 합은 항상 짝수임을 증명하시오

 

두 짝수를 각각 x, y라 하면  x = 2a, y = 2b ( a와 b는 정수) 형태로 나타낼 수 있다. 

따라서 x + y는 2a + 2b로 나타낼 수 있고 이는 2(a+b) 와 같으므로 두 짝수의 합은 항상 짝수다.

- 수학적 귀납법

수학적 귀납법 (proof of mathematical induction)

 

수학적 귀납법은 모든 자연수 n에 대해 명제가 성립함을 증명하는 데 유용한 방법이다. 이는 3단계 과정을 거친다. 

 

1. 기본단계 : n = 1 일 때 명제가 참임을 증명한다
2. 귀납가정 : n = k 일 때 명제가 참이라고 가정한다.
3. 귀납단계 : n = k + 1 일 때 명제가 참임을 증명한다.

이렇게 되면 n이 2일 때도 명제가 참이 되는 것이고, 이를 반복함으로써 모든 자연수에 대해 참임을 증명할 수 있다.

 

예) 모든 양의 정수 n에 대해 2^n > n 임을 증명하라

 

1. 기본단계 :  n이 1 일 때 2 > 1 이므로 참이다
2. 귀납가정 : n이 k 일 때 2^k > k 가 참이라고 가정하고
3. 귀납단계 : n이 k+1 일 때 2^(k+1) > k + 1 임을 증명한다.  이는 먼저 귀납 가정의 식에서 양변에 2를 곱해  2^(k+1) > 2k를 만들고 , 이 때 k는 임의의 자연수이므로 2k >= k + 1 가 성립한다. ( 끽해봤자 1일 때 같고 그 외엔 항상 k + 1 이 2k 보다 작다 ) 이를 이어 붙이면 2^(k+1) > 2k >= k + 1이 되고 이는 곧 2^(k+1) > k + 1 이라 표현할 수 있다. 

위와 같이 기본단계 - 귀납가정 - 귀납단계를 거치는 수학적 귀납법을 활용해 이 명제가 참임을 증명할 수 있다.

- 간접 증명법

간접 증명법 (indirect proof)

 

간접증명법은 증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법이다.

종류로는 '대우 증명법' 과 '모순 증명법' ,  '반례증명법'과 '존재증명법'이 있다

 

• 대우증명법 (proof by transposition)

p → q 를 증명하는 대신 그 대우인 ~p →~q 를 증명하는 방법

 

예) x^2이 짝수라면 x도 짝수임을 증명하시오

 

위 명제의 대우는 'x^2이 짝수가 아니라면 x도 짝수가 아니다'이다. 

이를 증명하기 위해 x를  홀수 (2k + 1 , 단 k는 정수)로 두고 x^2을 구하면 4(k^2 + 1) 1이 나오므로 홀수의 제곱은 항상 홀수임을 알 수 있다. 따라서 조건명제의 대우가 참임으로 조건명제 'x^2이 짝수라면 x도 짝수'라는 조건명제 역시 참이다.

 

• 모순증명법 (proof by contradiction)

p → q가 사실이 아님을 가정하고 증명을 진행하고 모순을 발견해 p→q가 참임을 증명하는 방법

 

• 반례증명법

전체 한정자(∀)가 쓰인 명제가 거짓임을 증명할 때 사용하는 방법

 

• 존재증명법

존재 한정자 (∃)가 쓰인 명제가 참임을 증명할 때 사용하는 방법. 이는 p(x)를 참으로 만드는 x를 주어진 정의역에서 직접 찾는 구성적 존재 증명법 (constructive proof of existence)과 직접 x를 찾진 않지만 우회적인 방법을 통해 명제가 타당함을 보이는 비구성적 존재 증명법 (nonconstructive proof of existence) 으로 나뉜다.

- 그 외 다양한 증명방법

 

• 전수증명법 (proof by exhaustion) 

명제에서 유도될 수 있는 경우의 수가 적을 때 일일이 모든 경우의 수를 조사하는 방법

 

• 조합적 증명법 (combinatiorial proof)

두 집합의 원소의 개수가 동일하다는 것을 증명할 때 사용되는 증명 방법. '전단 증명'과 '중복 산정'으로 나뉜다.

 

• 컴퓨터를 이용한 증명 (computer-assisted proof)

수학적 증명 과정중에 컴퓨터를 이용한 계산이 포함되는 경우. 계산이 많이 필요한 경우 사용된다.