수학적 증명의 방법

대수 고등 · 교육과정: 직접증명·대우·귀류법·수학적 귀납법 — 명제가 참임을 보이는 네 가지 표준 절차. · v1 · 🤖 LLM 버전

이 개념은 직접증명·대우증명법·귀류법·수학적 귀납법이라는 네 가지 표준 절차로 어떤 명제가 참임을 논리적으로 보이는 방법을 다룬다.

정의

명제 $p \to q$($p$이면 $q$이다라고 읽는다)가 참임을 보이는 대표적인 방법은 다음 네 가지다.

1. 직접증명법: $p$가 참이라고 가정하고, 이미 알려진 정의·공리·정리를 순서대로 적용하여 $q$가 참임을 이끌어낸다.
2. 대우증명법: $p \to q$의 대우 $\neg q \to \neg p$($\neg q$는 낫 큐, $q$가 아니다라고 읽는다)를 대신 증명한다. 원래 명제와 대우는 항상 논리적으로 동치이므로, 대우를 증명하면 원래 명제도 증명된 것이다.
3. 귀류법(모순에 의한 증명): 결론을 부정한 $\neg q$가 참이라고 가정한 뒤, 논리를 전개하여 모순(참인 동시에 거짓인 문장)을 이끌어낸다. 가정이 모순을 낳으므로 그 가정은 거짓이고, 따라서 $q$가 참이다.
4. 수학적 귀납법: 자연수 $n$에 대한 명제 $p(n)$이 모든 자연수 $n$에 대해 성립함을 보일 때 쓴다. (i) $p(1)$이 참임을 보이고, (ii) $p(k)$가 참이라고 가정했을 때 $p(k+1)$도 참임을 보이면, 모든 자연수 $n$에 대해 $p(n)$이 참이다.

직관

대우증명법은 "$A$이면 $B$이다"를 곧장 보이기 어려울 때 문장을 뒤집어 "$B$가 아니면 $A$가 아니다"를 보이는 우회로다. 귀류법은 탐정이 용의자를 특정할 때 "만약 범인이 아니라면"이라고 가정했다가 알리바이와 모순되는 증거가 나오면 그 가정을 폐기하는 방식과 같다. 수학적 귀납법은 도미노를 세워 놓은 것과 같다 — 첫 번째 도미노가 넘어지고(기초 단계), 어떤 도미노가 넘어지면 반드시 다음 도미노도 넘어진다는 것(귀납 단계)을 보이면, 결국 모든 도미노가 넘어진다.

유도

이미 아는 것은 명제 $p \to q$의 참·거짓 정의뿐이다. 그런데 어떤 명제는 $p$에서 $q$로 곧장 논리를 전개하기가 매우 까다롭다. 예를 들어 "$n^2$이 짝수이면 $n$은 짝수이다"를 직접증명하려면 "$n^2$이 짝수다"라는 조건에서 $n$ 자체의 성질을 곧바로 뽑아내야 하는데, 이는 거꾸로 가는 셈이라 다루기 어렵다.

이때 대우 $\neg q \to \neg p$가 원래 명제와 논리적으로 같은 값을 가진다는 사실을 진리표로 확인할 수 있다.

네 경우 모두 $p\to q$와 $\neg q\to\neg p$의 참·거짓이 정확히 일치한다. 즉 둘은 동치이므로, $p\to q$가 막히면 $\neg q\to\neg p$를 증명해도 된다 — 이것이 대우증명법의 근거다. 위 예시라면 "$n$이 홀수이면 $n^2$이 홀수이다"를 보이면 되는데, $n=2m+1$로 두면 $n^2=4m^2+4m+1=2(2m^2+2m)+1$이 되어 훨씬 쉽게 풀린다.

귀류법은 여기서 한 걸음 더 간다. 명제 논리에서는 하나의 명제 $q$가 참이거나 거짓이거나 둘 중 하나이며 동시에 둘 다일 수 없다(배중률). 그러므로 $\neg q$를 참이라 가정했을 때 이미 참으로 알려진 사실과 모순되는 결과 $r \wedge \neg r$($r$이고 $r$이 아니다)이 나온다면, $\neg q$는 거짓일 수밖에 없고 따라서 $q$가 참이다.

수학적 귀납법이 (i)·(ii) 두 단계로 이루어지는 이유도 같은 논리다. (i)로 $p(1)$이 참임을 확보하고, (ii)로 "$p(k)$ 참 $\to$ $p(k+1)$ 참"이라는 사슬을 확보하면, $p(1)$ 참 $\to$ $p(2)$ 참 $\to$ $p(3)$ 참 $\to \cdots$ 이 끝없이 이어져 모든 자연수에 대해 성립함이 보장된다. 자세한 논리적 근거는 수학적 귀납법 문서에서 다룬다.

예시

직접증명법: "두 홀수의 합은 짝수이다." 홀수를 $2m+1$, $2n+1$($m, n$은 정수)로 두면 합은 $2m+1+2n+1 = 2(m+n+1)$이 되어 짝수이다.

