이산수학 증명법 쉽게 이해하기: 직접증명과 귀납법 기준

• 증명 문제가 어렵게 느껴지는 이유
• 조건과 결론을 먼저 나누어야 한다
• 직접증명은 정의를 식으로 바꾸는 연습이다
• 대우증명은 방향을 바꿔 더 쉬운 문장으로 푸는 방식이다
• 귀납법은 자연수 문제가 다음 단계로 이어질 때 쓴다
• 반례는 모든 경우를 주장하는 문장을 확인할 때 필요하다
• 증명법을 고를 때 확인할 기준

증명 문제가 어렵게 느껴지는 이유

이산수학에서 증명을 처음 만나면 계산 문제와 느낌이 다릅니다. 계산 문제는 식을 정리하다 보면 답이 나오지만, 증명 문제는 첫 문장을 어떻게 시작해야 할지부터 막히는 경우가 많습니다. 그래서 증명법 이름을 외워도 실제 문제 앞에서는 손이 잘 안 움직입니다.

처음부터 모든 증명법을 같은 무게로 외우려고 하면 더 헷갈립니다. 직접증명, 대우증명, 모순증명, 귀납법, 반례증명, 존재증명 같은 말이 한꺼번에 나오면 각각의 쓰임보다 이름이 먼저 남습니다. 하지만 실제로 문제를 풀 때는 이름을 먼저 고르는 것이 아니라, 문장이 어떤 구조인지 먼저 읽어야 합니다.

예를 들어 “정수 n에 대하여 n이 짝수이면 n²도 짝수이다”라는 문장을 보면, 바로 n²을 계산하려고 하기 쉽습니다. 그런데 증명에서는 계산보다 먼저 해야 할 일이 있습니다. 무엇을 가정하고, 무엇을 보여야 하는지 분리하는 일입니다.

이 기준이 잡히면 증명법이 조금 덜 낯설어집니다. 직접증명은 조건에서 결론으로 바로 가는 방식이고, 대우증명은 같은 뜻의 다른 방향으로 바꿔 푸는 방식입니다. 귀납법은 자연수 단계가 이어질 때 쓰고, 반례는 “모든 경우”라는 주장을 깨야 할 때 확인합니다. 이름을 먼저 외우기보다 이런 사용 상황을 먼저 구분하는 쪽이 처음 공부할 때 덜 흔들립니다.

조건과 결론을 먼저 나누어야 한다

증명 문제를 읽을 때 가장 먼저 볼 부분은 조건과 결론입니다. 조건은 출발점이고, 결론은 도착점입니다. 증명은 출발점에서 도착점까지 논리적으로 이어 가는 글입니다. 이 구조를 잡지 못하면 어떤 증명법을 써야 하는지도 흐려집니다.

조건명제는 보통 “만약 P이면 Q이다” 형태로 읽을 수 있습니다. 여기서 P는 가정할 내용이고, Q는 보여야 할 내용입니다. 수학 문장은 일상 문장보다 압축되어 있으므로, 문제를 보자마자 식을 쓰기보다 먼저 문장을 잘라 보는 과정이 필요합니다.

문장을 먼저 나누어 보기

명제
정수 n에 대하여 n이 짝수이면 n²도 짝수이다.

조건
n이 짝수이다.

결론
n²도 짝수이다.

처음 할 일
조건에 있는 “짝수”라는 말을 수학식으로 바꾼다.

여기서 바로 중요한 지점이 나옵니다. 증명에서 “짝수”라는 말은 느낌으로 처리하지 않습니다. 짝수는 2로 나누어떨어지는 정수이고, 수식으로는 n = 2k라고 쓸 수 있습니다. 여기서 k는 어떤 정수입니다.

처음에는 이 부분이 낯설 수 있습니다. “n이 짝수라면 그냥 짝수라고 하면 되지 왜 n = 2k라고 쓰지?”라는 생각이 들 수 있습니다. 하지만 증명에서는 말로 된 조건을 계산 가능한 형태로 바꿔야 다음 줄을 이어 갈 수 있습니다. 정의를 꺼내는 이유가 여기에 있습니다.

문제를 풀기 전에 조건과 결론을 한 줄씩 분리해 두면 증명 방향도 더 선명해집니다. 조건에 있는 단어는 출발 재료이고, 결론에 있는 단어는 만들어야 할 모양입니다. 짝수를 증명해야 한다면 마지막에는 2 × 정수 꼴이 나와야 하고, 홀수를 증명해야 한다면 2 × 정수 + 1 꼴이 나와야 합니다.

직접증명은 정의를 식으로 바꾸는 연습이다

직접증명은 조건에서 출발해서 결론까지 바로 이어 가는 방식입니다. 증명 문제를 봤을 때 특별한 이유가 없다면 직접증명을 먼저 떠올리는 것이 자연스럽습니다. 조건을 식으로 바꾸었을 때 결론이 비교적 가까이 보이면 직접증명으로 풀 가능성이 큽니다.

