7주차 · 강의 — 예제 · 연습 · 해설

예제 — 판정과 진리표를 함께 만들기

1~2주차의 예제가 증명을 한 줄씩 만들었다면, 이번 주의 예제는 판정을 한 칸씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 진리값 계산

문제. \(P\): “\(3 \mid 12\)”, \(Q\): “\(5 \mid 12\)”일 때 다음의 진리값을 구한다. (a) \(P \land Q\) (b) \(P \lor Q\) (c) \(\neg Q\) (d) \(\neg P \land Q\)

설계 — 계산 전에 정하는 두 가지. 증명의 번역표(가정 \(\to\) 출발점, 목표 \(\to\) 도착점)와 같은 순서다. 주어진 것과 만들 것을 먼저 확정한다.

	말	처리 방식
주어진 것 (출발점)	원자 명제 \(P\), \(Q\)	각각의 진리값을 2주차 정의 2.1로 판정해 확정한다
만들 것 (도착점)	(a)~(d)의 진리값	정의 7.3의 규칙을 안쪽부터 적용해 T/F 하나를 판독한다

확인 10. 출발점부터 처리해 보자. \(12 = 3 \times \underline{\quad}\)이고 그 수가

정수이므로 \(P\)는 \(\underline{\quad}\)이다. \(12 = 5c\)인 정수 \(c\)는 \(\underline{\quad}\)하므로

\(Q\)는 \(\underline{\quad}\)이다.

답

\(12 = 3 \times 4\)이고 \(4 \in \mathbb{Z}\)이므로 \(P\)는 참(T)이다. \(12 = 5c\)이려면

\(c = \frac{12}{5}\)인데 정수가 아니므로 그런 정수는 존재하지 않고, \(Q\)는

거짓(F)이다. 원자의 진리값 판정에 쓴 것은 2주차 정의 2.1(근거 ①)이다 — 논리

계산은 언제나 원자 판정 위에 선다.

확인 11. (a)~(c)를 판정해 보자. (a) \(P \land Q\) — 적용할 규칙은

“\(\underline{\qquad}\)일 때만 참”이므로 값은 \(\underline{\quad}\).

(b) \(P \lor Q = \underline{\quad}\). (c) \(\neg Q = \underline{\quad}\).

답

(a) “둘 다 참일 때만 참”이 \(\land\)의 규칙이다. \(Q\) 하나가 F인 순간 조건이

무너지므로 \(P\)를 볼 것도 없이 F — 하나의 거짓이 전체를 거짓으로 만든다.

(b) \(\lor\)는 “적어도 하나가 참이면 참” — \(P\)가 T이므로 T. 하나의 참이 전체를

참으로 만든다 — \(\land\)과 정확히 반대 방향이다.

(c) \(\neg\)는 진리값을 뒤집는다 — \(Q\)가 F이므로 \(\neg Q\)는 T.

확인 12. (d) \(\neg P \land Q\)는 연산이 두 개다. §1.6의 절차대로 안쪽부터:

\(\neg P = \underline{\quad}\)이고, 따라서 $\neg P \land Q = \underline{ } \land

\underline{ } = \underline{ }$이다.

답

안쪽 \(\neg P\)부터: \(P\)가 T이므로 \(\neg P\) = F. 바깥 \(\land\): \(\neg P \land Q\) =

F \(\land\) F = F. (\(\neg\)는 바로 뒤의 \(P\)에만 붙는다 — \(\neg(P \land Q)\)였다면

값이 T로 달라진다. 괄호의 유무가 명제를 바꾼다.)

완성본. 방금 만든 판정을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.

증명의 한 줄	왜 이 줄을 쓰는가?
\(12 = 3 \times 4\), \(4 \in \mathbb{Z}\)이므로 \(P\)는 T. \(12 = 5c\)인 정수 \(c\)는 없으므로 \(Q\)는 F.	원자 명제의 진리값 확정(정의 2.1, 근거 ①). 복합 명제의 계산은 원자의 값에서 시작한다.
(a) \(Q\)가 F이므로 \(P \land Q\) = F.	\(\land\)는 둘 다 T일 때만 T(정의 7.3) — 하나의 F가 전체를 F로 확정한다.
(b) \(P\)가 T이므로 \(P \lor Q\) = T.	\(\lor\)는 하나만 T여도 T — 하나의 T가 전체를 T로 확정한다.
(c) \(Q\)가 F이므로 \(\neg Q\) = T.	\(\neg\)는 진리값을 뒤집는다.
(d) \(\neg P\) = F이고, F \(\land\) F = F.	안쪽 연산부터 계산한다(§1.6의 절차 ②③).

예제 2.2 — \(\neg(P \land Q)\)의 진리표

이번에는 특정 진리값이 아니라 모든 진리값 조합에 대한 판정 — 진리표 — 을 만든다. 설계만 함께 하고, 표는 완성본으로 본다.

확인 13. §1.6의 절차대로 설계해 보자. ① 변수가 \(\underline{\quad}\)개이므로

\(\underline{\quad}\)행. ② 안쪽 연산의 열, 곧 원자 열 다음에 먼저 추가할 열은

\(\underline{\qquad}\)이다.

답

① 변수 2개(\(P\), \(Q\)) \(\to\) \(2^2 = 4\)행. ② 괄호 안의 \(P \land Q\) 열을 먼저 만들고,

그 열을 뒤집어 \(\neg(P \land Q)\) 열을 완성한다. 부정의 범위가 괄호로 \(P \land Q\)

전체에 걸려 있다 — \(\neg P \land Q\)(예제 2.1 (d))와는 다른 명제다.

\(P\)	\(Q\)	\(P \land Q\)	\(\neg(P \land Q)\)
T	T	T	F
T	F	F	T
F	T	F	T
F	F	F	T

관찰. 마지막 열이 T인 행은 둘째~넷째 행 — “\(P\) 그리고 \(Q\)”가 거짓이 되는 것은 적어도 하나가 거짓일 때다. 그렇다면 마지막 열은 \(\neg P \lor \neg Q\)의 열과 같아 보인다. 이 예감은 문제 4에서 행별 대조로 확인하고, 정식 이름(드모르간 법칙)과 선언은 9주차에서 한다 — 5주차에 벤 다이어그램으로 관찰만 해 둔 그 법칙의 논리 버전이다.

예제 2.3 — 수학 문장 분해

문제. “\(6 \le x \le 10\)”을 논리 연산으로 분해하시오.

이번에는 설계부터 혼자 한다 — 원자 문장이 무엇인지, 접속사가 무엇인지를 스스로 정한 뒤 아래 풀이와 대조한다.

풀이. 부등식 연쇄 \(6 \le x \le 10\)은 두 조건이 동시에 성립한다는 뜻이므로, 원자는 “\(6 \le x\)”와 “\(x \le 10\)” 두 개이고 접속사는 “그리고”다:

\[ (6 \le x) \land (x \le 10) \]

