4. 증명

개발한 프로그램의 처리 속도, 효율성, 유지보수성 등 여러가지 검증자료를 정리하여 이전 버전보다 향상된 기능을 보여주어야 하는데 이러한 과정을 증명(Proof)이라고 한다?

증명은 어떠한 명제가 참 또는 거짓임을 밝히는 과정이기 때문에 전제로 사용되는 명제들은 반드시 참이어야 하고 그 전제들은 논리적이고 정확해야한다.

4.1. 증명의 이해

4.1.1. 공리(Axiom)

def : 별도의 증명 없이 항상 참으로 이용되는 명제

공리는 이미 증명된 규칙이라고 보면된다. 이 공리로 부터 다른 모든 규칙들이 세워진다.

예시

• 서로 다른 두점을 잇는 직선은 하나다(비유클리드에서!).

• 어떤 자연수 n에 대해 n+1이 존재한다.

4.1.2. 정의(Definition)

def : 논의의 대상을 보편화하기 위해 사용하는 용어 또는 기호의 의미를 확실하게 규정한 문장이나 식

정의는 우리가 이걸 어떻게 부르겠다는 약속이다. 우리가 사용하는 단어들이 정의가 된 대표적인 예들이다.

예시

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

4.1.3. 정리(Theorem)

def : 공리와 정의를 통해 참으로 확인된 명제

예시

• 피타고라스의 정리 : 직각삼각형에서 빗변의 제곱은 밑변의 제곱과 높이의 제곱의 합니다.

4.1.4. 증명(Proof)

def : 하나의 명제가 참임을 확인하는 과정

증명을 하는 방법에는

• 직접증명법

• 간접증명법

• 존재증명법

• 수학적귀납법

등이 있다.

4.2. 직접증명법

def : 조건명제 p->q가 참임을 증명하기 위해 전제 p를 참으로 가정했을 때 결론 q도 참임을 증명하는 방법.

예시 : 두 홀수의 곱은 홀수임을 증명할 때

p : 두 정수 m,n은 홀수이다.
q : m,n의 곱은 홀수이다.

m = 2k+1, n = 2l+1 (k,l은 정수)

m과 n의 곱은 다음과 같다

m * n = (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1

(2kl + k + l)은 어쨌든 정수이고(정수는 덧셈에 대해 닫혀있다) 정수에 2배를 하면 짝수인데 거기에 1을 더했으므로 두 홀수의 곱은 홀수이다.

4.3. 간접증명법

주어진 명제 p->q를 그대로 증명하기 어려울 때 p->q와 동칭틴 다른 형태의 명제로 전환하여 공리, 정의, 정리등을 활용해 증명할 수 있는데, 이러한 증명법을 간접증명법이라한다.

즉, 명제 그대로 두고 증명하면 직접증명법! 명제를 좀 치환해서 증명하면 간접증명법!

간접증명법에는 대우증명법과 모순증명법이 있다.

4.3.1. 대우증명법(Proof by Contrapositive)

대우명제는 본명제와 참거짓이 같다. 그렇기 때문에 대우명제가 참임을 증명하면 본명제도 참이다.

def : 조건명제 p->q와 그 대우 ~q->~p가 동치임을 이용하여 증명하는 방법

예시 : 두 정수 m,n의 곱이 홀수이면, m,n은 모두 홀수임을 증명하라

p : 두 정수 m,n의 곱이 홀수이다.
q : m, n은 모두 홀수이다.
~p : 두 정수 m,n의 곱은 짝수이다.
~q : 두 정수 m,n은 짝수이다.

~q -> ~p : 두정수 m,n이 짝수이면 그 곱도 짝수이다.

m = 2k, n = 2l
m * n = 4kl

a = 2kl이라 하면

m * n = 2a

따라서 명제는 참이다.

4.3.2. 모순증명법

조건명제 p->q는 ~(p AND ~q)와 동치이다.

~(p AND ~q) === ~p OR ~(~q)
            === ~p OR q
            === p->q

이러한 성질을 이용해 명제 p and ~q를 증명하는 것이다. 즉 명제 p가 참인경우 명제 q를 부정하여 증명(~q)했을 때 명제 p and ~q가 거짓이 되면 본 명제 p->q는 참이되는 것이다.

def : 조건명제 p->q와 ~(p and ~q)가 동치임을 이용하여 p and ~q가 거짓임을 보여 증명하는 방법.

예시 : 두 홀수의 곱이 홀수가 됨을 증명

p : 두 정수 m, n 은 홀수이다.
q : m, n의 곱은 홀수이다.
~q : m, n의 곱은 짝수이다.
p and ~q : 두 정수 m, n은 홀수이고 m, n의 곱은 짝수이다.

m = 2k + 1, n = 2l + 1

m * n = (2k + 1)(2l + 1) = 2(2kl + k + l) + 1 이므로 m, n 의 곱은 홀수이다.

따라서 p and ~q 의 명제가 거짓이 되므로

~(p and ~q) 와 같은 p->q는 참이 된다.

4.4. 존재/반례 증명법

4.4.1. 존재증명법