직접증명을 어렵게 만드는 지점은 대부분 계산 자체가 아닙니다. 조건을 정의로 바꾸는 첫 단계가 익숙하지 않아서 막힙니다. 짝수, 홀수, 배수, 약수, 유리수 같은 표현은 증명 안에서 거의 항상 수식으로 다시 써야 합니다.

짝수의 제곱이 짝수임을 보이는 흐름

증명할 명제
정수 n에 대하여 n이 짝수이면 n²도 짝수이다.

1. n이 짝수라고 가정한다.
2. 짝수의 정의에 의해 n = 2k인 정수 k가 존재한다.
3. 양변을 제곱하면 n² = (2k)²이다.
4. n² = 4k² = 2(2k²)이다.
5. 2k²는 정수이므로 n²은 2 × 정수 꼴이다.
6. 따라서 n²도 짝수이다.

이 증명에서 핵심은 마지막 계산보다 두 번째 줄입니다. n이 짝수라는 조건을 n = 2k로 바꾸었기 때문에 이후 계산이 가능해집니다. 만약 이 변환을 하지 않으면 “짝수니까 제곱해도 짝수다”라는 말만 반복하게 됩니다. 그 말은 직관으로는 맞아 보여도 증명문으로는 부족합니다.

직접증명은 새로운 기교를 쓰는 방법이 아닙니다. 주어진 조건을 정의로 바꾸고, 이미 알고 있는 성질을 이용해 결론의 형태까지 끌고 갑니다. 그래서 증명 입문에서는 직접증명을 먼저 연습하는 흐름이 필요합니다. 다른 증명법도 결국 이 기본 흐름을 바탕으로 이해됩니다.

문제를 풀다가 막혔다면 계산을 더 복잡하게 만들기 전에 정의를 제대로 꺼냈는지 확인해야 합니다. “짝수”, “홀수”, “배수”, “약수”, “유리수” 같은 표현을 그대로 둔 채로 다음 줄을 쓰려 하면 증명이 흐려지는 경우가 많습니다.

대우증명은 방향을 바꿔 더 쉬운 문장으로 푸는 방식이다

모든 조건명제가 직접증명으로 쉽게 풀리지는 않습니다. 조건에서 출발했는데 결론이 잘 보이지 않는 문제가 있습니다. 이때 억지로 같은 방향으로 밀고 가기보다, 명제를 대우로 바꿔 보면 길이 짧아질 수 있습니다.

대우는 “P이면 Q이다”라는 명제를 “Q가 아니면 P가 아니다”로 바꾼 문장입니다. 원래 명제와 대우명제는 참과 거짓이 항상 같이 움직입니다. 그래서 대우명제를 증명하면 원래 명제를 증명한 것으로 볼 수 있습니다.

직접보다 대우가 더 편한 예시

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

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

대우증명 흐름
1. n이 홀수라고 가정한다.
2. 홀수의 정의에 의해 n = 2k + 1인 정수 k가 존재한다.
3. n² = (2k + 1)²이다.
4. n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1이다.
5. 따라서 n²은 홀수이다.
6. 대우명제가 참이므로 원래 명제도 참이다.

원래 명제는 n²이 짝수라는 조건에서 n이 짝수라는 결론을 끌어내야 합니다. 처음 공부할 때는 이 방향이 다소 어색하게 느껴질 수 있습니다. 반면 대우명제로 바꾸면 n이 홀수라는 조건에서 출발합니다. 홀수는 n = 2k + 1로 바로 표현할 수 있으므로 계산 흐름이 더 자연스럽습니다.

대우증명은 직접증명과 완전히 다른 방식이 아닙니다. 명제를 같은 의미의 다른 문장으로 바꾼 다음, 그 문장을 직접증명하는 구조에 가깝습니다. 그래서 “직접증명이 막히면 대우를 생각한다” 정도로 출발해도 충분합니다.

모순증명도 간접증명에 속하지만, 입문 단계에서는 대우증명과 섞어서 외우면 더 헷갈릴 수 있습니다. 우선은 조건명제에서 대우를 만들 수 있는지 확인하고, 대우로 바꿨을 때 정의를 바로 꺼낼 수 있는지 보는 식으로 연습하는 편이 부담이 적습니다.

귀납법은 자연수 문제가 다음 단계로 이어질 때 쓴다

수학적 귀납법은 자연수 n 전체에 대한 명제를 증명할 때 자주 사용합니다. 단, 문제에 n이 나온다고 해서 무조건 귀납법을 쓰는 것은 아닙니다. n에서 n + 1로 이어지는 구조가 보일 때 귀납법이 잘 맞습니다.

귀납법은 사다리로 생각하면 이해하기 쉽습니다. 첫 번째 칸에 올라갈 수 있고, 어떤 칸에 올라가 있으면 다음 칸으로도 갈 수 있다면 결국 모든 칸을 올라갈 수 있습니다. 여기서 첫 번째 칸을 확인하는 것이 기본단계이고, 다음 칸으로 이어지는지를 확인하는 것이 귀납단계입니다.