부등식 연쇄는 “그리고”의 축약 표기다. 반면 “\(x^2 = 4\)의 해는 \(x = 2\) 또는 \(x = -2\)”는 두 등식 중 적어도 하나가 성립한다는 뜻이므로 \((x = 2) \lor (x = -2)\)로 분해된다. 고1에서 외운 “연립부등식의 해는 교집합, 방정식의 해 모으기는 합집합”의 논리적 정체가 이것이다 — \(\land\)가 \(\cap\)으로, \(\lor\)가 \(\cup\)으로 나타난 것뿐이다(정의 7.3 아래의 논리–집합 대응표). 각 원자가 열린 문장(정의 7.2)이므로 분해 결과도 열린 문장이다.

관찰 — 세 예제의 같은 뼈대

예제 2.1(값 계산), 2.2(진리표), 2.3(문장 분해)은 소재가 다르지만 뼈대가 같다. 대응표의 빈칸을 채워 보자.

확인 14. 각 예제에서 다음 세 단계에 해당하는 대목을 찾아 보자.

① 원자 확정 — 2.1에서는 \(P, Q\)의 진리값 판정, 2.3에서는 \(\underline{\qquad}\)

② 안쪽부터 규칙 적용 — 2.1(d)에서는 \(\neg P\) 먼저, 2.2에서는 \(\underline{\qquad}\) 먼저

③ 결과 판독 — 2.1은 T/F 하나, 2.2는 \(\underline{\qquad}\) 전체

답

① 2.3에서는 원자 문장 두 개(”\(6 \le x\)”, “\(x \le 10\)”)를 찾아내는 일이다.

② 2.2에서는 괄호 안 \(P \land Q\) 열을 먼저 만든다.

③ 2.2의 결과는 마지막 열 전체 — 조합마다의 판정 목록이다.

세 예제 모두 정확히 이 세 걸음이다.

방금 확인한 뼈대에 이름을 붙인다.

백지 암기 대상

복합 명제 처리의 3단계 틀

① 원자 명제로 쪼개고 진리값(또는 변수)을 확정한다 \(\to\) ② 안쪽 연산부터 정의 7.3의 규칙을 하나씩 적용한다 \(\to\) ③ 마지막 값(또는 열)을 판독한다

이 틀은 8주차의 조건문, 9주차의 동치 계산에서도 그대로 쓰는 기본형이다.

빈칸 사다리 — 지지대를 하나씩 빼며

필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.

훈련 1 ●○○ — 값 빈칸

\(P\)가 참, \(Q\)가 거짓일 때 두 명제의 진리값을 계산한다.

계산. \(P \lor Q\)는 \(P\)가 참이므로 \(\underline{\quad(1)\quad}\)이고, 부정은 진리값을 뒤집으므로 \(\neg(P \lor Q) = \underline{\quad(2)\quad}\)이다. 한편 \(\neg P = \underline{\quad(3)\quad}\), \(\neg Q = \underline{\quad(4)\quad}\)이므로 \(\neg P \land \neg Q = \underline{\quad(5)\quad}\)이다.

(두 결과가 같은지 관찰해 둔다 — 예제 2.2의 예감과 짝을 이루는 관찰이고, 문제 18(b)에서 표 전체로 확인한다.)

훈련 2 ●●○ — 값과 근거를 함께

\(P\)와 그 부정을 연산으로 묶은 두 명제의 진리표다. 빈칸을 채운다.

\(P\)	\(\neg P\)	\(P \land \neg P\)	\(P \lor \neg P\)
T	\(\underline{\quad(1)\quad}\)	\(\underline{\quad(2)\quad}\)	\(\underline{\quad(3)\quad}\)
F	\(\underline{\quad(4)\quad}\)	\(\underline{\quad(5)\quad}\)	\(\underline{\quad(6)\quad}\)

마지막 두 열을 읽으면 — \(P \land \neg P\)는 진리값이 항상 \(\underline{\quad(7)\quad}\)이고, \(P \lor \neg P\)는 항상 \(\underline{\quad(8)\quad}\)이다. 근거: 어느 행에서든 \(P\)와 \(\neg P\)는 진리값이 서로 \(\underline{\quad(9)\quad}\)이기 때문이다.

이렇게 모든 행에서 거짓인 명제를 모순(contradiction), 모든 행에서 참인 명제를 항진명제(tautology)라 한다. “\(P \land \neg P\)는 항상 거짓” 위에 21주차 귀류법이 선다 — 지금 확인한 두 행짜리 표가 그 기초 공사다. 문제 16의 (a)(b)가 이 훈련의 결과를 재사용한다.

훈련 3 ●●● — 절차의 뼈대만

명제. \(\neg P \lor (Q \land R)\)의 진리표를 작성한다.

§1.6의 절차 세 걸음을 각 칸에 통째로 채운 뒤, 실제 표를 완성해 해설과 대조한다.

• ① 행 수와 원자 열 나열 방식: \(\underline{\quad(1)\quad}\)

• ② 원자 열 다음에 추가할 중간 열(안쪽부터 순서대로): \(\underline{\quad(2)\quad}\)

• ③ 완성 후 판독 — 마지막 열이 T가 되는 행의 특징: \(\underline{\quad(3)\quad}\)

(이 훈련이 문제 3, 19(8행 진리표)의 예행연습이다.)

연습문제 (20문항)

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다. 진리표 문제는 §1.6의 절차(행 수 \(\to\) 원자 열 \(\to\) 안쪽 열 \(\to\) 바깥 열) 순서로 쓴다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “(b)는 T(맞음)”는 0점이고, “\(P\)가 참이므로 \(\lor\)의

규칙(하나만 참이어도 참)에 의해 T”가 만점이다. 진리표 문제는 중간 열을 생략하지 않는

것까지가 근거다. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.

기본 ●○○

1. 명제인지 판별하고, 명제면 진리값을 쓰시오. (a) \(17 \in \mathbb{N}\) (b) \(x^2 \ge 0\) (c) \(\{1\} \subseteq \{1,2\}\) (d) 소수는 아름다운 수이다. (e) \(0.5 \in \mathbb{Z}\)

힌트

기준은 하나 — 진리값이 정확히 하나로 확정되는가(정의 7.1). 변수가 살아 있으면

열린 문장, 주관\(\cdot\)명령이면 명제 아님. (b)에서 \(x\)의 지위를 먼저 확인한다.

2. \(P\): “\(2\)는 짝수” (참), \(Q\): “\(7\)은 짝수” (거짓), \(R\): “\(9 = 3^2\)” (참)일 때 진리값을 구하시오. (a) \(P \land R\) (b) \(Q \lor R\) (c) \(\neg P \lor Q\) (d) \((P \land Q) \lor R\) (e) \(P \land (Q \lor \neg R)\)

힌트

원자의 값(T, F, T)을 먼저 적어 놓고, 괄호 안 \(\to\) 밖의 순서로 규칙을 기계 적용한다.

\(\land\)는 “둘 다 T여야 T”, \(\lor\)는 “하나만 T여도 T”다.

3. \(P \lor (Q \land R)\)의 진리표를 작성하시오. (8행)

힌트

변수 3개 \(\to\) \(2^3 = 8\)행. 원자 열은 §1.6 절차 ①의 반씩 쪼개기로 나열하고, 괄호 안

