# 11주차 — 명제의 부정 만들기 + 2부 총정리

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: 부정은 층별로 뒤집는 기계적 작업이다 — $\forall \leftrightarrow \exists$, $\land \leftrightarrow \lor$, 조건문은 "인데"로.

**이 주의 위치**: 50주 과정의 11주차. 2부(논리)의 마지막 주 — 부정 규칙과 추론 규칙을 더하고, 총정리 모의시험으로 7~11주차를 닫는다.

**원서 대응**: BoP(Book of Proof) 2.10–2.12 — 병행자 참고용. 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. 양화사$\cdot$논리 연산이 겹겹인 명제의 부정을 층별 절차로 만들고, 부정 기호가 밖에 남지 않은 끝 모양까지 완성한다.
1. 무대($\in S$)가 부정에서 뒤집히지 않는 이유를 실험으로 설명할 수 있다.
1. 추론 규칙(긍정 논법$\cdot$부정 논법)과 닮은꼴 오류 두 가지를 구분한다.
1. 2부(논리) 총정리 모의시험으로 7~11주차 내용을 자가 평가한다.

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

## 준비 운동 (10주차 복습)

1. $\forall x \exists y,\ y > x$와 $\exists y \forall x,\ y > x$의 진리값을 각각 판정하시오 (무대 $\mathbb{Z}$).
1. $\exists$ 명제가 참임을 보이려면 무엇이 필요한가? $\forall$ 명제가 거짓임을 보이려면?
1. $\neg(P \Rightarrow Q) \equiv \underline{\quad}$

답은 §6 해설 맨 앞에 있다. 채점까지 마친 뒤 본문으로 들어간다.

### 자주 나오는 세 가지 답

채점 결과는 대개 다음 세 유형 중 하나로 갈린다. 셋 다 10주차 내용을 절반 이상 소화한 상태이고, 셋 다 이번 주 모의시험 전에 메워야 할 정확한 간격이 있다.

- **유형 1 — 1번의 두 문장을 같은 뜻으로 판정한다.** 두 문장에 같은 재료

($\forall$, $\exists$, $y > x$)가 들어 있다는 관찰은 옳다. 간격은 순서다 — $\forall x \exists y$에서는 $x$마다 $y$를 새로 골라도 되고($y = x + 1$), $\exists y \forall x$에서는 하나의 $y$가 모든 $x$를 감당해야 한다 (10주차 §1.6, 확인 8$\cdot$9). 문제 12와 17이 이 간격을 다시 잰다.

- **유형 2 — 2번에서 $\forall$ 거짓 쪽이 막힌다.** "$\exists$ 참은 예를 하나

들면 된다"까지는 옳다. $\forall$ 거짓 쪽을 "모든 $x$를 다 확인할 수 없으므로 보일 수 없다"로 적는 경우가 많다 — "$\forall$의 부정이 $\exists$"라는 규칙이 없으면 거짓 증명이 전수 검사처럼 보이는 것이 원인이다. 반례 하나면 끝나는 이유가 이번 주 부정 규칙에서 확정된다.

- **유형 3 — 3번을 조건문 꼴로 적는다.** $\neg P \Rightarrow \neg Q$처럼 부정도

화살표 문장일 것이라고 적는 경우가 많다. 조건문을 다루는 데 익숙해진 손이 부정에도 같은 꼴을 기대한 것이 원인이다. 9주차 문제 7의 진리표가 보여 준 대로 조건문의 부정은 조건문이 아니라 "인데"($\land$) 꼴이다 — 문제 8이 이 꼴만 집중 훈련한다.

## 개념 — 부정 규칙과 추론 규칙

### 1 '아니다'를 앞에 붙이면 어디서 막히는가

이번 주의 과제는 "명제의 부정을 만든다"이다. 도구 없이 시도부터 해 보자. 명제 "$\forall x \in \mathbb{R},\ x^2 > 0$"이 거짓임을 증명하고 싶다.

:::{admonition} 시도 — '아니다'를 앞에 붙여 밀어붙이기
:class: quotebox

"명제 '$\forall x \in \mathbb{R},\ x^2 > 0$'는 참이 아니다."

— 주장으로는 이것으로 충분해 보인다. 그런데 이 문장이 참임을 **보이는**

다음 줄이 나오지 않는다. 무엇을 제시해야 하는가?
:::

