여러가지 증명법

수학적 귀납법(Mathematcal Induction)

수학적 귀납법에서는 명제 p1, p2, p3, ... pn이 사실이라고 할 때

pn+1의 경우에도 성립한다는 것을 보인다.

따라서, n이 1인 경우 성립하는 것을 보이고 또한 모든 n값에 대해 성립한다고 가정하면

n+1의 경우에도 성립하는 것을 보여주면 된다.

 

이때 출발점이 되는 n의 값을 '기초단계(basis)' 라고 하며,

p1, p2, p3, ... pn을 '귀납 가정(inductive assumption)',

pn+1의 경우에 성립됨을 보여주는 것을 '귀납 단계(inductive step)'라고 한다.

 

수학적 귀납법의 예시

 

모순 증명법(proof by contradiction)

주어진 문제의 명제를 일단 부정해놓고 논리를 전개하여, 그것이 모순됨을 보임으로써 본래의 명제가 사실임을 증명하는 방법이다. 이는 귀류법이라고도 한다.

 

p → q가 참인 것과 p ∧ (~q)가 거짓임은 논리적인 동치이다.

따라서 p ∧ (~q)가 참이라고 하고 모순이 유도되면 명제가 참임이 증명된다.

( 'p이면 q이다' 가 참일 때, 'p이고 q가 아니다는 거짓이다.' 역시 참이다. 따라서 둘은 논리적 동치이다.

이 때 'p이고 q가 아니다는 참이다.' 가 거짓임을 유도하면 결국 'p이면 q이다'가 '참'인 것을 증명하게 된다.)

모순 증명법의 예시

 

 

직접 증명법(direct proof)

통상 주어진 유용한 정보로부터 추론을 통하여 목적하는 결론에 도달할 수 있도록 유도하는 증명법으로,

명제 p → q의 직접 증명은 논리적으로 p의 진리값이 참일 때 q도 참임을 보이는 증명 방법이다.

 

문제) 만약 6x + 9y = 7이라면 x 또는 y가 정수가 아님을 증명해보자.

풀이)

6x + 9y = 7이라고 가정.

3(2x + 3y) = 7

2x + 3y = 7/3

7/3이 정수가 아니므로 2x + 3y은 정수가 될 수 없음.

따라서 x와 y는 정수가 아님.

 

 

대우 증명법(contrapositive proof)

p → q 와 ~q → ~p가 대우 관계로써 논리적 동치가 됨을 이용하여

 ~q → ~p가 참이면 p → q 또한 참임을 증명하는 방법이다.

 

문제) x가 짝수이면 x는 2이거나 소수가 아니다. 를 증명하라

풀이)

대우 : x는 2가 아니면서 소수라면 x는 홀수이다.

팩트 : 2가 아니면서 소수라면 x는 홀수이다.

따라서 증명이 되었다.

 

 

존재 증명법(existence proof)

술어 논리가 들어간다. 어떤 것이 존재한다는 것을 증명하는 매우매우 심플한 증명법이다.

p(x)를 x라는 변수를 가지는 명제라고 할 때,

p(x)가 참인 x가 적어도 하나는 존재한다는 것을 보이는 증명방법이다.

즉, '∃x such that p(x)'를 보이는 것이다.

단순하게 그냥 주어진 조건을 만족하는 x 하나만 찾아서 보여주면 증명된다.

 

문제) p(x)가 술어 'x는 정수이고 x² = 81일 때 이 식을 만족하는 x가 존재함을 증명하라.

풀이)

x = 9일 때 위 식이 성립된다.

따라서 존재가 증명되었다.

 

 

반례 증명법(proof by counter-example)

어떤 명제가 참 또는 거짓임을 입증하기가 어려운 경우, 주어진 명제에서 모순이 되는 간단한 하나의 예를 보임으로써 비교적 쉽게 증명할 수 있는 방법이다.

즉, 모든 x는 p(x)를 만족한다 가 거짓임을 보이기 위해서

만족하지 않는 x가 적어도 하나는 존재한다는 것을 증명하면 된다.

 

문제) 'p가 양의 정수이고, x = p² + 1이면 x는 소수이다.' 란 명제가 거짓임을 증명하라.

풀이)

p가 3일 경우 x = 10 이다. 10은 소수가 아니다.

따라서 거짓임이 증명되었다.

 

 

필요충분조건 증명법(if and only if proof)

p if and only if q의 경우

p ↔ q 는 (p → q) ∧ (q → p)와 논리적 동치이다.

이를 이용해 주어진 명제를 증명하는 방법이다.

 

문제) 모든 정수 n에 대해 n - 1이 짝수임과 n이 홀수임이 동치라는 것을 증명하라.

풀이)

(1) n이 홀수이면 n - 1이 짝수이다.

 - n이 홀수이면 어떤 정수 k에대해 n = 2k -1로 나타낼 수 있다.

 - n - 1 = (2k + 1) - 1 = 2k

 - 그러므로 n - 1 은 짝수이다.

(2) n -1이 짝수이면 n은 홀수이다.

 - 만약 n - 1 이 짝수이면 어떤 정수 k에 대해 n - 1 = 2k로 나타낼 수 있다.

 - 이 경우 n = 2k + 1로 n은 홀수가 된다.

따라서 위 두가지 경우가 모두 성립하므로 동치이다.