\(Q \land R\) 열을 먼저 만든 뒤 \(P\)와 \(\lor\)한다.

두 명제가 “같다”는 것 — 문제 4\(\cdot\)7\(\cdot\)13\(\cdot\)15\(\cdot\)18의 판정 기준

두 복합 명제를 비교하라는 문제가 이어진다. 비교 기준은 하나 — 진리표의 마지막

열이 모든 행에서 일치하는가다. 일치하면 두 명제는 어떤 진리값 조합에서도 같은

판정을 내리므로 서로 바꿔 쓸 수 있다. 이 관계의 정식 이름(논리적 동치)과 기호는

9주차에서 도입한다 — 지금은 판정만 한다.

4. \(\neg P \lor \neg Q\)의 진리표를 작성하고, 예제 2.2의 \(\neg(P \land Q)\) 열과 비교하시오.

힌트

\(\neg P\) 열과 \(\neg Q\) 열을 각각 만든 뒤 \(\lor\)한다. 완성되면 예제 2.2의 마지막 열

(F, T, T, T)과 행별로 대조한다 — 표를 다시 만들 필요는 없다(근거 ④).

5. 다음 문장을 \(P(x)\) 꼴 열린 문장과 논리 연산으로 분해하시오. (a) “\(x\)는 짝수이고 3의 배수이다” (b) “\(x < -2\) 또는 \(x > 2\)” (c) “\(x\)는 10 이상 20 미만”

힌트

접속사(“이고”, “또는”)를 찾아 원자 문장으로 쪼갠다 — 예제 2.3의 절차다. (c)는

접속사가 숨어 있다: “이상”과 “미만”이 각각 부등식 하나씩이다.

6. 다음 문장을 [참인 명제 / 거짓인 명제 / 열린 문장 / 명제 아님(기타)]으로 분류하시오. (a) \(3 < 2\) (b) \(x\)는 소수이다 (c) 답을 말해라. (d) \(\emptyset \subseteq \emptyset\) (e) \(n^2 = 2\)인 정수 \(n\)이 존재한다

힌트

문제 1과 같은 기준에 더해, (e)는 “존재한다”가 변수 \(n\)을 묶는다는 점에 주의한다 —

§1.4의 확인 4에서 본 “열린 문장을 명제로 만드는 둘째 방법”이다.

표준 ●●○

7. \(\neg(\neg P)\)의 진리표를 만들어 \(P\)와 같음을 확인하시오. 이 사실(“이중부정”)이 집합에서 무엇에 대응하는지 쓰시오.

8. \((P \lor Q) \land \neg(P \land Q)\)의 진리표를 작성하시오. 이 명제가 참이 되는 조건을 일상어로 표현하면 무엇인가? (힌트: “짜장 또는 짬뽕”의 그 ‘또는’)

힌트

중간 열 셋 — \(P \lor Q\), \(P \land Q\), \(\neg(P \land Q)\) — 을 차례로 쌓고 마지막에

\(\land\)한다. 완성되면 T인 행이 어떤 행인지 말로 옮겨 본다.

9. 두 열린 문장 \(P(n)\): “\(2 \mid n\)”, \(Q(n)\): “\(3 \mid n\)”에 대해, \(P(n) \land Q(n)\)이 참이 되는 \(n\)의 집합을 조건제시법과 생성형으로 각각 쓰시오. (5주차 문제 9의 재방문. “2로도 3으로도 나누어떨어지면 6의 배수”는 지금은 나열 관찰로 인정하고 쓴다 — 20주차에서 증명한다.)

10. \((P \land Q) \lor \neg P\)의 진리표를 작성하시오.

11. 식당 메뉴에 “식사 주문 시 커피 또는 차를 드립니다”라고 쓰여 있다. (a) 일상어 해석과 (b) 논리학의 \(\lor\) 해석이 어떻게 다른지 쓰고, (c) 5주차의 \(A \cup B\)가 어느 쪽 해석을 따르는지 답하시오.

힌트

“둘 다 받겠다”가 허용되는지가 두 해석의 분기점이다 — §1.5에서 수학이 어느 쪽을

택했고 왜 택했는지를 되짚는다.

12. 다음을 논리 연산으로 분해하시오. (a) \(|x| > 3\) (절댓값의 뜻을 부등식 두 개로) (b) \(0 < x \le 5\) (c) “\(n\)은 4의 배수도 6의 배수도 아니다”

힌트

(a) \(|x| > 3\)은 수직선에서 두 구간이다 — 잇는 접속사가 \(\land\)인지 \(\lor\)인지

헷갈리면, 원 문장을 만족하는 값 하나(예: \(x = 4\))를 골라 그 독법의 판정이 원

문장과 갈리는지 검사한다. (c) “~도 ~도 아니다”는 부정 두 개를 어느 접속사로

잇는지가 관건이다.

13. \(P \lor (\neg P \land Q)\)의 진리표를 작성하고, 이것이 \(P \lor Q\)와 같음을 확인하시오.

14. 집합 기호를 논리 기호로 번역하시오. (a) \(x \in A - B\) (b) \(x \in (A \cup B)^c\) (c) \(x \in A \cap (B \cup C)\)

힌트

각 연산의 정의문(“그리고 / 또는 / 아니다”)을 그대로 옮겨 적는다. (a)는 5주차

\(A - B\)의 정의문부터 소리 내어 읽어 본다.

도전 ●●●

15. 진리표를 사용해 다음을 판정하시오: \(P \land (Q \lor R)\)와 \((P \land Q) \lor (P \land R)\)는 모든 진리값 조합에서 일치하는가? 일치한다면, 이것은 집합의 어떤 법칙(\(\cap, \cup\)의 관계식)에 대응하는가?

힌트

8행짜리 표 두 개가 부담스러우면 행을 묶는다 — \(P\) = F인 네 행과 \(P\) = T인 네 행에서

두 식이 각각 무엇이 되는지를 따로 본다. 집합 대응은 대응표로 번역하면 나온다.

목표 열에서 명제를 역산하기 — 문제 16의 새 도구

지금까지는 명제에서 열을 계산했다. 문제 16은 방향이 반대다 — 열이 주어지고 그

열을 만드는 명제를 조립한다. 요령: 목표 열이 T인 행을 찾아, 그 행의 진리값 조합을

\(\land\)로 적는다(예: \(P\) = T, \(Q\) = F인 행 \(\to\) \(P \land \neg Q\)). 그런 행이 여럿이면

각각을 \(\lor\)로 잇는다. 항상 참\(\cdot\)항상 거짓인 열은 훈련 2가 이미 만들어 두었다.

16. 명제 변수 \(P, Q\)로 만든 복합 명제의 진리표 마지막 열은 (T/F 4칸이므로) 최대 \(2^4 = 16\)가지가 가능하다. 다음 각 목표 열을 만드는 복합 명제를 하나씩 제시하시오. (a) T, T, T, T (항상 참) (b) F, F, F, F (항상 거짓) (c) F, T, T, F (\(P, Q\)의 진리값이 다를 때만 참)

힌트

(a)(b)는 훈련 2의 두 열이 그대로 답이다. (c)에서 T인 행은 둘째 행(\(P\)=T, \(Q\)=F)과

