• 증명이란 무엇인가
• 가장 먼저 익혀야 할 직접증명법
• 수학적 귀납법은 왜 통하는가
• 직접이 어려울 때 쓰는 간접증명법
• 다양한 증명방법 한 번에 정리하기
• 정리
• FAQ

증명이란 무엇인가

증명은 어떤 명제가 참이라는 사실을 감으로 받아들이는 것이 아니라, 공리와 정의, 이미 알려진 사실을 바탕으로 논리적으로 확인하는 과정입니다. 그래서 증명 단원에서는 계산을 빨리 하는 것보다 문장을 어떻게 출발시키고, 어떤 근거로 다음 줄을 이어 가는지가 더 중요합니다. 저는 이 지점에서 먼저 공리, 정의, 정리, 증명의 역할을 구분해 두는 것이 필요하다고 봅니다.

공리는 별도의 증명 없이 출발점으로 받아들이는 명제이고, 정의는 용어의 뜻을 분명하게 정해 주는 약속입니다. 정리는 이런 공리와 정의, 그리고 이미 증명된 사실을 이용해서 참임이 확인된 명제입니다. 결국 증명은 정리를 만들어 내는 과정이라고 볼 수 있습니다. 이 구조를 이해하고 나면 왜 증명에서 정의를 꺼내는 일이 중요한지도 자연스럽게 보입니다.

증명을 시작할 때 가장 먼저 확인할 것

1. 내가 증명하려는 문장이 모든 경우에 대한 주장인가
2. 어떤 조건이 주어졌을 때 결론이 따라오는 형태인가
3. 거짓임을 보이는 반례 하나로 끝나는 문장인가
4. 자연수 전체에 대한 규칙이라서 귀납법이 필요한가

증명 문제를 보면 바로 식을 만지기보다, 먼저 문장의 형태를 읽어야 합니다. 모든 정수에 대해 참인지, 조건명제인지, 존재를 묻는지, 자연수 전체에 대한 규칙인지에 따라 선택해야 하는 증명법이 달라지기 때문입니다.

초급자일수록 이 분류를 건너뛰고 곧바로 풀이를 시작하는 경우가 많습니다. 하지만 증명은 문제를 푸는 기술이면서 동시에 문제를 읽는 기술이기도 합니다. 어떤 구조의 문장인지 먼저 파악해야 적절한 증명법을 선택할 수 있습니다.

가장 먼저 익혀야 할 직접증명법

직접증명법은 가장 기본적인 증명 방식입니다. 조건명제라면 가정을 먼저 받아들이고, 그 가정에서 정의와 성질을 차근차근 꺼내 결론까지 밀고 가는 방식입니다. 증명 입문에서 가장 먼저 익혀야 하는 이유는, 다른 많은 증명법도 결국 직접증명의 흐름을 변형한 형태이기 때문입니다.

직접증명은 어떻게 시작하는가

명제: 모든 정수 n에 대하여 n이 짝수이면 n^2도 짝수이다.
(ex. 짝수 14의 제곱은 짝수 144, 짝수 16의 제곱은 짝수 256)

증명 흐름
n을 임의의 정수라고 둔다.
n이 짝수라고 가정한다.
그러면 n = 2k인 정수 k가 존재한다.
따라서 n^2 = (2k)^2 = 4k^2 = 2(2k^2)이다.
2k^2는 정수이므로 n^2는 짝수이다.

이 예시는 직접증명의 가장 전형적인 형태입니다. 핵심은 짝수라는 말을 그냥 느낌으로 쓰지 않고, 반드시 n = 2k라는 정의로 바꾸는 데 있습니다. 증명에서 막힐 때는 계산 실력보다 정의를 꺼내지 못한 경우가 더 많습니다.

