# 23주차 — 기법 선택 훈련: 같은 명제, 세 가지 증명 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 기법은 취향이 아니라 신호가 정한다 — 신호는 가정과 결론의 모양에 있다. **이 주의 위치**: 50주 과정의 23주차. 직접(15~18주차)$\cdot$대우(19주차)$\cdot$귀류(21~22주차)를 한 판에 올려놓고, 명제를 보고 하나를 고르는 절차를 만든다. **원서 대응**: BoP(Book of Proof) 4~6장 종합(6.4의 조언을 훈련으로 바꾼 것) — 병행자 참고용. 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. 같은 명제를 직접$\cdot$대우$\cdot$귀류로 각각 증명하고, 몸통$\cdot$서식 줄 수$\cdot$읽기 쉬움을 표로 비교한다. 1. 명제를 보고 기법을 고르는 판단(신호 읽기)을 순서도 한 장으로 고정하고, 즉답 수준으로 만든다. 1. 기법을 잘못 고른 답안과 기법을 오용한 답안을 진단하고, 무엇이 무너졌는지 정확히 지목한다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (22주차 복습) 1. 직접$\cdot$대우$\cdot$귀류의 "가정 / 도착지" 비교표를 백지에 쓰시오. 1. 기법 선택 가이드 4조(①직접 먼저 … ④남용 주의)를 쓰시오. 1. $\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주차까지 세 기법을 각각 배웠다. 이번 주에 새로 다루는 것은 "어떻게 증명하는가"가 아니라 "어느 기법으로 시작하는가"이다. 고르는 절차 없이 손에 잡히는 대로 밀어붙이면 어떻게 되는지부터 본다. :::{admonition} 시도 — 고르지 않고 직접부터 밀어붙이기 :class: quotebox 명제: 정수 $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$은 홀수이다"라는 보조정리가 따로 있어야 하고, 그 보조정리는 원래 명제와 같은 모양의 조건문이다 — 문제를 자기 자신으로 되돌린 셈이다. :::{container} quotebox **확인 1.** 막힌 원인은 계산 실력이 아니다. 가정 "$3n + 5$가 짝수"가 $n$에 대해 주는 정보의 **모양**을 한 구절로 적어 보자. 그 모양이 왜 계산을 막는가. ::: :::{admonition} 답 :class: quotebox dropdown 가정이 주는 것은 $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}$ | :::{container} quotebox **확인 2.** 빈칸 (1)~(4)를 채워 보자. (3)은 결론의 부정이고, (4)는 실제로 귀류로 써 본 뒤에 적는다. ::: :::{admonition} 답 :class: quotebox dropdown (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$을 얻는다"는 한 줄이다. 달라진 것은 그 한 줄을 감싸는 문장뿐이다. **둘째, 서식의 무게가 다르다.** 대우는 앞뒤로 두 줄(기법 선언, 원명제 회수)이 붙고, 귀류는 세 줄(가정 선언, 충돌 선언, 원명제 회수)이 붙는다. :::{container} quotebox **확인 3.** 몸통이 같은데 서식 줄 수가 다르다면, 둘 중 어느 쪽을 고르는 것이 좋은가. 그 판단의 근거를 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 서식이 가벼운 쪽, 곧 대우다. 근거는 읽는 사람이 검사해야 할 문장이 적다는 것이다 — 귀류가 더 쓰는 한 줄(충돌 선언)은 이 명제에서 아무 일도 하지 않는다. ($P$인 "$3n+5$ 짝수"를 마지막 충돌 선언에서만 썼다면 그것은 22주차 가이드 ④가 말하는 남용이다.) 다만 **둘 다 유효한 증명**이라는 사실은 변하지 않는다 — 가벼움은 우열이 아니라 선택의 기준이다. ::: 이 관찰에 이름을 붙인다. 식 자체에 새로운 것은 없다 — 세 기법 중 무엇도 이번 주에 새로 배우는 것이 아니다. 새로 배우는 것은 셋 중 하나를 명제의 모양만 보고 고르는 절차뿐이다. ### 정의 23.1 — 신호 읽기 (reading the signals) [백지 암기 대상] :::{container} quotebox 명제의 가정과 결론의 **모양**만 보고 직접$\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$, "무리수") | 등식이 아니라 "아니다"만 손에 들어온다 | 대우 | | 가정 | 긍정형이고 정의로 즉시 등식이 된다 | 순방향으로 계산이 시작된다 | 직접 | :::{container} quotebox **확인 4.** 다음 세 명제의 신호를 위 표에서 찾아 1순위 기법을 정해 보자. (가) $a \mid b$이면 $a \mid 3b^2$이다. (나) $n^2 + 1$이 짝수이면 $n$은 홀수이다. (다) $\sqrt{3}$은 무리수이다. ::: :::{admonition} 답 :class: quotebox dropdown (가) **직접.** 가정 $a \mid b$가 정의로 $b = ak$가 되어 즉시 등식이 손에 들어온다 — 가정 쪽 마지막 행의 신호다. (나) **대우.** 가정에서 $n$이 합성식 $n^2 + 1$ 안에 갇혀 있다 — 가정 쪽 셋째 행. 대우의 가정 "$n$이 짝수"는 $n = 2a$로 바로 풀린다. (다) **귀류.** 결론이 "유리수가 아니다"라는 부정형 개념뿐이라 만들 등식 꼴이 없다 — 결론 쪽 첫째 행. 부정해서 $\sqrt3 = \frac{a}{b}$를 받아야 계산이 시작된다. ::: 세 자리 판정을 순서로 굳히면 다음 상자가 된다. 백지에 쓸 수 있어야 한다. ### 5 선택 순서도 :::{admonition} 백지 암기 대상 :class: keybox **선택 순서도** **1단계.** 결론이 부정형$\cdot$비존재$\cdot$무리수$\cdot$무한인가 $\to$ **귀류** 후보. **2단계.** (조건문에서) 가정이 합성식($n^2$, $3n+5$)이거나 부정형인가, 또는 결론이 "또는"인가 $\to$ **대우** 후보. **3단계.** 해당 없음 $\to$ **직접**부터. 가정을 정의로 풀고 목표 꼴로 간다. **공통.** 시도가 막히면 다음 후보로 갈아탄다. 완성한 뒤에는 자기 점검 두 가지 — 귀류라면 "부정 가정을 충돌 선언 이전에 실제로 썼는가", 대우라면 "부정을 정확히 만들었는가". ::: ### 6 순서도 해부 — 조각마다 하는 일 이 상자는 다섯 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다. | **조각** | **하는 일** | **판정에서의 역할** | |---|---|---| | 1단계 "결론이 부정형인가" | 결론 쪽부터 본다 | 도착점 자체가 없는 명제를 가장 먼저 걸러낸다 | | 2단계 "가정이 합성식$\cdot$부정형인가" | 가정 쪽과 "또는"을 본다 | 정의를 풀어도 문자가 안 나오는 명제를 걸러낸다 | | 3단계 "해당 없음 $\to$ 직접" | 남은 것을 처리한다 | 신호가 없다는 것 자체가 직접의 신호다 | | 공통 "막히면 갈아탄다" | 순서도를 되돌릴 수 있게 한다 | 1순위가 막혀도 답안이 거기서 끝나지 않게 한다 | | 공통 "완성 후 자기 점검" | 완성본을 검사한다 | 남용(귀류)과 잘못 만든 부정(대우)을 잡아낸다 | **조각 삭제 실험.** 마지막 조각(자기 점검)을 지워 보자. 그러면 다음 답안이 아무 걸림 없이 통과한다. :::{admonition} 점검 없이 통과하는 답안 :class: quotebox 명제: $n$이 짝수이면 $n^2$은 짝수이다. "모순을 위해 $n$이 짝수인데 $n^2$이 홀수라고 가정하자. $n = 2k$이므로 $n^2 = 4k^2 = 2(2k^2)$은 짝수이다. 이는 $n^2$이 홀수라는 가정과 모순이다. 따라서 명제가 성립한다. $\blacksquare$" ::: :::{container} quotebox **확인 5.** 위 답안에는 논리적으로 틀린 줄이 없다. 그런데도 자기 점검 조각이 이 답안을 걸러내는 이유는 무엇인가. 어느 문장이 실제로는 쓰이지 않았는가. ::: :::{admonition} 답 :class: quotebox dropdown 부정 가정 "$n^2$이 홀수"가 몸통 계산에서 **한 번도 쓰이지 않았다** — 마지막 충돌 선언에서 이름만 불린다. 몸통 "$n = 2k \Rightarrow n^2 = 2(2k^2)$"은 그 자체로 원명제의 완전한 직접 증명이므로, 귀류라는 이름이 사실과 맞지 않는다 (22주차 문제 18에서 해부한 답안이다). 자기 점검 조각을 지우면 순서도는 기법을 고르기만 하고 **고른 결과가 맞았는지 검사하지 못한다.** ::: :::{container} quotebox **확인 6.** 1단계와 2단계의 순서를 바꾸면 무엇이 달라지는가. 명제 "$x$가 무리수이면 $x + 5$는 무리수이다"로 시험해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 이 명제는 결론도 부정형(무리수)이고 가정도 부정형(무리수)이라 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$ 이미 아는 사실과 충돌 | :::{container} quotebox **확인 7.** 위 표에서 셋째 열이 거의 같다. 그렇다면 "기법을 세 개 배웠다"는 말과 "같은 기술을 세 가지로 배치했다"는 말 중 어느 쪽이 정확한가. ::: :::{admonition} 답 :class: quotebox dropdown 뒤쪽이다. 새로 배운 것은 계산 기술이 아니라 **출발점과 도착점의 배치**다. 그래서 기법을 갈아타도 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를 부품으로 인용한다 | "기법 이름"은 근거가 아니다. "귀류로 증명했으므로"는 어떤 줄도 정당화하지 못한다 — 정당화하는 것은 그 줄에 붙은 ①~④뿐이다. :::{container} quotebox **확인 8.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) "귀류법으로 증명하므로 이 단계는 생략해도 된다" (나) "$n$이 홀수이므로 1주차 문제 13에 의해 $n^3$은 홀수이다" (다) "무리수와 무리수의 합은 무리수이므로 $\sqrt2 + \sqrt5$는 무리수이다" ::: :::{admonition} 답 :class: quotebox dropdown (가) 불허 — 기법 이름은 목록에 없다. 귀류를 택했다고 해서 몸통의 어느 줄도 면제되지 않는다. (나) 허용 — 근거 ④. 실제로 증명된 명제를 정확한 위치와 함께 인용했다. (다) 불허 — 인용된 "정리"가 존재하지 않는다. 15주차 문제 19에 반례 ($\sqrt2 + (-\sqrt2) = 0$)가 있으므로 그 문장은 거짓 명제다. 거짓 명제를 근거로 쓰면 결론의 참$\cdot$거짓과 무관하게 증명 전체가 무효가 된다(문제 19에서 이 답안을 정식으로 진단한다). :::