셋째 행(\(P\)=F, \(Q\)=T) — 각각을 \(\land\)로 적고 \(\lor\)로 잇는다. 또는 문제 8의

완성표에서 같은 열을 이미 만들었다(근거 ④).

참\(\cdot\)거짓 두 가정으로 나누기 — 문제 17의 도구

명제라면 진리값은 참이거나 거짓, 정확히 하나다. 그러므로 “참이라면 어떻게

되는가”와 “거짓이라면 어떻게 되는가”를 각각 검토하면 전체를 빠짐없이 덮는다 —

1주차 문제 16에서 쓴 경우 나누기와 같은 틀이고, 채점 기준도 같다(빠짐없이

덮는가, 각 경우가 완결되는가). 양쪽 모두에서 충돌이 나면 “어느 진리값도 배정할

수 없다”는 결론이 남는다. 이 사고가 21주차 귀류법으로 자란다.

17. (서술) “이 문장은 거짓이다”가 명제가 될 수 없는 이유를, 참이라 가정한 경우와 거짓이라 가정한 경우로 나누어 각각 한 문장으로 쓰시오. (귀류법식 사고의 첫 연습이다.)

힌트

각 경우에서 “가정한 진리값”과 “문장이 주장하는 내용”을 나란히 놓는다 — 이 문장은

자기 자신의 진리값을 주장하므로 둘이 충돌하는지 검사할 수 있다.

18. (a) \(\neg(P \land P)\)의 진리표를 만들어 \(\neg P\)와 같음을 확인하시오. (b) \(\neg(\neg P \land \neg Q)\)의 진리표를 만들어 \(P \lor Q\)와 같음을 확인하시오. — (b)는 “\(\lor\)는 \(\neg\)와 \(\land\)만으로 조립 가능”이라는 뜻이다.

힌트

(a)는 2행, (b)는 4행. (b)는 안쪽 \(\neg P \land \neg Q\) 열부터 쌓는다 — 훈련 1에서

한 값 계산의 표 버전이다. 완성되면 \(P \lor Q\) 열과 행별 대조한다.

19. \((P \lor Q) \land (\neg P \lor R)\)의 진리표(8행)를 작성하시오.

힌트

두 괄호의 열을 각각 만들고 \(\land\)한다. \(P\) = T인 행에서는 왼쪽 괄호가 자동으로

T이므로 전체 값은 오른쪽 괄호가 정하고, \(P\) = F인 행에서는 반대다 — 이 관찰이

계산을 절반으로 줄인다.

20. (서술) “거짓인 명제도 명제다”라는 사실이 수학에서 왜 중요한지, 다음 두 상황을 예로 들어 설명하시오: ① 어떤 추측(conjecture)이 거짓으로 판명되는 경우 ② 귀류법(21주차)에서 일부러 거짓일 수도 있는 가정을 세우는 경우. (각 두 문장 이내)

힌트

거짓인 문장이 명제가 아니라고 해 보자 — ①에서는 “그 추측은 거짓이다”라는 판정이,

②에서는 가정을 세우고 논리 연산을 적용하는 일이 각각 어떻게 되는지 따라가 본다.

1주차 문제 18의 반박 경험이 ①의 재료다.

백지 재현 — 복습 프로토콜

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.

1차 시도 (4일차) — 틀 카드 허용. 3단계 틀(§2 관찰)과 논리–집합 대응표만 펴 놓고, \(\land, \lor, \neg\)의 진리표 세 개와 예제 2.2의 진리표를 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다.

2차 시도 (5일차) — 완전 백지. 아무것도 보지 않고 수행한다:

• 명제의 정의를 “정확히 하나”라는 조각까지 그대로 쓰고, 거짓인 문장도 명제인 이유를 예와 함께 설명했다.

• \(\land, \lor, \neg\)의 진리표 세 개를 백지에 그렸다.

• 수학의 “또는”과 일상어 “또는”의 차이를, 5주차 합집합과의 정합성을 근거로 설명했다.

• 논리–집합 대응표(\(\land\)–\(\cap\), \(\lor\)–\(\cup\), \(\neg\)–\(^c\))를 썼다.

• 예제 2.2(\(\neg(P \land Q)\))의 4행 진리표를 절차대로 재현했다.

• \(P \land \neg P\)가 항상 거짓임을 진리표 없이 한 문장으로 설명했다.

• 열린 문장이 명제가 아닌 이유와, 명제로 만드는 두 가지 방법을 말했다.

막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.

막힌 지점	처방
명제 판별이 흔들린다	§1.3 해부 표 — “정확히 하나”의 역할과 삭제 실험
진리표의 행을 빠뜨린다	§1.6 절차 ① — 반씩 쪼개는 기계적 나열
\(\neg\)의 적용 범위가 헷갈린다	§1.6 절차 ② — 괄호 유무 비교(확인 7)
중간 열 없이 한 번에 쓰려다 막힌다	예제 2.2의 설계 — 안쪽 연산부터 열 하나씩
“또는” 판정이 갈린다	§1.5 — 포함적 or의 선택과 그 이유

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

해설

각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

빈칸 사다리 — 훈련 1

(1) T (\(P\)가 참이므로 하나만 참이어도 참) (2) F (T를 뒤집음) (3) F (4) T (5) F (F \(\land\) T — 둘 다 참이 아니므로)

※ \(\neg(P \lor Q)\)와 \(\neg P \land \neg Q\)가 이 값 조합에서 같은 F로 떨어졌다. 예제 2.2의 예감과 짝을 이루는 관찰이고, 문제 18(b)가 표 전체로 확정한다.

빈칸 사다리 — 훈련 2

(1) F (2) F (3) T (4) T (5) F (6) T (7) 거짓(F) (8) 참(T) (9) 반대 (한쪽이 T이면 다른 쪽은 반드시 F)

※ \(\land\)는 둘 다 참을 요구하는데 \(P\)와 \(\neg P\)는 동시에 참일 수 없으므로 \(P \land \neg P\)는 어느 행에서도 F다. \(\lor\)는 하나만 참이면 되는데 둘 중 하나는 반드시 참이므로 \(P \lor \neg P\)는 어느 행에서도 T다.

빈칸 사다리 — 훈련 3

(1) 변수 3개이므로 \(2^3 = 8\)행. \(P\) 열은 T 4개\(\cdot\)F 4개, \(Q\) 열은 TTFF 반복, \(R\) 열은 TF 반복. (2) 안쪽부터 — \(\neg P\) 열, \(Q \land R\) 열을 만든 뒤 마지막에 둘을 \(\lor\)한다. (3) 완성표는 다음과 같다.

\(P\)	\(Q\)	\(R\)	\(\neg P\)	\(Q \land R\)	\(\neg P \lor (Q \land R)\)
T	T	T	F	T	T
T	T	F	F	F	F
T	F	T	F	F	F
T	F	F	F	F	F
F	T	T	T	T	T
F	T	F	T	F	T
F	F	T	T	F	T
F	F	F	T	F	T

