Lesson 6 of 20

증명 — 우겨서 이기는 게 아니라 길을 놓는 일

직접증명 · 대우증명 · 귀류법 · 반례

"짝수 두 개를 더하면 짝수다." 여러분은 이게 참이라는 걸 압니다. 그런데 왜 참인가요? 2 + 4 = 6, 10 + 8 = 18… 백 개를 확인해도 증명이 아닙니다. 101번째에서 깨지지 않는다고 누가 보장하죠?

증명(proof)은 이미 참이라고 인정된 것에서 출발해, 규칙을 어기지 않는 걸음으로 목표까지 가는 길입니다. 길이 한 번 놓이면 모든 경우에 대해 끝납니다 — 무한히 많아도요.

이산수학에서 쓰는 길은 네 가지면 충분합니다.

방법	언제 쓰나	하는 일
직접증명	대부분	p 라고 치고, 계산해서 q 에 도착
대우증명	가정이 다루기 어려울 때	¬q 라고 치고 ¬p 에 도착 (3강의 대우)
귀류법	"없다 / 무한하다"를 보일 때	거짓이라고 치고 모순을 끌어냄
반례	∀ 명제를 깨뜨릴 때	어기는 예 하나를 제시

High school우겨서 이기는 게 아니라 길을 놓는 일

부제가 증명의 성격을 잘 말합니다.

증명 = 이미 참인 것에서 새로운 참으로 가는 길

왜 증명이 필요한가

확인 방법	보장
몇 개 해 본다	그것들만 ⚠
증명	전부 ✔

5강의 ∀ 를 확인하는 유일한 방법이다

네 가지 방법

방법	언제 쓰나
직접증명	가정에서 바로 갈 수 있을 때
대우증명	결론의 부정이 다루기 쉬울 때
귀류법	"없다" · "무리수다" 같은 부정 명제
반례	명제가 거짓임을 보일 때

도구가 넷이니 안 되면 다른 것을 시도한다

비유 — 산 정상 가는 길

길	—
정면 등산로	직접증명
뒷길	대우증명 — 같은 정상, 다른 길
"저기로는 못 간다"	귀류법

정상은 하나인데 길은 여럿이다 — 쉬운 길을 고른다

컴퓨터의 완전 탐색은 유한한 범위만 확인합니다.

Python Runs in your browser

# 확인은 증명이 아니지만, 감을 잡는 데는 좋습니다
짝수들 = [n for n in range(0, 21) if n % 2 == 0]
반례 = [(a, b) for a in 짝수들 for b in 짝수들 if (a + b) % 2 != 0]

print("0~20 짝수 쌍", len(짝수들) ** 2, "개를 모두 확인했습니다.")
print("반례:", 반례 if 반례 else "없음")
print()
print("하지만 21 이상은요? 100만은요? → 그래서 '증명'이 필요합니다.")

직접증명 — 정의를 펼쳐 쓰기

주장 : a와 b가 짝수이면 a + b도 짝수이다.

증명. 짝수의 정의는 "2로 나누어떨어지는 수", 즉 어떤 정수 k에 대해 a = 2k 로 쓸 수 있다는 뜻이다.

가정에 의해 a = 2k, b = 2m 인 정수 k, m이 있다.
그러면 a + b = 2k + 2m = 2(k + m) 이다.
k + m은 정수이므로 a + b는 2 × (정수) 꼴이다. 따라서 a + b는 짝수이다. ∎

대부분의 직접증명은 이렇게 정의를 문자로 펼쳐 쓰고, 정리해서, 다시 정의로 접는 모양입니다.

High school대우증명 — 뒤집어서 가기

3강에서 대우는 원명제와 같다고 했죠. 그 사실을 도구로 씁니다.

P → Q 를 증명하는 대신 ¬Q → ¬P 를 증명한다

언제 유리한가

상황	—
P 에서 시작하기 어렵다	대우를 본다
¬Q 가 구체적이다	대우가 쉽다 ✔

예 — "n² 이 짝수면 n 도 짝수"

방향	다루기
직접: n² 이 짝수 → ?	n 에 대해 말하기 어렵다
대우: n 이 홀수 → n² 이 홀수	계산하면 된다 ✔

n = 2k+1 이면 n² = 4k²+4k+1 = 2(2k²+2k)+1 — 홀수입니다.

"짝수" 는 2k 로 쓸 수 있지만 "짝수가 아님" 은 다루기 어렵다

왜 방향에 따라 난이도가 다른가

표현	다루기
있다 형태 (n=2k)	쉽다 — 대입한다
없다 형태	어렵다 — 무엇을 대입하나

가정을 구체적인 식으로 쓸 수 있는 쪽이 유리하다

비유 — 알리바이

증명할 것	방법
"내가 범인이 아니다"	어렵다 — 안 한 일은 못 보인다
"그 시간에 다른 곳에 있었다"	쉽다 — 증거가 있다 ✔

같은 결론인데 보이기 쉬운 쪽을 고른 것 — 그게 대우다

대우증명 — 뒤에서 접근하기

주장 : n²이 짝수이면 n도 짝수이다.

직접 하려면 "n²이 짝수다"에서 시작해야 하는데, 제곱근을 다루기가 성가십니다. 대우를 보면 훨씬 쉬워요 — "n이 홀수이면 n²도 홀수이다".

