11주차 — 명제의 부정 만들기 + 2부 총정리#
이 주의 길잡이
핵심 문장: 부정은 층별로 뒤집는 기계적 작업이다 — \(\forall \leftrightarrow \exists\), \(\land \leftrightarrow \lor\), 조건문은 “인데”로.
이 주의 위치: 50주 과정의 11주차. 2부(논리)의 마지막 주 — 부정 규칙과 추론 규칙을 더하고, 총정리 모의시험으로 7~11주차를 닫는다.
원서 대응: BoP(Book of Proof) 2.10–2.12 — 병행자 참고용. 원서 없이 읽을 수 있다.
이번 주 목표#
양화사\(\cdot\)논리 연산이 겹겹인 명제의 부정을 층별 절차로 만들고, 부정 기호가 밖에 남지 않은 끝 모양까지 완성한다.
무대(\(\in S\))가 부정에서 뒤집히지 않는 이유를 실험으로 설명할 수 있다.
추론 규칙(긍정 논법\(\cdot\)부정 논법)과 닮은꼴 오류 두 가지를 구분한다.
2부(논리) 총정리 모의시험으로 7~11주차 내용을 자가 평가한다.
본문 곳곳의 확인 상자는 연필로 먼저 답하는 자리다. 바로 아래의 답 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.
준비 운동 (10주차 복습)#
\(\forall x \exists y,\ y > x\)와 \(\exists y \forall x,\ y > x\)의 진리값을 각각 판정하시오 (무대 \(\mathbb{Z}\)).
\(\exists\) 명제가 참임을 보이려면 무엇이 필요한가? \(\forall\) 명제가 거짓임을 보이려면?
\(\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\)”이 거짓임을 증명하고 싶다.
시도 — ‘아니다’를 앞에 붙여 밀어붙이기
“명제 ‘\(\forall x \in \mathbb{R},\ x^2 > 0\)’는 참이 아니다.”
— 주장으로는 이것으로 충분해 보인다. 그런데 이 문장이 참임을 보이는
다음 줄이 나오지 않는다. 무엇을 제시해야 하는가?
여기서 멈춘다. 10주차에서 세운 판정 절차는 두 가지뿐이다 — \(\forall\) 문장은 “모든 원소가 통과하는지”를, \(\exists\) 문장은 “증인 하나”를 요구한다. 그런데 지금 손에 있는 것은 \(\neg(\forall \dots)\) — 부정 기호가 문장 전체를 밖에서 감싼 꼴이고, 이 꼴에는 어느 절차도 붙어 있지 않다.
확인 1. 막힌 자리에서 필요해지는 것은 어떤 꼴의 문장인가.
“…인 \(x\)가 \(\underline{\quad}\)한다” 꼴로 답해 보자.
답
“존재한다” — \(\exists\) 문장이다. \(\exists\) 문장에는 “증인 하나를 제시하면
참이 확정된다”는 판정 절차가 붙어 있다. 필요한 것은 \(\neg(\forall \dots)\)를
진리값이 같은 \(\exists\) 문장으로 바꿔 적는 규칙이고, 그런 규칙들의
목록이 이번 주의 전부다.
이 주 전체의 기준
부정 기호가 문장 밖에 붙어 있는 동안은 판정 절차가 발동하지 않는다.
부정을 안으로 밀어 넣어 양화사 문장으로 바꿔야 증명이 시작된다.
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\)가 아니다 |
확인 2. 빈칸 (1)~(4)를 채워 보자. 위 두 줄은 10주차의 판정에서,
아래 두 줄은 9주차의 동치 목록에서 나온다.
답
(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\)이 증인 — 참.
지우든 뒤집든 원문도 참이고 “부정”도 참이 되었다 — 진리값이 항상 반대여야 한다는 부정의 자격이 무너진 것이다. 무대는 주장의 내용이 아니라 심사가 벌어지는 범위의 선언이므로, 주장을 뒤집어도 심사 범위는 그대로여야 한다.
확인 3. 부정 제작에서 뒤집히는 것 세 가지와 뒤집히지 않는 것 한 가지를
총목록에서 찾아 말해 보자.
답
뒤집히는 것: 양화사(\(\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층짜리로 절차를 시연한다.
첫 걸음 — 맨 바깥층은 \(\forall x\)다. 총목록 4행을 적용하면 부정이 한 층 안으로 들어간다 (기호 \(\leadsto\)는 “…로 바뀐다”로 읽는다):
확인 4. 둘째 걸음을 적어 보자. 이번에 마주치는 바깥층은 무엇이고,
적용할 규칙은 총목록의 몇째 행인가.
답
바깥층은 \(\exists y\), 적용할 규칙은 5행(\(\neg \exists \leadsto \forall \neg\))이다:
무대가 있다면 그대로 두고 양화사만 뒤집는다.
확인 5. 마지막 걸음을 완성해 보자. 남은 \(\neg(P \Rightarrow Q)\)에
적용할 규칙은 무엇이고, 끝 모양은 어떤 문장인가.
답
조건문의 부정(총목록 3행) — 가정은 그대로, “인데”로 잇고, 결론만 부정한다:
화살표가 \(\land\)로 바뀌었다는 것에 주의한다 — 부정 뒤에 조건문은 남지 않는다.
끝 모양의 특징 — 완성 판정 기준
부정 기호(\(\neg\))가 양화사 밖에 하나도 남지 않고, 맨 안쪽 열린 문장에만
흡수된 상태 — 이것을 “부정을 완전히 안으로 밀어 넣었다”고 한다.
모의시험의 부정 문제(2, 7, 9, 15)는 전부 이 상태까지를 요구한다.
확인 6. 다음 중 완성 상태인 것은 어느 쪽인가.
(가) \(\exists x,\ \neg(\exists y,\ x + y = 0)\) (나) \(\exists x,\ \forall y,\ x + y \neq 0\)
답
(나). (가)는 \(\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) [백지 암기 대상]#
전제 전부가 참이 되는 모든 상황에서 결론도 반드시 참일 때, 그 추론은
타당하다(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\)는 참이다.
확인 7. 부정 논법이 타당함을 이미 가진 부품 두 개 — 9주차의 동치
하나와 방금의 긍정 논법 — 로 설명해 보자.
답
\(P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P\) (대우, 9주차 예제 2.1 —
근거 ④). 전제 \(P \Rightarrow Q\)를 동치인 \(\neg Q \Rightarrow \neg P\)로
바꿔 들면, 남은 전제 \(\neg Q\)와 함께 긍정 논법이 발동해 \(\neg P\)가 나온다.
새 규칙처럼 보이는 것이 기존 부품 두 개의 조립이다.
확인 8. 역 긍정의 오류가 오류임을 정의 11.1로 보이려면 무엇을 제작해야
하는가. 9주차 문제 10과 같은 꼴의 오류를, 9주차 문제 12의 소재(“6의 배수이면
짝수이다”)로 실제로 제작해 보자.
답
전제 둘(\(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주차에서 세운 양화사의 판정 기준 그 자체이고, 판정 기준은 양화사라는 기호의 정의였다 — 근거 ①의 자격으로 목록에 든다.
확인 9. 어떤 답안에 다음 세 걸음이 나왔다. 각각 허용되는가.
(가) “드모르간 2에 의해 \(\neg(P \lor Q)\)를 \(\neg P \land \neg Q\)로 바꾼다”
(나) “부정이니까 전부 반대로 적으면 \(\exists x \notin S,\ \neg P(x)\)”
(다) “\(>\)의 부정이므로 \(<\)로 바꾼다”
답
(가) 허용 — 근거 ④. 규칙 이름까지 댔으므로 완결이다.
(나) 불허 — 무대는 부정되지 않는다(§1.4의 실험). “전부 반대로”는 규칙이
아니라 규칙의 과잉 일반화다.
(다) 불허 — \(>\)가 성립하지 않는 경우는 \(=\)와 \(<\) 전부이므로 부정은
\(\le\)다. \(<\)로 바꾸면 \(=\)인 경우가 양쪽 모두에서 빠진다.