마지막 열이 T인 행의 특징: \(P\)가 거짓이거나, \(Q\)와 \(R\)가 둘 다 참인 행이다. (\(P\) = F인 네 행은 \(\neg P\) = T로 자동 통과하고, \(P\) = T인 행은 \(Q \land R\)가 값을 정한다.)

문제 1

접근. 판별 기준은 하나 — “진리값이 정확히 하나로 확정되는가”(정의 7.1). 변수가 살아 있으면 열린 문장, 주관\(\cdot\)명령\(\cdot\)질문이면 명제 아님. 명제로 판정되면 진리값까지 근거와 함께 적는다.

풀이. (a) 명제, 참 — 17은 자연수이므로 \(17 \in \mathbb{N}\)은 참으로 확정된다. (b) 명제 아님(열린 문장) — \(x\)가 정해지지 않아 진리값이 미정이다. ※ “모든 실수 \(x\)에 대해 \(x^2 \ge 0\)”으로 양화하면 참인 명제가 된다(10주차). 지금 상태로는 아직 문장에 변수가 살아 있다. (c) 명제, 참 — \(\{1\}\)의 원소 1이 \(\{1, 2\}\)에 속하므로(4주차 \(\subseteq\)의 정의) 참으로 확정된다. (d) 명제 아님 — “아름답다”는 객관적 판정 기준이 없는 주관 서술이다. (e) 명제, 거짓 — \(0.5\)는 정수가 아니므로 거짓으로 확정된다. 거짓이어도 확정이므로 명제의 자격은 충분하다.

복기. (b)와 (e)의 대비가 핵심이다 — (b)는 진리값 미정(명제 아님), (e)는 진리값 확정\(\cdot\)거짓(명제). “틀린 문장”과 “판정 안 되는 문장”은 다른 범주다.

문제 2

접근. 원자의 값 \(P\) = T, \(Q\) = F, \(R\) = T를 먼저 적어 놓고, 괄호 안부터 정의 7.3의 규칙을 기계 적용한다. \(\land\)는 “둘 다 T여야 T”, \(\lor\)는 “하나만 T여도 T”, \(\neg\)는 뒤집기다.

풀이. (a) \(P \land R\) = T \(\land\) T = T (둘 다 참). (b) \(Q \lor R\) = F \(\lor\) T = T (\(R\) 하나가 참이므로 충분). (c) 안쪽부터: \(\neg P\) = F. 따라서 \(\neg P \lor Q\) = F \(\lor\) F = F (어느 쪽도 참이 아니다). (d) 괄호부터: \(P \land Q\) = T \(\land\) F = F. 따라서 \((P \land Q) \lor R\) = F \(\lor\) T = T. (e) 괄호 안의 안쪽부터: \(\neg R\) = F, \(Q \lor \neg R\) = F \(\lor\) F = F. 따라서 \(P \land (Q \lor \neg R)\) = T \(\land\) F = F.

문제 3

접근. 변수 3개 \(\to\) \(2^3 = 8\)행. 원자 열은 §1.6 절차 ①의 반씩 쪼개기로 나열하고, 괄호 안 \(Q \land R\) 열을 먼저 만든 뒤 \(P\)와 \(\lor\)한다. \(P\) = T인 행은 계산 없이 T다 — 하나의 참이 \(\lor\) 전체를 참으로 만들기 때문이다.

풀이.

\(P\)	\(Q\)	\(R\)	\(Q \land R\)	\(P \lor (Q \land R)\)
T	T	T	T	T
T	T	F	F	T
T	F	T	F	T
T	F	F	F	T
F	T	T	T	T
F	T	F	F	F
F	F	T	F	F
F	F	F	F	F

검산. \(P\) = T인 위 네 행은 전부 T, \(P\) = F인 아래 네 행은 \(Q \land R\) 열과 값이 같다 — \(\lor\)의 규칙에서 예상되는 패턴 그대로다.

복기. 이 명제는 5주차 문제 14에서 수치로 관찰한 \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)의 논리 쪽 재료다 — 문제 15의 쌍둥이 분배법칙과 함께 9주차에서 정식 선언된다.

문제 4

접근. \(\neg P\), \(\neg Q\) 열을 각각 만든 뒤 \(\lor\)한다. 완성되면 예제 2.2의 \(\neg(P \land Q)\) 열과 행별로 대조한다 — 이미 만든 표의 재사용이 근거 ④다.

풀이.

\(P\)	\(Q\)	\(\neg P\)	\(\neg Q\)	\(\neg P \lor \neg Q\)
T	T	F	F	F
T	F	F	T	T
F	T	T	F	T
F	F	T	T	T

예제 2.2의 \(\neg(P \land Q)\) 열은 위에서부터 F, T, T, T — 네 행 전부에서 일치한다. 따라서 두 명제는 모든 진리값 조합에서 같은 판정을 내린다. “그리고의 부정 = 각각의 부정을 또는으로” — 드모르간 법칙의 진리표 확인이고, 정식 선언은 9주차에서 한다 (5주차에서 벤 다이어그램으로 관찰한 그 법칙이다).

복기. 두 명제의 “같음” 판정은 마지막 열의 행별 대조가 전부다 — §4의 상자에서 세운 기준 그대로이고, 이 대조가 9주차에서 논리적 동치라는 이름을 얻는다.

문제 5

접근. 접속사(“이고”, “또는”)와 범위 표현을 찾아 원자 문장으로 쪼갠다 — 예제 2.3의 절차다. 각 원자는 \(x\)가 살아 있는 열린 문장이므로 분해 결과도 열린 문장이다.

풀이. (a) 원자는 “\(x\)는 짝수”(\(2 \mid x\))와 “\(x\)는 3의 배수”(\(3 \mid x\)), 접속사는 “이고”: \((2 \mid x) \land (3 \mid x)\). (b) 원자는 “\(x < -2\)”와 “\(x > 2\)”, 접속사는 “또는”: \((x < -2) \lor (x > 2)\). 접속사 검산 — \(x = 3\)은 원 문장을 만족하지만, \((x < -2) \land (x > 2)\)는 어떤 \(x\)도 만족하지 못하는 항상 거짓인 문장이다. 원 문장에 해가 실재하므로 항상 거짓이 되는 \(\land\)-독법은 원 문장의 뜻일 수 없고, \(\lor\)가 맞는 접속사다. (c) “10 이상”은 \(x \ge 10\), “20 미만”은 \(x < 20\)이고 두 조건이 동시에 성립해야 하므로: \((x \ge 10) \land (x < 20)\). “이상/미만”에서 등호의 유무가 갈린다 — \(\ge\)에는 등호가 붙고 \(<\)에는 붙지 않는다.

복기. 일상어 문장의 분해는 ① 원자 찾기 ② 접속사 판별의 두 걸음이다. 접속사가 숨은 (c) 같은 문장은 범위의 양 끝을 각각 부등식으로 꺼내면 “그리고”가 드러난다.

문제 6

접근. 문제 1과 같은 기준으로 네 범주에 배정한다. (e)만 함정이 있다 — “존재한다”가 변수 \(n\)을 묶으므로, 변수가 보여도 열린 문장이 아니다(§1.4 확인 4의 둘째 방법).

