1. 4대 증명 전략 한눈에 보기
증명해야 할 명제가 "p → q" 형태일 때, 이를 증명하는 4가지 전략은 다음과 같다.
| 직접 증명 | Direct Proof | p 가정 | q 도출 | 가장 기본, p에서 q로 흐름이 보일 때 |
| 대우 증명 | Contraposition | ¬q 가정 | ¬p 도출 | 직접이 막히고 ¬q가 다루기 쉬울 때 |
| 모순 증명 | Contradiction | ¬p 가정 | 모순 도출 | 부정이 더 다루기 쉬울 때 (귀류법) |
| 경우별 증명 | Cases | p를 여러 경우로 분할 | 각 경우마다 q 증명 | 가정이 여러 시나리오로 갈릴 때 |
💡 어떤 전략이 정답인지는 정해져 있지 않다. 문제의 구조에 따라 가장 효율적인 전략을 선택하는 것이 핵심이다.
2. 사전 준비 — 짝수와 홀수의 정의
증명 예제 대부분이 짝수·홀수 정리이므로, 정의를 명확히 잡고 시작한다.
| 짝수(Even) | n = 2k (k는 정수) |
| 홀수(Odd) | n = 2k + 1 (k는 정수) |
이 정의는 증명에서 공리처럼 활용된다. 모든 짝수·홀수 증명은 이 정의를 출발점으로 한다.
3. ① 직접 증명 (Direct Proof) — 가장 정석
정의
가정 p가 참이라고 전제하고, 논리적 추론을 통해 결론 q가 참임을 직접 보이는 증명 전략.
길찾기 비유
출발점(p) ────────→ 도착점(q)
직진!우회나 복잡한 가정 없이, 오직 논리적인 흐름만으로 p에서 q로 직진한다.
3단계 풀이 패턴
| 1 | 가정 p가 참이라고 전제 |
| 2 | 정의·공리·이미 증명된 정리·추론 규칙 적용 |
| 3 | 논리적 단계를 거쳐 q가 참임을 도출 |
직접 증명 예제 ⭐
정리: "n이 홀수이면, n²도 홀수이다."
| 1. 가정 도입 | n이 홀수라고 가정. 즉 n = 2k + 1 (k는 정수) |
| 2. n² 전개 | n² = (2k + 1)² = 4k² + 4k + 1 |
| 3. 홀수 형태 변환 | n² = 2(2k² + 2k) + 1 |
| 4. 결론 도출 | 2k² + 2k는 정수이므로 2(정수) + 1 형태 → n²은 홀수 ✅ |
💡 직접 증명의 미학: "p이므로 q이다"라는 흐름이 한눈에 보인다. 가장 명확하고 직관적인 증명 방식.
4. ② 대우 증명 (Contraposition) — 역발상 우회
정의
명제 "p → q"를 직접 증명하기 어려울 때, 그 대우인 "¬q → ¬p"를 증명함으로써 원래 명제가 참임을 보이는 전략.
동치 관계
p → q ≡ ¬q → ¬p
3강에서 배운 함축의 동치 관계가 직접 적용된다. 두 명제는 논리적으로 완전히 같으므로, 어느 쪽을 증명해도 OK다.
비유
"비가 오면 땅이 젖는다"를 증명하기 어려울 때, "땅이 젖지 않았다면 비가 오지 않은 것이다"를 증명한다.
4단계 풀이 패턴
| 1 | 원래 명제 p → q의 대우 ¬q → ¬p 작성 |
| 2 | ¬q를 가정 (결론의 부정) |
| 3 | 논리적 추론으로 ¬p 도출 (가정의 부정) |
| 4 | 대우가 참 → 원래 명제도 참 |
대우 증명 예제 ⭐
정리: "3n + 2가 홀수이면, n은 홀수이다."
직접 증명을 시도하면 "3n + 2 = 2k + 1에서 n이 홀수임을 도출" → 어렵다. 대우로 가자.
대우 명제: "n이 짝수이면, 3n + 2는 짝수이다."
| 1. ¬q 가정 | n이 짝수라고 가정. 즉 n = 2k (k는 정수) |
| 2. 3n + 2 전개 | 3n + 2 = 3(2k) + 2 = 6k + 2 |
| 3. 짝수 형태 변환 | 3n + 2 = 2(3k + 1) |
| 4. ¬p 도출 | 3k + 1은 정수이므로 2(정수) 형태 → 3n + 2는 짝수 ✅ |
| 5. 결론 | 대우가 참이므로 원래 명제도 참 |
💡 대우 증명을 선택하는 기준: 결론의 부정 ¬q가 가정의 부정 ¬p보다 수식으로 다루기 쉬울 때 효과적이다. 이번 예제에서 "n이 짝수"는 "3n+2가 홀수"보다 식 전개가 훨씬 깔끔하다.
5. ③ 모순 증명 (Proof by Contradiction) — 귀류법 ⭐⭐⭐
정의
증명하려는 명제 p의 부정 ¬p가 참이라고 가정한 뒤, 논리적으로 모순(Contradiction)이 발생함을 보여 ¬p가 거짓임을 증명하고, 따라서 p가 참임을 입증하는 전략.
별명
"판 엎기 전략" 또는 "귀류법(歸謬法)"
시간여행 비유
"내가 시간 여행을 가서 부모님 만남을 방해한다면, 나는 존재할 수 없다" — 자기모순으로 가정이 틀렸음을 증명.
5단계 풀이 패턴
| 1 | p가 거짓이라 가정 (¬p 참이라 가정) |
| 2 | ¬p를 전제로 논리적 추론 진행 |
| 3 | 항상 거짓인 명제(F) 또는 모순(R ∧ ¬R) 도출 |
| 4 | 모순 발생 → ¬p는 거짓 |
| 5 | ¬p가 거짓이므로 p는 참 ✅ |
모순 증명 예제 ⭐
정리: "n이 정수일 때, 2n은 짝수이다."
이건 너무 자명해서 직접 증명이 더 쉽지만, 모순 증명의 흐름을 익히기 위한 예제다.
| 1. 억지 가정 (¬p) | 2n이 홀수라고 가정 |
| 2. 수식화 | 2n = 2k + 1 (k는 정수) |
| 3. k에 대해 정리 | k = (2n − 1) / 2 = n − 1/2 |
| 4. 모순 발견 | n은 정수인데 n − 1/2는 정수가 아님 → "k는 정수"라는 가정과 충돌 ❌ |
| 5. 결론 | 모순 발생 → 2n이 홀수라는 가정은 거짓 → 2n은 짝수 ✅ |
모순 증명의 진짜 위력 — 무리수 증명
모순 증명이 정말 빛나는 순간은 직접 증명이 불가능한 명제들이다.
고전 정리: "√2는 무리수이다."
직접 증명("√2가 무리수임을 직접 보여라")은 불가능하다. 하지만 모순 증명을 사용하면:
- √2가 유리수라고 가정
- √2 = a/b (a, b는 서로소 정수)로 표현 가능
- 양변 제곱: 2 = a²/b² → a² = 2b² → a²은 짝수 → a도 짝수
- a = 2c라 두면 4c² = 2b² → b² = 2c² → b도 짝수
- a, b 둘 다 짝수 → 서로소가 아님 → 처음 가정과 모순 ❌
- 따라서 √2는 무리수 ✅
💡 모순 증명을 선택하는 기준: ① 직접·대우 증명이 막힐 때 ② "어떤 것이 존재하지 않음"을 증명할 때 ③ 무리수·소수 등 부정형 증명일 때 강력하다.
6. ④ 경우별 증명 (Proof by Cases) — 분할 정복
정의
가정 p가 여러 상호 배타적인 경우(p₁ ∨ p₂ ∨ ... ∨ pₙ)로 나뉠 수 있을 때, 각 경우마다 결론 q가 참임을 개별적으로 증명하여 전체 명제가 참임을 보이는 전략.
분할 정복 비유
큰 적군을 한 번에 상대하지 말고, 잘게 쪼개서 각각 격파하라.
핵심 원리
(p₁ ∨ p₂ ∨ ... ∨ pₙ) → q ≡ (p₁ → q) ∧ (p₂ → q) ∧ ... ∧ (pₙ → q)
가정의 모든 가능성을 망라(Exhaustive)하고 서로 겹치지 않게(Mutually Exclusive) 분할한 뒤, 각 경우를 개별 증명한다.
4단계 풀이 패턴
| 1 | 가정 p를 모든 가능한 경우로 분할 (빠짐없이) |
| 2 | 각 경우가 서로 겹치지 않는지 확인 |
| 3 | 각 경우 pᵢ에 대해 pᵢ → q 개별 증명 |
| 4 | 모든 경우에서 q 도출 → 전체 명제 참 |
경우별 증명 예제 ⭐
정리: "실수 x, y에 대해 |xy| = |x| · |y| 이다."
x와 y의 부호에 따라 4가지 경우로 분할한다.
경우 1: x ≥ 0이고 y ≥ 0
| |xy| = xy | |x| · |y| = x · y = xy |
→ 좌변 = 우변 ✅
경우 2: x < 0이고 y ≥ 0
| |xy| = −(xy) | |x| · |y| = (−x) · y = −xy |
→ 좌변 = 우변 ✅
경우 3: x ≥ 0이고 y < 0
| |xy| = −(xy) | |x| · |y| = x · (−y) = −xy |
→ 좌변 = 우변 ✅
경우 4: x < 0이고 y < 0
| |xy| = xy | |x| · |y| = (−x) · (−y) = xy |
→ 좌변 = 우변 ✅
결론: 모든 가능한 경우에서 |xy| = |x| · |y| 성립 → 정리 증명 완료 ✅
경우별 증명의 2대 주의사항
| 빠짐없이 (Exhaustive) | 모든 가능한 경우를 다 다뤄야 함. 하나라도 빠지면 증명 무효 |
| 겹치지 않게 (Mutually Exclusive) | 각 경우가 명확히 분리되어야 함 |
💡 경우별 증명을 선택하는 기준: 절댓값, 짝수/홀수, 양수/음수/0 등 자연스러운 분기가 있는 문제에서 유용하다. 분할이 명확하지 않으면 다른 전략을 고려하자.
7. 4대 전략 선택 가이드 ⭐ 시험 만점 비결
문제를 보고 어떤 전략을 선택할지 빠르게 판단하는 의사결정 흐름이다.
| p에서 q로 흐름이 자연스럽게 보임 | 직접 증명 |
| 직접 증명이 막힘, ¬q가 ¬p보다 다루기 쉬움 | 대우 증명 |
| "존재하지 않는다", "무리수다" 같은 부정형 명제 | 모순 증명 |
| 직접·대우 모두 막힘, 가정의 부정이 단순 | 모순 증명 |
| 가정에 양수/음수, 짝수/홀수, 0 등 분기 존재 | 경우별 증명 |
의사결정 순서
1. 직접 증명 시도 → 흐름이 보이면 GO
↓ 막히면
2. ¬q와 ¬p 비교 → ¬q가 다루기 쉬우면 대우 증명
↓ 둘 다 어려우면
3. 모순 증명 시도 → ¬p에서 모순 찾기
↓ 가정이 분기되면
4. 경우별 증명으로 전환💡 시험 팁: 처음부터 무조건 직접 증명을 시도하지 말고, 5초간 명제 형태를 분석한 뒤 가장 효율적인 전략을 고르자. 부정형 명제(~가 아니다, ~가 존재하지 않는다)는 거의 모순 증명이 정답이다.
8. 4대 전략 비교표
| 직접 증명 | p | q | — | 가장 명확, 직관적 |
| 대우 증명 | ¬q | ¬p | p→q ≡ ¬q→¬p | 우회로, 식 전개 단순화 |
| 모순 증명 | ¬p | F (모순) | ¬¬p ≡ p | 부정형 명제에 강력 |
| 경우별 증명 | p₁∨p₂∨... | 각 pᵢ → q | (p₁∨p₂)→q ≡ (p₁→q)∧(p₂→q) | 분기 명확한 문제 |
📌 한눈에 보는 핵심정리
| 직접 증명 | p 가정 → 정의·정리 적용 → q 도출 |
| 대우 증명 | ¬q 가정 → ¬p 도출, p→q ≡ ¬q→¬p |
| 모순 증명 | ¬p 가정 → 모순 도출 → p 참 (귀류법) |
| 경우별 증명 | 가정을 분할 → 각 경우마다 q 증명 |
| 짝수 정의 | n = 2k (k는 정수) |
| 홀수 정의 | n = 2k + 1 (k는 정수) |
| 전략 선택 | 부정형 → 모순, 분기형 → 경우별, 식 어려움 → 대우, 기본 → 직접 |
| 모순 증명 위력 | √2 무리수 증명 등 직접 불가능한 정리에 필수 |
| 경우별 주의점 | 빠짐없이 + 겹치지 않게 |
🧠 예상문제 2제
문제 1. 증명 전략 식별
다음 정리를 증명할 때 가장 효율적인 증명 전략은?
정리: "√3은 무리수이다."
① 직접 증명 (Direct Proof) ② 대우 증명 (Contraposition) ③ 모순 증명 (Proof by Contradiction) ④ 경우별 증명 (Proof by Cases)
👉 정답: ③
"√3은 무리수이다" = "√3은 유리수가 아니다" — 부정형 명제다.
부정형 명제는 직접 증명으로 접근하면 막힌다. "√3을 직접 무리수로 표현"하는 것은 불가능하기 때문. 대신 모순 증명으로:
- √3이 유리수라고 가정 (¬p)
- √3 = a/b로 표현 (a, b는 서로소)
- 양변 제곱 후 식 전개
- a, b가 둘 다 3의 배수임이 도출 → 서로소 가정과 모순 ❌
- 따라서 √3은 무리수 ✅
💡 시험 빈출 패턴: "~는 무리수이다", "~는 존재하지 않는다", "~는 끝이 없다" 같은 부정형·무한형 명제는 거의 100% 모순 증명이 정답이다.
문제 2. 대우 증명 단계 풀이
다음 정리를 대우 증명으로 풀 때, 2단계에 도출할 수식으로 옳은 것은?
정리: "n²이 짝수이면, n도 짝수이다."
[대우 명제 작성] n이 홀수이면, n²도 홀수이다.
[1단계] n이 홀수라고 가정. 즉 n = 2k + 1 (k는 정수)
[2단계] n² = ?
[3단계] n²을 2(정수) + 1 형태로 변형
[4단계] n²은 홀수임이 증명됨 → 원래 명제 참① n² = 4k² + 4k + 1 ② n² = 4k² + 1 ③ n² = 2k² + 2k + 1 ④ n² = (2k)² + 1
👉 정답: ①
n = 2k + 1을 제곱하면:
n² = (2k + 1)²
= (2k)² + 2 · (2k) · 1 + 1²
= 4k² + 4k + 1이를 3단계에서 다음과 같이 변형하면 홀수 형태가 된다:
n² = 4k² + 4k + 1 = 2(2k² + 2k) + 12k² + 2k는 정수이므로 2(정수) + 1 형태 → n²은 홀수 ✅
따라서 대우가 참 → 원래 명제 "n²이 짝수이면 n도 짝수" 도 참.
💡 추가 학습: 이 정리는 √2의 무리수 증명에서 핵심 보조정리로 사용된다. "n²이 짝수 → n도 짝수"라는 사실이 √2 증명 과정의 핵심 단계이기 때문이다. 이렇게 한 정리가 다른 정리의 증명 도구로 쓰이는 것이 8강에서 배운 보조정리(Lemma) 의 역할이다.
'📌 SW전공-개념 > 이산구조' 카테고리의 다른 글
| [이산구조 개념-11] 추론 엔진과 패러다임 변화 — 전문가 시스템에서 딥러닝까지 (0) | 2026.06.03 |
|---|---|
| [이산구조 개념-10] 존재 증명과 유일성 증명 — "있다"와 "오직 하나"의 수학 (0) | 2026.06.02 |
| [이산구조 개념-08] 한정자 추론 규칙 — UI·EI와 증명의 언어 (0) | 2026.05.31 |
| [이산구조 개념-07] 형식적 증명 — 추론 규칙으로 결론 만들기 (1) | 2026.05.30 |
| [이산구조 개념-06] 추론 규칙 7선 — 논리적 추론의 도구함 (0) | 2026.05.29 |