9주차 · 강의 — 예제 · 연습 · 해설#
예제 — 동치 판정을 함께 만들기#
완성된 판정을 먼저 보이지 않는다. 예제 2.1은 표의 설계부터 결론 선언까지 한 걸음씩 만들고, 예제 2.2는 설계만 함께 하고, 예제 2.3은 처음부터 혼자 한다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.
예제 2.1 — 대우 동치의 증명 (진리표)#
명제. \(P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P\).
§1.1의 갈아타기가 성립하려면 이 동치가 증명되어야 한다. 이번 주 전체에서 가장 중요한 표다.
설계 — 쓰기 전에 정하는 두 가지. 증명 문제와 마찬가지로, 목표가 요구하는 것(도착점)과 쓸 수 있는 재료(출발점)를 먼저 정한다.
말 |
번역 |
|
|---|---|---|
목표 \(\to\) 도착점 |
두 명제가 동치 |
정의 9.1: 모든 행에서 두 열의 진리값이 일치함을 보인다 |
재료 \(\to\) 출발점 |
진리표 계산 규칙 |
\(\Rightarrow\)의 진리표(8주차), \(\neg\)의 값 뒤집기 |
확인 9. 표의 뼈대를 설계해 보자. 행은 몇 개인가. 왼쪽 명제
\(P \Rightarrow Q\)와 오른쪽 명제 \(\neg Q \Rightarrow \neg P\)의 열을 계산하기
위해 중간에 어떤 열이 더 필요한가.
답
변수가 \(P, Q\) 두 개이므로 \(2^2 = 4\)행. 왼쪽 \(P \Rightarrow Q\)는 \(P, Q\)
열에서 바로 계산되지만, 오른쪽 \(\neg Q \Rightarrow \neg P\)를 계산하려면
화살표의 앞뒤 재료인 \(\neg Q\) 열과 \(\neg P\) 열이 먼저 필요하다.
열의 순서는 곧 계산의 순서다:
\(P\), \(Q\), \(P \Rightarrow Q\), \(\neg Q\), \(\neg P\), \(\neg Q \Rightarrow \neg P\) — 여섯 열.
한 행씩 — 판단이 갈리는 행부터. \(\Rightarrow\) 열의 계산에서 조심할 곳은 화살표 앞이 T인데 뒤가 F인 경우뿐이다(8주차 — 그때만 F).
확인 10. 둘째 행(\(P\) = T, \(Q\) = F)을 채워 보자.
\(P \Rightarrow Q = \underline{\quad}\), \(\neg Q = \underline{\quad}\),
\(\neg P = \underline{\quad}\), \(\neg Q \Rightarrow \neg P = \underline{\quad}\).
답
\(P \Rightarrow Q\) = T\(\Rightarrow\)F = F. \(\neg Q\) = T, \(\neg P\) = F이므로
\(\neg Q \Rightarrow \neg P\) = T\(\Rightarrow\)F = F. 조건문이 무너지는 유일한 행에서
오른쪽 명제도 정확히 같은 이유(앞이 T, 뒤가 F)로 무너진다 — 이 행이
동치의 핵심 행이다.
확인 11. 셋째 행(\(P\) = F, \(Q\) = T)을 채워 보자.
\(P \Rightarrow Q = \underline{\quad}\), \(\neg Q \Rightarrow \neg P = \underline{\quad}\).
답
\(P \Rightarrow Q\) = F\(\Rightarrow\)T = T (앞이 거짓이므로 공허한 참 — 8주차).
\(\neg Q\) = F, \(\neg P\) = T이므로 \(\neg Q \Rightarrow \neg P\) = F\(\Rightarrow\)T = T —
역시 공허한 참. 일치한다. 남은 두 행(1행과 4행)은 양쪽 다 T가 나오는
쉬운 행이다 — 각자 채워서 아래 완성본과 대조해 보자.
완성본. 네 행을 모두 채우면 —
증명.
\(P\) |
\(Q\) |
\(P \Rightarrow Q\) |
\(\neg Q\) |
\(\neg P\) |
\(\neg Q \Rightarrow \neg P\) |
|---|---|---|---|---|---|
T |
T |
T |
F |
F |
T |
T |
F |
F |
T |
F |
F |
F |
T |
T |
F |
T |
T |
F |
F |
T |
T |
T |
T |
3열과 6열이 모든 행에서 일치하므로 동치이다. \(\blacksquare\)
각 단계가 왜 필요한지를 표로 정리하면 —
증명의 한 줄 |
왜 이 줄을 쓰는가? |
|---|---|
행 4개를 나열한다 (\(P\), \(Q\) 열) |
변수 2개의 조합 \(2^2 = 4\)가지가 검사 범위의 전부다 — 정의 9.1의 “모든 진리값 조합” |
\(P \Rightarrow Q\) 열을 계산한다 |
좌변 명제의 진리값 목록 — 대조의 한쪽을 마련한다 |
\(\neg Q\), \(\neg P\) 열을 계산한다 |
우변을 한 번에 계산할 수 없으므로 중간 재료를 열로 쪼갠다 — 누구나 검사할 수 있는 계산이 된다 |
\(\neg Q \Rightarrow \neg P\) 열을 계산한다 |
우변 명제의 진리값 목록 — 대조의 다른 쪽 |
3열과 6열을 행별로 대조하고 결론을 선언한다 |
전 행 일치가 정의 9.1의 합격 기준이다. 대조 결과의 선언까지가 증명이다 |
이 표 하나가 “모든 명제 쌍”을 처리하는 이유. \(P\)와 \(Q\) 자리에 구체적인 명제를 넣어 보자 — \(P\): “\(n^2\)이 짝수이다”, \(Q\): “\(n\)이 짝수이다” (준비 운동 4번의 명제다). 이 두 명제의 진리값이 어떤 조합이 되든 그 조합은 표의 네 행 중 하나이고, 그 행에서 3열과 6열의 값이 같다. 따라서 이 명제와 그 대우는 반드시 같은 진리값을 갖는다. 다른 어떤 명제 쌍을 넣어도 마찬가지다 — 문자 \(P, Q\)로 만든 표 하나가 무한히 많은 명제 쌍을 한 번에 처리한다. 1주차 확인 13에서 본 문자의 일반성이 명제 차원에서 반복된 것이다.
자주 하는 실수 — 중간 열 생략. 6열을 머릿속 계산으로 바로 적는 경우가 많다. 틀리지 않았더라도, 중간 열이 없는 표는 남이(그리고 일주일 뒤의 자신이) 검사할 수 없다. 열 하나가 계산 한 걸음이다 — 전부 적는다.
예제 2.2 — 역이 동치가 아님의 증명#
명제. \(P \Rightarrow Q \not\equiv Q \Rightarrow P\).
기호 \(\not\equiv\)는 “동치가 아니다”로 읽는다 — \(\equiv\)에 빗금을 그은 것이다. 이번에는 설계만 함께 하고, 증명은 완성된 산문으로 본다.
확인 12. 번역부터 해 보자. “동치가 아니다”를 정의 9.1로 번역하면
무엇을 제시해야 하는가. 4행 표 전체가 필요한가.
답
동치의 정의가 “모든 행에서 일치”이므로, 동치가 아니라는 주장은 “일치하지
않는 행이 존재한다”이다. 따라서 진리값이 갈리는 행 하나를 지목하고
그 행에서 양쪽 값을 실제로 계산해 보이면 끝난다 — 표 전체는 필요 없다.
후보 행은 예제 2.1에서 계산해 둔 행들 가운데서 고르면 된다.
증명. 동치가 아님은 진리값이 갈리는 행 하나로 충분하다. \(P\) = F, \(Q\) = T일 때: \(P \Rightarrow Q\)는 F\(\Rightarrow\)T = T이지만 \(Q \Rightarrow P\)는 T\(\Rightarrow\)F = F. 진리값이 다르므로 동치가 아니다. \(\blacksquare\)
동치 증명(예제 2.1)은 표 전체를 요구했고, 비동치 증명은 행 하나로 끝났다. “모든 행에서”라는 주장과 “그런 행이 존재한다”라는 주장이 요구하는 부담의 비대칭이다 — 10주차 양화사에서 이 비대칭을 정면으로 다룬다.
예제 2.3 — 문장의 대우·역 쓰기#
원명제. “정수 \(n\)에 대해, \(n^2\)이 짝수이면 \(n\)은 짝수이다.”
이번에는 설계부터 스스로 해 보자.
확인 13. 원명제의 \(P\)와 \(Q\)를 지목하고, 대우와 역을 만들어 보자.
\(P\): \(\underline{\qquad}\) / \(Q\): \(\underline{\qquad}\)
대우(\(\neg Q \Rightarrow \neg P\)): \(\underline{\qquad}\)
역(\(Q \Rightarrow P\)): \(\underline{\qquad}\)
답
\(P\): “\(n^2\)이 짝수이다” / \(Q\): “\(n\)이 짝수이다”.
대우: “\(n\)이 짝수가 아니면, \(n^2\)은 짝수가 아니다.”
역: “\(n\)이 짝수이면 \(n^2\)은 짝수이다.”
대우의 “짝수가 아니다”는 “홀수이다”로 바꿔 적을 수 있다 — 모든 정수는
짝수이거나 홀수이기 때문이다(1주차 문제 16에서 인정하고 쓴 사실,
33주차에서 증명). 부정을 긍정 낱말로 바꾸는 이 정리가 대우를 다루기 쉽게
만드는 마지막 손질이다.
정리하면.
대우: “\(n\)이 짝수가 아니면(= 홀수이면), \(n^2\)은 짝수가 아니다(= 홀수이다).”
역: “\(n\)이 짝수이면 \(n^2\)은 짝수이다.”
갈아타기의 완성. 원명제의 직접 증명은 §1.1에서 막혔다 — \(n^2 = 2k\)에서 \(n\)을 꺼낼 수 없었다. 그런데 방금 만든 대우 “홀수의 제곱은 홀수”는 1주차 문제 11에서 이미 증명되어 있다. 예제 2.1의 대우 동치에 의해 대우와 원명제는 모든 상황에서 같은 진리값을 가지므로, 대우의 증명은 곧 원명제의 증명이다. 준비 운동 4번의 막힘이 여기서 풀렸다 — 새 계산은 한 줄도 없었고, 필요한 것은 “갈아타도 된다”는 판정(근거 ④)뿐이었다. 이것이 19주차 대우 증명법의 원리 전부다.
역은 사정이 다르다. “짝수의 제곱은 짝수”(1주차 문제 9)로 따로 증명해야 하는 별개의 명제다. 원명제와 역이 둘 다 참인 것은 두 증명이 각각 이루어진 결과이지, 한쪽이 다른 쪽을 보장한 것이 아니다 — 2주차 문제 19의 해설에서 예고한 “명제와 역은 진위도 난이도도 별개”가 판정으로 확정된 것이다.
관찰 — 세 판정의 같은 뼈대#
예제 2.1, 2.2, 2.3은 소재가 다르지만 절차의 뼈대가 같다. 대응표의 빈칸을 채워 보자.
확인 14. 세 예제가 공통으로 밟은 걸음을 채워 보자.
① 주장을 정의 9.1로 번역한다 — 동치 주장은 “모든 행 일치”,
비동치 주장은 “\(\underline{\qquad}\)”.
② 번역이 요구하는 만큼 계산한다 — 동치는 표 \(\underline{\quad}\),
비동치는 행 \(\underline{\quad}\).
③ \(\underline{\qquad}\)를 선언한다.
답
① “갈리는 행의 존재” ② 전체 / 하나 ③ 대조 결과와 결론
(예제 2.1: “3열과 6열이 모든 행에서 일치하므로 동치이다” /
예제 2.2: “진리값이 다르므로 동치가 아니다”).
예제 2.3은 이 절차로 판정해 둔 동치(대우)를 근거 ④로 소비한 것이다 —
판정이 끝난 동치는 증명의 부품이 된다.
방금 확인한 뼈대에 이름을 붙인다.
백지 암기 대상
동치 판정의 두 모드
동치 주장(\(\equiv\))은 모든 행의 대조로, 비동치 주장(\(\not\equiv\))은 갈리는 행 하나로 판정한다.
판정을 통과한 동치는 근거 ④가 되어, 증명에서 명제를 같은 명제로 교체하는 데 쓴다.
빈칸 사다리 — 지지대를 하나씩 빼며#
필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.
훈련 1 ●○○ — 진리표 빈칸#
명제. \(\neg(P \lor Q) \equiv \neg P \land \neg Q\) (드모르간 2).
증명. 표의 빈칸을 채운다.
\(P\) |
\(Q\) |
\(P \lor Q\) |
\(\neg(P \lor Q)\) |
\(\neg P\) |
\(\neg Q\) |
\(\neg P \land \neg Q\) |
|---|---|---|---|---|---|---|
T |
T |
T |
F |
F |
F |
\(\underline{\quad(1)\quad}\) |
T |
F |
\(\underline{\quad(2)\quad}\) |
\(\underline{\quad(3)\quad}\) |
F |
T |
F |
F |
T |
T |
F |
T |
F |
\(\underline{\quad(4)\quad}\) |
F |
F |
\(\underline{\quad(5)\quad}\) |
\(\underline{\quad(6)\quad}\) |
T |
T |
\(\underline{\quad(7)\quad}\) |
4열과 7열이 모든 행에서 일치하므로 동치이다. \(\blacksquare\)
훈련 2 ●●○ — 계산과 법칙 이름을 함께#
이번에는 진리표 없이, 목록의 법칙을 등식처럼 적용한다. 식과 법칙 이름이 모두 빈칸이다.
과제. \(\neg(\neg P \lor Q)\)를 부정 기호가 괄호 밖에 남지 않는 꼴로 바꾼다.
마무리 질문. \(\neg P \lor Q\)는 조건문 분해에 의해 \(\underline{\quad(5)\quad}\)와 동치이다. 따라서 방금 계산한 것은 그 명제의 부정이 \(P \land \neg Q\)와 동치라는 것 — 목록의 어느 줄을 유도한 셈인가: \(\underline{\quad(6)\quad}\).
(문제 18이 이 훈련의 완성형이다.)
훈련 3 ●●● — 뼈대만 남기고#
명제. 정수 \(n\)에 대해, \(5n + 3\)이 짝수이면 \(n\)은 홀수이다.
가정 “\(5n + 3\)이 짝수”를 정의로 풀어도 \(5n + 3 = 2k\)에서 \(n\)의 등식이 바로 나오지 않는다 — 대우로 갈아타면 가정이 다루기 쉬워진다. 절차의 각 칸을 통째로 채운다.
① 대우 만들기: \(\underline{\quad(1)\quad}\)
② 대우를 1주차의 3단계 틀로 증명: \(\underline{\quad(2)\quad}\)
③ 원명제로 돌아오는 결론 선언 (근거 포함): \(\underline{\quad(3)\quad}\)
(이 훈련이 문제 11의 예행연습이다.)
연습문제 (20문항)#
해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다.
이번 주의 채점 기준
답이 아니라 근거가 점수다. “동치다(맞음)”는 0점이고, 모든 행을 계산해
대조한 표(동치), 또는 갈리는 행 하나의 계산(비동치)이 만점이다.
부정 만들기 문제에서는 “아니다”가 문장 전체를 감싸고 있으면 아직 끝난 것이
아니다 — 법칙으로 괄호를 전부 해체해야 완결이다.
난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.
기본 ●○○#
1. 진리표로 드모르간 1 (\(\neg(P \land Q) \equiv \neg P \lor \neg Q\))을 증명하시오.
힌트
훈련 1의 표에서 \(\lor\)가 \(\land\)로, \(\land\)가 \(\lor\)로 바뀐 7열 표다.
최종 대조할 두 열이 몇 번째 열인지 먼저 정해 두고 계산한다.
§1.2에서 이미 채운 값들을 중간 열로 복원하는 작업이기도 하다.
2. 다음 명제의 역과 대우를 쓰시오 (한국어로). (a) 비가 오면 땅이 젖는다. (b) \(n\)이 6의 배수이면 \(n\)은 2의 배수이다. (c) \(x = 2\)이면 \(x^2 = 4\)이다.
힌트
역은 자리만 바꾸고, 대우는 자리를 바꾼 뒤 양쪽을 부정한다 — §1.7의 규칙을
기계적으로 적용한 뒤, 한국어 문장이 자연스러운지 확인한다.
3. 문제 2의 각 명제에 대해: 원명제의 진리값과 역의 진리값을 판정하시오 (거짓이면 반례).
힌트
원명제와 역은 독립적으로 판정한다 — 원명제가 참이어도 역의 진리값은
반례 수색으로 따로 정한다(§1.7의 규칙). (a)의 역이 무너지는 일상 사례를
하나 찾아보자 — 비 말고도 땅을 적시는 것이 있는가.
4. 다음 명제의 대우를 쓰시오. (a) \(x \in A \cap B\)이면 \(x \in A\)이다. (b) \(n^2 \neq n\)이면 \(n \neq 1\)이다.
힌트
부정할 때 \(\in\)은 \(\notin\)으로, \(\neq\)는 \(=\)로 — 기호의 부정부터 정확히
만들고 자리를 바꾼다. (b)에서는 부정의 부정이 긍정으로 돌아온다.
5. 다음 동치 여부를 판정하시오 (동치면 근거 이름, 아니면 반례 행). (a) \(\neg(\neg P)\)와 \(P\) (b) \(P \land Q\)와 \(Q \land P\) (c) \(P \Rightarrow Q\)와 \(Q \Rightarrow P\)
힌트
목록(§1.6)에 있는 법칙이면 이름 인용으로 충분하다 — 이미 근거 ④다.
목록에 없으면 판정의 두 모드 중 하나로: 작은 표 전체, 또는 갈리는 행 하나.
(c)의 후보 행은 예제 2.2에서 찾아 두었다.
6. 다음 문장의 부정을 쓰시오 (드모르간 적용, “아니다”가 문장 전체를 감싸지 않게). (a) \(x > 0\) 이고 \(x < 5\) (b) \(n\)은 짝수이거나 \(n < 0\)이다
힌트
“이고” \(\leftrightarrow\) “이거나”를 뒤집고 각 조각을 부정한다(드모르간).
부등호의 부정은 여집합 방향이다: \(>\)의 부정은 \(\le\), \(<\)의 부정은 \(\ge\).
표준 ●●○#
7. 진리표로 \(\neg(P \Rightarrow Q) \equiv P \land \neg Q\)를 증명하시오.
힌트
좌변 열은 8주차 진리표에서 F였던 행만 T가 된다. 우변 \(P \land \neg Q\) 열이
정확히 그 행에서만 T인지 대조한다 — 확인 7에서 관찰은 끝냈고, 이제 여섯 열
표로 완성하는 일만 남았다.
8. 다음 문장의 부정을 쓰시오 (부정 기호나 “아니다”가 문장 전체를 감싸지 않는, 풀어헤친 형태로). (a) \(x \ge 0\) 또는 \(x \le -3\) (b) \(n\)은 짝수이고 소수이다. (c) \(a \mid b\)이면 \(a \mid b^2\)이다. (d) \(x \in A \cup B\) (힌트: 합집합 정의 \(\to\) 드모르간)
힌트
문장의 구조(또는 / 그리고 / 이면 / 집합 기호)부터 식별하고, 구조에 맞는
부정 법칙을 목록에서 고른다. (c)는 조건문의 부정 — “인데” 문장이 된다.
(d)는 \(\in\)과 \(\cup\)의 정의로 \(\lor\) 문장으로 바꾼 뒤에 드모르간을 쓴다.
9. \((P \Rightarrow Q) \land (Q \Rightarrow R)\)이 참일 때 \(P \Rightarrow R\)도 참인가? 진리표(8행) 또는 논증으로 판정하시오. 이 성질의 이름(수학에서 익숙한 구조)을 붙여 보시오.
힌트
8행 표(확인 4)도 좋지만, “\(P\)가 참이라 하자”로 시작해 화살표 두 개를
차례로 통과하는 논증이 더 짧다. \(P\)가 거짓인 경우는 조건문이 어떻게
처리해 주는가(8주차의 공허한 참).
10. 다음 추론의 오류를 논리 용어로 지적하시오: “미분가능하면 연속이다. \(f\)는 연속이다. 따라서 \(f\)는 미분가능하다.”
힌트
전제와 결론을 화살표로 적어 놓고, 결론에 도달하는 데 실제로 쓴 화살표가
원명제인지 그 변형인지 본다. §1.7의 표에서 원명제와 동치가 아니었던
변형이 무엇이었는지 떠올린다.
11. 명제 “정수 \(n\)에 대해, \(3n + 5\)가 짝수이면 \(n\)은 홀수이다”의 대우를 쓰고, 그 대우를 1주차 방식(정의 대입)으로 증명하시오. 이로써 원명제도 증명되었다고 말할 수 있는 근거는 무엇인가?
힌트
대우를 만들 때 부정을 정확히 — “\(3n+5\)가 짝수”의 부정은 “\(3n+5\)가 홀수”,
“\(n\)이 홀수”의 부정은 “\(n\)이 짝수”. 자리 교환까지 마치면 가정이
“\(n = 2k\)”로 풀리는 다루기 쉬운 명제가 된다. 훈련 3에서 걸은 절차 그대로다.
12. 원명제 “\(n\)이 6의 배수이면 \(n\)은 짝수이다”에 대해 역\(\cdot\)이\(\cdot\)대우를 쓰고 각각의 진리값을 판정하시오 (거짓이면 반례).
힌트
네 판정 중 실제 계산이 필요한 것은 둘뿐이다 — 대우는 원명제와, 이는 역과
진리값이 항상 같다(§1.7, 확인 6). 어느 둘만 판정하면 되는가.
13. \(P \Rightarrow Q\)와 이(\(\neg P \Rightarrow \neg Q\))가 동치가 아님을 반례 행 하나로 보이시오.
힌트
예제 2.2에서 역을 무너뜨린 행(\(P\) = F, \(Q\) = T)을 이에도 시험해 본다.
14. “실수 \(x\)에 대해, \(x^2 \neq 4\)이면 \(x \neq 2\)이다”가 참임을 대우를 이용해 한 줄로 설명하시오.
힌트
대우를 만들면 \(\neq\)가 전부 \(=\)로 바뀐다 — 문제 4(b)에서 이미 걸은 길이다.
대입 한 번으로 확인되는 명제가 나온다.
도전 ●●●#
15. \(P \iff Q \equiv (P \land Q) \lor (\neg P \land \neg Q)\)를 진리표로 증명하시오. 오른쪽 식을 말로 풀면 왜 “같은 진리값”인지 해석하시오.
힌트
우변이 T가 되는 행을 먼저 예상해 보자 — \(P \land Q\)는 “둘 다 T”인 행을,
\(\neg P \land \neg Q\)는 “둘 다 F”인 행을 각각 담당하고 \(\lor\)로 합쳐진다.
예상을 적어 두고 표와 대조하면 계산 실수가 걸러진다.
이 문제가 빌려 쓰는 사고 — 가정하고 충돌을 확인하기
아래 문제 16에서 A의 정체는 두 가지(기사/건달) 중 하나다. 이럴 때는 한쪽을
가정하고, 그 가정 아래에서 발언의 진리값을 계산한 뒤, 가정과 계산 결과가
충돌하는지 본다. 충돌하면 그 가정은 기각되고 남는 쪽이 정체다.
결론의 후보를 가정으로 세워 모순으로 기각하는 이 동선은 21주차 귀류법의
예행연습이다. 계산의 관건은 8주차의 공허한 참이다.
16. 어떤 섬에 “기사(항상 참말)”와 “건달(항상 거짓말)”만 산다. 주민 A가 말했다: “내가 기사라면, 보물은 동쪽에 있다.” A의 정체와 보물의 위치를 논리로 추론하시오. (힌트: A가 건달이라 가정하면 A의 발언은 거짓이어야 한다. 그런데 A가 건달이면 “내가 기사”가 거짓이므로 발언 전체는 공허한 참 — 모순.)
새 작업 방식 — 진리표 없이, 법칙의 사슬로
문제 17~18은 표를 만들지 않는다. §1.6의 목록을 등식 변형처럼 한 단계씩
적용하고, 단계마다 사용한 법칙의 이름을 적는다 — 진리표로 증명해 둔 동치
(근거 ④)만으로 진행하는 첫 훈련이다. 훈련 2에서 같은 동선을 한 번 걸었다.
법칙은 양방향으로 쓸 수 있다 — 동치는 교체이므로 왼쪽을 오른쪽으로 바꾸는
것도, 오른쪽을 왼쪽으로 바꾸는 것도 허용된다.
17. 동치 법칙만으로(진리표 없이) 다음을 유도하시오: \(\neg\big(P \lor (Q \land R)\big) \equiv \neg P \land (\neg Q \lor \neg R)\). 각 단계에 사용한 법칙 이름을 쓰시오.
힌트
바깥 부정부터 한 겹씩 안으로 들여보낸다. 부정이 괄호를 뚫을 때마다
\(\lor\)와 \(\land\)가 한 번씩 뒤집힌다 — 두 번 뚫으면 두 번 뒤집힌다.
18. 동치 법칙만으로(진리표 없이) \(P \Rightarrow Q \equiv \neg(P \land \neg Q)\)를 유도하시오. (힌트: 조건문 분해 \(\to\) 이중부정 \(\to\) 드모르간)
힌트
문제의 힌트 순서대로 세 단계면 끝난다. 마지막 단계는 드모르간 1을
오른쪽에서 왼쪽으로 쓰는 것 — \(\neg P \lor \neg(\text{무엇})\) 꼴을
\(\neg(\,\cdot \land \cdot\,)\)로 묶는다.
19. \(P \iff Q\)와 \(\neg P \iff \neg Q\)가 동치임을 진리표로 확인하시오. 이 사실을 한 문장으로 해석하시오 (“쌍조건문의 \(\underline{\quad}\)는 자기 자신이다”).
힌트
여섯 열 표 — \(\neg P\), \(\neg Q\) 열을 중간 재료로 둔다. 해석 문장은 §1.7의
표에서 “대우 만들기”를 쌍조건문에 적용하면 무엇이 나오는지를 묻고 있다.
20. (서술) “반례”의 정의를 \(\neg(P \Rightarrow Q) \equiv P \land \neg Q\)로 설명하시오: 반례가 갖춰야 할 두 가지 조건은 무엇이며, 1주차 문제 18(\(n^2+n+41\))의 \(n = 40\)이 그 두 조건을 어떻게 만족하는가?
힌트
\(\land\)의 왼쪽 조각과 오른쪽 조각을 각각 “반례가 갖춰야 할 조건”으로 읽는다.
\(n = 40\)에 대해 두 조각을 하나씩 검증한다 — 가정 쪽 하나, 결론 쪽 하나.
백지 재현 — 복습 프로토콜#
권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.
1차 시도 (4일차) — 틀 카드 허용. 동치 목록(§1.6)과 판정의 두 모드 카드만 펴 놓고, 예제 2.1을 표의 설계부터 결론 선언까지 적는다. 본문은 보지 않는다.
2차 시도 (5일차) — 완전 백지. 아무것도 보지 않고 수행한다:
정의 9.1을 조각 그대로 썼다 (“모든 진리값 조합에서 같은 진리값”까지).
동치 목록 8개를 백지에 썼다 (이중부정 / 드모르간 2개 / 조건문 분해 / 대우 / 조건문의 부정 / 분배 2개).
분배 1\(\cdot\)2를 각각 8행 표로 검증했다 (§1.6 — 확인 4의 요령. 검증해야 근거 ④에 등록된다).
대우 동치를 여섯 열 진리표로 증명했다 (예제 2.1 재현 — 결론 선언까지).
역이 동치가 아님을 갈리는 행 하나로 보였다 (예제 2.2 재현).
“조건문의 부정은 그리고-문장”을 예와 함께 설명했다.
예제 2.3의 갈아타기(막힌 직접 증명 \(\to\) 이미 증명된 대우 \(\to\) 원명제 완성)를 말로 재현했다.
막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.
막힌 지점 |
처방 |
|---|---|
목록 8개가 다 나오지 않는다 |
§1.6 — 드모르간 2개는 말(“괄호를 뚫으면 뒤집힌다”)과 함께, 조건문 계열 3개는 문제 7\(\cdot\)18의 유도와 함께 다시 외운다 |
표의 행 수\(\cdot\)열 설계가 나오지 않는다 |
예제 2.1의 설계(확인 9) — 행은 \(2^n\), 열은 계산 순서다 |
\(\Rightarrow\) 열의 값이 틀린다 |
8주차 §1 — F는 T\(\Rightarrow\)F 한 경우뿐이고, 앞이 F이면 공허한 참이다 |
역\(\cdot\)이\(\cdot\)대우 만들기가 뒤섞인다 |
§1.7 — 역은 자리만, 이는 부정만, 대우는 둘 다 |
부정을 만들면 “이면”이 남는다 |
§1.8 — 조건문의 부정은 조건문이 아니라 \(\land\) 문장이다 |
하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.
해설#
각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.
빈칸 사다리 — 훈련 1#
(1) F (2) T (3) F (4) F (5) F (6) T (7) T
※ 4열은 3열의 값 뒤집기, 7열은 5\(\cdot\)6열의 \(\land\) — 열마다 계산 규칙이 다르다. 4열과 7열이 (F, F, F, T)로 완전히 일치하므로 드모르간 2가 증명되어 근거 ④에 등록된다. “\(\lor\)의 부정에서만 T가 남는 행은 둘 다 F인 마지막 행뿐”이라는 관찰까지 하면 표를 다 외우지 않아도 재구성할 수 있다.
빈칸 사다리 — 훈련 2#
(1) \(\neg Q\) (2) 드모르간 2 (3) \(P\) (4) 이중부정 (5) \(P \Rightarrow Q\) (6) 조건문의 부정
※ 부정이 \(\lor\) 괄호를 뚫으며 \(\land\)로 뒤집히고(드모르간 2), \(\neg(\neg P)\)가 \(P\)로 돌아왔다(이중부정). 마무리 질문의 답: \(\neg P \lor Q \equiv P \Rightarrow Q\) (조건문 분해, 8주차 문제 15)이므로, 방금 계산한 것은 \(\neg(P \Rightarrow Q) \equiv P \land \neg Q\) — 목록의 “조건문의 부정”을 법칙의 사슬만으로 유도한 것이다. 문제 18이 같은 유도의 완성형이다.
빈칸 사다리 — 훈련 3#
(1) 대우: “\(n\)이 짝수이면, \(5n + 3\)은 홀수이다.” (2) 증명: \(n\)을 짝수라 하자. 정의에 의해 \(n = 2k\)인 정수 \(k\)가 존재한다. 그러면
이고 \(5k + 1\)은 정수이므로 \(5n + 3\)은 홀수이다. \(\blacksquare\) (3) 대우가 참이고, 예제 2.1의 대우 동치(근거 ④)에 의해 대우와 원명제는 같은 진리값을 가지므로, 원명제도 참이다.
※ 원명제의 가정(”\(5n+3\)이 짝수”)은 풀어도 \(n\)의 등식이 나오지 않지만, 대우의 가정(”\(n\)이 짝수”)은 즉시 \(n = 2k\)로 풀린다 — 갈아타기가 이득이 되는 전형적 신호다. 19주차에서 이 신호를 목록으로 정리한다.
문제 1#
접근. 4행 표에 좌변(\(P \land Q\)를 계산한 뒤 부정)과 우변(\(\neg P\), \(\neg Q\)를 만든 뒤 \(\lor\))을 나란히 쌓고, 최종 두 열을 행별로 대조한다. 대조할 열이 4열과 7열임을 계산 전에 정해 두면 길을 잃지 않는다.
풀이.
\(P\) |
\(Q\) |
\(P \land Q\) |
\(\neg(P \land Q)\) |
\(\neg P\) |
\(\neg Q\) |
\(\neg P \lor \neg Q\) |
|---|---|---|---|---|---|---|
T |
T |
T |
F |
F |
F |
F |
T |
F |
F |
T |
F |
T |
T |
F |
T |
F |
T |
T |
F |
T |
F |
F |
F |
T |
T |
T |
T |
4열과 7열이 모든 행에서 (F, T, T, T)로 일치하므로 동치이다. \(\blacksquare\)
복기. “\(\land\)의 부정이 F가 되는 행은 둘 다 T인 첫 행뿐” — 훈련 1 (드모르간 2)의 관찰과 정확히 대칭이다. 이 두 표가 5주차의 집합 등식 \((A \cap B)^c = A^c \cup B^c\), \((A \cup B)^c = A^c \cap B^c\)의 논리적 원본이고, 그 연결의 계산은 문제 8(d)에서 밟는다.
문제 2#
접근. 역은 \(P\)\(\cdot\)\(Q\)의 자리 교환, 대우는 교환에 더해 양쪽 부정 — §1.7의 규칙을 기계적으로 적용한 뒤, 만들어진 한국어 문장이 자연스러운지와 부정이 정확한지(“젖지 않았다”, “배수가 아니다”)를 검사한다.
풀이. (a) 역: “땅이 젖으면 비가 온 것이다.” / 대우: “땅이 젖지 않았으면 비가 오지 않은 것이다.” (b) 역: “\(n\)이 2의 배수이면 6의 배수이다.” / 대우: “\(n\)이 2의 배수가 아니면 6의 배수가 아니다.” (c) 역: “\(x^2 = 4\)이면 \(x = 2\)이다.” / 대우: “\(x^2 \neq 4\)이면 \(x \neq 2\)이다.”
복기. 부정만 하고 자리를 바꾸지 않으면 대우가 아니라 이가 된다 (문제 13에서 이가 동치가 아님을 확인한다). 대우를 만들 때는 마지막에 “교환과 부정을 둘 다 했는가”를 점검한다 — 조작이 두 개라 하나가 빠지기 쉽다.
문제 3#
접근. 원명제와 역은 독립적으로 판정한다 — 원명제가 참이어도 역은 반례 수색의 대상이다(§1.7). 거짓 판정에는 반례를 완전 서식으로: 가정이 참임을 확인하고, 결론이 거짓임을 확인한다(2주차 도전 문제에서 세운 서식).
풀이. (a) 원명제: 참 (일상 명제로 인정한다). 역 “땅이 젖으면 비가 온 것이다”: 거짓 — 스프링클러가 물을 뿌린 경우, 땅이 젖었지만(역의 가정 참) 비는 오지 않았다(역의 결론 거짓). (b) 원명제: 참 — \(n = 6k\)인 정수 \(k\)가 존재하면 \(n = 2(3k)\)이고 \(3k \in \mathbb{Z}\)이므로 \(n\)은 2의 배수다. 역 “2의 배수이면 6의 배수”: 거짓 — 반례 \(n = 2\). \(2 = 2 \times 1\)이므로 2의 배수이지만, \(2 = 6c\)인 정수 \(c\)는 없다(\(c = \frac{1}{3} \notin \mathbb{Z}\)). (c) 원명제: 참 — \(x = 2\)를 대입하면 \(x^2 = 4\). 역 “\(x^2 = 4\)이면 \(x = 2\)”: 거짓 — 반례 \(x = -2\). \((-2)^2 = 4\)이므로 가정은 참이지만 \(-2 \neq 2\)이므로 결론은 거짓이다.
복기. 세 명제 모두 원명제는 참인데 역은 거짓이다 — “참인 명제의 역은 검증 전까지 별개의 미확정 명제”라는 §1.7의 규칙이 세 번 확인됐다. (c)의 반례 \(-2\)는 제곱이 부호를 지운다는 사실에서 나온다 — 25주차(iff)와 41주차(단사)에서 같은 반례가 계속 일한다.
문제 4#
접근. 대우 = 자리 교환 + 양쪽 부정. 부정할 때 \(\in\)은 \(\notin\)으로, \(\neq\)는 \(=\)로 — 기호마다 정확한 부정 상대가 있다.
풀이. (a) 원명제의 \(P\): “\(x \in A \cap B\)”, \(Q\): “\(x \in A\)”. 대우: “\(x \notin A\)이면 \(x \notin A \cap B\)이다.” (b) 원명제의 \(P\): “\(n^2 \neq n\)”, \(Q\): “\(n \neq 1\)”. 부정하면 \(\neq\)가 \(=\)로 돌아온다. 대우: “\(n = 1\)이면 \(n^2 = n\)이다.”
복기. (b)의 대우는 대입 한 번(\(1^2 = 1\))으로 참임이 확인된다 — 예제 2.1의 동치에 의해 원명제도 참이다. 부정형 가정(\(\neq\))은 전개할 등식이 없어 다루기 어렵지만, 대우로 뒤집으면 긍정형 등식이 된다. 대우 증명이 이득이 되는 신호의 미니 체험이고, 문제 14가 같은 구조의 실수 버전이다.
문제 5#
접근. 목록에 있는 법칙이면 이름 인용(근거 ④)으로 충분하다. 목록에 없으면 판정의 두 모드 — 동치 주장은 작은 표 전체, 비동치 주장은 갈리는 행 하나.
풀이. (a) 동치 — 이중부정 법칙. 확인 5에서 2행 표로 검증해 근거 ④에 올려 두었다. (b) 동치 — \(\land\)의 교환법칙. 목록에는 없지만 4행 표로 즉시 확인된다: \(P \land Q\)와 \(Q \land P\)는 “둘 다 T”인 첫 행에서만 T이고 나머지 세 행에서 F로, 열이 완전히 같다. (c) 동치 아님 — \(P\) = F, \(Q\) = T에서 \(P \Rightarrow Q\)는 F\(\Rightarrow\)T = T, \(Q \Rightarrow P\)는 T\(\Rightarrow\)F = F로 갈린다 (예제 2.2의 그 행).
복기. 세 항목이 판정의 세 갈래를 하나씩 보여 준다 — 이름 인용 / 새로 표 검증 / 반례 행. 어느 갈래로 갈지는 “목록에 있는가”와 “동치로 보이는가”의 두 질문으로 정해진다.
문제 6#
접근. 드모르간 — “이고”와 “이거나”를 서로 뒤집고 각 조각을 부정한다. 부등호의 부정은 여집합 방향(\(>\) \(\leftrightarrow\) \(\le\), \(<\) \(\leftrightarrow\) \(\ge\))이다.
풀이. (a) 원문장은 “\(x > 0\) \(\land\) \(x < 5\)”. 드모르간 1로 부정하면 각 조각이 부정되며 \(\lor\)로 바뀐다: “\(x \le 0\) 이거나 \(x \ge 5\)”. (b) 원문장은 “(\(n\) 짝수) \(\lor\) (\(n < 0\))”. 드모르간 2로: “\(n\)은 홀수이고 \(n \ge 0\)이다” (“짝수가 아니다”는 “홀수이다”로 — 예제 2.3의 손질).
검산: \(n = 4\)이면 원문장 참(짝수), 부정 거짓(홀수가 아님) — 정확히 반대다 ✓.
복기. 원문장과 부정은 모든 대상에서 진리값이 반대여야 한다. 아무 값이나 하나 대입해 반대가 되는지 보는 검산이 드모르간 적용 실수를 잡아 준다.
문제 7#
접근. 좌변 \(\neg(P \Rightarrow Q)\)의 열은 8주차 진리표에서 F였던 행만 T가 된다. 우변 \(P \land \neg Q\)의 열이 정확히 그 행에서만 T인지 여섯 열 표로 대조한다 — 확인 7의 관찰을 표로 완성하는 작업이다.
풀이.
\(P\) |
\(Q\) |
\(P \Rightarrow Q\) |
\(\neg(P \Rightarrow Q)\) |
\(\neg Q\) |
\(P \land \neg Q\) |
|---|---|---|---|---|---|
T |
T |
T |
F |
F |
F |
T |
F |
F |
T |
T |
T |
F |
T |
T |
F |
F |
F |
F |
F |
T |
F |
T |
F |
4열과 6열이 모든 행에서 (F, T, F, F)로 일치하므로 동치이다. \(\blacksquare\)
복기. T가 단 한 행 — 조건문이 무너지는 그 행뿐이다. “조건문의 부정은 가정이 성립하는데 결론이 무너지는 사례의 존재”라는 읽기가 이 표의 내용 전부이고, 반례의 정의(문제 20)와 반증(29주차)이 전부 이 한 줄 위에 선다.
문제 8#
접근. 문장의 구조(또는 / 그리고 / 이면 / 집합 기호)를 먼저 식별하고, 구조에 대응하는 부정 법칙을 목록에서 고른다. 조건문의 부정은 “인데” 문장이 된다 — “이면”이 남아 있으면 다시 본다(§1.8).
풀이. (a) 구조는 \(\lor\). 드모르간 2로: “\(x < 0\) 그리고 \(x > -3\)” (\(\ge\)의 부정은 \(<\), \(\le\)의 부정은 \(>\)). 두 조건을 겹치면 \(-3 < x < 0\) — 부정이 열린 구간 하나로 정리된다. (b) 구조는 \(\land\). 드모르간 1로: “\(n\)이 홀수이거나 소수가 아니다”. (c) 구조는 조건문. 조건문의 부정(\(P \land \neg Q\))으로: “\(a \mid b\)인데 \(a \nmid b^2\)이다”. “이면”이 사라지고 “인데”가 남았는지 점검한다. (d) \(x \in A \cup B\)는 합집합의 정의에 의해 “\(x \in A \lor x \in B\)”다. 드모르간 2로 부정하면 “\(x \notin A \land x \notin B\)”, 여집합 표기로는 \(x \in A^c \cap B^c\).
복기. (d)에서 \((A \cup B)^c\)의 원소 조건이 \(A^c \cap B^c\)의 원소 조건과 논리 법칙만으로 이어졌다 — 5주차에서 벤 다이어그램으로 관찰만 했던 집합 드모르간의 정체가 논리 드모르간이었던 것이다. 원소 추적에 의한 정식 증명은 27주차에서 완성한다.
문제 9#
접근. 변수 3개이므로 표는 8행(확인 4)이다. 표도 되지만, “\(P\)가 참이라 하자”로 시작해 두 화살표를 사슬로 통과하는 논증이 더 짧고 이후에 더 자주 쓰는 형태다. \(P\)가 거짓인 경우를 조건문이 어떻게 처리하는지도 빠뜨리지 않는다.
풀이. 참이다. 논증: 두 전제 \(P \Rightarrow Q\)와 \(Q \Rightarrow R\)이 참이라 하자. \(P \Rightarrow R\)이 참임을 보이면 된다. \(P\)가 참인 경우 — \(P \Rightarrow Q\)가 참이고 \(P\)가 참이므로 \(Q\)는 참이다. 다시 \(Q \Rightarrow R\)이 참이고 \(Q\)가 참이므로 \(R\)은 참이다. 따라서 이 경우 \(P \Rightarrow R\)은 T\(\Rightarrow\)T로 참이다. \(P\)가 거짓인 경우 — 조건문은 앞이 거짓이면 공허하게 참이므로(8주차) \(P \Rightarrow R\)은 자동으로 참이다. 모든 경우에 \(P \Rightarrow R\)이 참이다. \(\blacksquare\)
이름: 추이성(transitivity). 2주차 예제 2.1(\(\mid\)), 4주차(\(\subseteq\))에 이어 세 번째 만남이다 — “이면”의 사슬은 이어 붙일 수 있다.
복기. 화살표 사슬 잇기는 25주차(동치 사슬 \(P_1 \Rightarrow P_2 \Rightarrow \cdots\))에서 서식으로 승격된다. “앞이 거짓이면 공허한 참”으로 나머지 경우를 닫는 마무리도 함께 기억해 둔다.
문제 10#
접근. 전제 두 개(“미분가능 \(\Rightarrow\) 연속”, “\(f\)는 연속”)와 결론(”\(f\)는 미분가능”)을 화살표 그림으로 놓고, 결론으로 가는 데 실제로 어떤 화살표를 썼는지 본다 — 주어진 화살표인가, 그 역인가.
풀이. 역 긍정의 오류(affirming the converse)다. 이 추론이 결론에 도달하려면 “연속이면 미분가능”이라는 화살표가 필요한데, 그것은 전제 “미분가능하면 연속”의 역이다. 역은 원명제와 동치가 아니므로(예제 2.2) 전제에서 공짜로 나오지 않고, 이 경우 실제로 거짓이다 — 반례: \(f(x) = |x|\)는 \(x = 0\)에서 연속이지만 미분 불가능하다 (이 사실은 지금은 인정하고 쓴다 — 연속인 것의 증명은 47주차, 미분 불가능의 정밀한 처리는 대학 해석학에서 다룬다).
복기. 오류 판정의 절차 — 결론까지 실제로 쓰인 화살표를 그려 보고, 그중 전제에 없는 화살표(역\(\cdot\)이)가 끼어 있으면 그 자리가 오류다. 11주차의 추론 규칙 표에서 이 판정이 목록으로 정리된다.
문제 11#
접근. 대우부터 정확히 만든다 — 자리를 바꾸고 양쪽을 부정하면 “\(n\)이 짝수이면 \(3n + 5\)는 홀수이다”가 된다. 이 대우는 가정이 “\(n = 2k\)”로 풀리는 다루기 쉬운 꼴이므로 1주차의 3단계 틀이 그대로 작동한다(훈련 3의 절차).
풀이. 대우: “\(n\)이 짝수이면, \(3n + 5\)는 홀수이다.”
대우의 증명: \(n\)을 짝수라 하자. 정의에 의해 \(n = 2k\)인 정수 \(k\)가 존재한다. 그러면
이고 \(3k + 2 \in \mathbb{Z}\)이므로 \(3n + 5\)는 홀수이다. \(\blacksquare\)
원명제가 증명된 근거: 예제 2.1에서 진리표로 증명한 대우 동치 \(P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P\) (근거 ④)이다. 동치인 두 명제는 모든 상황에서 같은 진리값을 가지므로, 대우가 참임이 증명된 순간 그것과 동치인 원명제도 참이다. (이것이 19주차 대우 증명법의 공식 절차다.)
검산: \(n = 3\)이면 \(3n + 5 = 14\)로 짝수이고 3은 홀수 ✓ — 원명제의 사례 하나가 실제로 성립한다.
복기. 원명제의 가정 “\(3n + 5\)가 짝수”는 풀어도 \(n\)의 등식이 바로 나오지 않는다 — 가정이 합성식이고 결론이 단순식일 때 대우가 이득이라는 신호다. 19주차에서 신호 목록으로 정리된다.
문제 12#
접근. 세 변형을 기계적으로 만든 뒤, 실제 계산은 두 번만 한다 — 대우는 원명제와(예제 2.1), 이는 역과(서로 대우) 진리값이 같으므로, 원명제와 역만 판정하면 네 진리값이 전부 정해진다.
풀이. 원명제 “\(n\)이 6의 배수이면 \(n\)은 짝수이다”: 참 — \(n = 6k\)이면 \(n = 2(3k)\)이고 \(3k \in \mathbb{Z}\). 역 “\(n\)이 짝수이면 6의 배수이다”: 거짓 — 반례 \(n = 2\). \(2 = 2 \times 1\)로 짝수이지만 \(2 = 6c\)인 정수 \(c\)는 없다. 이 “\(n\)이 6의 배수가 아니면 짝수가 아니다”: 거짓 — 반례 \(n = 2\). 2는 6의 배수가 아니지만(가정 참) 짝수다(결론 거짓). 대우 “\(n\)이 짝수가 아니면 6의 배수가 아니다”: 참 — 원명제와 동치이므로 별도 계산 없이 따라온다.
복기. 역과 이에 같은 반례 \(n = 2\)가 통했다 — 역과 이는 서로 대우라서 진리값이 항상 같기 때문이다(확인 6). 넷 중 독립인 진리값은 두 개뿐이라는 구조를 알면 판정량이 절반이 된다.
문제 13#
접근. 갈리는 행 하나를 찾는다 — 역이 실패했던 행(\(P\) = F, \(Q\) = T)이 첫 후보다(예제 2.2). 이는 역과 진리값이 같으므로 같은 행에서 무너질 것이다.
풀이. \(P\) = F, \(Q\) = T인 행에서: \(P \Rightarrow Q\)는 F\(\Rightarrow\)T = T이지만, \(\neg P \Rightarrow \neg Q\)는 T\(\Rightarrow\)F = F다. 진리값이 갈리는 행이 존재하므로 두 명제는 동치가 아니다. \(\blacksquare\)
복기. 비동치 증명은 행 하나로 완결이다(판정의 두 모드). 그리고 이 행은 예제 2.2에서 역을 무너뜨린 행과 같다 — 이와 역이 서로 대우(동치)이므로 무너지는 자리도 같다. 반례 행을 재활용하는 감각도 부품 재사용의 일종이다.
문제 14#
접근. 대우로 갈아타면 무엇이 되는지 먼저 적는다 — \(\neq\)가 전부 \(=\)로 바뀐 긍정형 명제가 나오고, 대입 한 번으로 확인된다.
풀이. 대우는 “\(x = 2\)이면 \(x^2 = 4\)이다”인데, \(x = 2\)를 대입하면 \(2^2 = 4\)로 자명하게 참이다. 대우가 참이므로, 대우 동치(예제 2.1, 근거 ④)에 의해 원명제 “\(x^2 \neq 4\)이면 \(x \neq 2\)이다”도 참이다.
복기. 부정(\(\neq\))이 잔뜩 붙은 명제는 대우로 뒤집으면 긍정형이 되어 쉬워지는 경우가 많다 — 문제 4(b)와 같은 신호이고, 19주차 대우 증명에서 “가정이 부정형이면 대우를 검토한다”로 정식화된다.
문제 15#
접근. 4행 표. 우변은 두 조각의 \(\lor\)인데, \(P \land Q\)는 “둘 다 T”인 행을, \(\neg P \land \neg Q\)는 “둘 다 F”인 행을 각각 담당한다 — 이 예상을 적어 두고 표와 대조한다.
풀이.
\(P\) |
\(Q\) |
\(P \iff Q\) |
\(P \land Q\) |
\(\neg P \land \neg Q\) |
우변(\(\lor\)) |
|---|---|---|---|---|---|
T |
T |
T |
T |
F |
T |
T |
F |
F |
F |
F |
F |
F |
T |
F |
F |
F |
F |
F |
F |
T |
F |
T |
T |
3열과 6열이 모든 행에서 (T, F, F, T)로 일치하므로 동치이다. \(\blacksquare\)
해석: 쌍조건문 \(P \iff Q\)가 참인 경우는 “둘 다 참”이거나 “둘 다 거짓” — 곧 진리값이 같은 두 경우다. 우변은 그 두 경우를 \(\lor\)로 나열한 것이므로, “같은 진리값”이라는 말을 식으로 옮긴 것이 정확히 우변이다.
복기. 8주차 문제 4에서 \(P \iff Q\)를 \((P \Rightarrow Q) \land (Q \Rightarrow P)\)에서 유도해 (T, F, F, T) 열을 얻었다 — 같은 열이 다른 분해로 다시 나왔다. 한 명제에 동치인 꼴이 여럿이고, 어느 꼴을 쓸지는 용도가 정한다(25주차 iff 증명에서 회수).
문제 16#
접근. 정체의 후보가 두 가지뿐이므로, 한쪽을 가정하고 발언의 진리값을 계산해 가정과 충돌하는지 본다(문제 앞 상자의 동선). 건달 가정에서는 8주차의 공허한 참이 결정적으로 작동한다.
풀이. A의 발언을 조건문으로 적으면 — \(P\): “A는 기사이다”, \(Q\): “보물은 동쪽에 있다”, 발언: \(P \Rightarrow Q\).
A가 건달이라 가정하자. 건달의 모든 발언은 거짓이므로 \(P \Rightarrow Q\)는 거짓이어야 한다. 그런데 A가 건달이면 \(P\)(“A는 기사”)는 거짓이고, 앞이 거짓인 조건문은 공허하게 참이다(8주차). “발언이 거짓”과 “발언이 참”이 동시에 요구되어 모순이다 — 건달 가정은 기각된다.
정체는 두 가지뿐이므로 A는 기사다. 그러면 발언 \(P \Rightarrow Q\)는 참이고, \(P\)(“A는 기사”)도 참이므로, 조건문의 진리표에서 T\(\Rightarrow\)?가 참이려면 결론도 참일 수밖에 없다 — 보물은 동쪽에 있다.
검산: A가 기사이고 보물이 동쪽이면 발언은 T\(\Rightarrow\)T = T — 참말만 하는 기사와 일관된다 ✓.
복기. 결론의 후보를 가정으로 세우고 모순으로 기각하는 동선 — 21주차 귀류법의 사고가 퍼즐의 옷을 입고 먼저 온 것이다. 공허한 참이 “쓸모없는 규약”이 아니라 추론을 결정짓는 실전 부품임도 확인됐다(8주차 문제 20의 회수).
문제 17#
접근. 진리표 금지 = 목록의 동치를 등식 변형처럼 사슬로 적용하라는 뜻이다 (문제 앞 상자). 바깥 부정부터 한 겹씩 안으로 들여보내고, 단계마다 법칙 이름을 적는다.
풀이.
첫 단계에서 부정이 \(\lor\) 괄호를 뚫으며 \(\land\)로 바뀌었고, 둘째 단계에서 안쪽 \(\land\) 괄호를 뚫으며 \(\lor\)로 바뀌었다.
복기. 부정이 괄호를 뚫을 때마다 \(\lor \leftrightarrow \land\)가 한 번씩 뒤집힌다 — 두 겹이면 두 번. 이 리듬이 11주차 양화사 부정(\(\forall \leftrightarrow \exists\)가 겹겹이 뒤집히는)에서 그대로 반복된다. 진리표가 판정의 원리라면, 법칙의 사슬은 판정을 빠르게 재사용하는 계산이다 — 둘 다 갖추면 표는 검산 수단이 된다.
문제 18#
접근. 힌트의 순서대로 세 단계 — 조건문을 \(\neg, \lor\)로 분해하고, \(Q\)를 이중부정으로 부풀린 뒤, 드모르간 1을 오른쪽에서 왼쪽으로 써서 하나의 부정으로 묶는다. 법칙은 양방향으로 쓸 수 있다(동치는 교체이므로).
풀이.
복기. 유도된 식을 말로 읽으면 — “P이면 Q” = “P인데 Q가 아닌 일은 없다”. 조건문의 부정이 \(P \land \neg Q\)인 이유(§1.8)가 이 한 줄에서 한눈에 보인다. 훈련 2의 마무리 질문이 같은 유도를 부정 쪽에서 밟은 것이었다 — 같은 동치 사슬을 어느 끝에서 출발해도 목록이 닫혀 있다.
문제 19#
접근. 여섯 열 표 — \(\neg P\), \(\neg Q\)를 중간 재료로 두고 \(\neg P \iff \neg Q\) 열을 계산한다. \(\iff\)는 양쪽 값이 같을 때 T다(8주차 문제 4). 해석 문장은 §1.7의 대우 만들기를 쌍조건문에 적용해 본 것이다.
풀이.
\(P\) |
\(Q\) |
\(P \iff Q\) |
\(\neg P\) |
\(\neg Q\) |
\(\neg P \iff \neg Q\) |
|---|---|---|---|---|---|
T |
T |
T |
F |
F |
T |
T |
F |
F |
F |
T |
F |
F |
T |
F |
T |
F |
F |
F |
F |
T |
T |
T |
T |
3열과 6열이 모든 행에서 (T, F, F, T)로 일치하므로 동치이다. \(\blacksquare\)
해석: “쌍조건문의 대우는 자기 자신이다.” \(P\)와 \(Q\)의 진리값이 같다는 것과 \(\neg P\)와 \(\neg Q\)의 진리값이 같다는 것은 같은 말이기 때문이다 — 값을 둘 다 뒤집어도 “같음”은 보존된다.
복기. 조건문은 대우를 만들면 다른 생김새가 되지만 쌍조건문은 제자리로 돌아온다 — 대칭인 관계(\(\iff\))와 방향 있는 관계(\(\Rightarrow\))의 차이다. 25주차에서 iff 증명을 방향별로 쪼갤 때 이 대칭성이 배경에서 일한다.
문제 20#
접근. \(\neg(P \Rightarrow Q) \equiv P \land \neg Q\)에서 \(\land\)의 양쪽 조각을 하나씩 읽어 내면 그것이 반례의 요구 조건 두 개다. \(n = 40\)에 대해 두 조각을 각각 검증한다.
풀이. (예시 답안) “모든 \(n\)에 대해 \(P(n)\)이면 \(Q(n)\)”이 거짓이라는 것은 \(\neg(P \Rightarrow Q)\)가 성립하는 사례가 존재한다는 것이고 (“모든”의 부정이 “사례의 존재”가 되는 정확한 문법은 10주차에서 만든다 — 지금은 §1.8의 읽기를 인정하고 쓴다), 동치에 의해 그 사례는 \(P \land \neg Q\)를 만족한다. 따라서 반례는 두 조건을 동시에 갖춰야 한다: ① 가정 \(P\)를 만족할 것 ② 결론 \(Q\)를 만족하지 않을 것. \(n = 40\)의 검증 — ① 40은 자연수이므로 주장 “\(f(n) = n^2 + n + 41\)은 모든 자연수 \(n\)에 대해 소수”의 가정 범위에 든다. ② \(f(40) = 40^2 + 40 + 41 = 40 \cdot 41 + 41 = 41 \cdot 41 = 41^2\)은 1과 자신 외의 약수 41을 가지므로 소수가 아니다 — 결론을 부정한다. 두 조건이 모두 확인됐으므로 \(n = 40\)은 \(P \land \neg Q\)의 증인이고, 이 증인 하나의 존재가 원명제의 거짓을 확정한다.
복기. “반례: \(n = 40\)” 한 줄로 끝내면 미완성이다 — 완결 서식은 검증 두 개(\(P\) 확인, \(\neg Q\) 확인)다. 이 서식이 29주차 반증 주간의 표준 서식이 되고, 그 논리적 출처가 이번 주의 조건문 부정이다.
다음 주 예고: “모든(\(\forall\))”과 “어떤(\(\exists\))” — 수학 명제의 마지막 부품인 양화사를 배운다. 예제 2.2에서 본 비대칭(동치 증명은 표 전체, 비동치 증명은 행 하나)이 \(\forall\)과 \(\exists\)의 증명 부담 비대칭으로 정식화되고, \(\forall x \exists y\)와 \(\exists y \forall x\)가 왜 완전히 다른 명제인지가 중심 주제다.