대우증명법: "$n^2$이 짝수이면 $n$은 짝수이다." 대우 "$n$이 홀수이면 $n^2$이 홀수이다"를 증명한다. $n=2k+1$이면 $n^2 = 4k^2+4k+1 = 2(2k^2+2k)+1$이므로 홀수다. 대우가 참이므로 원래 명제도 참이다.

귀류법: "$\sqrt{2}$는 무리수이다." $\sqrt{2}$가 유리수라고 가정하면 $\sqrt{2} = \dfrac{p}{q}$($p,q$는 서로소인 자연수)로 쓸 수 있다. 양변을 제곱하면 $2q^2 = p^2$이므로 $p^2$은 짝수, 따라서 $p$도 짝수다. $p=2r$로 두면 $2q^2 = 4r^2$, 즉 $q^2 = 2r^2$이 되어 $q$도 짝수다. 그런데 $p, q$가 모두 짝수면 서로소라는 가정과 모순이다. 따라서 $\sqrt{2}$는 무리수다.

수학적 귀납법: "$1+2+\cdots+n = \dfrac{n(n+1)}{2}$." (i) $n=1$일 때 좌변 $=1$, 우변 $=\dfrac{1\cdot2}{2}=1$로 성립. (ii) $n=k$일 때 성립한다고 가정하면 $1+\cdots+k+(k+1) = \dfrac{k(k+1)}{2}+(k+1) = \dfrac{(k+1)(k+2)}{2}$가 되어 $n=k+1$일 때도 성립. 따라서 모든 자연수 $n$에 대해 성립한다.

🌍 실생활 예시

컴퓨터 과학에서 재귀 알고리즘이나 반복문(loop)이 항상 올바른 결과를 낸다는 것을 증명할 때 수학적 귀납법과 똑같은 구조(기초 단계 + 귀납 단계)를 쓴다. 예를 들어 "이 정렬 알고리즘은 길이 $n$인 배열을 항상 올바르게 정렬한다"를 보일 때, 길이 1인 배열(기초)에서 시작해 길이 $k$까지 성립한다는 가정 아래 길이 $k+1$에서도 성립함을 보이는 방식으로 프로그램의 정확성을 증명한다.

⚠️ 흔한 실수

• 역과 대우를 혼동한다: $p\to q$를 증명한다면서 실제로는 역 $q\to p$를 증명하는 경우가 많다. 역은 원래 명제와 동치가 아니므로 증명이 되지 않는다 — 반드시 대우 $\neg q\to\neg p$를 증명해야 한다.
• 귀류법에서 모순을 구체적으로 짚지 않는다: "가정하면 이상해진다" 정도로 얼버무리면 증명이 아니다. $\sqrt{2}$ 예시처럼 "$p,q$가 서로소인데 둘 다 짝수다"처럼 실제로 충돌하는 두 문장을 명시해야 한다.
• 수학적 귀납법에서 귀납 가정을 안 쓴다: $n=k+1$일 때를 $n=k$일 때 참이라는 가정 없이 처음부터 새로 증명해버리면 귀납법이 아니라 개별 확인일 뿐이다. 반드시 $p(k)$가 참이라는 가정을 식 전개에 실제로 사용해야 한다.

확인 문제

1. "$n$이 자연수일 때 $n^2$이 3의 배수이면 $n$도 3의 배수이다"를 먼저 직접증명으로 시도해 보고 왜 막히는지 설명한 뒤, 대우를 이용해 증명하라.
2. $\sqrt{3}$이 무리수임을 귀류법으로 증명하라.
3. 수학적 귀납법으로 $1^2+2^2+\cdots+n^2 = \dfrac{n(n+1)(2n+1)}{6}$이 모든 자연수 $n$에 대해 성립함을 증명하라.

📜 역사

증명이라는 형식을 체계화한 것은 고대 그리스 수학이다. 유클리드의 『원론』(기원전 300년경)에는 소수가 무한히 많다는 것을 귀류법으로 증명한 내용(제9권)이 실려 있으며, $\sqrt{2}$가 무리수라는 사실도 고대 그리스 수학 전통에서 귀류법으로 증명되었다고 알려져 있다. 수학적 귀납법의 사고방식은 오래전부터 부분적으로 쓰였지만, 17세기 프랑스의 파스칼이 파스칼의 삼각형을 다루면서 오늘날과 비슷한 형태로 명확히 사용한 것으로 알려져 있다. "수학적 귀납법(mathematical induction)"이라는 용어는 이후 19세기에 정착되었다.

관련 개념

• 명제 — 참·거짓을 판별할 수 있는 문장, 증명이 다루는 대상
• 수학적 귀납법 — 네 방법 중 자연수에 대한 명제를 다루는 방법의 상세 문서
• 제곱근과 무리수 — 귀류법의 대표 예시인 $\sqrt{2}$의 무리수 증명과 연결
• 집합 — 명제와 조건을 다루는 논리 전개의 기초