23주차 — 기법 선택 훈련: 같은 명제, 세 가지 증명

이 주의 길잡이

핵심 문장: 기법은 취향이 아니라 신호가 정한다 — 신호는 가정과 결론의 모양에 있다.

이 주의 위치: 50주 과정의 23주차. 직접(15~18주차)\(\cdot\)대우(19주차)\(\cdot\)귀류(21~22주차)를 한 판에 올려놓고, 명제를 보고 하나를 고르는 절차를 만든다.

원서 대응: BoP(Book of Proof) 4~6장 종합(6.4의 조언을 훈련으로 바꾼 것) — 병행자 참고용. 원서 없이 읽을 수 있다.

이번 주 목표

1. 같은 명제를 직접\(\cdot\)대우\(\cdot\)귀류로 각각 증명하고, 몸통\(\cdot\)서식 줄 수\(\cdot\)읽기 쉬움을 표로 비교한다.

2. 명제를 보고 기법을 고르는 판단(신호 읽기)을 순서도 한 장으로 고정하고, 즉답 수준으로 만든다.

3. 기법을 잘못 고른 답안과 기법을 오용한 답안을 진단하고, 무엇이 무너졌는지 정확히 지목한다.

본문 곳곳의 확인 상자는 연필로 먼저 답하는 자리다. 바로 아래의 답 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

준비 운동 (22주차 복습)

1. 직접\(\cdot\)대우\(\cdot\)귀류의 “가정 / 도착지” 비교표를 백지에 쓰시오.

2. 기법 선택 가이드 4조(①직접 먼저 … ④남용 주의)를 쓰시오.

3. \(\neg(P \Rightarrow Q) \equiv \underline{\quad}\)

자주 나오는 세 가지 답 — 2번 문항

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

• 유형 1 — 순서만 나열. “직접 \(\to\) 대우 \(\to\) 귀류” 세 낱말만 적는다. 순서는

정확하다. 빠진 것은 화살표의 조건이다 — 무엇을 보고 다음 칸으로 넘어가는지가 적혀 있지 않으면, 그 순서는 실제 명제 앞에서 아무것도 결정하지 못한다. §1.4가 그 조건(신호)을 명제의 어느 자리에서 읽는지 지정한다.

• 유형 2 — ④를 빠뜨림. ①~③만 적고 남용 경고를 적지 않는다. 세 조는 정확하다.

④가 빠지면 완성된 답안을 검사할 기준이 사라진다 — 22주차 문제 18의 답안처럼 논리적으로 틀린 곳이 없는데도 기법 이름이 사실과 다른 답안을 걸러낼 수 없다. §1.6의 조각 삭제 실험이 이 손실을 눈으로 확인하는 자리다.

• 유형 3 — 쥐는 가정의 수로 서열화. “귀류가 가정을 둘 쥐므로 귀류부터 쓴다”고

적는다. 22주차 §1.5의 비교표를 정확히 읽은 결과다. 다만 쥐는 가정의 수와 읽기 쉬움은 다른 축이다 — 가정이 많다는 것은 쓸 수 있는 것이 많다는 뜻이지 짧아진다는 뜻이 아니고, 실제로 예제 2.2에서 귀류는 몸통이 같은 채로 서식만 길어진다.

개념 — 신호를 읽어 기법을 고른다

1 기법을 고르지 않고 밀어붙이면 어디서 막히는가

22주차까지 세 기법을 각각 배웠다. 이번 주에 새로 다루는 것은 “어떻게 증명하는가”가 아니라 “어느 기법으로 시작하는가”이다. 고르는 절차 없이 손에 잡히는 대로 밀어붙이면 어떻게 되는지부터 본다.

시도 — 고르지 않고 직접부터 밀어붙이기

명제: 정수 \(n\)에 대해, \(3n + 5\)가 짝수이면 \(n\)은 홀수이다.

“\(3n + 5\)가 짝수라 하자. 정의에 의해 \(3n + 5 = 2k\)인 정수 \(k\)가 존재한다.

이항하면 \(3n = 2k - 5 = 2(k - 3) + 1\)이므로 \(3n\)은 홀수이다.

따라서 \(n\)은 … “

