논리추론 Ch7: 귀류법과 수학적 귀납법 — 증명의 두 가지 강력한 무기

어떤 명제를 증명하기 어렵다면, 때로는 반대 방향에서 접근하는 것이 훨씬 효과적입니다. 귀류법(歸謬法)은 “이것이 거짓이라고 가정하면 모순이 생긴다, 따라서 참이다”라는 논리적 역전이고, 수학적 귀납법은 무한한 경우를 유한한 단계로 증명하는 우아한 방법입니다. 두 기법 모두 직접 증명이 어려운 상황에서 빛을 발합니다.

귀류법 (Proof by Contradiction)

고전적 예제: √2는 무리수이다

정리: √2는 무리수이다 (분수로 표현될 수 없다)

귀류법 증명:

① √2가 유리수라고 가정하자. 즉, 서로소인 정수 a, b에 대해:

$\sqrt{2} = \frac{a}{b} \quad (a, b \text{는 서로소, } b \neq 0)$

② 양변을 제곱하면:

$2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$

③ a²이 짝수이면 a도 짝수이다 (홀수의 제곱은 홀수이므로).

a = 2k라 쓰면:

$(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$

④ b²이 짝수이면 b도 짝수이다.

⑤ 모순: a도 짝수, b도 짝수 → 두 수가 공약수 2를 가짐. 그런데 a, b는 서로소라고 가정했다. 모순!

⑥ 결론: 가정(√2가 유리수)이 거짓. 따라서 √2는 무리수이다. ■

예제 2: 소수는 무한히 많다 (유클리드)

귀류법:

① 소수가 유한하다고 가정: p₁, p₂, …, pₙ이 소수의 전부

② N = (p₁ × p₂ × … × pₙ) + 1을 구성

③ N을 p₁, p₂, …, pₙ 중 어느 것으로도 나누면 나머지가 1 → 어느 소수로도 나누어지지 않음

④ 모든 자연수 > 1은 소수 또는 소수의 곱인데, N은 기존 소수 목록의 어떤 소수로도 나누어지지 않음 → N 자체가 새 소수이거나 새 소수 인수를 포함

⑤ 모순: p₁, …, pₙ이 모든 소수라는 가정에 위배

⑥ 결론: 소수는 무한히 많다. ■

논리 추론에서의 귀류법

시험에서는 수학보다 논리 퍼즐 형태로 자주 출제됩니다:

예: “A가 범인이 아니라면 B와 C 모두 알리바이가 있어야 한다. 그런데 B에게는 알리바이가 없다. 따라서 A가 범인이다.”

구조:

¬A → (B ∧ C)
¬B (B의 알리바이 없음)
∴ A (대우: ¬B → A)

이것도 귀류법의 응용 — “A가 아니다”라고 가정하면 B와 C 모두 알리바이가 있어야 하는데 B가 없으므로 모순. 따라서 A가 범인.

수학적 귀납법 (Mathematical Induction)

원리

수학적 귀납법은 자연수에 대한 명제를 무한히 증명하는 방법입니다.

목표: 모든 자연수 n에 대해 P(n)이 성립함을 증명

[단계 1 — 기저(Base Case)]: P(1)이 성립함을 보인다
[단계 2 — 귀납(Inductive Step)]: P(k)가 성립한다고 가정할 때,
                                  P(k+1)도 성립함을 보인다
결론: 모든 자연수 n에 대해 P(n)이 성립한다

비유: 도미노

기저: 첫 번째 도미노가 넘어진다
귀납: k번째 도미노가 넘어지면 (k+1)번째도 넘어진다
결론: 모든 도미노가 넘어진다

예제: 1 + 2 + 3 + … + n = n(n+1)/2

정리: 모든 자연수 n에 대해 $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

증명:

[기저 단계] n = 1:

좌변: 1
우변: 1×2/2 = 1 ✓

[귀납 단계] P(k): $1 + 2 + ... + k = \frac{k(k+1)}{2}$ 가 성립한다고 가정하자.

P(k+1)을 보여야 한다: $1 + 2 + ... + k + (k+1) = \frac{(k+1)(k+2)}{2}$

좌변 = $\frac{k(k+1)}{2} + (k+1)$ [귀납 가정 사용]

$= (k+1)\left(\frac{k}{2} + 1\right)$

$= (k+1) \cdot \frac{k+2}{2}$

$= \frac{(k+1)(k+2)}{2}$ = 우변 ✓

결론: 수학적 귀납법에 의해 모든 자연수 n에 대해 성립한다. ■

예제 2: 2ⁿ > n (n ≥ 1)

[기저] n = 1: 2¹ = 2 > 1 ✓

[귀납] 2ᵏ > k가 성립한다고 가정.

$2^{k+1} = 2 \cdot 2^k > 2k = k + k \geq k + 1 \quad (k \geq 1이므로 k \geq 1)$

따라서 $2^{k+1} > k+1$ ✓

결론: 모든 n ≥ 1에서 성립. ■

귀류법 vs 수학적 귀납법 vs 직접증명

방법	언제 사용	구조
직접증명	P가 참임을 순방향으로 보일 수 있을 때	P → Q 직접 유도
귀류법	”P가 거짓”이라고 가정하면 모순이 쉽게 보일 때	¬P → ⊥
대우 증명	대우(¬Q → ¬P)가 직접증명보다 쉬울 때	¬Q → ¬P
수학적 귀납법	자연수 n에 대한 무한한 경우를 증명할 때	P(1) + P(k)→P(k+1)

귀류법 vs 대우 증명:

대우: “Q가 아니면 P가 아니다”를 직접 증명 — 순방향
귀류법: “P이고 Q가 아니다”라고 가정 → 모순 → P이면 Q이다 — 간접적

쓰임이 비슷하지만 구조가 다릅니다. 시험에서 두 방법을 혼동하지 마세요.

실전 문제

문제 1 (귀류법)

다음을 귀류법으로 증명하라. “n²이 짝수이면 n도 짝수이다.”

증명:

n²이 짝수이지만 n이 홀수라고 가정하자.

n이 홀수이면 n = 2m+1로 쓸 수 있다.

n² = (2m+1)² = 4m² + 4m + 1 = 2(2m² + 2m) + 1 → 홀수

그런데 n²이 짝수라고 가정했다. 모순.

따라서 n도 짝수이다. ■

문제 2 (수학적 귀납법)

다음을 수학적 귀납법으로 증명하라. 모든 자연수 n에 대해 $1 + 3 + 5 + ... + (2n-1) = n^2$

[기저] n = 1: 좌변 = 1, 우변 = 1² = 1 ✓

[귀납] $1 + 3 + ... + (2k-1) = k^2$ 이라 가정.

좌변(k+1 항까지) = $k^2 + (2(k+1)-1) = k^2 + 2k + 1 = (k+1)^2$ = 우변 ✓

결론: 모든 n에서 성립. ■

문제 3 (논리 퀴즈에서의 귀류법)

A, B, C 세 명 중 한 명이 거짓말쟁이다. A: “나는 정직하다” B: “A가 거짓말쟁이다” C: “B가 거짓말쟁이다”

거짓말쟁이는 누구인가?

귀류법 적용:

경우 1: A가 거짓말쟁이라고 가정

A는 거짓말 → A의 말 “나는 정직하다”는 거짓 → 맞음 (일관성 OK)
B의 말 “A가 거짓말쟁이다”는 참 → B는 정직 (일관성 OK)
C의 말 “B가 거짓말쟁이다”는 거짓 → C는 거짓말쟁이

모순: 거짓말쟁이가 A와 C 두 명이 됨 → 가정 기각

경우 2: B가 거짓말쟁이라고 가정

B의 말 “A가 거짓말쟁이다”는 거짓 → A는 정직
A의 말 “나는 정직하다”는 참 → A는 정직 (일관성 OK)
C의 말 “B가 거짓말쟁이다”는 참 → C는 정직 (일관성 OK)

모순 없음 → B가 거짓말쟁이

정답: B

자주 하는 실수

귀류법에서

실수: 가정과 결론을 혼동 — “¬P를 가정”했는데 증명 중에 P를 사용하는 순환 오류

올바른 체크: 가정(¬P)에서 출발하여 모순에 이르는 논리 흐름이 끊기지 않는지 확인

수학적 귀납법에서

실수: 귀납 단계에서 P(k+1)을 직접 증명하려 함 → P(k)를 반드시 사용해야 귀납의 의미가 있음

실수 2: 기저 단계 생략 — n=1뿐 아니라 때로 n=0이나 n=2에서 시작할 수 있으므로 문제에서 확인

핵심 요약

귀류법:    ¬P → ⊥ → P
           "반대를 가정하면 모순 → 원래 명제 참"

수학적 귀납법:
  기저: P(1) 성립 확인
  귀납: P(k) → P(k+1) 증명
  결론: 모든 자연수 n에 대해 P(n) 성립

둘의 차이:
  귀류법 = 간접증명 (모순 유도)
  귀납법 = 도미노 증명 (무한 확장)

수학적 귀납법은 도미노처럼 생각하면 결코 어렵지 않습니다. 첫 조각이 넘어지고(기저), 하나가 넘어지면 다음도 넘어진다(귀납)는 두 가지만 보이면 — 무한히 많은 경우를 단 두 단계로 증명한 것입니다. 귀류법은 직접 가기 어려운 길을 우회하는 지혜입니다. 반대로 가면 막힌다는 것을 보여줌으로써, 원래 길이 맞다는 것을 증명합니다. 다음 편(Ch8)에서는 실전 논리 문제 전략 — 귀류·전건 확정·연쇄추론 통합 적용을 다룹니다.

Oiyo