수학에서 말하는 증명(Proof)이란 뭘까?

수학의 꽃은 증명이라고 한다. 이산수학에서도 증명은 상당히 중요한 파트 중 하나이다. 오늘은 증명의 정의와 증명이 어떻게 이루어지는지 알아보자!

 

---

증명이 도대체 뭐길래?

증명이란 쉽게 말해서 수학적으로 명제가 확실함을 밝히는 과정이다.

 

조금 더 정확하고 있어보이게 말하자면, 주어진 공리나 이미 증명된 정리로부터 특정 명제나 논리적으로 타당함을 이끌어 내는 과정이라고 볼 수 있다.

 

여기서 몇 가지 용어를 정리해야 한다.

 

1. 공리란, 증명할 필요없이 사실로 받아드리는 명제를 말한다.

2. 정리란, 공리로부터 증명된 공리가 아닌 명제를 말한다.

 

즉, 증명이란 공리가 사실이라면 이 명제는 논리적으로 반드시 사실임을 보이는 과정이다.

---

증명의 종류

수학에서 가장 많이 쓰이는 증명은 크게 4가지가 있다. 

1. 직접증명(Direct Proof)
2. 대우를 통한 증명(Proof by Contraposition)
3. 귀류법(Proof by Contradiction)
4. 일일히 증명(Proof by Exhaustion)

각각의 증명 방법은 항진명제(언제나 참인 명제)로 정당화 시킬 수 있다.

 

이 4가지 증명을 하나하나 알아보자.

---

직접 증명(Direct Proof)

직접증명은, 말 그래로 직접 증명하는 것이다. 

 

만약에 P 라는 명제가 사실이고, P 와 Q 의 관계를 묘사하는 P ⇒ Q 라는 명제가 사실이라면, 직관적으로 Q가 반드시 사실이라는 것을 추측할 수 있다. 이걸 알아듣기 편하게 자연 언어로 하면 P가 사실이고, "P가 사실이면 Q가 사실이다"라는 문장이 사실이라면, 당연히 Q도 사실이다. 언핏 듣기에는 당연한 말이지만, 이 당연한 말이 수학의 근간을 지탱하고 있다고 해도 과언은 아니다.

 

직접 증명은 아래와 같은 항진명제로 정당화될 수 있다.

MP : (P ∧ (P ⇒ Q)) ⇒ Q

이 증명 방식은 어려운 말로 모데스 포넌(Modus Ponens)라고 하기도 하는데, 지식을 자랑하려는 용도가 아니라면 많이 듣지 못 할 말이라 굳이 기억하지 않아도 상관없다.

 

간단한 직접 증명의 예시로 어떤 정수가 홀수라면 그 정수의 제곱도 홀수임을 증명해보자. 

 

우선, 이를 기호로 나타내면 다음과 같다.

∀ n ∈ Z (n is odd ⇒ n^2 is odd)

이를 직접증명으로 증명해보자.

 

(n is odd) 

⇒ ∃ k ∈ Z (n = 2k + 1)

⇒ n^2 =(2k+1)^2 =4k^2 +4k+1 = 2(2k^2 + 2k) + 1

⇒ (n^2 is odd)

QED

 

위와 같이 증명할 수 있다. 이 증명에서는, P ⇒ Q 를 증명하기 위해 P로 출발해서 Q를 이끌어냈다.

---

대우를 통한 증명(Proof by Contraposition)

대우를 통한 증명을 대우를 증명함으로써 원래 명제를 증명하는 방법이다.

 

여기서 대우란 원래 함축 관계, P ⇒ Q 에서 ~Q⇒ ~P 가 된 것을 말한다. 대우는 원래 명제와 동치이다. (즉, 진리값이 같다.) 그렇기 때문에 대우를 증명하면 원래 명제를 증명한 것과 동일한 효과를 낸다.

 

대우를 통한 증명은 아래와 같은 항진명제를 통해 정당화 될 수 있다.

MT : ((P ⇒ Q) ∧ ~Q) ⇒ ~ P

이 증명 방식은 위의 직접 증명 방식처럼 있어보이는 단어로 모데스 톨렌(Modus Tollens)라고 하지만, 역시나 자주 들을 일은 없을 것이다.

 

대우를 통한 증명은 원래 명제보다 그 부정이 더 다루기 쉬운 경우에 많이 이용된다.

---

귀류법(Proof by Contradiction)

귀류법은, 수학 역사상 가장 위대한 발견이라고 해도 손색이 없을 정도로 뛰어난 증명 방법이다. 

 

귀류법은, 우선 전제를 부정한다. 그리고 모순을 이끌어 낸 뒤, 이런 모순이 존재하는 이유는 전제를 부정했기 때문이고, 그렇기 때문에 전제를 부정할 수 없다, 즉 사실이라는 것을 증명하는 것이다. 

 

귀류법은 아래와 같은 항진명제로 정당화 될 수 있다.

RAA : (¬P ⇒ Q) ∧ (¬P ⇒ ¬Q)) ⇒ P

귀류법은 어려운 말로 Reductio Ad Absurdum 이라고 한다. 이 단어는 앞의 MP와 MT와는 달리, RAA 라는 약어로 가끔 볼 수 있다.

 

귀류법의 가장 유명한 예시는 √2가 유리수가 아니라는 증명이다.

 

이를 증명하기 위해 √2가 무리수가 아니라고 가정해보자. 즉, √2는 유리수이다. 유리수의 정의에 의하여 다음이 성립한다.

 

∃ p,q ∈ Z, q≠0 : √2 =p / q

⇒ gcd(p, q) = 1, 2 = p^2 / q^2

⇒ 2q^2 = p^2

 

⇒ p^2 is even

 

⇒ p is even

 

⇒ ∃ k ∈ Z p = 2k

⇒ 2q^2 = (2k)^2, q^2 = 2k^2

⇒ q^2 is even

⇒ q is even

⇒ gcd(p, q) != 1

QED

---

일일히 증명(Proof by Exhaustion)

마지막으로 너무 단순하다고 생각할 수도 있지만, 모든 경우의 수를 고려해서 하나하나 증명할 수도 있다. 일반적으로 일일히 증명하는 방법은 다른 증명 방법에 비해 단순 무식하고 우아하지 않다고 생각할 수 있지만, 수학적으로는 증명되었다는 점에서 동일하다.

 

또, 무시해서도 안 될게 4색문제 같은 경우도 컴퓨터가 일일히 경우의 수를 따져가며 증명되었기 때문에 실제 자주 쓰이는 증명 방법 중에 하나이기도 하다.

---