여기서 멈춘다. 손에 있는 것은 “\(3n\)이 홀수”이고 만들어야 할 것은 “\(n\)이 홀수”인데, 곱 \(3n\)에서 인수 \(n\)만의 홀짝을 꺼내 주는 등식이 없다. 꺼내려면 “\(3n\)이 홀수이면 \(n\)은 홀수이다”라는 보조정리가 따로 있어야 하고, 그 보조정리는 원래 명제와 같은 모양의 조건문이다 — 문제를 자기 자신으로 되돌린 셈이다.

확인 1. 막힌 원인은 계산 실력이 아니다. 가정 “\(3n + 5\)가 짝수”가 \(n\)에 대해

주는 정보의 모양을 한 구절로 적어 보자. 그 모양이 왜 계산을 막는가.

답

가정이 주는 것은 \(n\) 자체에 대한 등식이 아니라 합성식 \(3n + 5\)에 대한 등식이다.

\(n\)은 그 식 안에 갇혀 있고, 정의를 풀어도 나오는 것은 \(3n\) 또는 \(3n + 5\)일 뿐

\(n = (\text{무엇})\) 꼴이 아니다. 19주차 §1.1에서 만난 것과 같은 자리다 —

가정에서 문자가 꺼내지지 않으면 직접 증명은 시작되지 않는다. 막힘의

원인은 계산이 아니라 정보의 모양이다.

같은 명제를 대우로 갈아타면 가정이 “\(n\)이 홀수”가 되고, 그때는 \(n = 2a + 1\)이 곧바로 손에 들어온다.

대우 증명. 대우는 “\(n\)이 짝수이면 \(3n + 5\)는 홀수이다”이다. \(n = 2a\)라 하면

\[ 3n + 5 = 6a + 5 = 2(3a + 2) + 1 \]

이고 \(3a + 2\)는 정수이므로 \(3n + 5\)는 홀수이다. 대우가 증명되었으므로 원명제가 성립한다. \(\blacksquare\)

막힘과 두 줄을 가른 것은 계산이 아니라 배치다. 어느 명제를 손에 쥐고 시작하는지만 바꿨을 뿐인데 한쪽은 보조정리를 새로 파야 했고 다른 쪽은 대입 한 번으로 끝났다. 이 배치를 명제를 보고 미리 정하는 것이 이번 주의 내용이다.

2 세 경로를 끝까지 밀어 보기 — 표 채우기

같은 명제 하나를 세 경로로 각각 끝까지 밀어 본 결과를 표로 정리한다. 빈칸을 연필로 먼저 채운다. 명제는 §1.1의 “\(3n + 5\)가 짝수이면 \(n\)은 홀수이다”이다.

경로	무엇을 손에 쥐고 시작하는가	무엇을 만들면 끝나는가	이 명제에서의 결과
직접	\(3n + 5 = 2k\)인 정수 \(k\)	\(n = 2(\text{정수}) + 1\) 꼴	\(3n\)이 홀수까지 가고 막힘
대우	\(\underline{\quad(1)\quad}\)	\(\underline{\quad(2)\quad}\)	두 줄로 완성
귀류	\(3n + 5\)가 짝수 그리고 \(\underline{\quad(3)\quad}\)	아무 모순	\(\underline{\quad(4)\quad}\)

확인 2. 빈칸 (1)~(4)를 채워 보자. (3)은 결론의 부정이고, (4)는 실제로

귀류로 써 본 뒤에 적는다.

답

(1) \(n = 2a\)인 정수 \(a\) (곧 “\(n\)이 짝수”라는 가정).

(2) \(3n + 5 = 2(\text{정수}) + 1\) 꼴, 곧 “\(3n + 5\)가 홀수”.

(3) \(n\)이 짝수.

(4) 세 줄로 완성. 가정에서 \(n = 2a\)를 받아 \(3n + 5 = 2(3a+2) + 1\)이 홀수임을

보이면 “\(3n + 5\)가 짝수”라는 가정과 충돌한다.

세 경로를 나란히 놓으면 두 가지가 보인다.

첫째, 몸통은 하나뿐이다. 대우와 귀류가 실제로 계산한 것은 똑같이 “\(n = 2a\)를 대입해 \(3n + 5 = 2(3a+2) + 1\)을 얻는다”는 한 줄이다. 달라진 것은 그 한 줄을 감싸는 문장뿐이다.