풀이. (a) 거짓인 명제 — \(3 < 2\)는 거짓으로 확정된다. (b) 열린 문장 — \(x\)가 정해지지 않아 진리값 미정이다 (\(x = 7\)이면 참, \(x = 8\)이면 거짓). (c) 명제 아님(기타) — 명령문에는 참\(\cdot\)거짓을 물을 수 없다. (d) 참인 명제 — \(\emptyset \subseteq \emptyset\)은 공허한 참(4주차 §1.4)이다: \(\emptyset\)의 원소 중 \(\emptyset\)에 속하지 않는 것이 하나도 없으므로 \(\subseteq\)의 조건이 성립한다. (e) 거짓인 명제 — “존재한다”까지 붙어 있으므로 진리값이 확정된다. 거짓인 이유: 정수 \(n\)이 \(|n| \le 1\)이면 \(n^2 \le 1\)이고 \(|n| \ge 2\)이면 \(n^2 \ge 4\)이므로, \(n^2 = 2\)인 정수는 없다. 열린 문장으로 분류하면 안 되는 항목이다.

복기. 변수가 보인다고 곧 열린 문장이 아니다 — 변수가 묶여 있는가를 본다. (b)의 \(x\)는 자유롭고 (e)의 \(n\)은 “존재한다”에 묶여 있다. 10주차 양화사의 예고편이다.

문제 7

접근. 변수 1개 \(\to\) 2행. \(\neg P\) 열을 만들고 한 번 더 뒤집는다. 집합 대응은 대응표에서 \(\neg \leftrightarrow {}^c\)를 두 번 적용해 본다.

풀이.

\(P\)	\(\neg P\)	\(\neg(\neg P)\)
T	F	T
F	T	F

\(\neg(\neg P)\) 열이 \(P\) 열과 두 행 모두에서 일치한다 — 두 번 뒤집으면 원래 값으로 돌아온다(이중부정). 집합 대응: \(\neg \leftrightarrow {}^c\)이므로 \((A^c)^c = A\) — 5주차 문제 5에서 \(U = \{1, \dots, 10\}\)의 수치로 확인한 그 사실의 논리적 정체다.

복기. 5주차에서는 원소 나열로, 이번 주에는 2행짜리 진리표로 같은 사실을 확인했다 — 집합의 사실을 논리로 계산하는 27주차 방식의 첫 맛보기다.

문제 8

접근. 중간 열 셋 — \(P \lor Q\), \(P \land Q\), \(\neg(P \land Q)\) — 을 차례로 쌓고 마지막에 \(\land\)한다. 완성되면 T인 행의 공통점을 말로 옮긴다.

풀이.

\(P\)	\(Q\)	\(P \lor Q\)	\(P \land Q\)	\(\neg(P \land Q)\)	전체
T	T	T	T	F	F
T	F	T	F	T	T
F	T	T	F	T	T
F	F	F	F	T	F

T인 행은 둘째\(\cdot\)셋째 행 — 정확히 하나만 참일 때 참이다. 이것이 일상어의 배타적 ‘또는’(exclusive or, XOR)이다: “짜장 또는 짬뽕”은 하나만 고르라는 뜻이고, 둘 다인 첫째 행을 \(\neg(P \land Q)\) 조각이 걸러 낸다. 수학은 포함적 or(\(\lor\))를 기본으로 쓰되, 배타적 or가 필요하면 이렇게 기본 연산으로 조립해서 쓴다.

복기. “일상어 뜻을 기본 연산으로 조립한다”가 이식 가능한 패턴이다. 이 열 (F, T, T, F)은 문제 16(c)에서 재사용되고, 27주차에서 대칭차 \(A \triangle B\)라는 집합 버전으로 다시 만난다.

문제 9

접근. \(\land \leftrightarrow \cap\) 대응을 그대로 쓴다 — 5주차 문제 9에서 집합 기호로 다룬 것을 논리 기호로 다시 쓰는 문제다. 생성형은 두 조건을 동시에 만족하는 수를 나열해 규칙을 찾는다.

풀이. 조건제시법: \(P(n) \land Q(n)\)이 참인 \(n\)의 집합이므로

\[ \{n \in \mathbb{Z} : (2 \mid n) \land (3 \mid n)\} \]

생성형: 두 조건을 모두 만족하는 정수를 나열하면 \(0, \pm 6, \pm 12, \dots\) — 6의 배수와 일치하므로 \(\{6k : k \in \mathbb{Z}\}\)이다. (2와 3의 공배수 = 6의 배수. “\(2 \mid n\)이고 \(3 \mid n\)이면 \(6 \mid n\)”의 엄밀한 증명은 20주차 소재이고, 지금은 5주차 문제 9와 같은 나열 관찰로 인정하고 쓴다.)

복기. 같은 집합의 세 표기 — 5주차의 \(A \cap B\), 이번 주의 \(\{n : P(n) \land Q(n)\}\), 생성형 \(\{6k\}\) — 가 전부 연결됐다. 논리 기호는 새 대상이 아니라 기존 대상의 새 표기다.

문제 10

접근. 변수 2개 \(\to\) 4행. \(P \land Q\) 열과 \(\neg P\) 열을 각각 만들고 \(\lor\)한다 — 절차대로면 계산할 것이 없는 문제다.

풀이.

\(P\)	\(Q\)	\(P \land Q\)	\(\neg P\)	\((P \land Q) \lor \neg P\)
T	T	T	F	T
T	F	F	F	F
F	T	F	T	T
F	F	F	T	T

복기. 이 마지막 열(T, F, T, T)은 8주차에서 \(P \Rightarrow Q\)의 진리표로 다시 나타난다 — 그때 이 표를 인용할 수 있도록 결과를 기억해 둘 만하다.

문제 11

접근. “둘 다 받겠다”가 허용되는지가 두 해석의 분기점이다. (c)는 §1.5에서 수학이 포함적 독법을 택한 이유(5주차 합집합과의 정합)를 회수하는 자리다.

풀이. (a) 일상어(식당) 해석: 커피와 차 중 하나만 선택하라는 뜻이다 — 둘 다 받는 것은 허용되지 않는 배타적 ‘또는’이고, 문제 8에서 조립한 XOR가 그 정체다. (b) 논리학의 \(\lor\) 해석: 커피만 받아도, 차만 받아도, 둘 다 받아도 참이다 — 포함적 or. 거짓이 되는 경우는 아무것도 받지 않을 때뿐이다. (c) \(A \cup B\)는 포함적 해석을 따른다 — \(x\)가 양쪽 집합에 다 속해도 합집합의 원소다. 합집합이 교집합 부분을 빼지 않는 이유가 정확히 이것이고, \(\lor\)의 정의가 \(\cup\)과 어긋나지 않도록 포함적으로 선택된 사정을 §1.5에서 보았다.

문제 12

접근. 절댓값\(\cdot\)범위\(\cdot\)”~도 ~도 아니다”를 각각 알맞은 접속사로 잇는다. 접속사 선택이 헷갈리면 원 문장을 만족하는 값 하나를 골라, 그 독법의 판정이 원 문장과 갈리는지 검사한다(문제 5 (b)의 요령).

