# 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$의 값 뒤집기 | :::{container} quotebox **확인 9.** 표의 뼈대를 설계해 보자. 행은 몇 개인가. 왼쪽 명제 $P \Rightarrow Q$와 오른쪽 명제 $\neg Q \Rightarrow \neg P$의 열을 계산하기 위해 중간에 어떤 열이 더 필요한가. ::: :::{admonition} 답 :class: quotebox dropdown 변수가 $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). :::{container} quotebox **확인 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}$. ::: :::{admonition} 답 :class: quotebox dropdown $P \Rightarrow Q$ = T$\Rightarrow$F = **F**. $\neg Q$ = T, $\neg P$ = F이므로 $\neg Q \Rightarrow \neg P$ = T$\Rightarrow$F = **F**. 조건문이 무너지는 유일한 행에서 오른쪽 명제도 정확히 같은 이유(앞이 T, 뒤가 F)로 무너진다 — 이 행이 동치의 핵심 행이다. ::: :::{container} quotebox **확인 11.** 셋째 행($P$ = F, $Q$ = T)을 채워 보자. $P \Rightarrow Q = \underline{\quad}$, $\neg Q \Rightarrow \neg P = \underline{\quad}$. ::: :::{admonition} 답 :class: quotebox dropdown $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$에 빗금을 그은 것이다. 이번에는 설계만 함께 하고, 증명은 완성된 산문으로 본다. :::{container} quotebox **확인 12.** 번역부터 해 보자. "동치가 **아니다**"를 정의 9.1로 번역하면 무엇을 제시해야 하는가. 4행 표 전체가 필요한가. ::: :::{admonition} 답 :class: quotebox dropdown 동치의 정의가 "모든 행에서 일치"이므로, 동치가 아니라는 주장은 "일치하지 않는 행이 **존재한다**"이다. 따라서 진리값이 갈리는 행 **하나**를 지목하고 그 행에서 양쪽 값을 실제로 계산해 보이면 끝난다 — 표 전체는 필요 없다. 후보 행은 예제 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$은 짝수이다." 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 13.** 원명제의 $P$와 $Q$를 지목하고, 대우와 역을 만들어 보자. $P$: $\underline{\qquad}$ / $Q$: $\underline{\qquad}$ 대우($\neg Q \Rightarrow \neg P$): $\underline{\qquad}$ 역($Q \Rightarrow P$): $\underline{\qquad}$ ::: :::{admonition} 답 :class: quotebox dropdown $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은 소재가 다르지만 절차의 뼈대가 같다. 대응표의 빈칸을 채워 보자. :::{container} quotebox **확인 14.** 세 예제가 공통으로 밟은 걸음을 채워 보자. ① 주장을 정의 9.1로 번역한다 — 동치 주장은 "모든 행 일치", 비동치 주장은 "$\underline{\qquad}$". ② 번역이 요구하는 만큼 계산한다 — 동치는 표 $\underline{\quad}$, 비동치는 행 $\underline{\quad}$. ③ $\underline{\qquad}$를 선언한다. ::: :::{admonition} 답 :class: quotebox dropdown ① "갈리는 행의 존재" ② 전체 / 하나 ③ 대조 결과와 결론 (예제 2.1: "3열과 6열이 모든 행에서 일치하므로 동치이다" / 예제 2.2: "진리값이 다르므로 동치가 아니다"). 예제 2.3은 이 절차로 판정해 둔 동치(대우)를 근거 ④로 **소비**한 것이다 — 판정이 끝난 동치는 증명의 부품이 된다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **동치 판정의 두 모드** 동치 주장($\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(\neg P \lor Q) \equiv \neg(\neg P) \land \underline{\quad(1)\quad} \quad (\text{법칙: } \underline{\quad(2)\quad}) $$ $$ \equiv \underline{\quad(3)\quad} \land \neg Q \quad (\text{법칙: } \underline{\quad(4)\quad}) $$ **마무리 질문.** $\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$ 그래도 안 되면 풀이를 읽는다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "동치다(맞음)"는 0점이고, 모든 행을 계산해 대조한 표(동치), 또는 갈리는 행 하나의 계산(비동치)이 만점이다. 부정 만들기 문제에서는 "아니다"가 문장 전체를 감싸고 있으면 아직 끝난 것이 아니다 — 법칙으로 괄호를 전부 해체해야 완결이다. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** 진리표로 드모르간 1 ($\neg(P \land Q) \equiv \neg P \lor \neg Q$)을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 훈련 1의 표에서 $\lor$가 $\land$로, $\land$가 $\lor$로 바뀐 7열 표다. 최종 대조할 두 열이 몇 번째 열인지 먼저 정해 두고 계산한다. §1.2에서 이미 채운 값들을 중간 열로 복원하는 작업이기도 하다. ::: **2.** 다음 명제의 역과 대우를 쓰시오 (한국어로). (a) 비가 오면 땅이 젖는다. (b) $n$이 6의 배수이면 $n$은 2의 배수이다. (c) $x = 2$이면 $x^2 = 4$이다. :::{admonition} 힌트 :class: quotebox dropdown 역은 자리만 바꾸고, 대우는 자리를 바꾼 뒤 양쪽을 부정한다 — §1.7의 규칙을 기계적으로 적용한 뒤, 한국어 문장이 자연스러운지 확인한다. ::: **3.** 문제 2의 각 명제에 대해: 원명제의 진리값과 역의 진리값을 판정하시오 (거짓이면 반례). :::{admonition} 힌트 :class: quotebox dropdown 원명제와 역은 **독립적으로** 판정한다 — 원명제가 참이어도 역의 진리값은 반례 수색으로 따로 정한다(§1.7의 규칙). (a)의 역이 무너지는 일상 사례를 하나 찾아보자 — 비 말고도 땅을 적시는 것이 있는가. ::: **4.** 다음 명제의 대우를 쓰시오. (a) $x \in A \cap B$이면 $x \in A$이다. (b) $n^2 \neq n$이면 $n \neq 1$이다. :::{admonition} 힌트 :class: quotebox dropdown 부정할 때 $\in$은 $\notin$으로, $\neq$는 $=$로 — 기호의 부정부터 정확히 만들고 자리를 바꾼다. (b)에서는 부정의 부정이 긍정으로 돌아온다. ::: **5.** 다음 동치 여부를 판정하시오 (동치면 근거 이름, 아니면 반례 행). (a) $\neg(\neg P)$와 $P$ (b) $P \land Q$와 $Q \land P$ (c) $P \Rightarrow Q$와 $Q \Rightarrow P$ :::{admonition} 힌트 :class: quotebox dropdown 목록(§1.6)에 있는 법칙이면 이름 인용으로 충분하다 — 이미 근거 ④다. 목록에 없으면 판정의 두 모드 중 하나로: 작은 표 전체, 또는 갈리는 행 하나. (c)의 후보 행은 예제 2.2에서 찾아 두었다. ::: **6.** 다음 문장의 부정을 쓰시오 (드모르간 적용, "아니다"가 문장 전체를 감싸지 않게). (a) $x > 0$ 이고 $x < 5$ (b) $n$은 짝수이거나 $n < 0$이다 :::{admonition} 힌트 :class: quotebox dropdown "이고" $\leftrightarrow$ "이거나"를 뒤집고 각 조각을 부정한다(드모르간). 부등호의 부정은 여집합 방향이다: $>$의 부정은 $\le$, $<$의 부정은 $\ge$. ::: ### 표준 ●●○ **7.** 진리표로 $\neg(P \Rightarrow Q) \equiv P \land \neg Q$를 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 좌변 열은 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$ 드모르간) :::{admonition} 힌트 :class: quotebox dropdown 문장의 구조(또는 / 그리고 / 이면 / 집합 기호)부터 식별하고, 구조에 맞는 부정 법칙을 목록에서 고른다. (c)는 조건문의 부정 — "인데" 문장이 된다. (d)는 $\in$과 $\cup$의 정의로 $\lor$ 문장으로 바꾼 뒤에 드모르간을 쓴다. ::: **9.** $(P \Rightarrow Q) \land (Q \Rightarrow R)$이 참일 때 $P \Rightarrow R$도 참인가? 진리표(8행) 또는 논증으로 판정하시오. 이 성질의 이름(수학에서 익숙한 구조)을 붙여 보시오. :::{admonition} 힌트 :class: quotebox dropdown 8행 표(확인 4)도 좋지만, "$P$가 참이라 하자"로 시작해 화살표 두 개를 차례로 통과하는 논증이 더 짧다. $P$가 거짓인 경우는 조건문이 어떻게 처리해 주는가(8주차의 공허한 참). ::: **10.** 다음 추론의 오류를 논리 용어로 지적하시오: "미분가능하면 연속이다. $f$는 연속이다. 따라서 $f$는 미분가능하다." :::{admonition} 힌트 :class: quotebox dropdown 전제와 결론을 화살표로 적어 놓고, 결론에 도달하는 데 실제로 쓴 화살표가 원명제인지 그 변형인지 본다. §1.7의 표에서 원명제와 동치가 아니었던 변형이 무엇이었는지 떠올린다. ::: **11.** 명제 "정수 $n$에 대해, $3n + 5$가 짝수이면 $n$은 홀수이다"의 대우를 쓰고, 그 대우를 1주차 방식(정의 대입)으로 증명하시오. 이로써 원명제도 증명되었다고 말할 수 있는 근거는 무엇인가? :::{admonition} 힌트 :class: quotebox dropdown 대우를 만들 때 부정을 정확히 — "$3n+5$가 짝수"의 부정은 "$3n+5$가 홀수", "$n$이 홀수"의 부정은 "$n$이 짝수". 자리 교환까지 마치면 가정이 "$n = 2k$"로 풀리는 다루기 쉬운 명제가 된다. 훈련 3에서 걸은 절차 그대로다. ::: **12.** 원명제 "$n$이 6의 배수이면 $n$은 짝수이다"에 대해 역$\cdot$이$\cdot$대우를 쓰고 각각의 진리값을 판정하시오 (거짓이면 반례). :::{admonition} 힌트 :class: quotebox dropdown 네 판정 중 실제 계산이 필요한 것은 둘뿐이다 — 대우는 원명제와, 이는 역과 진리값이 항상 같다(§1.7, 확인 6). 어느 둘만 판정하면 되는가. ::: **13.** $P \Rightarrow Q$와 이($\neg P \Rightarrow \neg Q$)가 동치가 아님을 반례 행 하나로 보이시오. :::{admonition} 힌트 :class: quotebox dropdown 예제 2.2에서 역을 무너뜨린 행($P$ = F, $Q$ = T)을 이에도 시험해 본다. ::: **14.** "실수 $x$에 대해, $x^2 \neq 4$이면 $x \neq 2$이다"가 참임을 대우를 이용해 한 줄로 설명하시오. :::{admonition} 힌트 :class: quotebox dropdown 대우를 만들면 $\neq$가 전부 $=$로 바뀐다 — 문제 4(b)에서 이미 걸은 길이다. 대입 한 번으로 확인되는 명제가 나온다. ::: ### 도전 ●●● **15.** $P \iff Q \equiv (P \land Q) \lor (\neg P \land \neg Q)$를 진리표로 증명하시오. 오른쪽 식을 말로 풀면 왜 "같은 진리값"인지 해석하시오. :::{admonition} 힌트 :class: quotebox dropdown 우변이 T가 되는 행을 먼저 예상해 보자 — $P \land Q$는 "둘 다 T"인 행을, $\neg P \land \neg Q$는 "둘 다 F"인 행을 각각 담당하고 $\lor$로 합쳐진다. 예상을 적어 두고 표와 대조하면 계산 실수가 걸러진다. ::: :::{admonition} 이 문제가 빌려 쓰는 사고 — 가정하고 충돌을 확인하기 :class: quotebox 아래 문제 16에서 A의 정체는 두 가지(기사/건달) 중 하나다. 이럴 때는 한쪽을 가정하고, 그 가정 아래에서 발언의 진리값을 계산한 뒤, 가정과 계산 결과가 충돌하는지 본다. 충돌하면 그 가정은 기각되고 남는 쪽이 정체다. 결론의 후보를 가정으로 세워 모순으로 기각하는 이 동선은 21주차 귀류법의 예행연습이다. 계산의 관건은 8주차의 공허한 참이다. ::: **16.** 어떤 섬에 "기사(항상 참말)"와 "건달(항상 거짓말)"만 산다. 주민 A가 말했다: "내가 기사라면, 보물은 동쪽에 있다." A의 정체와 보물의 위치를 논리로 추론하시오. (힌트: A가 건달이라 가정하면 A의 발언은 거짓이어야 한다. 그런데 A가 건달이면 "내가 기사"가 거짓이므로 발언 전체는 공허한 참 — 모순.) :::{admonition} 새 작업 방식 — 진리표 없이, 법칙의 사슬로 :class: quotebox 문제 17~18은 표를 만들지 않는다. §1.6의 목록을 등식 변형처럼 한 단계씩 적용하고, 단계마다 사용한 법칙의 이름을 적는다 — 진리표로 증명해 둔 동치 (근거 ④)만으로 진행하는 첫 훈련이다. 훈련 2에서 같은 동선을 한 번 걸었다. 법칙은 양방향으로 쓸 수 있다 — 동치는 교체이므로 왼쪽을 오른쪽으로 바꾸는 것도, 오른쪽을 왼쪽으로 바꾸는 것도 허용된다. ::: **17.** 동치 법칙만으로(진리표 없이) 다음을 유도하시오: $\neg\big(P \lor (Q \land R)\big) \equiv \neg P \land (\neg Q \lor \neg R)$. 각 단계에 사용한 법칙 이름을 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 바깥 부정부터 한 겹씩 안으로 들여보낸다. 부정이 괄호를 뚫을 때마다 $\lor$와 $\land$가 한 번씩 뒤집힌다 — 두 번 뚫으면 두 번 뒤집힌다. ::: **18.** 동치 법칙만으로(진리표 없이) $P \Rightarrow Q \equiv \neg(P \land \neg Q)$를 유도하시오. (힌트: 조건문 분해 $\to$ 이중부정 $\to$ 드모르간) :::{admonition} 힌트 :class: quotebox dropdown 문제의 힌트 순서대로 세 단계면 끝난다. 마지막 단계는 드모르간 1을 오른쪽에서 왼쪽으로 쓰는 것 — $\neg P \lor \neg(\text{무엇})$ 꼴을 $\neg(\,\cdot \land \cdot\,)$로 묶는다. ::: **19.** $P \iff Q$와 $\neg P \iff \neg Q$가 동치임을 진리표로 확인하시오. 이 사실을 한 문장으로 해석하시오 ("쌍조건문의 $\underline{\quad}$는 자기 자신이다"). :::{admonition} 힌트 :class: quotebox dropdown 여섯 열 표 — $\neg P$, $\neg Q$ 열을 중간 재료로 둔다. 해석 문장은 §1.7의 표에서 "대우 만들기"를 쌍조건문에 적용하면 무엇이 나오는지를 묻고 있다. ::: **20.** (서술) "반례"의 정의를 $\neg(P \Rightarrow Q) \equiv P \land \neg Q$로 설명하시오: 반례가 갖춰야 할 두 가지 조건은 무엇이며, 1주차 문제 18($n^2+n+41$)의 $n = 40$이 그 두 조건을 어떻게 만족하는가? :::{admonition} 힌트 :class: quotebox dropdown $\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$가 존재한다. 그러면 $$ 5n + 3 = 10k + 3 = 10k + 2 + 1 = 2(5k + 1) + 1 $$ 이고 $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$가 존재한다. 그러면 $$ 3n + 5 = 6k + 5 = 6k + 4 + 1 = 2(3k + 2) + 1 $$ 이고 $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 **접근.** 진리표 금지 = 목록의 동치를 등식 변형처럼 사슬로 적용하라는 뜻이다 (문제 앞 상자). 바깥 부정부터 한 겹씩 안으로 들여보내고, 단계마다 법칙 이름을 적는다. **풀이.** $$ \neg\big(P \lor (Q \land R)\big) \equiv \neg P \land \neg(Q \land R) \quad \text{(드모르간 2)} $$ $$ \equiv \neg P \land (\neg Q \lor \neg R) \quad \text{(드모르간 1)} \qquad \blacksquare $$ 첫 단계에서 부정이 $\lor$ 괄호를 뚫으며 $\land$로 바뀌었고, 둘째 단계에서 안쪽 $\land$ 괄호를 뚫으며 $\lor$로 바뀌었다. **복기.** 부정이 괄호를 뚫을 때마다 $\lor \leftrightarrow \land$가 한 번씩 뒤집힌다 — 두 겹이면 두 번. 이 리듬이 11주차 양화사 부정($\forall \leftrightarrow \exists$가 겹겹이 뒤집히는)에서 그대로 반복된다. 진리표가 판정의 원리라면, 법칙의 사슬은 판정을 빠르게 재사용하는 계산이다 — 둘 다 갖추면 표는 검산 수단이 된다. ### 문제 18 **접근.** 힌트의 순서대로 세 단계 — 조건문을 $\neg, \lor$로 분해하고, $Q$를 이중부정으로 부풀린 뒤, 드모르간 1을 오른쪽에서 왼쪽으로 써서 하나의 부정으로 묶는다. 법칙은 양방향으로 쓸 수 있다(동치는 교체이므로). **풀이.** $$ P \Rightarrow Q \equiv \neg P \lor Q \quad \text{(조건문 분해)} $$ $$ \equiv \neg P \lor \neg(\neg Q) \quad \text{(이중부정)} $$ $$ \equiv \neg\big(P \land \neg Q\big) \quad \text{(드모르간 1을 거꾸로)} \qquad \blacksquare $$ **복기.** 유도된 식을 말로 읽으면 — "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$가 왜 완전히 다른 명제인지가 중심 주제다.