둘째, 서식의 무게가 다르다. 대우는 앞뒤로 두 줄(기법 선언, 원명제 회수)이 붙고, 귀류는 세 줄(가정 선언, 충돌 선언, 원명제 회수)이 붙는다.

확인 3. 몸통이 같은데 서식 줄 수가 다르다면, 둘 중 어느 쪽을 고르는 것이

좋은가. 그 판단의 근거를 한 문장으로 적어 보자.

답

서식이 가벼운 쪽, 곧 대우다. 근거는 읽는 사람이 검사해야 할 문장이 적다는

것이다 — 귀류가 더 쓰는 한 줄(충돌 선언)은 이 명제에서 아무 일도 하지 않는다.

(\(P\)인 “\(3n+5\) 짝수”를 마지막 충돌 선언에서만 썼다면 그것은 22주차 가이드 ④가

말하는 남용이다.) 다만 둘 다 유효한 증명이라는 사실은 변하지 않는다 —

가벼움은 우열이 아니라 선택의 기준이다.

이 관찰에 이름을 붙인다. 식 자체에 새로운 것은 없다 — 세 기법 중 무엇도 이번 주에 새로 배우는 것이 아니다. 새로 배우는 것은 셋 중 하나를 명제의 모양만 보고 고르는 절차뿐이다.

정의 23.1 — 신호 읽기 (reading the signals) [백지 암기 대상]

명제의 가정과 결론의 모양만 보고 직접\(\cdot\)대우\(\cdot\)귀류 중 하나를 1순위 기법으로

정하는 절차를 신호 읽기라 한다. 읽는 자리는 두 곳뿐이다 — 가정의 모양과

결론의 모양. 이 절차의 본문은 §1.5의 선택 순서도로 고정한다.

3 세 기법의 관계 한눈에

\(P \Rightarrow Q\)에 대하여 —

기법	출발	도착	특징
직접	\(P\)	\(Q\)	정보가 순방향으로 흐른다. 가장 읽기 쉽다
대우	\(\neg Q\)	\(\neg P\)	직접 증명의 거울상. 도착지가 \(\neg P\)로 고정된다
귀류	\(P\) 와 \(\neg Q\)	아무 모순	쥐는 가정이 둘로 가장 많고 도착지가 열려 있다. 그만큼 남용도 쉽다

세 기법 모두 몸통은 15주차의 직접 증명 기술(정의 전개, 대수 변형, 이미 증명한 명제 인용, 경우 나누기)이다. 다른 것은 출발점과 도착점의 배치뿐이다.

4 신호는 명제의 어느 자리에 있는가

기법을 고르는 근거를 “느낌”에 두면 매번 다른 답이 나온다. 근거를 명제의 특정 자리에 고정한다 — 신호는 결론의 모양과 가정의 모양 두 곳에만 있다.

신호가 있는 자리	관찰되는 모양	그 모양이 뜻하는 것	1순위 기법
결론	무리수\(\cdot\)비존재\(\cdot\)무한 등 “아니다”로만 서술되는 것	도착점으로 삼을 등식 꼴이 아예 없다	귀류
결론	“또는”	부정하면 “그리고” — 가정이 둘로 늘어난다	대우(귀류도 유효)
가정	합성식(\(n^2\), \(3n + 5\)) 안에 문자가 갇혀 있다	정의를 풀어도 문자 자체가 안 나온다	대우
가정	부정형(\(a \nmid b\), “무리수”)	등식이 아니라 “아니다”만 손에 들어온다	대우
가정	긍정형이고 정의로 즉시 등식이 된다	순방향으로 계산이 시작된다	직접

확인 4. 다음 세 명제의 신호를 위 표에서 찾아 1순위 기법을 정해 보자.

(가) \(a \mid b\)이면 \(a \mid 3b^2\)이다.

(나) \(n^2 + 1\)이 짝수이면 \(n\)은 홀수이다.

(다) \(\sqrt{3}\)은 무리수이다.

답

(가) 직접. 가정 \(a \mid b\)가 정의로 \(b = ak\)가 되어 즉시 등식이 손에 들어온다

— 가정 쪽 마지막 행의 신호다.

(나) 대우. 가정에서 \(n\)이 합성식 \(n^2 + 1\) 안에 갇혀 있다 — 가정 쪽 셋째 행.

