19주차 — 대우 증명 (Contrapositive Proof)

이 주의 길잡이

핵심 문장: 대우 증명은 새 논리가 아니라, 원명제와 동치인 명제 중 다루기 쉬운 쪽을 골라 직접 증명하는 것이다.

이 주의 위치: 50주 과정의 19주차. 5부(간접 증명)의 개막 — 1주차 문제 11 해설이 예고했던 막힘을 처음으로 해결한다.

원서 대응: BoP(Book of Proof) 5.1 (Contrapositive Proof). 원서 없이 읽을 수 있다.

이번 주 목표

1. 대우 증명의 서식을 백지에 쓰고, 대우를 부정 규칙(11주차)으로 정확히 제작할 수 있다.

2. 직접 증명이 막히는 신호 세 가지를 읽고 대우로 갈아탈 수 있다.

3. 대우의 몸통에 경우 나누기(17주차)와 기증명 명제(1\(\cdot\)15\(\cdot\)17주차)를 겹쳐 쓸 수 있다.

4. 대우와 이(inverse)를 구별하고, 무대 조건이 부정되지 않는 이유를 설명할 수 있다.

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

준비 운동 (18주차 복습)

1. “\(n\)이 홀수이면 \(n^2\)은 홀수이다”를 안 보고 증명하시오 (1주차 문제 11 — 이번 주의 핵심 부품).

2. \(n^2\)을 3으로 나눈 나머지가 0 또는 1임을 증명하는 분할은 무엇인지 쓰시오 (17주차 문제 8).

3. “\(P \Rightarrow Q\)”의 대우를 쓰고, 둘이 동치인 근거가 몇 주차의 무엇인지 쓰시오.

4. 정수 \(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번을 끝까지 밀어붙여 보자.

시도 — 직접 증명으로 밀어붙이기

명제: 정수 \(n\)에 대해, \(n^2\)이 짝수이면 \(n\)은 짝수이다.

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

목표는 \(n = 2 \times (\text{정수})\) 꼴을 만드는 것이다.

그런데 손에 있는 등식의 좌변은 \(n^2\)이므로, \(n\)을 얻으려면 …”

여기서 멈춘다. 다음 줄이 나오지 않는다.

확인 1. 멈춘 자리에서 다음 줄이 나오려면 \(n\)에 대해 어떤 종류의

정보가 필요한가. 그리고 지금 손에 있는 등식은 그것을 주는가.

답

“\(n\)은 (무엇)과 같다” 꼴의 등식, 곧 좌변이 \(n\)인 등식이 필요하다. 손에 있는 것은 좌변이 \(n^2\)인 등식뿐이다. \(n^2 = 2k\)의 양변에

제곱근을 취하면 \(|n| = \sqrt{2k}\)가 나올 뿐 \(n\)에 대한 등식이 아니고(\(n\)은 음수일 수 있다), 그 값이 정수라는 근거도 없다 — 근거 목록에 없는

조작이므로 증명의 줄로 쓸 수 없다. 곧 가정 쪽에서 정보를 꺼낼 수 없는 막힘이다 (18주차 §1의 신호 첫 줄).

막힌 것은 도구가 아니라 명제의 방향이다. 같은 소재로 방향만 뒤집은 “\(n\)이 짝수이면 \(n^2\)은 짝수이다”는 가정이 \(n\)에 대한 것이라 정의가 즉시 풀리고, 1주차 문제 9에서 이미 증명해 두었다. 곧 소재는 같은데 한 방향은 막히고 다른 방향은 열려 있다.

그렇다고 열린 쪽을 증명하고 끝낼 수는 없다. 열린 쪽은 원명제의 역이고, 역은 원명제와 동치가 아니다(9주차 §1.7). 준비 운동의 유형 2가 정확히 이 자리에서 멈춘 답안이다.

이 주 전체의 기준

막힌 명제를 버리지 않는다. 그 명제와 동치인 다른 명제를 찾아 그쪽을

직접 증명한다. 동치가 아닌 명제로 갈아타면 별개의 명제를 증명한 것이 된다.

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}\)

확인 2. 표의 빈칸 (1)~(4)를 채우고, 세 변형 중 갈아탈 수 있는 것이

어느 것인지 한 문장으로 적어 보자.

답

(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) [백지 암기 대상]

명제 “\(P\)이면 \(Q\)이다”의 대우 증명이란, 그 대우 “\(\neg Q\)이면 \(\neg P\)이다”를

직접 증명한 뒤, 동치 \(P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P\)(9주차 예제 2.1)를

근거로 원명제의 증명으로 삼는 것이다.