여기서 멈춘다. 10주차에서 세운 판정 절차는 두 가지뿐이다 — $\forall$ 문장은 "모든 원소가 통과하는지"를, $\exists$ 문장은 "증인 하나"를 요구한다. 그런데 지금 손에 있는 것은 $\neg(\forall \dots)$ — 부정 기호가 문장 전체를 **밖에서** 감싼 꼴이고, 이 꼴에는 어느 절차도 붙어 있지 않다.

:::{container} quotebox
**확인 1.** 막힌 자리에서 필요해지는 것은 어떤 꼴의 문장인가.

"…인 $x$가 $\underline{\quad}$한다" 꼴로 답해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

"존재한다" — $\exists$ 문장이다. $\exists$ 문장에는 "증인 하나를 제시하면

참이 확정된다"는 판정 절차가 붙어 있다. 필요한 것은 $\neg(\forall \dots)$를

**진리값이 같은** $\exists$ 문장으로 바꿔 적는 규칙이고, 그런 규칙들의

목록이 이번 주의 전부다.
:::

:::{admonition} 이 주 전체의 기준
:class: quotebox

부정 기호가 문장 밖에 붙어 있는 동안은 판정 절차가 발동하지 않는다.

부정을 안으로 밀어 넣어 양화사 문장으로 바꿔야 증명이 시작된다.
:::

### 2 규칙을 만들어 보기 — 이미 아는 판정 모으기

규칙은 새로 발명할 것이 없다. 각 꼴의 문장이 **거짓이 되는 정확한 상황**을 이미 9~10주차에서 판정했기 때문이다. 표의 빈칸을 채워 보자.

| **원문** | **원문이 거짓이 되는 정확한 상황** |
|---|---|
| 모든 $x \in S$가 조건을 만족한다 | 조건을 만족하지 않는 $x \in S$가 $\underline{\quad(1)\quad}$한다 |
| 조건을 만족하는 $x \in S$가 존재한다 | $\underline{\quad(2)\quad}$ $x \in S$가 조건을 만족하지 않는다 |
| $P$ 그리고 $Q$ | $\underline{\quad(3)\quad}$ 중 적어도 하나가 성립한다 |
| $P$이면 $Q$이다 | $P$ $\underline{\quad(4)\quad}$ $Q$가 아니다 |

:::{container} quotebox
**확인 2.** 빈칸 (1)~(4)를 채워 보자. 위 두 줄은 10주차의 판정에서,

아래 두 줄은 9주차의 동치 목록에서 나온다.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) 존재  (2) 모든  (3) $\neg P$와 $\neg Q$  (4) 인데.

위 두 줄은 10주차의 "$\forall$가 거짓 = 반례가 존재 / $\exists$가 거짓 =

전원 탈락" 판정 그대로이고, 아래 두 줄은 9주차에서 진리표로 증명한 동치

(드모르간 1, 조건문의 부정)다. 오른쪽 열에 처음 보는 내용이 하나도 없다.
:::

이 관찰에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 9~10주차에 흩어져 있던 판정들을 "부정 만들기"라는 한 작업의 규칙표로 모았을 뿐이다.

### 3 부정 규칙 총목록 [백지 암기 대상]

| **원문** | **부정** | **근거** |
|---|---|---|
| $P \land Q$ | $\neg P \lor \neg Q$ | 드모르간 1 (9주차 동치 목록) |
| $P \lor Q$ | $\neg P \land \neg Q$ | 드모르간 2 (9주차 동치 목록) |
| $P \Rightarrow Q$ | $P \land \neg Q$ ("인데") | 조건문의 부정 (9주차 문제 7) |
| $\forall x \in S,\ P(x)$ | $\exists x \in S,\ \neg P(x)$ | 10주차 판정 기준 — 반례의 존재 |
| $\exists x \in S,\ P(x)$ | $\forall x \in S,\ \neg P(x)$ | 10주차 판정 기준 — 전원 탈락 |
| $\neg P$ | $P$ | 이중부정 (9주차 동치 목록) |

표의 각 줄에서 원문과 부정은 어떤 상황에서도 진리값이 정확히 **반대**다. 이것이 "부정"이라는 말의 자격이고, 아래 실험에서 이 자격이 무너지는 사례를 본다.