대우의 가정 “\(n\)이 짝수”는 \(n = 2a\)로 바로 풀린다.

(다) 귀류. 결론이 “유리수가 아니다”라는 부정형 개념뿐이라 만들 등식 꼴이

없다 — 결론 쪽 첫째 행. 부정해서 \(\sqrt3 = \frac{a}{b}\)를 받아야 계산이 시작된다.

세 자리 판정을 순서로 굳히면 다음 상자가 된다. 백지에 쓸 수 있어야 한다.

5 선택 순서도

백지 암기 대상

선택 순서도

1단계. 결론이 부정형\(\cdot\)비존재\(\cdot\)무리수\(\cdot\)무한인가 \(\to\) 귀류 후보.

2단계. (조건문에서) 가정이 합성식(\(n^2\), \(3n+5\))이거나 부정형인가, 또는

결론이 “또는”인가 \(\to\) 대우 후보.

3단계. 해당 없음 \(\to\) 직접부터. 가정을 정의로 풀고 목표 꼴로 간다.

공통. 시도가 막히면 다음 후보로 갈아탄다. 완성한 뒤에는 자기 점검 두 가지 —

귀류라면 “부정 가정을 충돌 선언 이전에 실제로 썼는가”, 대우라면

“부정을 정확히 만들었는가”.

6 순서도 해부 — 조각마다 하는 일

이 상자는 다섯 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다.

조각	하는 일	판정에서의 역할
1단계 “결론이 부정형인가”	결론 쪽부터 본다	도착점 자체가 없는 명제를 가장 먼저 걸러낸다
2단계 “가정이 합성식\(\cdot\)부정형인가”	가정 쪽과 “또는”을 본다	정의를 풀어도 문자가 안 나오는 명제를 걸러낸다
3단계 “해당 없음 \(\to\) 직접”	남은 것을 처리한다	신호가 없다는 것 자체가 직접의 신호다
공통 “막히면 갈아탄다”	순서도를 되돌릴 수 있게 한다	1순위가 막혀도 답안이 거기서 끝나지 않게 한다
공통 “완성 후 자기 점검”	완성본을 검사한다	남용(귀류)과 잘못 만든 부정(대우)을 잡아낸다

조각 삭제 실험. 마지막 조각(자기 점검)을 지워 보자. 그러면 다음 답안이 아무 걸림 없이 통과한다.

점검 없이 통과하는 답안

명제: \(n\)이 짝수이면 \(n^2\)은 짝수이다.

“모순을 위해 \(n\)이 짝수인데 \(n^2\)이 홀수라고 가정하자. \(n = 2k\)이므로

\(n^2 = 4k^2 = 2(2k^2)\)은 짝수이다. 이는 \(n^2\)이 홀수라는 가정과 모순이다.

따라서 명제가 성립한다. \(\blacksquare\)”

확인 5. 위 답안에는 논리적으로 틀린 줄이 없다. 그런데도 자기 점검 조각이

이 답안을 걸러내는 이유는 무엇인가. 어느 문장이 실제로는 쓰이지 않았는가.

답

부정 가정 “\(n^2\)이 홀수”가 몸통 계산에서 한 번도 쓰이지 않았다 — 마지막

충돌 선언에서 이름만 불린다. 몸통 “\(n = 2k \Rightarrow n^2 = 2(2k^2)\)”은 그

자체로 원명제의 완전한 직접 증명이므로, 귀류라는 이름이 사실과 맞지 않는다

(22주차 문제 18에서 해부한 답안이다). 자기 점검 조각을 지우면 순서도는

기법을 고르기만 하고 고른 결과가 맞았는지 검사하지 못한다.

확인 6. 1단계와 2단계의 순서를 바꾸면 무엇이 달라지는가.

명제 “\(x\)가 무리수이면 \(x + 5\)는 무리수이다”로 시험해 보자.

답

이 명제는 결론도 부정형(무리수)이고 가정도 부정형(무리수)이라 1단계와 2단계에

모두 걸린다. 순서를 바꾸면 1순위가 귀류에서 대우로 바뀌는데, **둘 다 실제로

통한다**(문제 12에서 두 방식으로 모두 증명한다). 곧 순서도는 유일한 정답을