즉, 직접증명은 새로운 기교를 쓰는 것이 아니라 주어진 가정을 식으로 번역하는 훈련입니다. 짝수, 홀수, 배수, 유리수 같은 표현은 거의 항상 정의로 내려와야 합니다. 저는 초심자가 직접증명을 어려워하는 가장 큰 이유가 바로 이 변환 습관이 아직 익숙하지 않기 때문이라고 봅니다.

직접증명은 언제 잘 맞는가

직접증명이 잘 맞는 경우
- 가정에서 출발해 결론을 자연스럽게 만들 수 있을 때
- 짝수, 홀수, 배수, 약수, 유리수처럼 정의를 바로 꺼낼 수 있을 때
- 조건명제 P -> Q에서 P를 이용하면 Q가 비교적 가까이 있을 때

직접증명은 가장 단순해 보이지만, 오히려 증명의 기본 체력을 만드는 방식입니다. 문제를 풀다 보면 직접이 잘 되는 문제와 잘 안 되는 문제가 분명히 나뉘는데, 그 차이를 체감하는 것이 다음 단계로 넘어가는 출발점이 됩니다.

수학적 귀납법은 왜 통하는가

수학적 귀납법은 자연수 전체에 대해 성립하는 명제를 증명할 때 사용하는 대표적인 방법입니다. 한 개 한 개를 모두 확인하는 것이 아니라, 첫 번째가 맞고 다음 단계로 계속 이어진다는 사실을 보이면 전체가 성립한다고 판단하는 구조입니다. 초급자에게는 낯설 수 있지만, 구조만 익히면 오히려 매우 기계적으로 적용할 수 있는 증명법입니다.

기본단계, 귀납가정, 귀납단계

명제: 1 + 2 + 3 + ... + n = n(n+1) / 2
(ex. 1부터 10까지 모두 더한 값 = 10 * 11 / 2)

기본단계
n = 1일 때
왼쪽 = 1, 오른쪽 = 1(1+1) / 2 = 1
성립한다.

귀납가정
n = k일 때
1 + 2 + 3 + ... + k = k(k+1) / 2 라고 가정한다.

귀납단계
n = k+1일 때
1 + 2 + 3 + ... + k + (k+1)
= k(k+1) / 2 + (k+1)
= (k+1)(k+2) / 2
따라서 성립한다.

귀납법에서 가장 중요한 것은 귀납가정을 단순한 결론이 아니라 다음 단계 계산에 실제로 끼워 넣는 도구로 보는 것입니다. 많은 학습자가 여기서 막히는 이유는, 귀납가정을 써야 한다는 사실은 알지만 어디에 대입해야 하는지 감이 없기 때문입니다.

저는 귀납법을 사다리처럼 이해하는 편이 가장 쉽다고 봅니다. 첫 칸에 올라설 수 있다는 것이 기본단계이고, 어떤 칸에 올라서 있으면 다음 칸으로도 갈 수 있다는 것이 귀납단계입니다. 그러면 첫 칸에서 시작해 모든 칸으로 이어질 수 있으므로 자연수 전체에 대해 성립한다고 보는 것입니다.

귀납법은 언제 떠올려야 하는가

귀납법을 먼저 떠올릴 신호
- n에 대한 합 공식이 나온다
- 자연수 n 전체에 대한 명제다
- 수열, 점화식, 나눗셈 성질이 단계적으로 반복된다
- n에서 n+1로 넘어가는 구조가 보인다

문제에 자연수 n이 나오기만 한다고 무조건 귀납법을 쓰는 것은 아닙니다. 하지만 명제가 단계적으로 이어지는 구조를 갖고 있다면 귀납법이 매우 강력합니다. 특히 합 공식, 부등식, 나눗셈 관련 명제, 재귀적 구조에서는 귀납법이 자주 등장합니다.

직접이 어려울 때 쓰는 간접증명법