증명(대우). n이 홀수라 하자. 그러면 n = 2k + 1.
n² = (2k+1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1 — 2 × (정수) + 1 꼴, 즉 홀수이다.
대우가 참이므로 원래 명제도 참이다. ∎

대우가 참이면 원래도 참 — 3강에서 배운 그대로입니다.

Python Runs in your browser

# 대우증명의 계산을 눈으로 확인
for k in range(6):
    n = 2 * k + 1                 # 홀수
    print(f"n={n:<3} n²={n*n:<4} = 2×{(n*n - 1)//2} + 1  → 홀수")
print()
print("홀수의 제곱은 언제나 홀수 → 대우가 참 → 원래 명제도 참")

High school√2 는 분수가 아니다 — 귀류법의 걸작

note 가 든 이 증명은 2500년 된 것입니다.

귀류법 — 아니라고 가정했더니 모순이 나온다

증명의 흐름

단계	내용
1	√2 = a/b 라고 가정 (기약분수)
2	양변 제곱 → 2b² = a²
3	a² 이 짝수 → a 도 짝수 (대우증명!)
4	a = 2k 대입 → b² = 2k² → b 도 짝수
5	a, b 가 둘 다 짝수 — 기약이 아니다 ⚠
6	모순 → 가정이 틀렸다

3단계에서 앞에서 증명한 것을 쓴다 — 증명이 쌓인다

왜 걸작인가

이유	설명
짧다	여섯 줄
도구가 적다	짝수·홀수만
결론이 크다	무리수의 존재를 증명했다

"모든 수는 분수로 쓸 수 있다" 는 믿음을 무너뜨렸다

피타고라스 학파에게 충격이었습니다. 전설에 따르면 이걸 밝힌 사람이 바다에 던져졌다고 해요.

귀류법의 논리

단계	근거
¬P 를 가정	—
모순 도출	¬P 는 거짓이다
따라서 P	1강의 배중률 ⭐

"참 아니면 거짓" 이라는 1강의 약속이 여기서 쓰인다

비유 — 수사에서의 소거법

"이 사람이 범인이라면" 가정하고 따라갔더니 알리바이와 충돌합니다.

따라서 범인이 아니다 — 직접 증명하지 않고도 안다

귀류법 — 아니라고 치고 모순을 끌어내기

보이고 싶은 것을 부정한 뒤, 그 가정에서 말이 안 되는 결론을 끌어내는 방법입니다. 말이 안 되는 결론이 나왔으니 출발점이 틀린 것이고, 따라서 원래 명제가 참이라는 거예요.

"~인 것은 없다", "~은 무한히 많다" 처럼 직접 구성하기 어려운 주장에 특히 강합니다.

목록이 유한하다고 치면 언제나 목록 밖의 소수가 만들어집니다.

Python Runs in your browser

# 소수가 무한히 많다는 유클리드의 귀류법을 흉내 내 봅니다
def 소수인가(n):
    if n < 2: return False
    d = 2
    while d * d <= n:
        if n % d == 0: return False
        d += 1
    return True

소수들 = [2, 3, 5, 7, 11]
곱하기_더하기_1 = 1
for p in 소수들:
    곱하기_더하기_1 *= p
곱하기_더하기_1 += 1

print("소수가", 소수들, "뿐이라고 치면")
print("모두 곱하고 1을 더한 수:", 곱하기_더하기_1)
print("이 수는 목록의 어떤 소수로도 나눠지지 않습니다:",
      [곱하기_더하기_1 % p for p in 소수들])
print("소수인가?", 소수인가(곱하기_더하기_1), "→ 목록에 없는 새 소수! 모순입니다.")

High school반례는 하나면 충분하지만

note 의 이 대비가 5강의 비대칭을 잇습니다.

목적	필요한 것
거짓임을 보인다	반례 하나 ✔
참임을 보인다	증명 — 예시는 안 된다 ⚠

예시를 백만 개 들어도 증명이 아니다

유명한 반례 이야기

"n² + n + 41 은 항상 소수다"

n	값	소수?
0	41	✔
1	43	✔
…	…	✔
39	1601	✔
40	1681 = 41²	✗ ⚠

40번 맞았는데 41번째에서 깨진다

더 극단적인 예도 있습니다

어떤 명제는 수천조 번까지 맞다가 깨집니다.

교훈	—
컴퓨터로 많이 확인했다	증명이 아니다

1강의 테스트 vs 증명 이야기가 여기서 되풀이된다

그래서 프로그래밍에서도

방법	보장
테스트 100개 통과	그 100개 ⚠
형식 검증	모든 입력 ✔

항공기·의료기기 소프트웨어는 증명을 요구하기도 한다

반례를 찾는 요령

먼저 볼 곳	—
0 · 1 · 음수	경계값
빈 것	빈 집합 · 빈 리스트
아주 큰 값	—

반례는 대개 극단에 있다 — 코드 버그도 마찬가지다

예시 40개는 증명이 아닙니다.

Python Runs in your browser

# 40번 맞고 41번째에 깨지는 유명한 반례
def 소수인가(n):
    if n < 2: return False
    d = 2
    while d * d <= n:
        if n % d == 0: return False
        d += 1
    return True

for n in range(0, 43):
    값 = n * n + n + 41
    if not 소수인가(값):
        print(f"반례 발견! n={n} → {값} = {41}×{값 // 41}  (소수가 아님)")
        break
    if n < 3 or n > 38:
        print(f"n={n:<3} → {값:<6} 소수 ✓")

🤔 Check yourself

"n이 홀수이면 n²도 홀수이다"를 증명해서 "n²이 짝수이면 n도 짝수이다"를 얻는 방법은?

Answer ¬q → ¬p 를 증명해 p → q 를 얻었으니 대우증명입니다. 3강에서 본 대로 원래 명제와 대우는 언제나 운명을 같이하므로, 다루기 쉬운 쪽을 골라 증명하면 됩니다.

🤔 Check yourself

"모든 홀수는 소수이다"가 거짓임을 보이는 가장 짧은 방법은?

🤔 Check yourself

귀류법의 뼈대를 바르게 말한 것은?