맨 안쪽까지 내려가 열린 문장을 부정할 때는 등호$\cdot$부등호가 뒤집힌다: $=$의 부정은 $\neq$, $>$의 부정은 $\le$, $<$의 부정은 $\ge$ — 반대 방향 부등호가 아니라 "성립하지 않는 경우 전부"다(예제 2.1에서 확인한다).

### 4 규칙 해부 — ∀ 부정의 세 조각

양화사 줄 하나를 해부한다. $\forall x \in S,\ P(x)$의 부정 "$\exists x \in S,\ \neg P(x)$"는 세 조각으로 되어 있다.

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| $\exists x$ | 양화사 반전 | "모든"의 실패는 낙오자 **하나**의 존재 — 요구 수준이 전수에서 하나로 뒤집힌다 |
| $\in S$ | 무대 유지 | 원문과 **같은 무대**에서 심사한다 — 양화사 두 줄에서 뒤집히지 않는 부분(조건문의 가정과 함께, 부정에서 살아남는 자리다) |
| $\neg P(x)$ | 조건 부정 | 부정이 한 층 안으로 들어간다 — 남은 층에 같은 절차를 반복할 자리 |

**조각 삭제$\cdot$변형 실험 — 무대를 건드리면.** $S = \{1, 2, 3\}$에서 원문을 "$\forall x \in S,\ x \le 5$"라 하자. 세 원소 전부 통과하므로 원문은 참이다.

- 올바른 부정 $\exists x \in S,\ x > 5$: $S$ 안에 5를 넘는 원소가 없다 — 거짓.

원문과 진리값이 반대다.

- 무대 조각을 **지운** 문장 $\exists x,\ x > 5$: 심사 범위가 사라져 아무 수나

후보가 된다 — $x = 6$이 증인, **참**.

- 무대까지 **뒤집은** 문장 $\exists x \notin S,\ x > 5$: 역시 $x = 6$이 증인 — **참**.

지우든 뒤집든 원문도 참이고 "부정"도 참이 되었다 — 진리값이 항상 반대여야 한다는 부정의 자격이 무너진 것이다. 무대는 주장의 내용이 아니라 심사가 벌어지는 범위의 선언이므로, 주장을 뒤집어도 심사 범위는 그대로여야 한다.

:::{container} quotebox
**확인 3.** 부정 제작에서 뒤집히는 것 세 가지와 뒤집히지 않는 것 한 가지를

총목록에서 찾아 말해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

뒤집히는 것: 양화사($\forall \leftrightarrow \exists$), 연결사($\land

\leftrightarrow \lor$), 조건문(화살표가 "인데"로). 뒤집히지 않는 것:

무대($\in S$) — 조건문 줄에서 가정이 그대로 남는 것과 같은 이치다.

$\neg(\forall x \in \mathbb{R}, \dots)$은

$\exists x \in \mathbb{R}, \dots$이지 $\exists x \notin \mathbb{R}$이 아니다.
:::

### 5 기계적 절차 — 왼쪽부터 층별 뒤집기

규칙이 여섯 개뿐이므로, 겹겹인 명제도 **바깥층부터 한 겹씩** 규칙 하나를 적용하면 풀린다. 3층짜리로 절차를 시연한다.

$$
\neg \Big( \forall x,\ \exists y,\ \big(P(x, y) \Rightarrow Q(x,y)\big) \Big)
$$

첫 걸음 — 맨 바깥층은 $\forall x$다. 총목록 4행을 적용하면 부정이 한 층 안으로 들어간다 (기호 $\leadsto$는 "…로 바뀐다"로 읽는다):

$$
\neg \forall x \leadsto \exists x\, \neg : \qquad \exists x,\ \neg\Big(\exists y,\ \big(P \Rightarrow Q\big)\Big)
$$

:::{container} quotebox
**확인 4.** 둘째 걸음을 적어 보자. 이번에 마주치는 바깥층은 무엇이고,

적용할 규칙은 총목록의 몇째 행인가.
:::

:::{admonition} 답
:class: quotebox dropdown

바깥층은 $\exists y$, 적용할 규칙은 5행($\neg \exists \leadsto \forall \neg$)이다:

$$
\exists x,\ \forall y,\ \neg(P \Rightarrow Q)
$$

무대가 있다면 그대로 두고 양화사만 뒤집는다.
:::

:::{container} quotebox
**확인 5.** 마지막 걸음을 완성해 보자. 남은 $\neg(P \Rightarrow Q)$에

