귀류법이란? 뜻과 증명 예시, 대우법과 차이까지

📐 개념 정리

귀류법은 증명하려는 결론이 거짓이라고 가정한 뒤 모순을 끌어내 결론이 참임을 보이는 간접 증명법이다. 논리 구조와 배중률, 루트2가 무리수라는 증명과 소수가 무한하다는 유클리드의 증명을 단계별로 따라가고, 대우법·귀납법과 무엇이 다른지 정리했다.

귀류법은 어떤 명제가 참임을 직접 보이는 대신, 그 명제가 거짓이라고 일단 가정하고 그 가정에서 말이 안 되는 결과, 즉 모순을 끌어내는 증명 방법이다. 가정이 모순을 낳았다면 가정이 틀린 것이고, 따라서 원래 명제는 참이어야 한다. 고등학교 1학년 집합과 명제 단원에서 배우는 간접 증명의 대표이며, 루트2가 무리수라는 증명과 소수가 무한히 많다는 증명이 귀류법의 가장 유명한 예시다.

귀류법 뜻 — 결론을 부정하면 모순이 생긴다

귀류법이라는 이름은 '잘못된 곳으로 돌아가게 한다'는 뜻의 한자어에서 왔다. 라틴어 이름은 레둑티오 아드 압수르둠, 우리말로 옮기면 '불합리로의 환원'이다. 상대가 틀렸음을 보이기 위해 상대의 주장을 그대로 받아들인 척하고 끝까지 따라가 보면 터무니없는 결론에 이른다는 논법으로, 수학 이전에 고대 그리스의 철학 논쟁에서 먼저 쓰였다. 수학에서는 피타고라스 학파가 정사각형의 대각선 길이가 분수로 표현되지 않는다는 사실을 발견할 때 이 방법을 썼다고 전해진다.

귀류법이 필요한 이유는 어떤 명제는 직접 증명이 어렵거나 불가능하기 때문이다. '어떤 수가 무리수다'라는 명제를 직접 보이려면 그 수가 어떤 분수와도 같지 않다는 것을 무한히 많은 분수에 대해 확인해야 한다. 반면 '분수라고 가정하자'에서 출발하면 유한한 몇 줄의 계산만으로 모순에 도달한다. 존재하지 않음, 무한히 많음, 유일함처럼 부정이나 무한이 들어간 명제에서 귀류법이 특히 강력한 이유가 여기에 있다.

귀류법의 논리 구조 — 왜 모순이 나오면 증명이 끝나는가

증명하려는 명제를 '가정 $p$이면 결론 $q$이다'라고 두자. 귀류법은 가정 $p$를 그대로 두고 결론의 부정 $\lnot q$를 하나 더 가정한다. 이 두 가정에서 출발해 어떤 명제 $r$과 그 부정 $\lnot r$이 동시에 성립한다는 결과, 즉 모순을 끌어내면 증명이 끝난다.

$$\bigl(p \land \lnot q\bigr) \Rightarrow \bigl(r \land \lnot r\bigr) \qquad \therefore \quad p \Rightarrow q$$

$\land$는 '그리고', $\lnot$은 '아니다', $\Rightarrow$는 '이면'을 뜻한다. 왼쪽 모순이 나오면 $p$와 $\lnot q$가 함께 참일 수 없으므로 $p$가 참일 때 $q$는 참이어야 한다.

이 추론이 정당한 근거는 배중률이다. 배중률은 어떤 명제든 참이거나 거짓이거나 둘 중 하나이며 세 번째 가능성은 없다는 논리 법칙이다. $q$가 거짓이라는 가정이 불가능하다면 남는 선택지는 $q$가 참인 것뿐이다. 귀류법은 이 '남는 선택지'를 결론으로 삼는다. 그래서 귀류법 증명의 마지막 문장은 언제나 '이는 모순이다. 따라서 $q$이다'로 끝난다.

귀류법 증명 예시 1 — 루트2는 무리수다

가장 널리 알려진 귀류법 예시다. 증명할 명제는 '$\sqrt{2}$는 무리수이다'이고, 귀류법에 따라 그 부정인 '$\sqrt{2}$는 유리수이다'를 가정한다. 유리수는 서로소인 두 정수의 비로 쓸 수 있으므로, 더 이상 약분되지 않는 분수 꼴로 놓고 양변을 제곱한다.

$$\sqrt{2} = \frac{p}{q},\quad \gcd(p,q)=1 \;\Longrightarrow\; p^2 = 2q^2$$

$p$, $q$는 정수이고 $q \neq 0$, $\gcd(p,q)=1$은 두 수의 최대공약수가 1, 즉 서로소라는 뜻이다.

$p^2 = 2q^2$이므로 $p^2$은 짝수이고, 홀수의 제곱은 홀수이므로 $p$ 자체가 짝수다. 그러면 $p = 2k$로 쓸 수 있고, 이를 대입하면 $4k^2 = 2q^2$, 곧 $q^2 = 2k^2$이 되어 같은 논리로 $q$도 짝수다. 그런데 $p$와 $q$가 모두 짝수라면 최대공약수가 2 이상이 되어 서로소라는 처음 조건과 어긋난다. 이것이 모순이므로 '$\sqrt{2}$는 유리수이다'라는 가정이 틀렸고, 따라서 $\sqrt{2}$는 무리수다.