이 정의를 답안의 형식으로 옮기면 아래 다섯 줄이 된다. 이번 주의 모든 증명이 이 형식을 따른다.

백지 암기 대상

대우 증명의 서식

명제. \(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\)이다”	도착점 선언	대우의 결론에 정확히 도달했음을 확인한다
“대우가 증명되었으므로 원명제도 성립한다”	회수	동치(근거 ④)로 원명제를 되찾는다

조각 삭제 실험. 둘째 조각 “대우는 …이다”를 지워 보자. 그러면 답안에는 선언 한 줄과 몸통만 남고, 몸통은 어떤 명제를 증명하든 문법적으로는 매끄럽게 흘러간다.

확인 3. “대우는 …이다”라는 줄을 지우는 순간 정확히 무엇이 무너지는가.

(한 문제만의 문제인지, 대우 대신 이를 적은 답안은 어떻게 되는지 함께

생각해 보자.)

답

제작물을 검사할 자리가 사라진다. 대우 대신 이(inverse)를 만들어 놓고도 몸통은 끝까지 완주되고, 그 이가 마침 참인 명제라면 답안은 완성된 것처럼 보인다 —

원명제는 한 번도 다루어지지 않았는데도 그렇다. 곧 참인 다른 명제를 증명하고 끝내는 오류가 검사망을 통과한다. 문제 19가 정확히 이 사례이고, 서식의 둘째

줄은 그 오류를 답안 안에서 스스로 잡기 위한 장치다.

셋째 조각 “\(\neg Q\)라 가정하자”를 지워도 같은 종류의 붕괴가 일어난다 — 계산에 쓰인 등식들의 출처가 비어 몸통 전체가 가정 없는 주장이 된다.

4 대우 제작 — 부정 규칙이 소비되는 자리

대우를 만드는 절차는 세 걸음이다.

1. 명제를 “\(P\)이면 \(Q\)이다” 꼴로 정리하고 \(P\), \(Q\)를 식별한다.

2. 11주차 부정 규칙 총목록으로 \(\neg P\)와 \(\neg Q\)를 각각 만든다.

3. 자리를 바꿔 “\(\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주차)

확인 4. 명제 “정수 \(x, y\)에 대해, \(xy\)가 홀수이면 \(x\)와 \(y\)가 모두

홀수이다”의 대우를 만들어 보자. \(\neg Q\)부터 적는다:

\(\neg Q = \underline{\qquad}\), \(\neg P = \underline{\qquad}\),

대우 \(= \underline{\qquad}\).

답

\(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에서 확인한 것과 같은 이치다 — 무대는 주장의 내용이 아니라 심사가 벌어지는 범위의 선언이다.

확인 5. 명제 “실수 \(x, y \ge 0\)에 대해, \(x \ne y\)이면 \(x^2 \ne y^2\)이다”의

대우를 만들어 보자. 조건 “\(x, y \ge 0\)”은 어디로 가는가.

답

\(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주차다).

확인 6. 다음 세 명제에 대해 직접\(\cdot\)대우 중 유리한 쪽과 그 신호를 골라 보자.

(가) \(n\)이 홀수이면 \(n^3\)은 홀수이다.

(나) \(n^3\)이 짝수이면 \(n\)은 짝수이다.

(다) \(a \mid b\)이면 \(a \mid bc\)이다.

답

(가) 직접 — 가정 “\(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에서 시도한 “양변에 제곱근을 취한다”는 목록에 없다 — 근호를 씌운 값이 정수라는 보장이 근거 ①~④ 어디에도 없기 때문이다.

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

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

(가) “대우가 증명되었으므로 원명제도 성립한다.”

(나) “\(n^2 = 2k\)이므로 \(n = \sqrt{2k}\)는 정수이다.”

(다) “결론의 부정은 드모르간에 의해 ‘\(x \le 5\)이고 \(y \le 5\)’이다.”

답

(가) 허용 — 근거 ④. 인용하는 것은 9주차 예제 2.1에서 진리표로 증명한 동치다. 이 한 줄이 대우 증명의 결과를 원명제로 옮기는 유일한 통로다.

(나) 불허 — 목록 밖이다. 제곱근을 취하는 조작 자체가 근거 ①~④에 없고, \(\sqrt{2k}\)가 정수라는 주장에는 근거가 붙어 있지 않다.

(다) 허용 — 근거 ④. 드모르간 2는 9주차 동치 목록에 있고, 11주차 부정 규칙 총목록에 같은 줄이 등록되어 있다. 규칙 이름을 대는 것까지가 근거다.