귀류법(Proof by contradiction)

그림 출처: 네이버 블로그(http://naver.me/GZzg4H9V)

 

    귀류법(歸謬法)은 "P이면 Q이다."라는 명제에서 결론인 Q를 부정함으로써 생기는 새로운 명제 "P이면서 Q가 아니다."에서 모순이 발생함을 증명하여 원래의 명제가 참임을 증명하는 간접 증명법입니다. 배리법(背理法) 또는 반증법(反證法)이라고도 불리는 이 방법은 현재 고등학교 1학년 학생이 배우는 <수학> 과목에서도 등장하는 증명법으로, 가장 유명한 문제는 다음과 같은 명제를 증명하는 것입니다.

 

$\sqrt{2}$는 유리수가 아니다.

 

고등학교 교과과정에서는 다음과 같은 과정을 거쳐 이 명제를 증명합니다.

 

1. 결론을 부정하여 $\sqrt{2}$가 유리수라고 가정한다.
2. 유리수의 정의에 의해 서로소인 어떤 두 정수 $p$와 $q$를 이용하여 $\sqrt{2} = \frac{p}{q} (q \neq 0)$의 꼴로 나타낼 수 있다.
3. 양변을 정리한 뒤 제곱하면 $p^2 = 2 q^2$이라는 식을 얻을 수 있다.
4. $p^2$는 $2$를 약수로 가지게 되므로 $p$는 $2$를 약수로 가진다. (대우를 통해 증명 가능)
5. 또다른 정수 $p'$를 이용해 $p = 2p'$로 나타내면 $4 p'^2 = 2 q^2$가 되고, 다시 정리하면 $q^2 = 2 p'^2$이 된다.
6. 마찬가지로 $q^2$이 $2$를 약수로 가지므로 $q$ 역시 $2$를 약수로 가진다.
7. 4와 6에 의해서 $p$와 $q$는 공약수 2를 가진다. 이는 2에서 내린 "$p$와 $q$는 서로소다."라는 전제와 모순된다.
8. 즉, $\sqrt{2}$가 유리수라는 가정은 틀렸다. 만약  $\sqrt{2}$가 실수라는 것을 보인다면 $\sqrt{2}$는 무리수라고 결론지을 수도 있다.

    사실 귀류법은 이 명제나 "소수는 무한히 많다."라는 명제를 증명해보는 것 말고는 고등학교 수학에서 중요하게 다뤄지지 않습니다. 이런 방법이 있다고 알려줄 뿐이지, 왜 결론을 부정할 때 모순이 생기면 원래의 명제가 참이 될 수 밖에 없는지를 엄밀하게 설명해주지도 않습니다. 수능에서도 수학적 귀납법과 함께 빈칸 채우는 문제가 한 문제씩 꼭 나왔던 것 같지만, 증명 과정을 논리적으로 따라가지 않아도 4점을 거저먹을 수 있는 문제였던 걸로 기억합니다. 이번 글에서는 어떤 원리를 통해 귀류법으로 명제가 참임을 증명할 수 있는지를 제대로 알아보겠습니다.

 

조건문

    우선 "P이면 Q이다."라는 명제는 조건문의 형태를 띄고 있습니다. 이를 기호로 쓴다면 다음과 같이 표현할 수 있습니다.

$$p \rightarrow q$$

 

이 때, $p$는 가설(hypothesis), 전제(premise), 혹은 전건(antecedent)라고 불리며, $q$는 결론(conclusion), 혹은 후건(consequence)이라고 불립니다.

 

 

   예를 들어, "비가 많이 내리면, 야구 경기가 취소된다."라는 명제에 대해 생각해봅시다. 이 명제는 언제 참이 될까요? 만약 이러한 규정이 존재하고, 비가 많이 내렸을 때 정말로 야구 경기가 취소됐다면 이는 규정에 맞는 상황입니다. 반대로 비가 많이 내림에도 경기가 취소되지 않는 경우가 존재한다면 이 규정에 어긋나게 되며, 이는 곧 명제가 거짓이라는 것을 의미합니다.

 

    그렇다면 아예 비가 내리지 않는 상황에서는 어떻게 생각할 수 있을까요? 비가 내리지 않았는데 야구 경기가 취소되는 경우, 그리고 비가 내리지 않고 야구 경기도 진행하는 경우는 각각 참과 거짓을 어떻게 판별할 수 있을까요? 모든 명제는 참과 거짓이라는 두 가지 진리값 중 하나를 반드시 가지기 때문에, 이러한 경우들에도 명제는 반드시 참이거나 거짓이거나 둘 중 하나일 텐데 말이죠. 하나씩 자세히 살펴보도록 합시다.

 

• 비가 내리지 않았는데 야구 경기가 취소됐을 경우, 어떠한 이유든 비오는 것과는 관계 없는 다른 이유에서 경기가 취소됐을 것이기 때문에 규정에 어긋나는 상황은 아니다. 즉, 명제는 참이다.
• 비가 내리지 않았고 야구 경기도 계속 진행됐을 경우, 아무 일도 일어나지 않은 정상적인 상황이므로 규정에 어긋나는 상황이 아니며, 명제는 참이다.

   

    다시 말해, 전제가 거짓이라면 결론이 참이든 거짓이든 명제는 참이라는 것입니다. 이를 진리표로 나타내자면 다음과 같습니다.

 

$p$	$q$	$p \rightarrow q$
T	T	T
T	F	F
F	T	T
F	F	T

 

진리표를 통해 알 수 있듯, $p \rightarrow q$는 $p$가 참이고 $q$가 거짓일 때만 거짓입니다. 즉, 다음과 같은 명제와 항상 같은 진리값을 가지게 됩니다.

 

$$\sim \left( p \wedge \sim q \right)$$

 

또한, 드 모르간의 법칙(De Morgan's laws)에 의해 다음과 같은 명제와도 동치입니다.

 

$$\sim p \vee q$$

 

    필자 같은 경우에는 이러한 동치 관계가 처음에는 와닿지가 않았는데, 재미있게도 영어에서 비슷한 표현을 찾을 수 있었습니다. "If you talk here, you will be kicked out."이라는 문장이 도서관 벽에 걸려있다고 가정합시다. 이는 곧 "여기서 떠들면 쫓겨난다."라는 의미를 가지며, $p \rightarrow q$의 형태를 가지는 조건문입니다. 한편, 영어에서는 이를 "Don't talk here, or you will be kicked out."과 같은 형식으로 표현하곤 하는데, 이는 $\sim p \vee q$와 비슷한 형식의 문장입니다. 완전히 부합하는 설명은 아니지만, 헷갈릴 때 이와 같은 비유를 생각한다면 더 기억이 잘 날 것입니다.

 

귀류법의 원리

    우리가 참임을 증명하고 싶은 명제가 $p \rightarrow q$라고 해봅시다. 앞서 살펴봤듯 이 문제는 곧 $\sim p \vee q$가 참이라는 것을 보이는 것과 동치이며, 마찬가지로 $\left( p \wedge \sim q \right)$가 거짓이라는 것을 보이는 것과 동치입니다. 귀류법은 이 중에서 후자에 주목합니다. 즉, 결론 Q를 부정한 채 전제 P와 같이 두고 생각하는 문장 "P이면서 Q가 아니다."에서 모순이 발생하여 항상 거짓이 된다면, "P이면 Q이다."라는 문장이 항상 참이 된다는 것입니다. 

 

    즉, 귀류법은 엄밀하게 말해서 $\left( p \wedge \sim q \right) \rightarrow F$를 증명함으로써 $\left( p \rightarrow q \right) \rightarrow T$를 증명하는 간접 증명법입니다. 그런데 고등학교 과정에서는 NOT이나 조건문에 대해서만 가르치지 AND나 OR과 같은 다른 논리 연산에 대해서는 가르치지 않으므로 많은 사람들이 $\left( p \rightarrow \sim q \right) \rightarrow F$를 증명함으로써 $\left( p \rightarrow q \right) \rightarrow T$를 증명한다는 식으로 기억합니다. $p \wedge \sim q$와 $p \rightarrow \sim q$는 엄연히 다른 문장을 의미하기 때문에 주의할 필요가 있습니다.

 

예시

    귀류법을 통해서 다음과 같은 명제도 참임을 증명할 수 있습니다.

 

어떤 두 유리수 사이에는 반드시 하나 이상의 무리수가 존재한다.

 

이를 조건문의 형태로 표현해보자면 어떤 두 수 $a$와 $b$가 있을 때, 전제 $p$는 "$a$, $b$는 유리수다.", 결론 $q$는 "$a$와 $b$ 사이에는 반드시 하나 이상의 무리수가 존재한다."가 될 것입니다. 즉, 명제 $p \rightarrow q$는 다음과 같습니다.

 

어떤 두 수 $a$와 $b$가 유리수라면, $a$와 $b$ 사이에는 반드시 하나 이상의 무리수가 존재한다.

 

우선 결론 $q$의 부정인 $\sim q$에 대해 생각해봅시다. 즉, 다음과 같은 명제 $\sim q$가 참이라고 가정하는 것입니다.

 

$a$와 $b$ 사이에는 무리수가 존재하지 않는다.

 

이러면 우리가 거짓임을 증명해야 하는 명제 $p \wedge \sim q$는 다음과 같습니다.

 

$a$와 $b$는 유리수이며, 둘 사이에는 무리수가 존재하지 않는다.

 

일반성을 잃지 않고 $a < b$라고 할 수 있으며, 0보다 크고 1보다 작은 어떤 무리수 $k$를 하나 정의할 수 있습니다. 이 때, $b - a > 0$이므로 다음과 같은 부등식이 성립합니다.

 

$$0 < k < 1 \Rightarrow 0 < k \left( b - a \right) < b - a$$

 

이 부등식의 모든 변에 $a$를 더해주면 다음과 같이 정리됩니다.

 

$$a < k \left( b - a \right) < b$$

 

이 때, $k \left( b - a \right)$는 무리수와 유리수의 곱이므로 항상 무리수입니다. 그러면 이 부등식 자체가 $a$와 $b$ 사이에 어떤 무리수 $k \left( b - a \right)$가 존재한다는 것을 의미하게 됩니다. 이는 둘 사이에 무리수가 존재하지 않는다는 $p \wedge \sim q$의 내용과 모순되며, $p \wedge \sim q$가 언제나 거짓임을 의미합니다. 다르게 표현하자면 $p \rightarrow q$가 항상 참이라는 이야기가 되겠지요. 이러면 귀류법을 통해 원래의 명제가 참이라는 것이 증명됐습니다.

 

    이 외에도 "소수는 무한히 많다."라는 명제가 기원전 3세기에 고대 그리스의 수학자 유클리드(Euclid)에 의해 귀류법으로 증명되기도 하였습니다. 또한 프랑스의 수학자 샤를 에르미트(Charles Hermite)는 귀류법을 이용해서 "원주율 $\pi$는 무리수다."라는 명제와 "자연로그의 밑 $e$는 초월수다."라는 명제가 참이라는 것을 증명하였습니다. 이처럼 수학의 중요한 정리들 중에는 귀류법을 통해 증명된 것들이 많으며, 그만큼 귀류법은 간단하면서도 막강한 증명법이라고 할 수 있습니다.