풀이. (a) \(|x| > 3\)은 “원점에서 거리가 3보다 크다”이므로 수직선의 두 구간 — \(x > 3\) 또는 \(x < -3\) — 이다: \((x > 3) \lor (x < -3)\). 검산 — \(x = 4\)는 \(|x| > 3\)을 만족하지만 \((x > 3) \land (x < -3)\)은 어떤 \(x\)도 만족하지 못한다. 원 문장에 해가 실재하므로 항상 거짓인 \(\land\)-독법은 뜻일 수 없다 — 구간이 두 쪽으로 갈라진 조건은 \(\lor\)로 잇는다. (b) \(0 < x \le 5\)는 부등식 연쇄이므로 “그리고”의 축약이다(예제 2.3): \((0 < x) \land (x \le 5)\). (c) “4의 배수도 6의 배수도 아니다”는 두 부정이 동시에 성립한다는 뜻이다: \(\neg(4 \mid n) \land \neg(6 \mid n)\), 즉 \((4 \nmid n) \land (6 \nmid n)\). “~도 ~도 아니다”의 접속사는 \(\lor\)가 아니라 \(\land\)다 — 두 성질을 모두 갖지 않아야 하기 때문이다.

복기. (a)와 (b)의 대비 — 갈라진 구간은 \(\lor\), 이어진 구간은 \(\land\) — 가 부등식 번역의 기준이다. (c)는 9주차 드모르간 법칙에서 \(\neg\big((4 \mid n) \lor (6 \mid n)\big)\)과 같은 문장임이 밝혀진다.

문제 13

접근. 변수 2개 \(\to\) 4행(8행이 아니다 — 행 수는 명제의 길이가 아니라 변수의 개수가 정한다). 안쪽 \(\neg P \land Q\) 열을 만들고 \(P\)와 \(\lor\)한 뒤, \(P \lor Q\) 열을 나란히 세워 행별 대조한다.

풀이.

\(P\)	\(Q\)	\(\neg P \land Q\)	\(P \lor (\neg P \land Q)\)	\(P \lor Q\)
T	T	F	T	T
T	F	F	T	T
F	T	T	T	T
F	F	F	F	F

4열과 5열이 모든 행에서 일치한다. 해석: “P이거나, P가 아니면서 Q”는 결국 “P이거나 Q”와 같은 판정을 내린다 — \(\neg P\) 조각은 판정에 아무 기여가 없는 군더더기다. 논리식도 대수식처럼 간소화될 수 있다는 첫 사례이고, 이런 간소화 규칙들의 체계적 목록이 9주차의 내용이다.

문제 14

접근. 각 집합 연산의 정의문(“그리고 / 또는 / 아니다”)을 대응표대로 기호에 옮겨 적는다. 바깥 연산부터 한 겹씩 벗기면 겹친 연산도 기계적으로 처리된다.

풀이. (a) \(A - B\)의 정의는 “\(A\)에는 속하고 \(B\)에는 속하지 않는다”(5주차)이므로: \((x \in A) \land \neg(x \in B)\), 즉 \((x \in A) \land (x \notin B)\). (b) 바깥의 여집합부터: \(x \in (A \cup B)^c\)는 “\(x \in A \cup B\)가 아니다”이므로 \(\neg\big((x \in A) \lor (x \in B)\big)\). (c) 바깥의 \(\cap\)부터: \((x \in A) \land (x \in B \cup C)\)이고, 안쪽을 마저 풀면 \((x \in A) \land \big((x \in B) \lor (x \in C)\big)\).

복기. 집합 기호 \(\to\) 논리 기호의 번역은 정의문 낭독과 같다 — 새로 생각할 것이 없다. 이 번역이 27주차에서 집합 항등식 증명의 첫 단계로 승격되고, (b)의 논리식에 드모르간(9주차)을 적용하면 \((A \cup B)^c = A^c \cap B^c\)가 계산으로 나온다.

문제 15

접근. 두 명제 모두 변수 3개 \(\to\) 8행. 각각의 마지막 열을 만들어 행별 대조한다. 지름길도 있다 — \(P\) = F인 네 행과 \(P\) = T인 네 행을 묶어 보면 계산이 절반으로 준다.

풀이. 왼쪽 식과 오른쪽 식의 열을 한 표에 쌓는다.

\(P\)	\(Q\)	\(R\)	\(Q \lor R\)	\(P \land (Q \lor R)\)	\(P \land Q\)	\(P \land R\)	\((P \land Q) \lor (P \land R)\)
T	T	T	T	T	T	T	T
T	T	F	T	T	T	F	T
T	F	T	T	T	F	T	T
T	F	F	F	F	F	F	F
F	T	T	T	F	F	F	F
F	T	F	T	F	F	F	F
F	F	T	T	F	F	F	F
F	F	F	F	F	F	F	F

5열과 8열이 8행 전부에서 일치한다. (행 묶음으로 보면 — \(P\) = F인 아래 네 행은 양쪽 다 F이고, \(P\) = T인 위 네 행은 양쪽 다 \(Q \lor R\)의 값과 같다.)

집합 대응: 대응표로 번역하면 \(\land \to \cap\), \(\lor \to \cup\)이므로 분배법칙 \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)이다.

복기. 5주차 문제 14에서 쌍둥이 판(\(\cup\)의 분배, \(A \cup (B \cap C)\))을 수치로 관찰한 분배법칙 가족이, 이번에는 \(\cap\) 판으로 8행짜리 유한 검사로 확정됐다 — 변수가 셋뿐이므로 조합 여덟 개가 전부이고, 전부를 검사했으므로 끝이다. 그 쌍둥이 \(P \lor (Q \land R)\) 판(문제 3의 명제)과 함께 9주차 동치 법칙 목록에 오르고, 27\(\cdot\)30주차에서 집합 증명의 근거로 재사용된다.

문제 16

접근. (a)(b)는 훈련 2의 두 열이 그대로 답이다. (c)는 §4의 상자대로 역산한다 — 목표 열이 T인 행의 진리값 조합을 각각 \(\land\)로 적고 \(\lor\)로 잇는다. 또는 문제 8의 완성표에서 같은 열을 이미 만들었다(근거 ④).

풀이. (예시 답 — 같은 열을 만드는 다른 명제도 정답이다.) (a) \(P \lor \neg P\) — 훈련 2에서 모든 행이 T임을 확인했다(항진명제). (b) \(P \land \neg P\) — 훈련 2에서 모든 행이 F임을 확인했다(모순). (c) 목표 열 F, T, T, F에서 T인 행은 둘째 행(\(P\) = T, \(Q\) = F)과 셋째 행(\(P\) = F, \(Q\) = T)이다. 각 행을 \(\land\)로 적으면 \(P \land \neg Q\)와 \(\neg P \land Q\), 이 둘을 \(\lor\)로 이으면

\[ (P \land \neg Q) \lor (\neg P \land Q) \]

문제 8의 \((P \lor Q) \land \neg(P \land Q)\)도 같은 열을 만들므로 역시 정답이다.