모든 명제가 직접증명으로 잘 풀리지는 않습니다. 어떤 문제는 가정에서 바로 결론으로 가는 길이 너무 멀어서 막히고, 오히려 반대 방향이나 모순을 이용하면 훨씬 자연스럽게 풀립니다. 이럴 때 쓰는 것이 간접증명법입니다. 대표적으로 대우증명법과 모순증명법이 있습니다.

대우증명법은 왜 유용한가

원래 명제
정수 n에 대하여 n^2가 짝수이면 n도 짝수이다.

대우명제
정수 n에 대하여 n이 홀수이면 n^2도 홀수이다.

증명 흐름
n이 홀수라고 가정한다.
그러면 n = 2k+1 이다.
따라서 n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1
그러므로 n^2도 홀수이다.

원래 명제는 직접 가려면 조금 어색하지만, 대우명제로 바꾸면 훨씬 익숙한 계산이 됩니다. 대우명제는 원래 명제와 논리적으로 같은 진리값을 가지기 때문에, 대우를 증명하면 원래 명제도 증명한 것이 됩니다.

즉, 대우증명법은 어려운 명제를 더 쉬운 형태로 바꾸는 전략입니다. 직접증명으로 막혔을 때는 무작정 버티기보다, 결론의 부정을 가정해서 출발하는 편이 더 짧게 풀릴 수 있습니다.

모순증명법은 어떻게 쓰는가

모순증명 기본 틀
증명하려는 명제가 거짓이라고 가정한다.
그 가정으로부터 동시에 참일 수 없는 결과를 만든다.
따라서 처음 가정이 잘못되었음을 보인다.
결론적으로 원래 명제가 참이다.

모순증명법은 명제를 부정한 뒤 출발해서, 그 결과가 말이 되지 않음을 보여주는 방식입니다. 예를 들어 어떤 정수 해가 존재하지 않는다는 명제, 혹은 어떤 수가 무리수라는 명제는 모순증명으로 자연스럽게 접근되는 경우가 많습니다.

다만 초급자에게는 대우증명과 모순증명이 비슷하게 느껴질 수 있습니다. 차이는 대우증명은 보통 원래 조건명제를 아예 동치인 다른 형태로 바꿔 직접 증명하는 것이고, 모순증명은 명제의 부정을 가정한 뒤 불가능한 상황까지 끌고 가는 방식이라는 점입니다. 즉 대우증명은 조건명제의 구조를 바꿔 더 쉬운 직접증명으로 들어가는 느낌이고, 모순증명은 끝까지 갔을 때 말이 되지 않음을 보여 주는 방식이라고 이해하면 구분이 쉬워집니다.

다양한 증명방법 한 번에 정리하기

증명 단원에서는 직접증명, 귀납법, 간접증명만 배우는 것이 아닙니다. 문제에 따라 반례증명법, 존재증명법, 전수증명법, 조합적 증명법도 함께 등장합니다. 이 방법들은 자주 쓰이는 상황이 비교적 분명하기 때문에, 각각의 역할을 짧고 선명하게 구분해 두는 것이 좋습니다.

반례증명법과 존재증명법

반례증명법
모든 경우에 대해 참이라고 한 명제에서
단 한 개의 예가 명제를 깨면 전체 명제는 거짓이다.

존재증명법
어떤 대상을 만족하는 예가 하나라도 있음을 보이면
존재 명제는 참이 된다.

반례증명법은 보편명제를 무너뜨릴 때 매우 강력합니다. 모든 수에 대해 참이라고 했는데 단 하나의 예외가 발견되면 그 명제는 더 이상 참일 수 없습니다. 반대로 존재증명법은 예를 하나만 찾아도 충분한 구조를 갖습니다. 존재를 보일 때는 직접 예를 만드는 구성적 존재증명과, 예를 직접 만들지 않고 존재만 보이는 비구성적 존재증명으로 나눌 수 있습니다.

전수증명법과 조합적 증명법

전수증명법
경우의 수가 많지 않을 때 모든 경우를 직접 확인한다.