적용할 규칙은 무엇이고, 끝 모양은 어떤 문장인가.
:::

:::{admonition} 답
:class: quotebox dropdown

조건문의 부정(총목록 3행) — 가정은 그대로, "인데"로 잇고, 결론만 부정한다:

$$
\exists x,\ \forall y,\ \big(P \land \neg Q\big)
$$

화살표가 $\land$로 바뀌었다는 것에 주의한다 — 부정 뒤에 조건문은 남지 않는다.
:::

:::{admonition} 끝 모양의 특징 — 완성 판정 기준
:class: quotebox

부정 기호($\neg$)가 양화사 밖에 하나도 남지 않고, 맨 안쪽 열린 문장에만

흡수된 상태 — 이것을 "부정을 완전히 안으로 밀어 넣었다"고 한다.

모의시험의 부정 문제(2, 7, 9, 15)는 전부 이 상태까지를 요구한다.
:::

:::{container} quotebox
**확인 6.** 다음 중 완성 상태인 것은 어느 쪽인가.

(가) $\exists x,\ \neg(\exists y,\ x + y = 0)$  (나) $\exists x,\ \forall y,\ x + y \neq 0$
:::

:::{admonition} 답
:class: quotebox dropdown

(나). (가)는 $\neg$가 아직 양화사 $\exists y$ 밖에 있으므로 한 층이 남은

중간 상태다 — 절차를 멈출 자리가 아니다. (나)는 부정이 열린 문장의

$\neq$ 안까지 흡수된 끝 모양이다.
:::

### 6 부정은 어디에 쓰이는 증명 기술인가

부정 만들기는 이후 주차의 세 가지 증명 기법이 공통으로 쓰는 준비 작업이다.

- **반증(29주차).** "$\forall x,\ P(x)$는 거짓"의 증명 = 부정

"$\exists x,\ \neg P(x)$"의 증명 = 반례 하나의 제작. 1주차 문제 18부터 쓰던 반례가 여기서 정체를 얻는다 — **반례는 부정의 증인이다.**

- **귀류법(21주차).** 첫 줄이 "결론의 부정을 가정하자"이다. 부정을 정확히

만들지 못하면 첫 줄부터 엉뚱한 명제를 다루게 된다. 문제 20이 그 첫 줄을 미리 써 보는 자리다.

- **대우 증명(19주차).** $\neg Q \Rightarrow \neg P$의 재료 두 개가 전부

부정이다. 부정이 틀리면 증명 전체가 다른 명제의 증명이 된다.

### 7 추론 규칙 — 전제에서 결론으로 가는 허가

증명문의 매 줄은 앞 줄들에서 다음 줄을 얻는 걸음이다. 어떤 걸음이 허용되는지를 이번 주에 못 박는다. 판정 기준부터 정의한다.

### 정의 11.1 — 타당한 추론 (valid inference) [백지 암기 대상]

:::{container} quotebox
전제 전부가 참이 되는 **모든** 상황에서 결론도 반드시 참일 때, 그 추론은

**타당하다**(valid)고 한다. 전제가 전부 참이면서 결론이 거짓인 상황이

하나라도 있으면 그 추론은 **오류**다.
:::

타당성은 결론이 실제로 참인지와 다른 문제다 — 심사 대상은 결론이 아니라 전제와 결론 사이의 **연결**이다(문제 13(d)에서 이 구분이 갈림길이 된다). 대표적인 타당한 추론 두 가지와, 닮은꼴 오류 두 가지를 표로 못 박는다.

| **이름** | **전제** | **결론** | **타당?** |
|---|---|---|---|
| 긍정 논법 (modus ponens) | $P \Rightarrow Q$, $\ P$ | $Q$ | ✓ |
| 부정 논법 (modus tollens) | $P \Rightarrow Q$, $\ \neg Q$ | $\neg P$ | ✓ (아래 확인 7) |
| 역 긍정의 오류 | $P \Rightarrow Q$, $\ Q$ | $P$ | ✗ (9주차 문제 10) |
| 이 긍정의 오류 | $P \Rightarrow Q$, $\ \neg P$ | $\neg Q$ | ✗ |

긍정 논법이 타당한 이유는 진리표에서 바로 읽힌다 — $P \Rightarrow Q$와 $P$가 동시에 참인 행은 첫 행(T, T)뿐이고, 그 행에서 $Q$는 참이다.

