# 19주차 — 대우 증명 (Contrapositive Proof) :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 대우 증명은 새 논리가 아니라, 원명제와 동치인 명제 중 다루기 쉬운 쪽을 골라 직접 증명하는 것이다. **이 주의 위치**: 50주 과정의 19주차. 5부(간접 증명)의 개막 — 1주차 문제 11 해설이 예고했던 막힘을 처음으로 해결한다. **원서 대응**: BoP(Book of Proof) 5.1 (Contrapositive Proof). 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. 대우 증명의 서식을 백지에 쓰고, 대우를 부정 규칙(11주차)으로 정확히 제작할 수 있다. 1. 직접 증명이 막히는 신호 세 가지를 읽고 대우로 갈아탈 수 있다. 1. 대우의 몸통에 경우 나누기(17주차)와 기증명 명제(1$\cdot$15$\cdot$17주차)를 겹쳐 쓸 수 있다. 1. 대우와 이(inverse)를 구별하고, 무대 조건이 부정되지 않는 이유를 설명할 수 있다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (18주차 복습) 1. "$n$이 홀수이면 $n^2$은 홀수이다"를 안 보고 증명하시오 (1주차 문제 11 — 이번 주의 핵심 부품). 1. $n^2$을 3으로 나눈 나머지가 0 또는 1임을 증명하는 분할은 무엇인지 쓰시오 (17주차 문제 8). 1. "$P \Rightarrow Q$"의 대우를 쓰고, 둘이 동치인 근거가 몇 주차의 무엇인지 쓰시오. 1. 정수 $n$에 대해 "$n^2$이 짝수이면 $n$은 짝수이다"를 지금 아는 방식으로 증명해 보자. 막히면 어디서 막혔는지를 문장으로 적는다. 1번의 대조 지점은 1주차 문제 11의 해설, 2번은 17주차 문제 8의 해설, 3번은 9주차 §1.7의 표다. 4번은 아래에서 유형별로 대조한다. ### 자주 나오는 세 가지 답 — 4번 문항 방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — 제곱근 취하기.** "$n^2 = 2k$이므로 $n = \sqrt{2k}$"까지 적는다. 우선 등식 변형부터 정확하지 않다 — 제곱근을 취해 나오는 것은 $|n| = \sqrt{2k}$이고($n = -2$, $k = 2$가 반례다), $n$ 자체에 대한 등식이 아니다. 설령 부호를 정리했다 해도 도착한 자리가 문제다 — 목표 꼴은 $n = 2 \times (\text{정수})$인데 $\sqrt{2k}$가 정수라는 보장이 어디에도 없고, 근호는 정수 세계 밖의 값을 낼 수 있다. 근거 목록(①~④)에 "제곱근을 취해도 정수다"라는 항목은 없다. - **유형 2 — 방향을 바꿔 증명.** "$n = 2a$이면 $n^2 = 2(2a^2)$이므로 짝수"라고 적고 끝낸다. 이 계산은 한 줄도 틀리지 않았고, 실제로 1주차 문제 9의 증명 그대로다. 문제는 증명된 명제가 원명제가 아니라 그 **역**이라는 것이다 (9주차 §1.7 — 역은 원명제와 동치가 아니다). 참인 명제를 증명했지만 요구된 명제는 손대지 않은 상태다. - **유형 3 — 두 줄에서 정지.** "$n^2$이 짝수라 가정하자. 정의에 의해 $n^2 = 2k$인 정수 $k$가 존재한다"까지 쓰고 멈춘다. 오프닝과 정의 풀기는 정확하다. 남은 것은 그다음 줄이 나오지 않는 이유를 밝히는 일이고, 이번 주 전체가 그 한 줄을 만드는 작업이다. ## 개념 — 명제를 갈아타는 법 ### 1 직접 증명으로 밀어붙이면 어디서 막히는가 4부의 도구 — 정의 풀어쓰기, 대수 변형, 경우 나누기 — 만으로 준비 운동 4번을 끝까지 밀어붙여 보자. :::{admonition} 시도 — 직접 증명으로 밀어붙이기 :class: quotebox 명제: 정수 $n$에 대해, $n^2$이 짝수이면 $n$은 짝수이다. "$n^2$이 짝수라 가정하자. 짝수의 정의에 의해 $n^2 = 2k$인 정수 $k$가 존재한다. 목표는 $n = 2 \times (\text{정수})$ 꼴을 만드는 것이다. 그런데 손에 있는 등식의 좌변은 $n^2$이므로, $n$을 얻으려면 …" ::: 여기서 멈춘다. 다음 줄이 나오지 않는다. :::{container} quotebox **확인 1.** 멈춘 자리에서 다음 줄이 나오려면 $n$에 대해 어떤 **종류**의 정보가 필요한가. 그리고 지금 손에 있는 등식은 그것을 주는가. ::: :::{admonition} 답 :class: quotebox dropdown "$n$은 (무엇)과 **같다**" 꼴의 등식, 곧 좌변이 $n$인 등식이 필요하다. 손에 있는 것은 좌변이 $n^2$인 등식뿐이다. $n^2 = 2k$의 양변에 제곱근을 취하면 $|n| = \sqrt{2k}$가 나올 뿐 $n$에 대한 등식이 아니고($n$은 음수일 수 있다), 그 값이 정수라는 근거도 없다 — 근거 목록에 없는 조작이므로 증명의 줄로 쓸 수 없다. 곧 **가정 쪽에서 정보를 꺼낼 수 없는 막힘**이다 (18주차 §1의 신호 첫 줄). ::: 막힌 것은 도구가 아니라 명제의 방향이다. 같은 소재로 방향만 뒤집은 "$n$이 짝수이면 $n^2$은 짝수이다"는 가정이 $n$에 대한 것이라 정의가 즉시 풀리고, 1주차 문제 9에서 이미 증명해 두었다. 곧 소재는 같은데 한 방향은 막히고 다른 방향은 열려 있다. 그렇다고 열린 쪽을 증명하고 끝낼 수는 없다. 열린 쪽은 원명제의 **역**이고, 역은 원명제와 동치가 아니다(9주차 §1.7). 준비 운동의 유형 2가 정확히 이 자리에서 멈춘 답안이다. :::{admonition} 이 주 전체의 기준 :class: quotebox 막힌 명제를 버리지 않는다. 그 명제와 **동치인** 다른 명제를 찾아 그쪽을 직접 증명한다. 동치가 아닌 명제로 갈아타면 별개의 명제를 증명한 것이 된다. ::: ### 2 무엇으로 갈아탈 수 있는가 — 표 채우기 원명제 "$n^2$이 짝수이면 $n$은 짝수이다"에서 $P$를 "$n^2$이 짝수", $Q$를 "$n$이 짝수"라 두자. 9주차 §1.7에서 만든 세 변형을 이 명제로 실제로 만들어 보고, 마지막 열에 동치 여부를 적는다. | **이름** | **식** | **이 명제에서 만들면** | **원명제와 동치?** | |---|---|---|---| | 역 (converse) | $Q \Rightarrow P$ | $n$이 짝수이면 $n^2$은 짝수이다 | $\underline{\quad(1)\quad}$ | | 이 (inverse) | $\neg P \Rightarrow \neg Q$ | $n^2$이 홀수이면 $n$은 홀수이다 | $\underline{\quad(2)\quad}$ | | 대우 (contrapositive) | $\neg Q \Rightarrow \neg P$ | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ | :::{container} quotebox **확인 2.** 표의 빈칸 (1)~(4)를 채우고, 세 변형 중 갈아탈 수 있는 것이 어느 것인지 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) 아니오 (9주차 예제 2.2에서 반례 행으로 확인). (2) 아니오 (9주차 문제 13). (3) "$n$이 홀수이면 $n^2$은 홀수이다". (4) 예 — 9주차 예제 2.1에서 진리표 네 행 전부로 증명했다. 갈아탈 수 있는 것은 대우 하나뿐이다. 그리고 그 대우는 1주차 문제 11에서 이미 증명해 둔 명제다. 원명제는 막혀 있었지만, 동치인 명제 쪽은 18주 전에 끝나 있었다. ::: 정리하면 이렇다. 대우의 가정 "$n$이 홀수"는 정의가 즉시 풀리는 꼴이므로 §1.1의 막힘이 사라지고, 대우가 증명되면 동치에 의해 원명제도 함께 증명된다. 이 두 문장에 정식 이름을 붙인다. 논리에 새로 추가되는 것은 없다 — 9주차에서 증명해 둔 동치 하나를 증명의 절차로 쓸 뿐이다. ### 정의 19.1 — 대우 증명 (contrapositive proof) [백지 암기 대상] :::{container} quotebox 명제 "$P$이면 $Q$이다"의 **대우 증명**이란, 그 대우 "$\neg Q$이면 $\neg P$이다"를 직접 증명한 뒤, 동치 $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$(9주차 예제 2.1)를 근거로 원명제의 증명으로 삼는 것이다. ::: 이 정의를 답안의 형식으로 옮기면 아래 다섯 줄이 된다. 이번 주의 모든 증명이 이 형식을 따른다. :::{admonition} 백지 암기 대상 :class: keybox **대우 증명의 서식** **명제.** $P$이면 $Q$이다. **증명.** 대우로 증명한다. 대우는 "$\neg Q$이면 $\neg P$이다"이다. $\neg Q$라 가정하자. $\quad\vdots$ (직접 증명의 몸통 — 근거 ①~④만) 따라서 $\neg P$이다. 대우가 증명되었으므로 원명제도 성립한다. $\blacksquare$ ::: 이번 주에 새로 등장하는 기호는 없다. $\neg$(7주차), $\Rightarrow$(8주차), $\equiv$(9주차)는 읽는 법까지 이미 정해 두었고, "$\neg Q \Rightarrow \neg P$"는 "큐가 아니면 피가 아니다"로 읽는다. ### 3 서식 해부 — 조각마다 하는 일 서식의 다섯 줄은 각각 다른 임무를 맡는다. 첫 줄은 기법 선언과 제작물 명시라는 두 임무를 겸하므로, 아래 표에서는 그 줄을 두 조각으로 나누어 여섯 조각으로 해부한다. 몸통을 뺀 다섯 조각이 이번 주에 새로 익히는 전부다. | **조각** | **하는 일** | **증명에서의 역할** | |---|---|---| | "대우로 증명한다" | 기법 선언 | 아래 문장들의 신분을 밝힌다 — 이 줄이 없으면 $\neg Q$ 가정이 원명제의 가정으로 읽힌다 | | "대우는 …이다" | 제작물 명시 | 만든 것이 대우인지 이인지 검사할 수 있게 적어 둔다 | | "$\neg Q$라 가정하자" | 출발점 확보 | 직접 증명의 오프닝과 같은 자리 — 여기서부터 정의를 푼다 | | 몸통 | 직접 증명 | 근거 ①~④만 쓴다. 4부에서 익힌 도구가 그대로 들어온다 | | "따라서 $\neg P$이다" | 도착점 선언 | 대우의 결론에 정확히 도달했음을 확인한다 | | "대우가 증명되었으므로 원명제도 성립한다" | 회수 | 동치(근거 ④)로 원명제를 되찾는다 | **조각 삭제 실험.** 둘째 조각 "대우는 …이다"를 지워 보자. 그러면 답안에는 선언 한 줄과 몸통만 남고, 몸통은 어떤 명제를 증명하든 문법적으로는 매끄럽게 흘러간다. :::{container} quotebox **확인 3.** "대우는 …이다"라는 줄을 지우는 순간 정확히 무엇이 무너지는가. (한 문제만의 문제인지, 대우 대신 이를 적은 답안은 어떻게 되는지 함께 생각해 보자.) ::: :::{admonition} 답 :class: quotebox dropdown 제작물을 검사할 자리가 사라진다. 대우 대신 이(inverse)를 만들어 놓고도 몸통은 끝까지 완주되고, 그 이가 마침 참인 명제라면 답안은 완성된 것처럼 보인다 — 원명제는 한 번도 다루어지지 않았는데도 그렇다. 곧 **참인 다른 명제를 증명하고 끝내는 오류**가 검사망을 통과한다. 문제 19가 정확히 이 사례이고, 서식의 둘째 줄은 그 오류를 답안 안에서 스스로 잡기 위한 장치다. ::: 셋째 조각 "$\neg Q$라 가정하자"를 지워도 같은 종류의 붕괴가 일어난다 — 계산에 쓰인 등식들의 출처가 비어 몸통 전체가 가정 없는 주장이 된다. ### 4 대우 제작 — 부정 규칙이 소비되는 자리 대우를 만드는 절차는 세 걸음이다. 1. 명제를 "$P$이면 $Q$이다" 꼴로 정리하고 $P$, $Q$를 식별한다. 1. 11주차 부정 규칙 총목록으로 $\neg P$와 $\neg Q$를 각각 만든다. 1. 자리를 바꿔 "$\neg Q$이면 $\neg P$이다"로 적는다. 3번의 "자리를 바꾼다"가 이(inverse)와 갈리는 지점이다. 부정만 하고 자리를 바꾸지 않으면 이가 되고, 이는 원명제와 동치가 아니다. 2번에서 자주 쓰이는 부정을 모아 둔다. 오른쪽 열은 전부 이미 세워 둔 근거다. | **원문 조각** | **부정** | **근거** | |---|---|---| | $n$은 짝수이다 | $n$은 홀수이다 | 짝/홀 분할 — 정수는 둘 중 정확히 하나 (17주차, 나눗셈 정리) | | $a \mid b$ | $a \nmid b$ | 정의 2.1의 표기 약속 | | $x \ge 0$ | $x < 0$ | 실수의 삼분법 (17주차) | | $x = y$ | $x \ne y$ | 등호의 부정 (11주차 §1.3) | | $A$ 그리고 $B$ | $\neg A$ 또는 $\neg B$ | 드모르간 1 (9주차 동치 목록) | | $A$ 또는 $B$ | $\neg A$ 그리고 $\neg B$ | 드모르간 2 (9주차 동치 목록) | | $x$는 무리수이다 | $x$는 유리수이다 | "유리수가 아니다"의 부정 — 이중부정 (9주차) | :::{container} quotebox **확인 4.** 명제 "정수 $x, y$에 대해, $xy$가 홀수이면 $x$와 $y$가 모두 홀수이다"의 대우를 만들어 보자. $\neg Q$부터 적는다: $\neg Q = \underline{\qquad}$, $\neg P = \underline{\qquad}$, 대우 $= \underline{\qquad}$. ::: :::{admonition} 답 :class: quotebox dropdown $Q$는 "$x$가 홀수이고 $y$가 홀수"이므로 드모르간 1에 의해 $\neg Q$는 "$x$가 짝수이거나 $y$가 짝수"이다. $\neg P$는 "$xy$가 짝수"이다. 대우는 "$x$가 짝수이거나 $y$가 짝수이면 $xy$는 짝수이다". 결론에 있던 "그리고"가 대우에서는 가정의 "또는"이 되었고, 가정의 "또는"은 17주차의 경우 나누기가 그대로 처리한다. 문제 10이 이 명제다. ::: **무대 조건은 부정되지 않는다.** "정수 $n$에 대해", "실수 $x, y \ge 0$에 대해"처럼 명제 전체가 놓인 범위를 정하는 부분은 $P$도 $Q$도 아니므로 대우에서 그대로 남는다. 11주차 §1.4에서 확인한 것과 같은 이치다 — 무대는 주장의 내용이 아니라 심사가 벌어지는 범위의 선언이다. :::{container} quotebox **확인 5.** 명제 "실수 $x, y \ge 0$에 대해, $x \ne y$이면 $x^2 \ne y^2$이다"의 대우를 만들어 보자. 조건 "$x, y \ge 0$"은 어디로 가는가. ::: :::{admonition} 답 :class: quotebox dropdown $P$는 "$x \ne y$", $Q$는 "$x^2 \ne y^2$"이고, 대우는 "실수 $x, y \ge 0$에 대해, $x^2 = y^2$이면 $x = y$이다"이다. 조건 "$x, y \ge 0$"은 무대이므로 부정되지 않고 대우에도 그대로 붙는다. 이 조건을 함께 부정해 "$x < 0$ 또는 $y < 0$"으로 옮기면 원명제와 무관한 명제가 만들어진다. 문제 17이 이 명제이고, 무대를 지우면 명제 자체가 거짓이 되는 것도 거기서 확인한다. ::: ### 5 언제 갈아타는가 — 신호 세 가지 [백지 암기 대상] 대우가 항상 유리한 것은 아니다. 갈아탈 자리를 알려 주는 신호는 세 가지다. | **신호** | **직접 증명에서 무엇이 막히는가** | **대우로 뒤집으면** | **예** | |---|---|---|---| | 가정이 $n^2$, $n^3$, $5n+3$ 등 **합성된 식**의 성질 | 등식의 좌변이 합성식이라 변수 자체를 꺼낼 수 없다 | 가정이 변수 자체의 성질이 되어 정의가 즉시 풀린다 | $n^2$ 짝수 $\Rightarrow$ $n$ 짝수 (예제 2.1), $3 \mid n^2 \Rightarrow 3 \mid n$ (예제 2.2) | | 가정이나 결론이 **부정형** ("~아니다", $\nmid$, $\ne$, 무리수) | 부정형에는 풀어 쓸 정의 꼴이 없다 | 부정형이 긍정형이 되어 정의를 가진 개념으로 바뀐다 | $3 \nmid n^2 \Rightarrow 3 \nmid n$ (문제 14) | | 결론이 **"또는"** 또는 **"그리고"** | 어느 쪽이 참인지 지목할 수 없거나, 두 주장을 한꺼번에 만들어야 한다 | "또는" 결론은 드모르간 2로 "그리고" 가정 두 개가 되고, "그리고" 결론은 드모르간 1로 "또는" 가정이 되어 경우 나누기로 처리된다 | $x + y > 10 \Rightarrow x > 5 \lor y > 5$ (예제 2.3), $xy$ 홀수 $\Rightarrow$ $x, y$ 모두 홀수 (문제 10) | 세 신호의 공통 원리는 하나다. **대우를 취하면 가정과 결론이 자리를 바꾸므로, 다루기 쉬운 쪽이 가정이 되도록 방향을 고르는 것**이다. 직접이 쉬우면 직접, 대우가 쉬우면 대우이며, 기법 선택은 취향이 아니라 문제 문장이 정한다 (기법 선택의 집중 훈련은 23주차다). :::{container} quotebox **확인 6.** 다음 세 명제에 대해 직접$\cdot$대우 중 유리한 쪽과 그 신호를 골라 보자. (가) $n$이 홀수이면 $n^3$은 홀수이다. (나) $n^3$이 짝수이면 $n$은 짝수이다. (다) $a \mid b$이면 $a \mid bc$이다. ::: :::{admonition} 답 :class: quotebox dropdown (가) 직접 — 가정 "$n$ 홀수"가 $n = 2a+1$로 즉시 풀린다. 신호가 하나도 없다. (나) 대우 — 가정 "$n^3$ 짝수"가 합성식이라 $n$을 꺼낼 수 없다(신호 1). 대우의 가정 "$n$ 홀수"는 즉시 풀린다. 문제 8이 이 명제다. (다) 직접 — 가정도 결론도 긍정형이고 정의가 바로 풀린다(2주차 훈련 1). 신호가 없을 때 대우로 가면 오히려 부정형 두 개를 다루게 되어 어려워진다. ::: ### 6 근거 목록 갱신 — 칸은 그대로 네 개 1~2주차에서 세운 근거 목록의 칸은 이번 주에도 네 개다. 이번 주가 채우는 것은 ①과 ④이며, ④에 새 항목이 추가되는 것이 아니라 이미 등록되어 있던 항목 하나가 처음으로 소비된다. | **근거** | **이번 주에 추가$\cdot$갱신되는 것** | **이번 주에는 이렇게 쓴다** | |---|---|---| | ① 정의 | **정의 19.1**(대우 증명) | 원명제를 대우로 번역한다. 몸통에서는 짝수$\cdot$나누어떨어짐$\cdot$유리수 등 기존 정의를 그대로 푼다 | | ② 닫힘성 | 변화 없음 | "$2k^2 + 2k$는 정수이므로"를 별도 설명 없이 쓴다 | | ③ 등식$\cdot$부등식의 성질 | 변화 없음 | 전개$\cdot$묶기$\cdot$대입, 부등식의 양변 연산 (W2)(W3)과 추이성 (W6) | | ④ 이미 증명한 명제 | **대우 동치**(9주차 예제 2.1)가 증명 기법으로 처음 소비된다. 부정 규칙 총목록(11주차), 나눗셈 정리(인정하고 사용), 1$\cdot$15$\cdot$17주차의 기증명 명제들이 몸통의 부품이 된다 | 회수 문장 "대우가 증명되었으므로 원명제도 성립한다"의 근거가 ④다 | 목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 §1.1에서 시도한 "양변에 제곱근을 취한다"는 목록에 없다 — 근호를 씌운 값이 정수라는 보장이 근거 ①~④ 어디에도 없기 때문이다. :::{container} quotebox **확인 7.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) "대우가 증명되었으므로 원명제도 성립한다." (나) "$n^2 = 2k$이므로 $n = \sqrt{2k}$는 정수이다." (다) "결론의 부정은 드모르간에 의해 '$x \le 5$이고 $y \le 5$'이다." ::: :::{admonition} 답 :class: quotebox dropdown (가) 허용 — 근거 ④. 인용하는 것은 9주차 예제 2.1에서 진리표로 증명한 동치다. 이 한 줄이 대우 증명의 결과를 원명제로 옮기는 유일한 통로다. (나) 불허 — 목록 밖이다. 제곱근을 취하는 조작 자체가 근거 ①~④에 없고, $\sqrt{2k}$가 정수라는 주장에는 근거가 붙어 있지 않다. (다) 허용 — 근거 ④. 드모르간 2는 9주차 동치 목록에 있고, 11주차 부정 규칙 총목록에 같은 줄이 등록되어 있다. 규칙 이름을 대는 것까지가 근거다. :::