1부터 n까지의 합 공식으로 보는 귀납법

증명할 명제
1 + 2 + 3 + ... + n = n(n + 1) / 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 = k + 1일 때도 성립한다.

귀납법에서 자주 헷갈리는 부분은 귀납가정입니다. 귀납가정은 “아무 근거 없이 k일 때 참이라고 우기는 말”이 아닙니다. k일 때 성립한다고 했을 때, 그 사실을 이용해서 k + 1일 때도 성립하는지 확인하는 장치입니다.

위 예시에서 귀납가정은 1 + 2 + … + k 부분을 k(k + 1) / 2로 바꾸는 데 사용됩니다. 즉 귀납가정은 증명문 안에 실제로 들어가야 합니다. 귀납가정을 써 놓고 이후 계산에 한 번도 사용하지 않는다면, 귀납법의 핵심 연결이 빠진 것입니다.

귀납법을 쓸지 고민될 때는 “이 명제가 k에서 k + 1로 넘어가는 구조를 갖고 있는가”를 먼저 보면 됩니다. 합 공식, 수열, 점화식, 자연수에 대한 나눗셈 성질처럼 이전 단계가 다음 단계 계산에 들어가는 문제라면 귀납법을 의심해 볼 만합니다.

반례는 모든 경우를 주장하는 문장을 확인할 때 필요하다

증명은 참을 보이는 일만 의미하지 않습니다. 어떤 명제가 거짓임을 보여야 할 때도 있습니다. 특히 “모든”이라는 말이 들어간 명제는 반례 하나로 깨질 수 있습니다.

예를 들어 “모든 소수는 홀수이다”라는 문장을 생각해 볼 수 있습니다. 대부분의 소수는 3, 5, 7, 11처럼 홀수라서 맞는 말처럼 보입니다. 하지만 2는 소수이면서 짝수입니다. 이 하나의 예 때문에 “모든 소수는 홀수이다”라는 명제는 거짓입니다.

반례를 찾을 때 확인할 문장

반례가 잘 맞는 경우
- 모든 A는 B이다.
- 임의의 x에 대해 어떤 성질이 항상 성립한다.
- 어떤 규칙이 예외 없이 참이라고 주장한다.

반례의 역할
조건은 만족하지만 결론은 만족하지 않는 예를 하나 찾는다.

반례는 아무 예시나 드는 것이 아닙니다. 조건은 만족해야 하고, 결론은 깨야 합니다. “모든 A는 B이다”를 반박하려면 A에 속하지만 B는 아닌 대상을 찾아야 합니다. 이 기준을 놓치면 예시는 들었지만 반례가 아닌 경우가 생깁니다.

반대로 “어떤 A가 존재한다”는 형태의 문장에서는 예시 하나가 명제를 참으로 만들 수도 있습니다. 그래서 문제를 읽을 때 “모든”인지 “존재”인지 구분해야 합니다. 이번 글에서는 증명 입문에 맞춰 반례를 중심으로 보지만, 이 구분은 뒤에서 존재증명을 공부할 때도 그대로 이어집니다.

증명법을 고를 때 확인할 기준

증명법은 이름을 많이 외운다고 바로 잘 골라지지 않습니다. 문제의 문장 구조를 읽고, 어떤 도구가 자연스러운지 판단해야 합니다. 처음에는 거창한 기준보다 몇 가지 신호를 확인하는 방식으로 접근하는 것이 현실적입니다.

문장에서 보이는 신호	먼저 생각할 방법
조건에서 결론까지 바로 이어질 것 같다	직접증명
결론을 바로 보이기 어렵고, 반대로 생각하면 쉬워 보인다	대우증명
자연수 n 전체에 대해 단계적으로 이어지는 주장이다	수학적 귀납법
모든 경우에 대해 참이라고 주장한다	반례 확인

처음 증명을 공부할 때는 모든 문제를 한 번에 능숙하게 풀려고 하기보다, 문장을 나누는 연습부터 해야 합니다. 조건이 무엇인지, 결론이 무엇인지, 조건 안에 정의로 바꿀 수 있는 표현이 있는지 확인합니다. 그다음 직접증명을 먼저 시도하고, 길이 잘 보이지 않을 때 대우나 귀납법을 생각하면 됩니다.

증명은 계산 실력만으로 해결되는 단원이 아닙니다. 문장을 읽고, 정의로 바꾸고, 그 정의를 이용해 다음 줄을 이어 가는 연습이 필요합니다. 직접증명, 대우증명, 귀납법, 반례는 각각 따로 외울 이름이라기보다 문제의 구조에 따라 꺼내 쓰는 도구입니다. 처음에는 이 네 가지 기준만 잡아도 증명 문제를 읽는 부담이 줄어듭니다.