# 11주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 부정을 함께 만들기 완성된 부정을 먼저 보이지 않는다. 층 구조 파악부터 진리값 판정까지 한 걸음씩 만든다. 예제 2.1은 한 줄씩 함께 만들고, 2.2는 설계만 함께 하고, 2.3은 설계부터 혼자 한다. ### 예제 2.1 — 단층 부정 **문제.** "$\forall x \in \mathbb{R},\ x^2 > 0$"의 부정을 만들고, 어느 쪽이 참인지 판정하시오. **설계 — 만들기 전에 정하는 두 가지.** 증명의 번역표(가정 $\to$ 출발점, 목표 $\to$ 도착점)와 같은 요령이다. 주어진 것의 구조와 만들 것의 꼴을 먼저 정한다. | | **말** | **번역** | |---|---|---| | 주어진 것 (출발점) | 원문 $\forall x \in \mathbb{R},\ x^2 > 0$ | 층 구조: $\forall$ 한 층 + 열린 문장 $x^2 > 0$ | | 만들 것 1 (도착점) | 원문의 부정 | 부정 기호가 밖에 남지 않은 문장 (§1.5의 끝 모양) | | 만들 것 2 | 진리값 판정 | 참인 쪽에 10주차 판정 절차를 적용 | :::{container} quotebox **확인 10.** 첫 걸음을 완성해 보자. 맨 바깥층 $\forall$에 총목록 4행을 적용하면 — "$\underline{\quad}\, x \in \mathbb{R},\ \neg(x^2 > 0)$". 무대 $\mathbb{R}$은 어떻게 되는가. ::: :::{admonition} 답 :class: quotebox dropdown $\exists x \in \mathbb{R},\ \neg(x^2 > 0)$. 무대 $\mathbb{R}$은 그대로다 — 뒤집히는 것은 양화사뿐이다(§1.4). ::: :::{container} quotebox **확인 11.** 둘째 걸음 — 열린 문장의 부정을 완성해 보자. $\neg(x^2 > 0)$은 $x^2\, \underline{\quad}\, 0$이다. $x^2 < 0$이라고 답하고 싶어지는 자리다 — 무엇이 빠지는가. ::: :::{admonition} 답 :class: quotebox dropdown $x^2 \le 0$. "$x^2 > 0$이 성립하지 않는 상황"은 $x^2 = 0$인 경우와 $x^2 < 0$인 경우 전부이므로, 둘을 합친 $\le$가 부정이다. $<$로만 적으면 $x^2 = 0$인 경우 — 바로 아래에서 승부를 가르는 경우 — 가 양쪽 어디에도 속하지 않게 된다. ::: :::{container} quotebox **확인 12.** 완성된 부정 "$\exists x \in \mathbb{R},\ x^2 \le 0$"은 $\exists$ 문장이므로 증인 하나로 판정이 끝난다. 증인을 제시하고 조건 성립을 검산해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $x = 0$: $0^2 = 0 \le 0$ ✓. 부정이 참이므로 원문은 거짓이다 — 부정과 원문은 진리값이 반대라는 자격(§1.3)이 판정을 이어 준다. ::: **완성본.** 방금 만든 걸음들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 원문은 $\forall x \in \mathbb{R},\ x^2 > 0$ — $\forall$ 한 층에 열린 문장이 실린 구조다. | 층 구조 파악이 첫 걸음이다. 어느 규칙을 쓸지는 맨 바깥층이 정한다. | | 부정 첫 걸음: $\exists x \in \mathbb{R},\ \neg(x^2 > 0)$ | $\neg\forall \leadsto \exists\neg$ (총목록 4행). 무대 $\mathbb{R}$은 부정되지 않는다. | | 정리하면: $\exists x \in \mathbb{R},\ x^2 \le 0$ | $>$의 부정은 $\le$ — 성립하지 않는 경우($=$, $<$) 전부를 덮는다. | | 증인 $x = 0$: $0^2 = 0 \le 0$ ✓ — 부정이 참이다. | $\exists$의 판정 절차(10주차): 증인 하나로 확정된다. | | 따라서 원문은 거짓이다. | 원문과 부정은 진리값이 반대다(부정의 자격). | **같은 $x = 0$의 두 얼굴.** 원문이 거짓임을 부정 없이 말하면 "반례 $x = 0$"이고, 부정으로 말하면 "부정의 증인 $x = 0$"이다 — 같은 수, 같은 검산이다. 1주차부터 쓰던 반례 제시가 실은 부정 규칙의 적용이었다는 것이 여기서 드러난다. ### 예제 2.2 — 이층 부정 **문제.** "$\forall x \in \mathbb{Z},\ \exists y \in \mathbb{Z},\ y > x$" (10주차의 참인 명제)의 부정을 만드시오. 이번에는 설계만 함께 한다. :::{container} quotebox **확인 13.** 만들기 전에 세 가지를 적어 보자. ① 층 구조: 바깥층 $\underline{\quad}$, 안층 $\underline{\quad}$, 맨 안쪽 열린 문장 $\underline{\quad}$. ② 걸음 순서: 어느 층부터 뒤집는가. ③ 마지막 걸음에서 $\neg(y > x)$는 무엇으로 정리되는가. ::: :::{admonition} 답 :class: quotebox dropdown ① 바깥층 $\forall x \in \mathbb{Z}$, 안층 $\exists y \in \mathbb{Z}$, 열린 문장 $y > x$. ② 바깥층부터 — $\forall$을 먼저 뒤집고, 다음 걸음에 $\exists$를 뒤집는다. ③ $y \le x$ ($>$의 부정, 확인 11 그대로). 재료가 다 모였다. 층별 절차를 돌린다. ::: **풀이.** $$ \neg(\forall x \exists y,\ y > x) \ \equiv\ \exists x,\ \neg(\exists y,\ y > x) \ \equiv\ \exists x,\ \forall y,\ y \le x $$ 읽으면 — "모든 정수 $y$가 자기 이하가 되는 정수 $x$가 존재한다", 곧 정수 전체에 **최댓값이 있다**는 주장이다. 원문이 참(10주차 — $x$마다 $y = x + 1$) 이므로 이 부정은 거짓이다. "정수 전체에 최댓값은 없다"라는 익숙한 사실이 층별 부정의 결과와 정확히 포개어진다. ### 예제 2.3 — 조건문이 낀 부정 **문제.** "모든 정수 $n$에 대해, $n$이 소수이면 $n$은 홀수이다"의 부정을 만들고 진리값을 판정하시오. 이번에는 설계부터 스스로 한다. :::{container} quotebox **확인 14.** 한국어 문장이므로 기호 번역이 먼저다. 층 구조까지 적어 보자. 기호 번역: $\underline{\qquad}$ / 층 구조: $\underline{\quad}$ 한 층 + $\underline{\quad}$문. ::: :::{admonition} 답 :class: quotebox dropdown $\forall n \in \mathbb{Z},\ (n \text{은 소수} \Rightarrow n \text{은 홀수})$ — $\forall$ 한 층 + 조건문. 걸음도 두 번이다: $\forall$을 뒤집고, 조건문을 "인데"로 바꾼다. ::: **풀이.** 원문을 기호로 옮기면 $\forall n \in \mathbb{Z},\ (n \text{ 소수} \Rightarrow n \text{ 홀수})$이다. 바깥층 $\forall$을 뒤집으면 $\exists n \in \mathbb{Z},\ \neg(n \text{ 소수} \Rightarrow n \text{ 홀수})$이고, 조건문의 부정으로 정리하면 $$ \exists n \in \mathbb{Z},\ (n \text{은 소수} \land n \text{은 홀수가 아니다}) $$ — "소수**인데** 짝수인 정수가 존재한다"이다. 이 부정은 참이다: 증인 $n = 2$ (2는 소수이고 짝수다). 따라서 원문은 거짓이고, $n = 2$가 원문의 반례다 — 예제 2.1 끝에서 본 대로, 반례와 부정의 증인은 같은 대상의 두 이름이다. ### 관찰 — 세 부정의 같은 뼈대 세 예제는 층 수만 다를 뿐 걸음이 같다. 대응표의 빈칸을 채워 보자. | **단계** | **예제 2.1** | **예제 2.2** | **예제 2.3** | |---|---|---|---| | ① 층 구조를 파악한다 | $\forall$ 한 층 | $\underline{\quad(1)\quad}$ | $\forall$ + 조건문 | | ② 바깥층부터 한 겹씩 뒤집는다 (무대 유지) | $\neg\forall \leadsto \exists\neg$ | $\forall \to \exists$, $\exists \to \forall$ | $\underline{\quad(2)\quad}$ | | ③ 맨 안쪽을 정리한다 | $x^2 \le 0$ | $\underline{\quad(3)\quad}$ | 소수 $\land$ 홀수 아님 | | ④ 참인 쪽을 판정한다 | 증인 $x = 0$ — 원문 거짓 | 원문 참 — 부정 거짓 | $\underline{\quad(4)\quad}$ | :::{container} quotebox **확인 15.** 대응표의 (1)~(4)를 채워 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $\forall$ + $\exists$의 두 층. (2) $\forall$을 $\exists$로 뒤집고, 조건문을 $\land$("인데")로. (3) $y \le x$ ($>$의 부정). (4) 증인 $n = 2$로 부정이 참 — 원문 거짓. 세 부정 모두 정확히 이 걸음이다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **부정 제작의 3단계** ① 층 구조를 파악한다 (한국어면 기호 번역부터) $\to$ ② 바깥층부터 한 겹씩 총목록의 규칙 하나를 적용한다 (무대는 그대로) $\to$ ③ 맨 안쪽 열린 문장의 부정을 정리한다 (등호$\cdot$부등호 반전 주의). 진리값이 요구되면 참인 쪽에 10주차 판정 절차를 적용한다 — 부정과 원문은 진리값이 반대다. ::: ## 빈칸 사다리 — 지지대를 하나씩 빼며 모의시험 전의 마지막 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식 빈칸 **과제.** "$\forall x \in \mathbb{R},\ (x > 1 \Rightarrow x^2 > x)$"의 부정을 층별로 완성한다. $$ \neg\Big(\forall x \in \mathbb{R},\ (x > 1 \Rightarrow x^2 > x)\Big) \ \equiv\ \exists x \in \mathbb{R},\ \neg\big(\underline{\quad(1)\quad}\big) \ \equiv\ \exists x \in \mathbb{R},\ \big(x > 1 \land \underline{\quad(2)\quad}\big) $$ 완성된 부정을 읽으면: "1보다 큰데 제곱해도 자기보다 커지지 않는 실수가 $\underline{\quad(3)\quad}$한다." ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 각 걸음의 규칙 이름도 빈칸이다. **과제.** "$\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ x + y = x$"의 부정을 만들고 진리값을 판정한다. **첫 걸음.** $\forall y \in \mathbb{R},\ \neg\big(\forall x \in \mathbb{R},\ x + y = x\big)$ — 근거: $\underline{\quad(1)\quad}$ **둘째 걸음.** $\forall y \in \mathbb{R},\ \exists x \in \mathbb{R},\ \neg(x + y = x)$ — 근거: $\underline{\quad(2)\quad}$ **정리.** $\forall y \in \mathbb{R},\ \exists x \in \mathbb{R},\ x + y \neq x$ — $=$의 부정은 $\underline{\quad(3)\quad}$ **판정.** 원문은 $\underline{\quad(4)\quad}$이다 — 증인 $y = \underline{\quad(5)\quad}$가 모든 $x$에 대해 $x + y = x$를 만족한다. 따라서 부정은 $\underline{\quad(6)\quad}$이다. ### 훈련 3 ●●● — 뼈대만 남기고 **과제.** "모든 정수 $n$에 대해, $n$이 홀수이면 $n + 1$은 짝수이다"를 다음 세 칸으로 처리한다. 각 칸을 통째로 채운다. - ① 기호 번역과 층 구조: $\underline{\quad(1)\quad}$ - ② 층별 부정 (끝 모양까지): $\underline{\quad(2)\quad}$ - ③ 어느 쪽이 참인지 판정과 그 근거 (참인 쪽은 1주차 도구로 증명까지): $\underline{\quad(3)\quad}$ (이 훈련이 문제 19의 예행연습이다 — 부정을 만들어 보면 원문 증명에서 무엇을 막아야 하는지가 보인다.) ## 연습문제 (20문항) 이 20문항은 2부(7~11주차) **총정리 모의시험**을 겸한다. 규칙은 세 줄이다. - 노트와 본문을 덮고 90분 안에 푼다. 시험 중에는 힌트 상자를 열지 않는다. - 다 푼 뒤 §6 해설로 채점한다. 문제 1(진리표 백지 테스트)을 틀리면 해당 주차부터 재복습한 뒤 넘어간다. - 채점 후 틀린 문제는 힌트 상자와 해설의 '접근'까지만 읽고 한 번 더 시도한다 — 그래도 안 되면 풀이를 읽는다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 범위는 7~11주차(2부 논리) 전체다. 답이 아니라 **근거**가 점수다 — 부정 문제는 층마다 적용한 규칙 이름을, 판정 문제는 증인$\cdot$반례나 진리표 행을, 추론 문제는 규칙$\cdot$오류의 이름을 댈 수 있어야 정답으로 친다. ::: ### 기본 ●○○ **1.** [백지 테스트] $P \land Q$, $P \lor Q$, $\neg P$, $P \Rightarrow Q$, $P \iff Q$의 진리표를 그리시오. :::{admonition} 힌트 :class: quotebox dropdown 행 순서는 TT, TF, FT, FF로 고정한다. $\Rightarrow$는 F가 되는 행이 단 하나(T$\Rightarrow$F)이고, $\iff$는 두 값이 같은 행에서 T다. ::: **2.** 다음 문장의 부정을 쓰시오 (부정 기호가 밖에 남지 않게). (a) $\forall n \in \mathbb{N},\ n \ge 1$ (b) $\exists x \in \mathbb{R},\ x^2 = 2$ (c) $x > 0 \land x < 5$ (d) $n$은 짝수이거나 소수이다 :::{admonition} 힌트 :class: quotebox dropdown 각 문장의 최상위 구조($\forall$? $\exists$? $\land$? $\lor$?)를 식별하고 총목록에서 해당 규칙 한 줄만 적용한다. (a)에서 $\ge$의 부정에 주의한다. ::: **3.** "$P$ only if $Q$", "$P$는 $Q$이기 위한 충분조건", "$Q$는 $P$이기 위한 필요조건"을 각각 화살표로 번역하시오. :::{admonition} 힌트 :class: quotebox dropdown "only if 뒤에 오는 것이 결론"이다. 충분조건은 화살표의 꼬리, 필요조건은 화살표의 머리에 선다 (8주차). ::: **4.** 원명제 "$n$이 4의 배수이면 $n$은 짝수이다"의 역$\cdot$이$\cdot$대우를 쓰고, 원명제와 동치인 것을 고르시오. :::{admonition} 힌트 :class: quotebox dropdown 역은 화살표 뒤집기, 이는 양쪽 부정, 대우는 둘 다. 동치 판정은 9주차 동치 목록에서 하나, 나머지는 $n$ 하나로 반례를 든다. ::: **5.** 진리값을 판정하시오. (a) $1 = 2 \Rightarrow 2 = 3$ (b) $\emptyset \subseteq \{1\} \Rightarrow 1 \in \emptyset$ (c) $\exists x \in \mathbb{Z},\ x^2 = 9$ (d) $\forall x \in \mathbb{N},\ x^2 \neq x$ :::{admonition} 힌트 :class: quotebox dropdown (a)(b)는 가정의 진리값부터 판정한다 — 가정이 거짓인 조건문은 무조건 참이다 (8주차 공허한 참). (c)는 증인 하나, (d)는 반례 하나를 찾는다. ::: **6.** 다음이 명제인지 판별하고, 명제면 진리값을 쓰시오. (a) $x^2 = 4$ (b) $\exists x \in \mathbb{Z},\ x^2 = 4$ (c) 이 문제는 쉽다. (d) $\pi > 3$ :::{admonition} 힌트 :class: quotebox dropdown 명제의 자격은 진리값의 확정이다(7주차). 변수가 양화사로 묶였는지, 판정 기준이 객관적으로 있는지를 본다. ::: ### 표준 ●●○ **7.** 다음 문장의 부정을 쓰시오. (a) $\forall x \in \mathbb{R},\ (x > 2 \Rightarrow x^2 > 4)$ (b) $\exists n \in \mathbb{N},\ (n \text{은 짝수} \land n \text{은 소수})$ (c) 모든 학생이 수학과 영어를 둘 다 좋아한다. :::{admonition} 힌트 :class: quotebox dropdown (a)는 $\forall$ + 조건문의 두 걸음이다 — 예제 2.3과 같은 구조. (b)는 $\exists$ + $\land$. (c)는 한국어이지만 구조는 "모든 ~가 (A $\land$ B)"다 — 기호 번역부터 한다. ::: **8.** 다음 조건문의 부정을 "~인데 ~"꼴 한국어로 쓰시오. (a) $a \mid b$이면 $a \le b$이다. (b) $x$가 유리수이면 $x^2$은 유리수이다. :::{admonition} 힌트 :class: quotebox dropdown 가정은 그대로 두고 "인데"로 이은 뒤 결론만 부정한다. 화살표 문장으로 적었다면 §0 유형 3의 자리로 돌아간 것이다. ::: **9.** 다음 이층 명제의 부정을 만드시오 (층별 절차를 보이며). (a) $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ x + y = 0$ (b) $\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ xy = x$ :::{admonition} 힌트 :class: quotebox dropdown 바깥층부터 한 겹씩 — 예제 2.2의 절차 그대로다. 마지막 열린 문장에서 $=$의 부정은 $\neq$이다. ::: **10.** $x$는 실수. "$-1 \le x \le 1$은 $x^2 \le 1$이기 위한 무슨 조건인가?"를 진리집합으로 판정하시오. :::{admonition} 힌트 :class: quotebox dropdown 두 조건의 진리집합을 각각 구간으로 구하고 포함 관계를 비교한다 — $x^2 \le 1$은 인수분해 $(x-1)(x+1) \le 0$으로 푼다. 포함의 방향이 화살표의 방향이다 (8주차). ::: **11.** [백지 재현] $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$를 진리표로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 열 6개($P$, $Q$, $P \Rightarrow Q$, $\neg Q$, $\neg P$, $\neg Q \Rightarrow \neg P$), 행 4개다. 동치의 판정 기준은 "모든 행에서 두 열의 값이 일치"(9주차 정의). ::: **12.** $S = \{1, 2, 3, 4\}$에서 진리값을 판정하시오. (a) $\forall x \in S,\ \exists y \in S,\ x + y \le 5$ (b) $\exists y \in S,\ \forall x \in S,\ x + y \le 5$ :::{admonition} 힌트 :class: quotebox dropdown (a)는 $x$마다 $y$를 하나씩 찾으면 되고, (b)는 모든 $x$를 감당하는 만능 $y$ 하나가 필요하다 — 10주차 순서 감각. 무대가 유한하므로 전수 확인이 가능하다. ::: **13.** 다음 각 추론이 타당한지 판정하고, 타당하면 규칙 이름을, 오류면 오류 이름을 쓰시오. (a) 비가 오면 소풍이 취소된다. 소풍이 취소되지 않았다. 따라서 비가 오지 않았다. (b) 비가 오면 소풍이 취소된다. 소풍이 취소되었다. 따라서 비가 왔다. (c) $n$이 6의 배수이면 짝수다. $n = 12$는 6의 배수다. 따라서 12는 짝수다. (d) $n$이 6의 배수이면 짝수다. $n = 5$는 6의 배수가 아니다. 따라서 5는 홀수다. :::{admonition} 힌트 :class: quotebox dropdown 각 추론을 "$P \Rightarrow Q$ + 둘째 전제" 꼴로 정리해 §1.7의 표 네 행과 대조한다. (d)에서 결론이 실제로 참이라는 사실에 흔들리지 않는다 — 심사 대상은 결론이 아니라 연결이다(정의 11.1). ::: **14.** 다음 영어 문장을 기호로 번역하고 부정을 만드시오: "There is an integer that is greater than every natural number." :::{admonition} 힌트 :class: quotebox dropdown "There is ~ that ... every ..." — $\exists$ 안에 $\forall$이 든 이층 구조다. 번역을 먼저 완성하고, 부정은 층별 절차로 만든다. ::: ### 도전 ●●● **15.** (10주차 문제 19 완성) 수열 극한 정의의 부정을 층별 절차로 완성하시오: $$ \neg\Big( \forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \in \mathbb{N},\ (n > N \Rightarrow |a_n - L| < \varepsilon) \Big) $$ :::{admonition} 힌트 :class: quotebox dropdown 3층 + 조건문이지만 새 규칙은 하나도 없다 — $\forall \to \exists$, $\exists \to \forall$, $\forall \to \exists$, 마지막 조건문은 $\land$로. "$\varepsilon > 0$"의 "$> 0$"은 무대다 — 부정되지 않는다. ::: **16.** 동치 법칙만으로(진리표 없이) 다음을 유도하시오: $\neg\big(P \Rightarrow (Q \lor R)\big) \equiv P \land \neg Q \land \neg R$. 각 단계의 법칙 이름을 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 두 걸음이다 — 조건문의 부정을 먼저, 드모르간 2를 다음에. 매 줄 옆에 법칙 이름을 적는 것까지가 문제의 요구다. ::: **17.** "모든 학생이 어떤 동아리에는 가입해 있다"와 "어떤 동아리는 모든 학생이 가입해 있다"를 기호로 구분해 쓰고($S$: 학생, $C$: 동아리, $J(s, c)$: $s$가 $c$에 가입), 앞 문장은 참인데 뒤 문장은 거짓인 상황(학생 2명, 동아리 2개)을 설계하시오. :::{admonition} 힌트 :class: quotebox dropdown 앞 문장은 학생마다 동아리가 달라도 되고($\forall \exists$), 뒤 문장은 동아리 하나가 전원을 수용해야 한다($\exists \forall$). "서로 다른 동아리에 하나씩 가입한 두 학생"을 조립하면 두 문장이 갈라진다. ::: :::{admonition} 문제 18을 위한 준비 — 기사와 건달 :class: quotebox 이 섬의 주민은 기사(모든 발언이 참) 아니면 건달(모든 발언이 거짓)이다. 규칙은 두 줄이다: 주민이 문장 $S$를 말했을 때, 그가 기사이면 $S$는 참이고 건달이면 $S$는 거짓이다. 정체를 모르면 두 경우로 나눠 각각 추적한다 — 경우 나누기(1주차 문제 16)와 이번 주의 부정 규칙이 재료의 전부다. ::: **18.** 기사(항상 참말)$\cdot$건달(항상 거짓말)의 섬. 주민 B가 말했다: "나는 건달이거나, 보물은 서쪽에 있다." B의 정체와 보물의 위치를 추론하시오. :::{admonition} 힌트 :class: quotebox dropdown B가 건달이라고 가정하면 발언 전체가 거짓이다 — $\lor$의 부정은 드모르간 2로 "둘 다 거짓". 그 두 조각 중 하나가 가정과 충돌한다. ::: **19.** "정수 $n$에 대해, $n^2 + n + 1$은 홀수이다"가 참임을 다음 두 단계로 처리하시오. (a) 이 명제의 부정을 쓰시오. (b) 원명제를 증명하시오. (힌트: $n^2 + n = n(n+1)$은 1주차 문제 16) :::{admonition} 힌트 :class: quotebox dropdown (a)는 $\forall$의 부정 한 걸음이다. (b)는 1주차의 직접 증명 — $n(n+1)$이 짝수라는 1주차 문제 16을 근거 ④로 인용하면 한 줄이 줄어든다. ::: **20.** (서술, 21주차 예고) 귀류법으로 "$\sqrt{2}$는 무리수"를 증명하려 한다. 첫 줄에 가정해야 할 문장을 부정 규칙으로 정확히 만들고("무리수 = 유리수가 아닌 실수"를 사용), 그 가정을 3주차 $\mathbb{Q}$의 정의로 풀어 쓴 두 번째 줄까지 써 보시오. (증명 전체는 21주차에서) :::{admonition} 힌트 :class: quotebox dropdown "무리수 = 유리수가 **아닌** 실수"에서 부정할 것은 "아니다"이다 — 이중부정으로 긍정이 된다. 둘째 줄은 3주차 $\mathbb{Q}$의 정의 ("정수를 0 아닌 정수로 나눈 분수 꼴")를 그대로 푼다. ::: ## 백지 재현 — 복습 프로토콜 권장 일정 — 1~2일차: §0~§3 학습 / 3일차: 1차 재현 / 4일차: 모의시험(§4) 90분과 채점 / 5일차: 완전 백지 재현과 오답 재시도. 재현은 두 번으로 나눈다 — 한 번에 완전 백지로 가지 않는다. **1차 시도 (3일차) — 틀 카드 허용.** 부정 규칙 총목록(§1.3)과 '부정 제작의 3단계'만 펴 놓고, 예제 2.2(이층 부정)와 2.3(조건문이 낀 부정)을 층별 절차를 보이며 처음부터 끝까지 적는다. 본문은 보지 않는다. **2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다: - [ ] 부정 규칙 6개(총목록 표)를 백지에 썼다. - [ ] "무대는 부정되지 않는다"를 §1.4의 실험 예($S = \{1,2,3\}$)와 함께 설명했다. - [ ] 이층 양화사 부정을 층별 절차로 재현했다 (예제 2.2). - [ ] 긍정 논법$\cdot$부정 논법과 두 오류를 예문 하나씩으로 구분했다. - [ ] 모의시험 1, 11번(백지 테스트)을 통과했다. - [ ] 모의시험에서 틀린 문제를 전부 다시 풀어 통과했다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 어느 규칙부터 쓸지 모르겠다 | 예제 2.1의 설계 — 층 구조 파악이 먼저다. 맨 바깥층이 규칙을 정한다 | | 무대까지 뒤집었다 | §1.4의 삭제$\cdot$변형 실험 — 원문과 "부정"이 동시에 참이 되는 붕괴를 다시 본다 | | 조건문의 부정이 화살표로 나온다 | §0 유형 3과 총목록 3행 — 부정 뒤에 조건문은 남지 않는다 | | 부등호의 부정이 반대 부등호로 나온다 | 확인 11 — 성립하지 않는 경우 전부($=$ 포함)를 덮어야 한다 | | 추론의 타당$\cdot$오류 구분이 안 된다 | 정의 11.1과 §1.7의 표 — "전제 참 + 결론 거짓 상황"을 제작해 본다 | | 부정은 만드는데 진리값 판정이 안 된다 | 10주차 판정 절차 — 참인 쪽에 증인 또는 전수 확인을 적용한다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 준비 운동 1. $\forall x \exists y,\ y > x$는 참 — 어떤 $x$가 와도 $y = x + 1$이 조건을 만족한다 ($x$마다 $y$가 달라도 된다). $\exists y \forall x,\ y > x$는 거짓 — 모든 $x$를 감당하는 만능 $y$가 필요한데, $x = y$를 대면 $y > y$가 되어 실패한다. 순서가 진리값을 가른다 (10주차 §1.6, 확인 8$\cdot$9). 1. $\exists$ 참: 증인 하나를 제시하고 조건 성립을 검산한다. $\forall$ 거짓: 반례 하나를 제시한다. 둘 다 "하나"로 끝난다 — 이 대칭의 정체가 이번 주 부정 규칙($\neg\forall = \exists\neg$)이다. 1. $P \land \neg Q$ (9주차 동치 목록 — 조건문의 부정). ### 빈칸 사다리 — 훈련 1 (1) $x > 1 \Rightarrow x^2 > x$ — $\forall$을 뒤집은 직후이므로 조건문 전체가 $\neg$ 안에 남아 있다. (2) $x^2 \le x$ — 조건문의 부정("인데")에서 결론만 부정하며, $>$의 부정은 $\le$다. (3) 존재 ※ 원문은 참이다($x > 1 > 0$이면 $x \cdot x > 1 \cdot x$) — 따라서 이 부정은 거짓이다. 부정이 거짓임을 따로 증명할 필요는 없다 — 진리값 반대가 부정의 자격이다. ### 빈칸 사다리 — 훈련 2 (1) $\neg\exists \leadsto \forall\neg$ (총목록 5행) (2) $\neg\forall \leadsto \exists\neg$ (총목록 4행) (3) $\neq$ (4) 참 (5) $0$ — 모든 $x$에 대해 $x + 0 = x$ ✓ (6) 거짓 ※ 부정이 거짓임을 직접 확인할 수도 있다: $y = 0$일 때 "$\exists x,\ x + 0 \neq x$"는 거짓이므로 $\forall y$가 무너진다 — 두 판정이 일치한다. ### 빈칸 사다리 — 훈련 3 (1) $\forall n \in \mathbb{Z},\ (n \text{은 홀수} \Rightarrow n + 1 \text{은 짝수})$ — $\forall$ 한 층 + 조건문의 이층 구조. (2) $\exists n \in \mathbb{Z},\ (n \text{은 홀수} \land n + 1 \text{은 짝수가 아니다})$ — $\forall$을 뒤집고(4행) 조건문을 "인데"로(3행). (3) 원문이 참이다. 증명: $n$을 홀수라 하자. 정의에 의해 $n = 2k + 1$인 정수 $k$가 존재한다. 그러면 $n + 1 = 2k + 2 = 2(k + 1)$이고 $k + 1$은 정수이므로 $n + 1$은 짝수이다. $\blacksquare$ 따라서 부정은 거짓이다 — "홀수인데 다음 수가 짝수가 아닌 정수"는 존재하지 않는다. ※ 부정을 먼저 만들어 두면 원문 증명이 무엇을 막는 일인지가 보인다 — 문제 19에서 같은 구도를 다시 쓴다. ### 문제 1 **접근.** 2부 전체의 출발점을 백지에서 확인하는 문제다. 채점 포인트는 세 곳 — $\Rightarrow$의 F행이 T$\Rightarrow$F 한 곳뿐인지, $\iff$가 "두 값이 같을 때 참"인지, 행 순서(TT, TF, FT, FF)가 고정되어 있는지. **풀이.** 다섯 표를 한 표로 모으면 다음과 같다 (행 순서 TT, TF, FT, FF). | **$P$** | **$Q$** | **$P \land Q$** | **$P \lor Q$** | **$\neg P$** | **$P \Rightarrow Q$** | **$P \iff Q$** | |---|---|---|---|---|---|---| | T | T | T | T | F | T | T | | T | F | F | T | F | F | F | | F | T | F | T | T | T | F | | F | F | F | F | T | T | T | $\land$는 T가 한 행(둘 다 T), $\lor$는 F가 한 행(둘 다 F), $\Rightarrow$는 F가 한 행(T$\Rightarrow$F), $\iff$는 값이 일치하는 두 행에서 T — 각 열의 특징 한 줄씩이 암기의 확인 장치다. **복기.** $\Rightarrow$ 열의 세 T 중 아래 두 행(가정이 F인 행)이 공허한 참이다. 문제 5(a)의 근거가 이 두 행 중 하나(F$\Rightarrow$F)이고, 5(b)는 반대로 유일한 F행(T$\Rightarrow$F)이 근거다. ### 문제 2 **접근.** 각 문장의 최상위 구조($\forall$? $\exists$? $\land$? $\lor$?)를 식별하고 총목록의 해당 규칙 하나를 적용한다. 맨 안쪽에서 등호$\cdot$부등호 반전을 마무리한다. **풀이.** (a) 최상위는 $\forall$. 총목록 4행으로 $\exists n \in \mathbb{N},\ \neg(n \ge 1)$, $\ge$의 부정은 $<$이므로 — $\exists n \in \mathbb{N},\ n < 1$. (b) 최상위는 $\exists$. 총목록 5행으로 $\forall x \in \mathbb{R},\ \neg(x^2 = 2)$ — $\forall x \in \mathbb{R},\ x^2 \neq 2$. (c) 최상위는 $\land$. 드모르간 1로 $\neg(x > 0) \lor \neg(x < 5)$ — $x \le 0 \lor x \ge 5$. ($>$의 부정은 $\le$, $<$의 부정은 $\ge$.) (d) "이거나"는 $\lor$. 드모르간 2로 "$n$은 짝수가 아니고 소수도 아니다" — $n$은 홀수이고 소수가 아니다. (정수에서 "짝수가 아니다 = 홀수"는 모든 정수가 짝수 아니면 홀수라는 사실에서 나온다 — 1주차 문제 16의 상자에서 인정하고 쓰기로 한 사실이고, 33주차에서 증명한다.) **복기.** 네 항목 전부 "최상위 구조 식별 $\to$ 규칙 한 줄 $\to$ 안쪽 정리"의 세 동작이다. 부정 제작의 3단계가 단층에서는 이렇게 짧아진다. ### 문제 3 **접근.** 8주차의 세 가지 읽기를 화살표 하나로 통일하는 문제다. "only if 뒤가 결론", "충분조건은 화살표의 꼬리", "필요조건은 화살표의 머리"를 각각 적용한다. **풀이.** "$P$ only if $Q$": $P$가 성립하는 것은 $Q$가 성립할 때뿐이다 — $P$인데 $Q$가 아닌 상황이 금지된다. 곧 $P \Rightarrow Q$. "$P$는 $Q$이기 위한 충분조건": $P$만 성립하면 $Q$가 따라온다 — $P \Rightarrow Q$. "$Q$는 $P$이기 위한 필요조건": $P$가 성립하려면 $Q$가 반드시 있어야 한다 — $Q$가 없으면 $P$도 없다, 곧 $P \Rightarrow Q$. 셋 다 $P \Rightarrow Q$ — 같은 명제의 세 가지 표현이다. **복기.** 낱말이 무엇이든 화살표는 충분한 쪽에서 필요한 쪽으로 간다. 이 번역이 문제 10(필요충분 판정)의 언어 기반이다. ### 문제 4 **접근.** $P$: "$n$은 4의 배수", $Q$: "$n$은 짝수"로 두고 기계적으로 만든다 — 역은 화살표 뒤집기($Q \Rightarrow P$), 이는 양쪽 부정($\neg P \Rightarrow \neg Q$), 대우는 둘 다($\neg Q \Rightarrow \neg P$). 동치 판정은 9주차 동치 목록과 반례로. **풀이.** 역: "$n$이 짝수이면 4의 배수이다." 이: "$n$이 4의 배수가 아니면 짝수가 아니다." 대우: "$n$이 짝수가 아니면(홀수이면) 4의 배수가 아니다." 동치인 것은 **대우** — $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$ (9주차 예제 2.1, 이번 주 문제 11에서 재현). 역과 이는 동치가 아니다: $n = 2$가 역의 반례다 (2는 짝수인데 4의 배수가 아니므로 역은 거짓 — 원명제는 참). 이는 역의 대우이므로 역과 진리값이 같고, 같은 $n = 2$에서 무너진다 ($\neg P$ 참: 2는 4의 배수가 아님, $\neg Q$ 거짓: 2는 짝수). **복기.** 역과 이는 서로 대우 관계라 늘 운명을 같이한다 — 반례도 하나로 겸용된다. 원명제와 짝인 것은 대우뿐이다. ### 문제 5 **접근.** (a)(b)는 조건문 — 가정의 진리값부터 판정한다. 가정이 거짓이면 공허한 참(문제 1의 표 아래 두 행), 가정이 참이면 결론이 승부를 정한다. (c)(d)는 양화사 — 증인 또는 반례를 찾는다. **풀이.** (a) 참. 가정 $1 = 2$가 거짓이므로 F$\Rightarrow$F — 공허한 참이다. 결론을 볼 필요도 없다. (b) **거짓**. 가정 $\emptyset \subseteq \{1\}$은 참이다 — 공집합은 모든 집합의 부분집합(4주차, 공허한 참으로 증명). 결론 $1 \in \emptyset$은 거짓이다 — 공집합에는 원소가 없다. T$\Rightarrow$F이므로 조건문 전체가 거짓 — 진리표에서 유일한 F행이다. (c) 참. 증인 $x = 3$: $3^2 = 9$ ✓ ($x = -3$도 증인이다 — 증인은 하나면 충분하다). (d) 거짓. 반례 $x = 1$: $1^2 = 1$이므로 $x^2 \neq x$가 성립하지 않는다. **복기.** (b)가 이 문제의 함정이다 — "가정이 공허한 참으로 참"과 "조건문이 공허한 참"은 다른 층의 이야기다. 가정의 진리값 판정과 조건문 전체의 판정을 분리하는 것이 요령이다. ### 문제 6 **접근.** 명제의 자격은 진리값의 확정이다(7주차). 자유 변수가 남아 있는지, 변수가 양화사로 묶였는지, 판정 기준이 객관적인지 — 세 검사를 차례로 돌린다. **풀이.** (a) 명제 아님 — $x$가 자유 변수인 열린 문장이다. $x = 2$이면 참, $x = 3$이면 거짓이므로 진리값이 확정되지 않는다. (b) 명제, **참** — (a)의 $x$가 $\exists$로 묶여 진리값이 확정됐다. 증인 $x = 2$: $2^2 = 4$ ✓ ($x = -2$도 증인). (c) 명제 아님 — "쉽다"의 판정 기준이 객관적으로 정해져 있지 않다. 참$\cdot$거짓을 확정할 장치가 없는 문장이다. (d) 명제, **참** — $\pi = 3.14\dots > 3$으로 진리값이 확정된다. **복기.** (a)와 (b)의 대비가 이 문제의 핵심이다 — 같은 식이라도 양화사가 붙는 순간 열린 문장이 명제가 된다(10주차). 부정 규칙이 다루는 대상도 언제나 이렇게 확정된 명제다. ### 문제 7 **접근.** (a)는 $\forall$ + 조건문의 두 걸음(예제 2.3의 구조), (b)는 $\exists$ + $\land$의 두 걸음, (c)는 한국어이지만 구조는 "모든 ~가 (A $\land$ B)" — 기호 번역부터 하면 (a)(b)와 같은 기계 작업이 된다. **풀이.** (a) 첫 걸음($\neg\forall \leadsto \exists\neg$): $\exists x \in \mathbb{R},\ \neg(x > 2 \Rightarrow x^2 > 4)$. 둘째 걸음(조건문의 부정): $\exists x \in \mathbb{R},\ (x > 2 \land x^2 \le 4)$ — "2보다 큰데 제곱이 4 이하인 실수가 존재한다." 이 부정은 거짓이다 — 원문이 참이기 때문이다 ($x > 2 > 0$이면 $x \cdot x > 2 \cdot 2 = 4$). (b) 첫 걸음($\neg\exists \leadsto \forall\neg$): $\forall n \in \mathbb{N},\ \neg(n \text{ 짝수} \land n \text{ 소수})$. 둘째 걸음(드모르간 1): $\forall n \in \mathbb{N},\ (n \text{은 홀수} \lor n \text{은 소수가 아니다})$ — "모든 자연수는 홀수이거나 소수가 아니다." 이 부정은 거짓이다 — $n = 2$가 원문의 증인이다 (2는 짝수이고 소수). (c) 기호 번역: $\forall s,\ \big(M(s) \land E(s)\big)$ ($M$: 수학을 좋아함, $E$: 영어를 좋아함). 부정: $\exists s,\ (\neg M(s) \lor \neg E(s))$ — "수학과 영어 중 적어도 하나는 좋아하지 않는 학생이 존재한다." ($\neg(A \land B) \equiv \neg A \lor \neg B$, 드모르간 1까지 적용한 끝 모양이다.) **복기.** "둘 다"의 부정은 "둘 다 아님"이 아니라 "적어도 하나는 아님"이다 — (b)(c)에서 두 번 반복된 드모르간의 요점이고, 문제 18의 퍼즐에서 한 번 더 쓴다. ### 문제 8 **접근.** 조건문의 부정 = 가정 유지 + "인데" + 결론 부정. 한국어로 옮기는 것까지가 과제다 — 화살표 문장이 나오면 §0 유형 3의 자리다. **풀이.** (a) "$a \mid b$**인데** $a > b$이다." ($\le$의 부정은 $>$.) 이 부정을 만족하는 예가 실제로 있다 — $a = 3$, $b = 0$: $3 \mid 0$은 참(2주차 문제 2, 모든 정수는 0을 나눈다)인데 $3 > 0$이다. $a = 5$, $b = -5$도 같은 증인이다 ($5 \mid -5$인데 $5 > -5$). 따라서 원명제 "$a \mid b$이면 $a \le b$"는 거짓이다 — 부정을 정확히 만들어 보면 반례의 명세서가 나온다. (b) "$x$가 유리수**인데** $x^2$은 유리수가 아니다." 문제의 요구는 부정 제작까지다 — 이 부정의 진리값 판정(유리수의 곱이 유리수인가)은 뒤 주차의 닫힘성 증명에서 다룬다. **복기.** (a)의 발견이 이 문제의 소득이다: 부정문은 반례가 갖춰야 할 조건의 목록이다. 반례를 찾을 때 부정부터 만드는 습관이 29주차 반증의 표준 절차가 된다. ### 문제 9 **접근.** 바깥층부터 한 겹씩 — 예제 2.2의 절차 그대로다. 층마다 규칙 이름을 대고, 마지막 열린 문장에서 $=$의 부정 $\neq$로 마무리한다. **풀이.** (a) 층별로: $$ \neg\big(\forall x,\ \exists y,\ x + y = 0\big) \ \equiv\ \exists x,\ \neg\big(\exists y,\ x + y = 0\big) \ \equiv\ \exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ x + y \neq 0 $$ (첫 걸음 $\neg\forall \leadsto \exists\neg$, 둘째 걸음 $\neg\exists \leadsto \forall\neg$, 마지막 $=$의 부정.) 읽기: "어느 $y$와 더해도 0이 되지 않는 실수 $x$가 존재한다." 원문이 참($x$마다 $y = -x$)이므로 이 부정은 거짓이다. (b) 층별로: $$ \neg\big(\exists y,\ \forall x,\ xy = x\big) \ \equiv\ \forall y,\ \neg\big(\forall x,\ xy = x\big) \ \equiv\ \forall y \in \mathbb{R},\ \exists x \in \mathbb{R},\ xy \neq x $$ 읽기: "어떤 $y$를 잡아도 $xy \neq x$인 $x$가 존재한다." 원문은 참이다 — 만능 증인 $y = 1$이 모든 $x$에 대해 $x \cdot 1 = x$를 만족한다. 따라서 부정은 거짓이다. 실제로 $y = 1$을 부정문에 대입하면 "$\exists x,\ x \neq x$"가 되어 거짓 — $\forall y$가 이 지점에서 무너진다. **복기.** 층이 몇 개든 걸음은 "바깥층 식별 $\to$ 규칙 한 줄"의 반복이다. 문제 15의 3층도 이 반복이 한 번 더 늘어날 뿐이다. ### 문제 10 **접근.** 조건 두 개를 진리집합으로 번역해 포함 관계를 비교한다 — $P \Rightarrow Q$가 참인 것과 $P$의 진리집합이 $Q$의 진리집합에 포함되는 것이 같은 말이다(8주차). 포함이 양방향이면 필요충분조건. **풀이.** $P$: $-1 \le x \le 1$의 진리집합은 $[-1, 1]$. $Q$: $x^2 \le 1$을 풀면 $x^2 - 1 \le 0$, 인수분해로 $(x-1)(x+1) \le 0$ — 곱이 0 이하이려면 두 인수의 부호가 다르거나 하나가 0이어야 하므로 $-1 \le x \le 1$, 진리집합은 $[-1, 1]$. 두 진리집합이 같으므로 포함이 양방향으로 성립하고, $-1 \le x \le 1$은 $x^2 \le 1$이기 위한 **필요충분조건**이다. 검산: 경계 $x = 1$에서 $1^2 = 1 \le 1$ ✓, 바깥 $x = 2$에서 $4 > 1$로 양쪽 모두 탈락 ✓ — 경계와 바깥에서 두 조건이 같이 움직인다. **복기.** "무슨 조건인가" 유형은 전부 진리집합의 포함 비교로 환원된다 — 말로 다투지 않고 집합을 계산한다. ### 문제 11 **접근.** 9주차 예제 2.1의 백지 재현이다. 열 6개, 행 4개 — 동치의 판정 기준은 "모든 행에서 두 열의 진리값이 일치"(9주차 정의)다. **풀이.** | **$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열($P \Rightarrow Q$)과 6열($\neg Q \Rightarrow \neg P$)이 네 행 전부에서 T, F, T, T로 일치한다. 따라서 $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$이다. $\blacksquare$ **복기.** 이 동치 하나가 부정 논법(확인 7)과 19주차 대우 증명의 허가서다 — 2부에서 가장 자주 재사용될 부품이므로 백지 재현 대상이다. ### 문제 12 **접근.** 무대가 유한집합이므로 전수 확인이 가능하다 — (a)는 $x$마다 $y$ 하나씩, (b)는 만능 $y$ 하나를 실제로 찾는다. 10주차 순서 감각의 수치 확인이다. **풀이.** (a) 참. $x$마다 $y = 1$을 대면 — $x = 1$: $1 + 1 = 2 \le 5$ ✓ / $x = 2$: $3 \le 5$ ✓ / $x = 3$: $4 \le 5$ ✓ / $x = 4$: $5 \le 5$ ✓. 네 경우 전부 통과하므로 $\forall x$가 성립한다. (b) 참. 증인 $y = 1$: 모든 $x \in S$에 대해 $x + 1 \le 5$는 $x \le 4$와 같은 말인데 $S$의 원소 전부가 4 이하다 ✓. 만능 증인이 실제로 존재한다. **복기.** 일반으로는 (b)가 (a)보다 강한 주장이라 (b)$\Rightarrow$(a)만 성립한다(10주차). 이 문제는 (b)까지 참인 경우다 — (a)가 참이라고 (b)가 자동으로 따라오는 것이 아니라, 만능 증인을 별도로 제시했기 때문에 참이다. 준비 운동 1번과 이 문제가 순서 감각의 양쪽 사례를 하나씩 보여 준다 — 이 문제 쪽이 10주차 예제 2.3(만능 증인이 실제로 존재하는 경우)과 같은 구도다. ### 문제 13 **접근.** 각 추론을 "$P \Rightarrow Q$ + 둘째 전제 $\to$ 결론" 꼴로 정리하고 §1.7의 표 네 행과 대조한다. 오류 판정은 정의 11.1 — 전제 참$\cdot$결론 거짓 상황의 존재 — 로 뒷받침한다. **풀이.** (a) $P$: 비가 온다, $Q$: 소풍이 취소된다. 전제 $P \Rightarrow Q$와 $\neg Q$에서 결론 $\neg P$ — 타당, **부정 논법(modus tollens)**. (b) 전제 $P \Rightarrow Q$와 $Q$에서 결론 $P$ — 오류, **역 긍정의 오류**. 소풍은 비가 아닌 다른 이유로 취소될 수 있다 — 두 전제가 참이면서 $P$가 거짓인 상황이 가능하므로 연결이 필연이 아니다. (c) $P$: $n$이 6의 배수, $Q$: $n$은 짝수. $12 = 6 \times 2$이므로 둘째 전제 $P$가 참 — 타당, **긍정 논법(modus ponens)**. 결론: 12는 짝수. (d) 전제 $P \Rightarrow Q$와 $\neg P$에서 결론 $\neg Q$ — 오류, **이 긍정의 오류**. 결론 "5는 홀수"는 실제로 참이지만, 그것은 이 추론이 보장한 것이 아니다 — 같은 꼴의 추론을 $n = 2$에 돌리면 "2는 6의 배수가 아니다, 따라서 2는 홀수"가 되어 무너진다. 타당성의 심사 대상은 결론의 진리값이 아니라 연결이다(정의 11.1). **복기.** (d)가 이 문제의 승부처다 — "결론이 맞았으니 추론도 맞다"는 판단 자체가 역 긍정의 오류와 같은 구조다. 오류 판정은 언제나 "전제 참 + 결론 거짓 상황"의 제작으로 한다. ### 문제 14 **접근.** "There is ~ that ... every ..." — $\exists$가 밖, $\forall$이 안인 이층 구조다. 번역을 먼저 확정하고, 부정은 층별 절차로 만든다. **풀이.** 번역: $\exists x \in \mathbb{Z},\ \forall n \in \mathbb{N},\ x > n$ — "모든 자연수보다 큰 정수가 존재한다." 부정(층별): 첫 걸음 $\neg\exists \leadsto \forall\neg$, 둘째 걸음 $\neg\forall \leadsto \exists\neg$, 마지막 $>$의 부정 $\le$: $$ \forall x \in \mathbb{Z},\ \exists n \in \mathbb{N},\ x \le n $$ — "어떤 정수든 그것 이상인 자연수가 존재한다." 부정이 참이다: 정수 $x$가 주어지면 $x \le 0$인 경우 $n = 1$이, $x \ge 1$인 경우 $n = x$가 조건을 만족한다 ($x \le x$ ✓). 따라서 원문은 거짓이다. **복기.** "자연수는 위로 끝이 없다"를 증인 제시로 확인했다 — 이 사실의 일반형(아르키메데스 성질)은 28주차 문제 16에서 사실로 인정해 사용하고, 45주차에서 재조명한다. 지금은 $x$마다 $n$을 구체적으로 대는 것으로 충분하다. ### 문제 15 **접근.** 3층 + 조건문이지만 새 규칙은 없다 — 층별 절차를 네 번 반복할 뿐이다. "$\varepsilon > 0$", "$N \in \mathbb{N}$" 같은 부분은 전부 무대이므로 부정되지 않는다. **풀이.** 바깥층부터 한 겹씩 통과시킨다. 첫 걸음 ($\neg\forall\varepsilon \leadsto \exists\varepsilon\,\neg$): $$ \exists \varepsilon > 0,\ \neg\Big(\exists N \in \mathbb{N},\ \forall n \in \mathbb{N},\ (n > N \Rightarrow |a_n - L| < \varepsilon)\Big) $$ 둘째 걸음 ($\neg\exists N \leadsto \forall N\,\neg$): $$ \exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \neg\Big(\forall n \in \mathbb{N},\ (n > N \Rightarrow |a_n - L| < \varepsilon)\Big) $$ 셋째 걸음 ($\neg\forall n \leadsto \exists n\,\neg$) 뒤 마지막으로 조건문의 부정($<$의 부정은 $\ge$): $$ \exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \exists n \in \mathbb{N},\ \big(n > N \land |a_n - L| \ge \varepsilon\big) $$ 읽기: "어떤 $\varepsilon$이 있어서, 어느 $N$을 잡아도, $N$보다 크면서 $L$에서 $\varepsilon$ 이상 떨어진 항이 존재한다" — "수열이 $L$로 수렴하지 않는다"의 정확한 뜻이다. 45주차에서 이 문장으로 발산을 증명한다. **복기.** "$\varepsilon > 0$"의 "$> 0$"이 부정 후에도 그대로인 것에 주목한다 — $\forall \varepsilon > 0$은 "무대가 양수 전체"라는 뜻이므로 무대 보존 규칙(§1.4)이 적용된다. 층이 깊어질수록 이 규칙이 답안의 정확도를 가른다. ### 문제 16 **접근.** 진리표 없이 근거 ④(9주차 동치 목록)만으로 유도하는 문제다. 조건문의 부정을 먼저 적용해 $\land$ 꼴을 만들고, 남은 $\neg(Q \lor R)$에 드모르간 2를 적용한다. **풀이.** $$ \neg\big(P \Rightarrow (Q \lor R)\big) \ \equiv\ P \land \neg(Q \lor R) \qquad \text{(조건문의 부정)} $$ $$ \equiv\ P \land (\neg Q \land \neg R) \qquad \text{(드모르간 2)} $$ $$ \equiv\ P \land \neg Q \land \neg R \qquad \text{(괄호 생략 — 표기 관례)} \qquad \blacksquare $$ 마지막 걸음은 등록된 법칙의 인용이 아니라 표기 관례다 — $\land$가 연이어 있을 때는 어느 쪽부터 묶어도 진리값이 같으므로 괄호를 생략해 적는다 (지금은 관례로 인정하고 쓴다). 법칙 이름이 필요한 걸음은 앞의 둘뿐이다. 해석: "P이면 Q 또는 R"이 거짓이라는 것은 "P인데 Q도 R도 아니다"라는 것이다 — 결론이 $\lor$인 조건문의 부정은 결론 쪽 후보 전부의 기각을 요구한다. **복기.** 이 꼴은 22주차 귀류법("또는" 결론의 부정을 가정으로 삼는 자리)에서 그대로 재사용된다 — 부정 한 번에 쓸 수 있는 가정이 두 개 생기는 구조다. ### 문제 17 **접근.** 두 문장의 차이는 양화사의 순서다 — 앞 문장($\forall s \exists c$)은 학생마다 동아리가 달라도 되고, 뒤 문장($\exists c \forall s$)은 동아리 하나가 전원을 수용해야 한다. 설계는 이 차이가 드러나는 최소 모형 — "서로 다른 동아리에 하나씩 가입한 두 학생" — 을 조립한다. **풀이.** 앞 문장: $\forall s \in S,\ \exists c \in C,\ J(s, c)$. 뒤 문장: $\exists c \in C,\ \forall s \in S,\ J(s, c)$. 설계: 학생 $S = \{s_1, s_2\}$, 동아리 $C = \{c_1, c_2\}$로 두고, $s_1$은 $c_1$에만, $s_2$는 $c_2$에만 가입시킨다 (참인 것은 $J(s_1, c_1)$과 $J(s_2, c_2)$뿐). 앞 문장 검증: $s_1$에게는 $c_1$이, $s_2$에게는 $c_2$가 있다 — 각자 가입한 동아리가 존재하므로 참. 뒤 문장 검증: $c_1$은 $s_2$가 미가입, $c_2$는 $s_1$이 미가입 — 전원을 수용한 동아리가 없으므로 거짓. **복기.** $\forall\exists$ 참 / $\exists\forall$ 거짓의 최소 모형은 "각자 다른 상대와 짝지어진 2$\times$2"다 — 준비 운동 1번($y = x + 1$)과 같은 구도의 유한 버전이고, 순서 문제의 반례 설계는 대부분 이 모형의 변주다. ### 문제 18 **접근.** B의 정체를 모르므로 두 경우로 나눈다(경우 나누기 — 1주차 문제 16). 각 경우에서 "기사의 발언은 참 / 건달의 발언은 거짓" 규칙을 적용하는데, 건달 경우에는 발언 전체의 **부정**이 성립해야 한다 — $\lor$의 부정은 드모르간 2로 "둘 다 거짓"이다. **풀이.** B의 발언을 $D \lor W$로 쓰자 ($D$: "나는 건달이다", $W$: "보물은 서쪽에 있다"). **경우 1: B가 건달.** 건달의 발언은 거짓이므로 $\neg(D \lor W)$, 드모르간 2로 $\neg D \land \neg W$ — 특히 $\neg D$("B는 건달이 아니다")가 성립해야 한다. 그러나 이 경우의 가정이 "B는 건달"이므로 모순이다. 이 경우는 일어날 수 없다. **경우 2: B가 기사.** 기사의 발언은 참이므로 $D \lor W$가 참이다. 그런데 $D$("나는 건달이다")는 거짓이다 — B는 기사이기 때문이다. $\lor$가 참이려면 두 조각 중 적어도 하나가 참이어야 하므로(8주차) 남은 $W$가 참이다. 두 경우가 정체의 전부를 덮고 경우 1이 기각되었으므로 — **B는 기사이고, 보물은 서쪽에 있다.** 검산: 기사 B의 발언 "나는 건달이거나 보물은 서쪽"은 $W$가 참이므로 참 ✓ — 모순이 없다. **복기.** 퍼즐의 열쇠는 "건달의 발언이 거짓"을 쓰는 순간 부정 제작이 필요해진다는 것이다 — 드모르간이 없으면 경우 1을 기각할 수 없다. 경우 나누기의 채점 기준(전체를 덮는가, 각 경우가 완결되는가)도 그대로 적용됐다. ### 문제 19 **접근.** (a)는 $\forall$의 부정 한 걸음 — 숨은 양화사("정수 $n$에 대해" = 모든 정수)를 드러내고 뒤집는다. (b)는 1주차의 직접 증명이다 — $n^2 + n = n(n+1)$이 짝수라는 1주차 문제 16을 근거 ④로 인용하면 전개 없이 끝난다. **풀이.** (a) 원문은 $\forall n \in \mathbb{Z},\ n^2 + n + 1 \text{은 홀수}$이다. 부정: $\exists n \in \mathbb{Z},\ n^2 + n + 1$은 홀수가 아니다 — 곧 "$n^2 + n + 1$이 **짝수**인 정수 $n$이 존재한다." (b) **증명.** 임의의 정수 $n$에 대해 $n^2 + n = n(n+1)$은 연속한 두 정수의 곱이므로 짝수이다 (1주차 문제 16 — 근거 ④). 즉 $n^2 + n = 2m$인 정수 $m$이 존재한다. 그러면 $$ n^2 + n + 1 = 2m + 1 $$ 이고 $m \in \mathbb{Z}$이므로, $n^2 + n + 1$은 홀수의 정의(정의 1.2)를 만족한다. $\blacksquare$ 검산: $n = 3$이면 $9 + 3 + 1 = 13$ — 홀수 ✓. $n = -2$이면 $4 - 2 + 1 = 3$ — 홀수 ✓. **복기.** (a)의 부정이 (b)의 과녁을 정해 준다 — 증명이 막아야 할 것은 "짝수가 되는 $n$ 하나의 존재"다. 이 문제는 15주차에서 "보조정리 인용"이라는 이름으로 다시 만난다 — 문제 16 같은 기존 결과를 부품으로 쓰는 방식의 정식화다. ### 문제 20 **접근.** 귀류법의 첫 줄은 결론의 부정이다. "무리수 = 유리수가 **아닌** 실수"이므로 부정할 것은 "아니다" — 이중부정(총목록 6행)으로 긍정이 된다. 둘째 줄은 그 가정을 3주차 $\mathbb{Q}$의 정의로 풀어 계산 재료(등식)를 꺼내는 자리다. **풀이.** 첫 줄: "$\sqrt{2}$가 무리수가 아니라고, 즉 **유리수라고 가정하자.**" ("유리수가 아니다"의 부정은 이중부정으로 "유리수이다" — 부정 기호가 남지 않은 끝 모양이다.) 둘째 줄: "그러면 $\mathbb{Q}$의 정의(3주차)에 의해 $\sqrt{2} = \dfrac{a}{b}$인 정수 $a, b$ ($b \neq 0$)가 존재한다." 21주차에서는 여기에 "$\dfrac{a}{b}$는 기약분수로 잡자"를 더한 뒤, 양변 제곱 $\to$ $a^2 = 2b^2$ $\to$ 짝홀 모순으로 증명을 완성한다. **복기.** 귀류법의 성패가 첫 줄의 부정 정확도에서 갈린다 — 부정이 틀리면 이후의 모든 계산이 엉뚱한 명제를 공격한다. 이 두 줄을 쓸 수 있다는 것은 21주차 준비의 절반이 끝났다는 뜻이다. ### 채점 가이드 - 1, 11번(백지 테스트) 통과 + 2, 7, 9번(부정)에서 층별 규칙 이름까지 댄 정답이 4개 이상 $\to$ 통과, 12주차로 간다. - 부정에서 무대까지 뒤집었다면($\exists x \notin \mathbb{R}$ 같은 답) $\to$ §1.4의 삭제$\cdot$변형 실험을 다시 본 뒤 2, 7, 9번을 재시도한다. - 13번의 오류 구분에 실패했다면 $\to$ 9주차 문제 10과 §1.7의 표를 재복습한다. - 15번 실패는 통과에 지장이 없다 (45주차에서 재훈련한다). 단, 층별 절차 자체가 무너진 것인지는 확인한다 — 절차가 무너졌다면 예제 2.2부터 다시 쓴다. --- **다음 주 예고:** 3부 '세기'가 시작된다. 목록(list)과 곱셈 원리로 "몇 가지인가?"를 세는데, 답을 맞히는 것보다 "왜 그 곱셈인가"를 논증하는 것이 목적이다. 이번 주의 부정 규칙도 곧바로 재사용된다 — "적어도 하나"를 세는 표준 전략이 부정("하나도 없다")을 경유하기 때문이다(12주차 문제 15).