검산. (c)를 네 행에 대입한다 — (T, T): \((T \land F) \lor (F \land T)\) = F ✓ / (T, F): \((T \land T) \lor (F \land F)\) = T ✓ / (F, T): \((F \land F) \lor (T \land T)\) = T ✓ / (F, F): \((F \land T) \lor (T \land F)\) = F ✓. 목표 열과 일치한다.

복기. “T인 행마다 \(\land\) 하나, 행들 사이는 \(\lor\)” — T인 행이 하나라도 있는 목표 열에는 이 절차가 그대로 통하고, 항상 거짓인 열 하나만 \(P \land \neg P\)(훈련 2)로 따로 처리하면, 16가지 열 전부가 \(\land, \lor, \neg\)만으로 조립된다. 기본 연산 세 개의 표현력이 그만큼 크다.

문제 17

접근. §4의 상자대로 두 가정 — 참 / 거짓 — 을 각각 검토한다. 명제라면 둘 중 하나이므로 두 경우가 전체를 빠짐없이 덮고, 양쪽 모두에서 충돌이 나면 “어느 진리값도 배정할 수 없다”는 결론이 남는다. 이 문장은 자기 자신의 진리값을 주장하므로, 가정한 값과 주장 내용을 나란히 놓으면 충돌 여부가 검사된다.

풀이. (예시 답안) 참이라고 가정하면, 문장이 주장하는 내용(“이 문장은 거짓이다”)이 성립해야 하므로 문장은 거짓이 되어, 참이라는 가정과 충돌한다. 거짓이라고 가정하면, “이 문장은 거짓이다”라는 주장이 틀린 것이므로 문장은 참이 되어, 거짓이라는 가정과 충돌한다. 참\(\cdot\)거짓 두 경우가 가능한 전부인데 어느 쪽에서도 일관된 배정이 없으므로, 이 문장은 “정확히 하나의 진리값”이라는 정의 7.1의 조건을 만족하지 못한다 — 명제가 아니다.

문제 18

접근. (a)는 변수 1개 \(\to\) 2행, (b)는 변수 2개 \(\to\) 4행. (b)는 안쪽 \(\neg P \land \neg Q\) 열부터 쌓는다 — 훈련 1에서 특정 값으로 계산한 것의 표 버전이다. 완성되면 각각 \(\neg P\) 열, \(P \lor Q\) 열과 행별 대조한다.

풀이. (a) 2행을 각각 계산한다. \(P\) = T이면 \(P \land P\) = T \(\land\) T = T이므로 \(\neg(P \land P)\) = F = \(\neg P\) ✓. \(P\) = F이면 \(P \land P\) = F이므로 \(\neg(P \land P)\) = T = \(\neg P\) ✓. 두 행 모두 일치한다. (b)

\(P\)	\(Q\)	\(\neg P\)	\(\neg Q\)	\(\neg P \land \neg Q\)	\(\neg(\neg P \land \neg Q)\)	\(P \lor Q\)
T	T	F	F	F	T	T
T	F	F	T	F	T	T
F	T	T	F	F	T	T
F	F	T	T	T	F	F

6열과 7열이 네 행 전부에서 일치한다 ✓. 곧 \(P \lor Q\)는 \(\neg(\neg P \land \neg Q)\)로 — \(\neg\)와 \(\land\)만으로 — 조립된다.

복기. (b)는 드모르간 법칙(문제 4의 예감, 9주차 선언)의 실전 사용이다: “\(\lor\)는 기본 연산이 아니어도 된다”는 뜻이므로, 이론상 \(\neg\)와 \(\land\) 두 개만으로 이번 주의 모든 명제를 적을 수 있다.

문제 19

접근. 변수 3개 \(\to\) 8행. 두 괄호의 열을 각각 만들고 \(\land\)한다. 지름길 — \(P\) = T인 행에서는 \(P \lor Q\)가 자동 T이므로 전체는 \(\neg P \lor R\) = F \(\lor\) \(R\) = \(R\)의 값이고, \(P\) = F인 행에서는 \(\neg P \lor R\)가 자동 T이므로 전체는 \(Q\)의 값이다.

풀이.

\(P\)	\(Q\)	\(R\)	\(P \lor Q\)	\(\neg P \lor R\)	전체
T	T	T	T	T	T
T	T	F	T	F	F
T	F	T	T	T	T
T	F	F	T	F	F
F	T	T	T	T	T
F	T	F	T	T	T
F	F	T	F	T	F
F	F	F	F	T	F

검산. 접근의 지름길과 대조한다 — \(P\) = T인 위 네 행의 전체 값(T, F, T, F)은 \(R\) 열과 같고, \(P\) = F인 아래 네 행의 전체 값(T, T, F, F)은 \(Q\) 열과 같다 ✓.

복기. “P가 참이면 R을 보고, 거짓이면 Q를 보라”는 스위치 구조가 이 명제의 정체다. 자동으로 통과되는 괄호를 먼저 골라내는 이 요령은 8행 이상의 표에서 계산량을 절반으로 줄인다 — 문제 15의 행 묶음과 같은 발상이다.

문제 20

접근. “거짓인 문장은 명제가 아니다”라고 가정해 보고, ①②의 활동에서 각각 무엇이 성립하지 않게 되는지 따라간다 — 1주차 문제 18의 반박 경험이 ①의 재료, 문제 17의 두-가정 검토가 ②의 재료다.

풀이. (예시 답안) ① 추측이 거짓으로 판명된다는 것은 “그 추측은 거짓이다”라는 판정이 성립한다는 뜻인데, 거짓인 문장이 명제가 아니라면 그 문장에는 진리값 자체가 없으므로 “거짓”이라는 판정도 성립하지 않는다. 1주차 문제 18의 “\(n^2 + n + 41\)은 모든 자연수에서 소수”도 거짓인 명제로 다뤄졌기에 \(n = 40\)이라는 반례로 처리할 수 있었다. ② 귀류법은 결론의 부정을 일단 명제로 받아들여 논리 연산을 적용하고 모순을 끌어내는 기법인데, 그 가정은 (증명이 성공한다면) 거짓인 문장이다. 거짓일 수 있는 문장을 명제로 취급해 \(\land, \lor, \neg\)를 적용할 수 없다면 귀류법의 전개 자체가 시작되지 않는다.

복기. 정의 7.1이 “참 또는 거짓”을 대등하게 받아들인 것은 관용이 아니라 필요다 — 반박(①)과 귀류법(②)이라는 증명 활동의 절반이 거짓인 명제를 재료로 쓰기 때문이다. 이번 주 핵심 문장(“자격은 참이 아니라 확정”)이 여기서 회수된다.

---

다음 주 예고: 이번 주의 \(\land, \lor, \neg\)에 넷째 연산 — 조건문 \(P \Rightarrow Q\) — 가 추가된다. “거짓에서 출발하면 무엇이든 참”이라는 규칙이 왜 필요한지, 고1의 필요조건\(\cdot\)충분조건이 진리표에서 어떻게 나오는지를 다룬다. 4주차의 공허한 참(\(\emptyset \subseteq A\))이 그 복선이었고, 문제 10에서 만든 열(T, F, T, T)이 다음 주의 주인공이다.