이 증명에서 놓치기 쉬운 부분은 '서로소'라는 조건을 처음에 걸어 두는 이유다. 이 조건이 없으면 $p$와 $q$가 둘 다 짝수여도 아무 모순이 아니다. 귀류법은 모순을 만들어야 끝나는 방법이므로, 모순이 부딪힐 벽을 미리 세워 두는 것이 증명의 설계에 해당한다. 내신 서술형에서 감점되는 답안 대부분이 이 조건을 빠뜨린 경우다.

귀류법 증명 예시 2 — 소수는 무한히 많다

유클리드가 원론 제9권에서 보인 증명으로, 무한을 다루는 명제에 귀류법이 어떻게 쓰이는지 보여 준다. 결론의 부정인 '소수는 유한개다'를 가정하면 소수를 빠짐없이 나열할 수 있다. 그 소수들을 전부 곱한 뒤 1을 더한 수를 만든다.

$$N = p_1 p_2 p_3 \cdots p_n + 1$$

$p_1, p_2, \ldots, p_n$은 존재한다고 가정한 모든 소수. $N$을 어느 $p_i$로 나누어도 나머지가 1이다.

$N$은 어떤 $p_i$로 나누어도 나머지가 1이므로 목록의 어떤 소수로도 나누어떨어지지 않는다. 그런데 1보다 큰 모든 자연수는 소수이거나 소수의 곱이므로, $N$은 그 자체가 소수이거나 목록에 없는 새로운 소수를 약수로 갖는다. 어느 쪽이든 '모든 소수를 나열했다'는 가정과 모순이다. 따라서 소수는 무한히 많다. 자주 하는 오해는 $N$ 자체가 항상 소수라는 것인데, 실제로 2·3·5·7·11·13 + 1 = 30031 = 59 × 509처럼 합성수인 경우도 있다. 증명이 요구하는 것은 $N$이 소수라는 것이 아니라 목록 밖의 소수가 반드시 존재한다는 것뿐이다.

귀류법 대우법 차이, 그리고 수학적 귀납법과의 차이

귀류법 대우법 차이는 무엇을 가정하고 무엇에 도착하느냐에 있다. 대우법은 '$p$이면 $q$'와 '$q$가 아니면 $p$가 아니다'의 참·거짓이 같다는 성질을 이용해, $\lnot q$만 가정하고 $\lnot p$라는 정해진 목적지에 직접 도착하는 증명이다. 귀류법은 $p$와 $\lnot q$를 함께 가정하고, 목적지가 정해져 있지 않다. $\lnot p$가 나와도 되고 $p$와 무관한 다른 모순이 나와도 된다. 그래서 대우법은 귀류법의 특수한 경우로 볼 수 있고, 모순의 종류가 자유로운 만큼 귀류법이 더 넓게 쓰인다.

예를 들어 '$n^2$이 짝수이면 $n$은 짝수이다'는 대우인 '$n$이 홀수이면 $n^2$은 홀수이다'를 직접 계산으로 보이는 편이 깔끔하다. 반면 '$\sqrt{2}$는 무리수이다'는 조건 $p$가 따로 없는 명제라 대우를 만들 수 없고 귀류법만 가능하다. 수학적 귀납법은 이 둘과 아예 성격이 다르다. 귀납법은 자연수 $n$에 대한 명제를 $n=1$에서 확인하고 $n=k$에서 $n=k+1$로 넘어가는 사다리를 세우는 직접 증명이며, 모순을 끌어내는 단계가 없다.

직접 증명

가정 $p$에서 출발해 결론 $q$까지 곧장 간다. 계산·대입·정리 적용이 주된 도구.

대우법

$\lnot q$에서 출발해 $\lnot p$에 도착한다. 목적지가 정해져 있는 간접 증명.

귀류법

$p$와 $\lnot q$를 함께 가정하고 어떤 모순이든 끌어낸다. 목적지가 자유로운 간접 증명.

수학적 귀납법

$n=1$ 확인과 $k \to k+1$ 단계로 모든 자연수를 덮는다. 모순이 등장하지 않는 직접 증명.

귀류법은 수학 밖에서도 매일 쓰인다. 스도쿠에서 어떤 칸에 5를 넣어 보고 몇 칸 뒤에 같은 줄에 5가 두 번 나오면 그 칸은 5가 아니라고 확정하는 것, 알리바이로 무죄를 보이는 것, 컴퓨터 프로그램이 종료된다는 성질을 증명하는 것 모두 결론의 부정에서 모순을 찾는 같은 구조다. 나는 고등학교 때 루트2 증명을 처음 외웠을 때 '왜 굳이 유리수라고 가정하지'라는 의문이 풀리지 않았는데, 대학에서 논리학을 배우며 배중률이 그 가정을 정당화한다는 것을 알고 나서야 증명을 외우는 대신 이해하게 됐다. 귀류법 문제를 풀 때 첫 줄에 '~라고 가정하자'를 쓰고 마지막 줄에 '이는 모순이다'를 쓰는 습관만 들여도 서술형 답안의 절반은 완성된다.

함께 읽으면 좋은 글

수학적 귀납법 뜻과 증명 방법, 예시로 완벽 정리 유클리드 호제법 원리와 증명, 최소공배수까지 정리 생존자 편향이란? 뜻과 예시, 오류를 피하는 법

참고 자료

Euclid's Elements, Book IX, Proposition 20 — 소수의 무한성 증명 원문(클라크대 D. Joyce 편) 위키백과 — 귀류법(歸謬法) 항목 국가교육과정정보센터 — 고등학교 수학 '집합과 명제' 단원 성취기준