:::{container} quotebox
**확인 7.** 부정 논법이 타당함을 이미 가진 부품 두 개 — 9주차의 동치

하나와 방금의 긍정 논법 — 로 설명해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

$P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$ (대우, 9주차 예제 2.1 —

근거 ④). 전제 $P \Rightarrow Q$를 동치인 $\neg Q \Rightarrow \neg P$로

바꿔 들면, 남은 전제 $\neg Q$와 함께 긍정 논법이 발동해 $\neg P$가 나온다.

새 규칙처럼 보이는 것이 기존 부품 두 개의 조립이다.
:::

:::{container} quotebox
**확인 8.** 역 긍정의 오류가 오류임을 정의 11.1로 보이려면 무엇을 제작해야

하는가. 9주차 문제 10과 같은 꼴의 오류를, 9주차 문제 12의 소재("6의 배수이면

짝수이다")로 실제로 제작해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

전제 둘($P \Rightarrow Q$, $Q$)이 참이면서 결론($P$)이 거짓인 상황 하나.

$n = 4$: "6의 배수이면 짝수" 참, "4는 짝수" 참 — 그러나 "4는 6의 배수"는

거짓. 상황 하나로 오류 판정이 끝난다 — 오류 판정도 반례 제작이다.
:::

**논리는 어디로 가는가.** 15주차부터 쓰게 될 실제 증명문에는 진리표나 $\equiv$ 계산이 등장하지 않는다. 2부에서 만든 도구는 증명문의 문장 뒤에서 각 걸음의 허용 여부를 판정하는 기준으로 작동한다 — 증명문에 "따라서"라고 적는 매 순간이 긍정 논법의 발동이고, 부정 규칙은 19$\cdot$21$\cdot$29주차 기법의 첫 줄을 만든다. 도구가 눈에 안 보이게 되는 것이 도구가 완성됐다는 뜻이다.

### 8 근거 목록 갱신 — 칸은 그대로 네 개

1주차 §1.6에서 세운 근거 목록의 칸은 그대로 네 개다. 이번 주에 ① 칸에 정의 11.1이 추가되고, ④ 칸에 부정 규칙 총목록과 추론 규칙 두 개가 등록된다.

| **근거** | **내용** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | 지난 주까지의 정의 + **정의 11.1** | "타당" $\leftrightarrow$ "전제 참인 모든 상황에서 결론 참" 사이를 번역한다 |
| ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | 증명 문제(문제 19)에서 1주차 그대로 쓴다 |
| ③ 등식의 성질 | 대입 / 전개 / 묶기 | 문제 19의 직접 증명에서 그대로 쓴다 |
| ④ 이미 증명한 명제 | 9주차 동치 8개 + **부정 규칙 총목록**(양화사 두 줄은 ①의 자격 — 아래 참조) + **추론 규칙 2개** | 층을 뒤집는 매 걸음에 규칙 이름을 댄다 — "드모르간 2에 의해" |

총목록의 논리 연산 세 줄과 이중부정은 9주차에서 진리표로 증명을 마친 동치들이다. 양화사 두 줄은 진리표로 증명할 수 없다 — 무대가 무한이면 행을 나열할 수 없기 때문이다. 이 두 줄의 근거는 10주차에서 세운 양화사의 판정 기준 그 자체이고, 판정 기준은 양화사라는 기호의 정의였다 — 근거 ①의 자격으로 목록에 든다.

:::{container} quotebox
**확인 9.** 어떤 답안에 다음 세 걸음이 나왔다. 각각 허용되는가.

(가) "드모르간 2에 의해 $\neg(P \lor Q)$를 $\neg P \land \neg Q$로 바꾼다"

(나) "부정이니까 전부 반대로 적으면 $\exists x \notin S,\ \neg P(x)$"

(다) "$>$의 부정이므로 $<$로 바꾼다"
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 허용 — 근거 ④. 규칙 이름까지 댔으므로 완결이다.

(나) 불허 — 무대는 부정되지 않는다(§1.4의 실험). "전부 반대로"는 규칙이

아니라 규칙의 과잉 일반화다.

(다) 불허 — $>$가 성립하지 않는 경우는 $=$와 $<$ 전부이므로 부정은

$\le$다. $<$로 바꾸면 $=$인 경우가 양쪽 모두에서 빠진다.
:::