조합적 증명법
같은 대상을 두 방식으로 세거나
두 집합 사이의 일대일 대응을 만들어 식이 같음을 보인다.

전수증명법은 경우의 수가 작을 때만 현실적으로 사용할 수 있습니다. 모든 경우를 빠짐없이 확인해야 하므로, 경우가 적은 문제에서는 오히려 가장 명확한 방법이 되기도 합니다. 여기서 중요한 점은 몇 개의 예만 확인하는 것은 전수증명법이 아니라는 사실입니다. 가능한 경우를 전부 확인해야만 전수증명법이라고 할 수 있습니다. 조합적 증명법은 개수를 세는 문제에서 특히 강력합니다. 대표적으로는 두 집합 사이에 일대일 대응을 만드는 전단증명과, 같은 대상을 서로 다른 기준으로 두 번 세는 중복산정증명이 있습니다. 같은 집합을 두 방식으로 세면 서로 다른 식이 사실은 같은 값을 나타낸다는 점을 증명할 수 있습니다.

이 단계에서 중요한 것은 각 증명법의 멋진 이름을 외우는 것이 아닙니다. 저는 문제를 읽고 나서 이 명제가 보편명제인지, 존재명제인지, 경우가 유한한지, 자연수 단계 구조를 갖는지부터 판단하는 습관이 훨씬 더 중요하다고 생각합니다.

정리

증명은 계산 문제처럼 하나의 공식으로 밀어붙이는 영역이 아닙니다. 대신 문장의 구조를 읽고, 그 구조에 맞는 도구를 고르는 과정에 가깝습니다. 직접증명은 가정에서 결론으로 곧장 가는 기본 도구이고, 수학적 귀납법은 자연수 전체에 대한 반복 구조를 다룰 때 적합합니다. 대우증명법과 모순증명법은 직접이 막힐 때 문제를 더 쉬운 방향으로 바꾸는 전략입니다.

반례증명법, 존재증명법, 전수증명법, 조합적 증명법까지 함께 정리해 두면 증명 단원을 훨씬 입체적으로 볼 수 있습니다. 결국 중요한 것은 각 방법의 정의를 외우는 것이 아니라, 어떤 문제에서 어떤 방식이 자연스러운지를 반복해서 익히는 것입니다. 저는 증명 단원을 공부할 때 항상 먼저 문장의 형태를 읽고, 그 다음에 증명법을 고르는 순서로 접근하는 것이 가장 안정적이라고 봅니다.

많이 받는 질문

Q. 직접증명과 대우증명 중 무엇을 먼저 시도하는 것이 좋나요?
보통은 직접증명을 먼저 떠올리는 편이 좋습니다. 가정에서 정의를 꺼내 결론까지 자연스럽게 이어지면 가장 간단하기 때문입니다. 다만 결론이 잘 안 나오고, 결론의 부정을 가정하면 더 쉬운 식이 보인다면 대우증명으로 전환하는 것이 효율적입니다.

Q. 수학적 귀납법에서 귀납가정은 왜 마음대로 해도 되는 건가요?
귀납가정은 아무 근거 없이 참이라고 우기는 것이 아닙니다. 어떤 자연수 k에서 성립한다고 가정했을 때, 그 가정이 참이라면 k+1에서도 참임을 보여 주는 장치입니다. 즉 귀납가정 자체를 결론으로 쓰는 것이 아니라, 다음 단계로 넘어가는 연결을 만드는 데 사용하는 것입니다.

Q. 반례 하나만으로 정말 전체 명제를 깨뜨릴 수 있나요?
보편명제라면 가능합니다. 예를 들어 모든 정수 n에 대해 어떤 성질이 참이라고 주장했는데, 단 하나의 정수에서 그 성질이 거짓이면 그 명제는 더 이상 모든 경우에 대해 참일 수 없습니다. 그래서 보편명제를 부정할 때 반례는 매우 강력한 도구입니다.