정하는 장치가 아니라 어디부터 시도할지를 정하는 장치다. 두 후보가 함께

걸리면 서식이 가벼운 쪽(§1.2 확인 3)을 먼저 잡으면 된다.

7 갈아탄 뒤에 쓰는 것은 언제나 같다

기법을 갈아타도 몸통에서 하는 일은 바뀌지 않는다. 세 경로 전부 15주차의 직접 증명 기술 위에서 굴러간다.

기법	갈아탄 뒤 실제로 증명하는 명제	그 명제를 증명하는 방법
직접	\(P \Rightarrow Q\)	정의 전개 \(\to\) 대수 변형 \(\to\) 목표 꼴
대우	\(\neg Q \Rightarrow \neg P\)	정의 전개 \(\to\) 대수 변형 \(\to\) 목표 꼴
귀류	\(P \land \neg Q\)에서 출발	정의 전개 \(\to\) 대수 변형 \(\to\) 이미 아는 사실과 충돌

확인 7. 위 표에서 셋째 열이 거의 같다. 그렇다면 “기법을 세 개 배웠다”는

말과 “같은 기술을 세 가지로 배치했다”는 말 중 어느 쪽이 정확한가.

답

뒤쪽이다. 새로 배운 것은 계산 기술이 아니라 출발점과 도착점의 배치다.

그래서 기법을 갈아타도 15주차의 서식\(\cdot\)근거 규칙은 그대로 적용되고, 갈아탄

명제를 한 줄로 명시(대우) 또는 가정 두 개를 한 줄로 명시(귀류)하는 서식만

앞뒤에 붙는다. 이 사실이 예제 2.1에서 대우와 귀류의 몸통이 겹치는 이유다.

8 근거 목록 갱신 — 칸은 그대로 네 개

이번 주에는 근거 목록에 새 칸이 생기지 않는다. ④ 칸에 21~22주차의 결과가 쌓일 뿐이다. 늘어나는 것은 근거가 아니라 근거를 꺼내기 전에 거치는 절차다.

근거	내용	이번 주에는 이렇게 쓴다
① 정의	짝수\(\cdot\)홀수(1주차), 나누어떨어짐(2주차), 유리수\(\cdot\)소수(15주차), 합동(20주차 정의 20.1)	어느 기법을 골랐든 몸통의 첫 줄은 정의 풀어쓰기다
② 닫힘성	정수의 합\(\cdot\)차\(\cdot\)곱은 정수, 유리수의 사칙연산 닫힘(15주차)	\(7a + 5\)가 정수임을 별도 설명 없이 쓴다
③ 등식의 성질	대입 / 전개 / 묶기 / 양변 연산	\(n = 2a\)를 합성식에 대입해 목표 꼴로 정리한다
④ 이미 증명한 명제	1~22주차의 예제\(\cdot\)문제 전부 + 부등식의 기본 성질 (W1)~(W6)(16주차)	1주차 문제 8\(\cdot\)13, 15주차 문제 9, 17주차 문제 9를 부품으로 인용한다

“기법 이름”은 근거가 아니다. “귀류로 증명했으므로”는 어떤 줄도 정당화하지 못한다 — 정당화하는 것은 그 줄에 붙은 ①~④뿐이다.

확인 8. 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가.

허용된다면 몇 번 근거인가.

(가) “귀류법으로 증명하므로 이 단계는 생략해도 된다”

(나) “\(n\)이 홀수이므로 1주차 문제 13에 의해 \(n^3\)은 홀수이다”

(다) “무리수와 무리수의 합은 무리수이므로 \(\sqrt2 + \sqrt5\)는 무리수이다”

답

(가) 불허 — 기법 이름은 목록에 없다. 귀류를 택했다고 해서 몸통의 어느 줄도

면제되지 않는다.

(나) 허용 — 근거 ④. 실제로 증명된 명제를 정확한 위치와 함께 인용했다.

(다) 불허 — 인용된 “정리”가 존재하지 않는다. 15주차 문제 19에 반례

(\(\sqrt2 + (-\sqrt2) = 0\))가 있으므로 그 문장은 거짓 명제다. 거짓 명제를 근거로

쓰면 결론의 참\(\cdot\)거짓과 무관하게 증명 전체가 무효가 된다(문제 19에서 이 답안을

정식으로 진단한다).