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

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

예제 — 판정과 유도를 함께 만들기#

완성된 표와 완성된 유도를 먼저 보이지 않는다. 백지에서 시작해 한 칸씩, 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 항진명제 판정 (진리표)#

명제. \(\big(P \wedge (P \Rightarrow Q)\big) \Rightarrow Q\)는 항진명제이다.

설계 — 쓰기 전에 정하는 두 가지. 표를 그리기 전에 두 가지를 먼저 정한다. 주어진 것(표의 크기)과, 만들어야 할 것(판정 문장)이다. 둘 다 정의로 번역해서 얻는다.

말

정의로의 번역

가정 (주어진 것)

성분 명제는 \(P\)와 \(Q\) 둘

진리값 조합이 \(2^2 = 4\)가지이므로 표는 네 행

목표 (만들 것)

항진명제임을 보인다

\(\underline{\quad(?)\quad}\)

확인 11. 목표 칸의 빈칸을 채워 보자. “항진명제임을 보인다”를 정의 3.3으로 번역하면 무엇을 보여야 하는가.

답

“마지막 열의 네 칸이 전부 T임을 보인다.” 정의 3.3의 “어떻게 정하든 항상 참”이

유한한 표에서는 “모든 행에서 T”가 된다. 한 행이라도 F가 나오면 항진이 아니므로,

네 행을 전부 계산하기 전에는 판정을 적을 수 없다.

출발점(네 행)과 도착점(마지막 열 전부 T)이 정해졌다. 그 사이는 계산이다.

1단계 — 열의 순서를 정한다. 표의 열은 아무 순서로나 놓는 것이 아니다. 바깥 연산을 계산하려면 그 재료가 되는 안쪽 연산의 값이 먼저 있어야 한다.

확인 12. 어떤 열을 어떤 순서로 만들어야 하는가. 식을 안쪽부터 벗겨 적어 보자.

답

\(P\), \(Q\) \(\to\) \(P \Rightarrow Q\) \(\to\) \(P \wedge (P \Rightarrow Q)\) \(\to\) 전체.

전체 식의 바깥 연산은 \(\Rightarrow\)이고, 그 전건이 \(P \wedge (P \Rightarrow Q)\)이며,

그 안에 다시 \(P \Rightarrow Q\)가 있다. 안쪽부터 만들면 각 열이 바로 앞 열들만을

재료로 삼으므로 계산이 한 방향으로 흐른다.

2단계 — 행마다 계산한다. 네 행 중 값이 가장 헷갈리는 2행부터 손으로 해 본다.

확인 13. 2행(\(P\) 참, \(Q\) 거짓)의 세 값을 차례로 채워 보자. \(P \Rightarrow Q = \underline{\quad}\), \(P \wedge (P \Rightarrow Q) = \underline{\quad}\), 전체 \(= \underline{\quad}\).

답

\(P \Rightarrow Q = F\) — 정의 3.2에서 조건문이 거짓인 유일한 행이 여기다.

\(P \wedge (P \Rightarrow Q) = T \wedge F = F\) — \(\wedge\)는 둘 다 T일 때만 T이므로

하나의 F가 전체를 F로 확정한다.

전체 \(= F \Rightarrow F = T\) — 전건이 거짓이므로 공허하게 참이다.

여기가 이 표에서 가장 헷갈리는 자리다. 전건이 F로 무너지는 순간 바깥 조건문은

후건을 볼 필요도 없이 T가 된다.

3단계 — 나머지 행을 채우고 판독한다. 판독의 기준은 정의 3.3 하나다.

확인 14. 1\(\cdot\)3\(\cdot\)4행의 세 값을 각각 채우고, 마지막 열을 보고 판정을 한 문장으로 적어 보자.

답

1행(\(P\)T \(Q\)T): \(T\), \(T \wedge T = T\), \(T \Rightarrow T = T\).

3행(\(P\)F \(Q\)T): \(T\), \(F \wedge T = F\), \(F \Rightarrow T = T\).

4행(\(P\)F \(Q\)F): \(T\), \(F \wedge T = F\), \(F \Rightarrow F = T\).

판정 — “마지막 열의 네 칸이 모두 T이므로 이 합성명제는 항진명제이다.”

3\(\cdot\)4행에서 \(P \Rightarrow Q\)가 T인 것은 전건 \(P\)가 거짓이기 때문이고, 그럼에도

\(P \wedge (P \Rightarrow Q)\)가 F인 것은 왼쪽 성분 \(P\)가 F이기 때문이다.

완성본. 방금 만든 네 행을 한 표로 모으면 아래와 같다.

\(P\)

\(Q\)

\(P \Rightarrow Q\)

\(P \wedge (P \Rightarrow Q)\)

\(\big(P \wedge (P \Rightarrow Q)\big) \Rightarrow Q\)

T

T

T

T

T

T

F

F

F

T

F

T

T

F

T

F

F

T

F

T

표를 손으로 베껴 쓰면서, 판정문의 각 줄 옆의 “왜”에 스스로 답해 본다.

증명의 한 줄

왜 이 줄을 쓰는가?

성분 명제는 \(P\)와 \(Q\)이므로 표는 네 행이다.

검사 범위를 먼저 못 박는다(정의 3.3의 “어떻게 정하든”). 행 수를 밝히지 않으면 빠진 행이 있는지 확인할 길이 없다.

먼저 \(P \Rightarrow Q\) 열을 만든다.

안쪽 연산의 값이 있어야 바깥 연산을 계산할 수 있다. 열의 순서가 곧 계산의 순서다(1단계).

그 열과 \(P\) 열로 \(P \wedge (P \Rightarrow Q)\) 열을 만든다.

앞의 두 열만을 재료로 \(\wedge\)의 규칙(정의 3.2)을 행마다 적용한다. 새 정보를 끌어오지 않는다.

그 열을 전건, \(Q\)를 후건으로 삼아 마지막 열을 만든다.

전체 식의 바깥 연산이 \(\Rightarrow\)이므로 마지막에 온다. 2행에서 전건이 F가 되어 값이 T로 확정된다.

마지막 열의 네 칸이 모두 T이므로 항진명제이다. \(\blacksquare\)

정의 3.3의 판정 기준과 일치함을 선언하며 마무리한다. 이 문장이 없으면 표는 계산 기록일 뿐 판정이 아니다.

이 네 칸이 뜻하는 것. 이 항진명제는 “\(P\)가 참이고 \(P \Rightarrow Q\)도 참이면 \(Q\)를 결론 지어도 된다”는 추론, 곧 전건 긍정의 정당성이다. 1권 이후 모든 증명이 이 걸음을 쓰지만 그 걸음이 옳다는 것은 검사한 적이 없었다. 표의 네 칸이 그 검사다.

(검산: 2행을 다시 계산하면 \(P \wedge (P \Rightarrow Q) = T \wedge F = F\)이고 \(F \Rightarrow F = T\) ✓. 검산은 판정이 아니지만 계산 오류 탐지기로는 훌륭하다.)

예제 2.2 — 조건문 부정: 진리표와 대수, 두 길#

명제. \(\sim(P \Rightarrow Q) \equiv P \wedge (\sim Q)\)임을 (a) 진리표로, (b) 동치 법칙만으로 보이라.

이번에는 설계만 함께 하고, 본문은 완성본으로 본다.

확인 15. 번역표를 채워 보자. (a)의 목표: \(\underline{\qquad}\). (b)의 목표: \(\underline{\qquad}\). 두 목표는 어떻게 다른가.

답

(a)의 목표 — 두 식의 열을 각각 만들어 네 행 모두에서 값이 일치함을 보인다.

(b)의 목표 — 왼쪽 식에서 출발해 법칙을 한 줄에 하나씩 적용하며 오른쪽 식에 닿는다.

차이는 방향이다. (a)는 오른쪽 식을 이미 알고 있어야 시작되는 검증이고,

(b)는 오른쪽 식을 모른 채 출발해도 되는 유도다. §1.1에서 진리표가 멈춘

자리를 (b)가 넘어간다.

(a) 진리표.

\(P\)

\(Q\)

\(P \Rightarrow Q\)

\(\sim(P \Rightarrow Q)\)

\(\sim Q\)

\(P \wedge (\sim 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

넷째 열과 여섯째 열이 네 행 모두에서 일치하므로 두 명제는 논리적으로 동치이다. \(\blacksquare\)

(b) 동치 법칙. 출발식 \(\sim(P \Rightarrow Q)\)에서 시작해 도착식 \(P \wedge (\sim Q)\)까지 세 줄로 간다.

\[ \sim(P \Rightarrow Q) \equiv \sim\big((\sim P) \vee Q\big) \qquad [\text{조건문 전개, 부분식에 적용}] \]
\[ \equiv \big(\sim(\sim P)\big) \wedge (\sim Q) \qquad [\text{드모르간 2}] \]
\[ \equiv P \wedge (\sim Q) \qquad [\text{이중부정}] \]

도착식에 닿았으므로 멈춘다. \(\blacksquare\)

증명의 한 줄

왜 이 줄을 쓰는가?

\(\sim(P \Rightarrow Q) \equiv \sim\big((\sim P) \vee Q\big)\) [조건문 전개, 부분식에 적용]

도착식에 \(\Rightarrow\)가 없으므로 먼저 없앤다. \(\Rightarrow\)가 남아 있으면 드모르간을 걸 자리가 없다 — 이것이 조건문 전개를 첫 줄에 두는 이유다. 법칙이 걸린 곳은 식 전체가 아니라 바깥 부정 안쪽의 \(P \Rightarrow Q\)이고, 그 자리에서의 교체를 허가하는 것이 §1.6의 대치 원리다.

\(\equiv \big(\sim(\sim P)\big) \wedge (\sim Q)\) [드모르간 2]

바깥 부정을 괄호 안으로 민다. 안이 \(\vee\)이므로 드모르간 2를 쓰고, 결과의 연산은 \(\wedge\)가 된다. 성분 각각에 부정이 새로 붙는다.

\(\equiv P \wedge (\sim Q)\) [이중부정]

\(\sim(\sim P)\)를 \(P\)로 줄인다. 이 줄을 빠뜨린 것이 §1.6의 답안 Q였다 — 부정의 개수를 세는 습관이 이 자리를 지킨다.

두 길의 관계. (a)는 네 행을 계산했고 (b)는 표를 한 번도 그리지 않았다. 그러나 (b)가 쓴 세 법칙은 각각 언젠가 진리표로 검증된 것이므로, (b)는 검증을 생략한 것이 아니라 이미 끝난 검증을 재사용한 것이다. 이 재사용이 §1.7 목록의 용도다. S10주차의 N4가 바로 이 동치이며, 1학기에 “규칙”으로만 익힌 것이 여기서 (a)라는 근거를 갖는다.

예제 2.3 — 역·이·대우의 진리표 완비#

명제. \(P \Rightarrow Q\)와 그 역 \(Q \Rightarrow P\), 이 \((\sim P) \Rightarrow (\sim Q)\), 대우 \((\sim Q) \Rightarrow (\sim P)\)의 진리표를 완성하고 동치 관계를 밝히라.

이번에는 설계부터 스스로 해 보자.

확인 16. 번역표를 스스로 채우고, 표를 다 그린 뒤 무엇을 어떻게 비교하게 될지까지 예측해 보자. 행은 몇 개이고, 만들 열은 몇 개인가.

답

성분은 \(P\)와 \(Q\) 둘이므로 행은 네 개다. 만들 열은 보조 열 \(\sim P\), \(\sim Q\)를

빼면 네 개 — 원명제, 역, 이, 대우.

비교는 네 열을 두 개씩 짝지어 여섯 쌍을 전부 보는 것이 아니다. 원명제 열을 기준으로

한 세 대조로 세 관계(원-역, 원-이, 원-대우)가 정해지고, 원명제와 대우가 동치이므로

대우와 역\(\cdot\)이의 관계도 그 셋으로부터 따라 나온다. 다만 역과 이의 관계만은 따라 나오지

않는다 — 둘 다 원명제와 다르다는 사실은 둘이 서로 같다는 것을 뜻하지 않기 때문이다.

그 한 쌍은 직접 대조한다. 그래서 필요한 대조는 여섯이 아니라 네 개다.

판정.

\(P\)

\(Q\)

\(\sim P\)

\(\sim Q\)

\(P \Rightarrow Q\)

역 \(Q \Rightarrow P\)

이 \((\sim P) \Rightarrow (\sim Q)\)

대우 \((\sim Q) \Rightarrow (\sim P)\)

T

T

F

F

T

T

T

T

T

F

F

T

F

T

T

F

F

T

T

F

T

F

F

T

F

F

T

T

T

T

T

T

보조 열 \(\sim P\)와 \(\sim Q\)를 먼저 만든 것은 안쪽 연산부터 열을 세운다는 순서를 지킨 결과다 — 그 두 열이 있으면 이와 대우의 값은 조건문 규칙을 행마다 적용하는 기계적 작업이 된다. 대조는 네 번 한다.

원명제 열과 대우 열은 네 행 모두에서 (T, F, T, T)로 일치하므로 \(P \Rightarrow Q \equiv (\sim Q) \Rightarrow (\sim P)\)이다. 역 열과 이 열은 네 행 모두에서 (T, T, F, T)로 일치하므로 역과 이도 동치이다. 원명제 열과 역 열은 2행과 3행에서 값이 갈리므로 \(P \Rightarrow Q \not\equiv Q \Rightarrow P\)이고, 이 열도 원명제 열과 같은 두 행에서 갈리므로 원명제와 이도 동치가 아니다. 곧 네 명제는 두 쌍의 동치로 나뉜다. \(\blacksquare\)

방금 수행한 대조는 확인 16에서 예측한 네 개다 — 원명제-대우, 원명제-역, 원명제-이, 그리고 앞의 셋으로부터 따라 나오지 않는 역-이. 나머지 두 쌍(대우-역, 대우-이)은 원명제와 대우가 동치라는 첫 결과에서 곧바로 따라 나오므로 표를 다시 읽지 않는다.

이번 판정은 표 뒤에 산문으로 결론을 적었다. 표는 계산 기록이고, 무엇이 판정되었는지는 문장으로 남겨야 읽는 쪽이 결론을 복원하지 않아도 된다.

진단 — 새는 답안이 왜 새는가. S12주차 예제 2.3이 해부한 답안은 대우를 증명하겠다고 선언하고 실제로는 이를 증명했다. 위 표가 그 답안이 무엇을 증명한 것인지 확정한다 — 이는 역과 동치이고(역 열과 이 열의 대조), 역은 원명제와 동치가 아니므로 (2행과 3행), 그 답안이 증명한 명제는 원명제가 아니다. 1권 9주차 §1.7의 판정이 여기서 네 열의 대조로 완결된다.

관찰 — 같은 뼈대#

세 예제는 소재가 다르지만 뼈대가 같다. 대응표의 빈칸을 채워 보자.

확인 17. 아래 표의 (1)~(4)를 채우고, 세 예제가 공유하는 걸음이 몇 개인지 세어 보자.

걸음

예제 2.1

예제 2.2 (a)

예제 2.3

① 행 수 확정

4

\(\underline{\quad(1)\quad}\)

\(\underline{\quad(2)\quad}\)

② 안쪽부터 열 만들기

\(P \Rightarrow Q\) \(\to\) \(P \wedge (P \Rightarrow Q)\) \(\to\) 전체

\(P \Rightarrow Q\) \(\to\) \(\sim(P \Rightarrow Q)\) / \(\sim Q\) \(\to\) \(P \wedge (\sim Q)\)

\(\underline{\quad(3)\quad}\)

③ 열 읽기

마지막 열이 전부 T \(\to\) 항진

\(\underline{\quad(4)\quad}\)

열끼리 대조 \(\to\) 두 동치쌍

답

(1) 4 (2) 4 (3) \(\sim P\), \(\sim Q\) \(\to\) 원명제\(\cdot\)역\(\cdot\)이\(\cdot\)대우의 네 열

(4) 두 열이 네 행에서 일치 \(\to\) 동치

공유하는 걸음은 세 개다. 소재가 항진 판정이든 동치 판정이든 네 명제의 비교든,

하는 일은 행 수 확정 \(\to\) 안쪽부터 열 만들기 \(\to\) 목적에 맞게 읽기로 같다.

달라지는 것은 ③의 읽는 법뿐이다.

방금 확인한 뼈대에 이름을 붙인다. 이번 주는 뼈대가 두 개다 — 표를 쓰는 길과 법칙을 쓰는 길.

백지 암기 대상

진리표 판정의 3단 틀

① 성분 명제를 세어 행 수 \(2^n\)을 확정한다 \(\to\) ② 안쪽 연산부터 열을 하나씩 만든다 \(\to\) ③ 목적에 맞게 열을 읽는다 (마지막 열이 전부 T이면 항진, 전부 F이면 모순, 두 열이 전 행 일치이면 동치)

백지 암기 대상

동치 유도의 3단 틀

① 출발식과 도착식을 적어 둔다 \(\to\) ② 한 줄에 법칙 하나씩 적용하며 줄 옆에 이름을 단다 \(\to\) ③ 도착식에 닿으면 멈춘다

이 3단 틀은 §1.6의 네 걸음을 압축한 것이다 — ②가 §1.6의 걸음 ②③을, ③이 걸음 ④를 맡는다. 걸음 번호를 인용할 때는 어느 서식의 번호인지 함께 적는다.

둘 중 무엇을 고를지는 과제의 문장이 정한다. “판정하시오”\(\cdot\)”검증하시오”는 첫째 틀, “간단히 하시오”\(\cdot\)”유도하시오”\(\cdot\)”법칙만으로”는 둘째 틀이다. 두 틀은 배타적이지 않다 — 유도로 얻은 결과를 표 한 행으로 검산하는 것이 예제 2.2가 보인 방식이다.

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

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

훈련 1 ●○○ — 진리표의 값 빈칸#

명제. \(\sim(P \vee Q) \equiv (\sim P) \wedge (\sim Q)\) (드모르간 2).

검증. 아래 표의 네 칸을 채운다.

\(P\)

\(Q\)

\(P \vee Q\)

\(\sim(P \vee Q)\)

\(\sim P\)

\(\sim Q\)

\((\sim P) \wedge (\sim Q)\)

T

T

T

F

F

F

\(\underline{\quad(1)\quad}\)

T

F

T

F

F

T

\(\underline{\quad(2)\quad}\)

F

T

T

\(\underline{\quad(3)\quad}\)

T

F

F

F

F

\(\underline{\quad(4)\quad}\)

T

T

T

T

  • \(\sim(P \vee Q)\) 열과 \((\sim P) \wedge (\sim Q)\) 열이 네 행 모두에서 일치하므로 두 명제는 논리적으로 \(\underline{\quad(5)\quad}\)이다.

  • 이 동치는 S10주차의 NOT 기계 여섯 규칙 중 \(\underline{\quad(6)\quad}\)에 해당한다.

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

이번에는 법칙 이름과 검산 계획도 빈칸이다.

명제. \(\sim\big(P \vee (\sim Q)\big) \equiv (\sim P) \wedge Q\).

유도.

\[ \sim\big(P \vee (\sim Q)\big) \equiv (\sim P) \wedge \underline{\quad(1)\quad} \qquad [\underline{\quad(2)\quad}] \]
\[ \equiv (\sim P) \wedge \underline{\quad(3)\quad} \qquad [\underline{\quad(4)\quad}] \]

  • 같은 동치를 진리표로 확인하려면 \(\underline{\quad(5)\quad}\)개의 행을 전부 대조해야 한다.

  • 위 유도에서 진리표를 그린 횟수는 \(\underline{\quad(6)\quad}\)번이다.

  • 결과를 한 행으로 검산한다. \(P\) 거짓\(\cdot\)\(Q\) 참인 행에서 왼쪽 값은 \(\underline{\quad(7)\quad}\)이고 오른쪽 값도 같다.

훈련 3 ●●● — 뼈대만 남기고#

이번에는 §2의 “동치 유도의 3단 틀”의 각 칸을 통째로 채운다.

명제(수출 법칙). \((P \wedge Q) \Rightarrow R \equiv P \Rightarrow (Q \Rightarrow R)\).

유도의 뼈대.

  • ① 출발식과 도착식: \(\underline{\quad(1)\quad}\)

  • ② 유도의 각 줄과 법칙 이름: \(\underline{\quad(2)\quad}\)

  • ③ 멈춤과 검산: \(\underline{\quad(3)\quad}\)

(이 훈련이 문제 8의 예행연습이다. 두 문제 모두 조건문 전개로 \(\Rightarrow\)를 없애는 데서 시작해, 마지막에 조건문 전개를 역방향으로 써서 \(\Rightarrow\)를 되돌린다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다. 이번 주는 §1.10의 예외 구역이므로 논리 기호를 답안 본문에 정면으로 써도 된다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. 진리표 문제의 채점 항목은 셋이다 — ① 성분 명제 수에

맞는 행을 빠짐없이 적었는가 ② 중간 열을 지우지 않고 남겼는가 ③ 판정 문장을

명시했는가. “항진이다”만 적힌 답안은 0점이고, 네 행의 마지막 열을 보인 뒤

“네 칸이 모두 T이므로 항진명제이다”라고 적은 답안이 만점이다.

대수 문제에는 항목이 하나 더 붙는다 — ④ 줄마다 법칙 이름이 달렸는가.

이름 없는 줄은 §1.6의 삭제 실험대로 검사될 수 없다. 힌트 상자는 5분 이상 막힌

뒤에만 연다.

기본 ●○○#

1. [백지] 다섯 연산의 진리표, 항진/모순의 정의, 논리 동치의 정의와 정리 3.1(\(R \equiv S\)인 것과 \(R \Leftrightarrow S\)가 항진명제인 것이 같은 판정임), 조건문의 세 변형과 동치 관계를 쓰시오.

힌트

적을 것이 네 덩어리다. 순서를 먼저 정하면 중간에 끊기지 않는다 — 표(정의 3.2) \(\to\)

항상 참\(\cdot\)항상 거짓(정의 3.3) \(\to\) 동치와 정리 3.1(정의 3.4) \(\to\) 세 변형(§1.8).

표는 네 행이고 열은 다섯 개다.

2. 진리표로 판정하시오 (항진/모순/둘 다 아님). (a) \(P \vee (\sim P)\) (b) \(P \wedge (\sim P)\) (c) \((P \Rightarrow Q) \vee (Q \Rightarrow P)\) (d) \(P \Rightarrow (P \vee Q)\)

힌트

(a)(b)는 성분이 \(P\) 하나이므로 행이 두 개다. (c)(d)는 두 개이므로 네 행이다.

(c)에서 조건문이 거짓인 행은 각각 하나뿐인데, 그 두 행이 같은 행일 수 있는지

확인해 보면 답이 먼저 보인다.

3. 예제 2.3의 네 명제 진리표를 백지 재현하고 두 동치쌍을 밝히시오.

힌트

보조 열 \(\sim P\)와 \(\sim Q\)를 먼저 만들어 두면 이와 대우의 열이 기계적으로 나온다.

재현이 끝나면 각 열을 값의 나열로 압축해 적어 본다 — (T, F, T, T)와 (T, T, F, T)

두 가지만 나온다.

4. 빈칸 사다리의 훈련 1~3을 백지에서 완성하시오.

힌트

훈련 3이 막히면 훈련 2의 유도를 먼저 다시 적는다. 두 유도의 첫 줄이 같은

법칙이다 — 도착식에 없는 연산을 첫 줄에서 없앤다.

5. 예제 2.2(b)의 대수 유도를 백지 재현하시오 (법칙 이름 포함).

힌트

세 줄이고 법칙도 셋이다. 마지막 줄에서 부정의 개수를 세어 본다 — 출발식과

도착식에 \(\sim\)이 각각 몇 개인지 확인하면 이중부정을 빠뜨렸는지 곧바로 드러난다.

6. 다음을 대수 법칙으로 간단히 하시오 (진리표 없이). (a) \(\sim(\sim P)\) (b) \(\sim(P \wedge (\sim Q))\) (c) \((\sim P) \vee Q\)를 조건문으로.

힌트

(b)는 두 걸음이다. 바깥 부정을 괄호 안으로 민 뒤, 안쪽에 생긴 \(\sim(\sim Q)\)를

처리한다. 결과가 (c)의 출발식과 같은 꼴이 되므로 한 걸음 더 갈 수 있다.

표준 ●●○#

7. \(P \Rightarrow Q \equiv (\sim P) \vee Q\)를 (a) 진리표로 확인하고, (b) 진리표 없이 각 진리값에서 설명하시오. 이 동치가 S15주차 소거법의 근거임을 한 줄로 적으시오.

힌트

(b)는 \(P\)가 참인 경우와 거짓인 경우로 갈라 말한다. \(P\)가 거짓이면 왼쪽은 공허하게

참이고 오른쪽은 \(\sim P\)가 참이라 참이다. \(P\)가 참인 경우도 같은 방식으로 두

식이 무엇에 달렸는지 말하면 된다.

세 성분 명제의 진리표 — 행이 여덟 개

문제 8부터 성분이 셋인 식이 나온다. 성분이 \(n\)개면 조합은 \(2^n\)가지이므로

행은 여덟 개다. 행을 빠뜨리지 않는 표준 배열은 왼쪽 열부터 T를 넷\(\cdot\)F를 넷,

가운데 열은 T를 둘\(\cdot\)F를 둘씩 번갈아, 오른쪽 열은 T와 F를 한 칸씩 번갈아 적는 것이다.

이 배열을 지키면 여덟 행이 서로 다르다는 것을 일일이 세지 않아도 보장된다.

대수로 푸는 쪽을 골라도 되며, 그때는 표 대신 줄마다 달린 법칙 이름이 채점 대상이 된다.

8. \((P \vee Q) \Rightarrow R \equiv (P \Rightarrow R) \wedge (Q \Rightarrow R)\)임을 진리표 또는 대수로 증명하시오 (가정 쪽의 “또는”이 각 경우 조건문의 “그리고”와 같다는 것 — S15주차 경우법의 논리적 근거이며, 1권 17주차 문제 20(a)에서 8행 진리표로 증명한 것을 이번에는 대수로 다시 유도한다).

힌트

대수 쪽이 짧다. 양쪽 모두 \(\Rightarrow\)를 조건문 전개로 없애 \(\vee\)와 \(\wedge\)만

남긴 뒤, 한쪽을 분배 법칙으로 펼치면 다른 쪽과 같은 꼴이 된다. 어느 분배를

쓸지는 \(R\)가 결과에 두 번 나타나야 한다는 데서 정해진다.

9. \(\big((P \Rightarrow Q) \wedge (Q \Rightarrow R)\big) \Rightarrow (P \Rightarrow R)\)이 항진임을 보이시오 (추이율 또는 삼단논법 — 진리표 8행 또는 논증).

힌트

8행을 전부 계산해도 되지만, 전건이 F인 행은 값이 자동으로 T라는 점을 쓰면 일이

줄어든다. 전건 \((P \Rightarrow Q) \wedge (Q \Rightarrow R)\)가 T인 행만 골라

그 행에서 \(P \Rightarrow R\)가 T인지 보면 충분하다.

10. 다음 답안을 진단하시오.

“\(P \Rightarrow Q\)를 증명하려면 역 \(Q \Rightarrow P\)를 증명하면 된다. 왜냐하면 조건문은 역과 동치이기 때문이다.”

힌트

진단은 세 조각이다 — 어느 문장이 틀렸는지, 진리표의 어느 행이 그것을 반박하는지,

올바른 진술은 무엇인지. 반박에 필요한 행은 §1.5에서 확인했듯 하나면 된다.

11. 분배 법칙 \(P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)\)을 진리표(8행)로 검증하시오.

12. \(\sim(P \Leftrightarrow Q)\)를 간단히 하시오 — \(P \Leftrightarrow Q \equiv (P \Rightarrow Q) \wedge (Q \Rightarrow P)\)에서 출발해 드모르간\(\cdot\)조건문 부정으로. 결과가 “\(P, Q\)의 진리값이 다르다”(배타적 또는)임을 진리표로 확인하시오.

힌트

출발식이 \(\wedge\)의 부정이므로 첫 줄은 드모르간 1이다. 그러면 조건문의 부정

두 개가 나란히 놓이고, 각각에 조건문 부정을 적용하면 끝난다. 결과의 두 항이

어느 행에서 참이 되는지 확인하면 배타적 또는이라는 이름의 뜻이 보인다.

13. 조건문 전개의 응용: “\(x > 0\)이면 \(x^2 > 0\)”을 “\(x \le 0\) 또는 \(x^2 > 0\)”으로 바꿔 쓰는 것이 왜 같은 뜻인지 \(P \Rightarrow Q \equiv (\sim P) \vee Q\)로 설명하시오.

14. 항진명제와 증명: “\(\big(P \wedge (P \Rightarrow Q)\big) \Rightarrow Q\)가 항진”(예제 2.1)이 왜 “전건 긍정 추론”의 정당성인지 설명하고, 1학기에서 이 추론을 쓴 예 하나(예: 특수화 후 결론 도출)를 드시오.

도전 ●●●#

15. 논리 동치 사슬: \(\sim\big((\sim P) \Rightarrow Q\big) \equiv (\sim P) \wedge (\sim Q)\)임을 대수 법칙만으로 유도하시오 (조건문 전개 \(\to\) 이중부정 \(\to\) 드모르간 — 각 단계 법칙 명시. 이중부정과 드모르간의 순서는 바꿔도 된다). 진리표로 검산하시오.

힌트

첫 줄에서 \((\sim P) \Rightarrow Q\)를 통째로 전개하면 안쪽에 \(\sim(\sim P)\)가

생긴다. 그것을 먼저 줄일지 바깥 부정을 먼저 밀지는 어느 쪽이든 되지만,

한 줄에 하나씩만 처리한다.

이 문제가 묻는 것 — 표현한다는 말의 뜻

다음 문제의 “표현한다”는 낯선 낱말이므로 뜻부터 못 박는다.

“\(\vee\)를 \(\{\sim, \wedge\}\)로 표현한다”는 것은 \(\vee\)가 사라진다는 말이 아니라,

\(\vee\)가 들어간 어떤 식이든 \(\sim\)과 \(\wedge\)만 쓴 동치인 식으로 바꿔 쓸 수 있다는

뜻이다. 그 바꿔 쓰기가 동치이므로 진리값이 보존되고, 따라서 두 표기는 같은

논리를 적는 두 방식이 된다. 지금은 동치 법칙 두 개로 확인만 하고, 몇 개의

연산이 최소인지를 따지는 논의는 이 과정 밖이다.

16. 함수 완비성 맛보기: 모든 논리 연산이 \(\{\sim, \wedge\}\)만으로 표현됨을 보이시오 — (a) \(P \vee Q \equiv \sim\big((\sim P) \wedge (\sim Q)\big)\) (드모르간) (b) \(P \Rightarrow Q \equiv \sim\big(P \wedge (\sim Q)\big)\) (조건문 부정의 부정). “몇 개의 연산이면 논리 전체를 짓는가”의 첫걸음.

힌트

(a)는 오른쪽에서 출발해 왼쪽으로 가는 편이 짧다 — 바깥 부정을 드모르간으로

밀면 안쪽 두 부정이 이중부정으로 지워진다. (b)도 같은 출발점이고, 마지막에

조건문 전개를 역방향으로 한 번 더 쓴다.

17. 쌍조건문의 대수: \(P \Leftrightarrow Q \equiv (P \wedge Q) \vee \big((\sim P) \wedge (\sim Q)\big)\)임을 증명하시오 (진리표 또는 대수 — “둘 다 참 이거나 둘 다 거짓”). 이것이 1권 25주차 iff 증명의 “양방향” 구조와 어떻게 연결되는지 한 문장으로 적으시오.

힌트

진리표 쪽이 안전하다. 오른쪽 식은 1행에서 왼쪽 항이 참, 4행에서 오른쪽 항이

참이고 나머지 두 행에서는 양쪽 다 거짓이다. 대수로 가려면 쌍조건문 분해와

조건문 전개로 시작해 분배를 두 번 쓰고, 모순명제가 된 항을 항등 법칙으로 지운다.

18. (진단 종합) 다음 주장들의 진위를 진리표로 판정하시오. (a) “\(P \Rightarrow Q\)와 \((\sim Q) \Rightarrow (\sim P)\)는 동치다.” (b) “\(P \Rightarrow Q\)와 \(Q \Rightarrow P\)는 동치다.” (c) “\(\sim(P \Rightarrow Q)\)와 \((\sim P) \Rightarrow (\sim Q)\)는 동치다.” (각각 참\(\cdot\)거짓을 판정하고 근거 행을 명시하시오.)

19. (메타) “\(R \equiv S\)이면 \(R \Leftrightarrow S\)가 항진이고, 역도 성립”을 증명하시오 (정의로부터 — 동치는 모든 행에서 진리값 일치이고, 그것이 \(\Leftrightarrow\)가 모든 행에서 T인 것과 같음을 보인다). 이것이 “논리 동치를 진리표로 판정”하는 방법의 근거임을 설명하시오.

힌트

정리 3.1의 증명이다. 양방향을 따로 적는다. 두 방향 모두 근거로 쓸 것은

정의 3.4의 셋째\(\cdot\)넷째 조각과 정의 3.2의 \(\Leftrightarrow\) 규칙 한 줄뿐이다 —

“값이 같다”와 “\(\Leftrightarrow\)가 T이다”가 행마다 같은 말임을 짚으면 끝난다.

20. (서술) (a) S10주차의 NOT 기계 N1~N6이 이번 주 “논리 동치 법칙”으로 정식화됨을 예제 2.2로 뒷받침하고, “1학기의 밀어넣기 규칙에 진리표 근거가 붙었다”를 세 문장 이내로 쓰시오. (b) 원칙 3의 예외(“논리 논의 시 기호 허용”)가 왜 정당하며, 그럼에도 증명 산문에서는 단어를 쓰는 이유(C1주차 문제 17)를 두 문장 이내로 쓰시오.

힌트

(a)는 §1.7의 대응표에서 한 줄을 골라 그 줄이 예제 2.2의 어느 부분에 대응하는지

짚으면 된다. (b)는 §1.10의 확인 10이 갈라 놓은 두 문장을 각각 한 문장으로

요약하면 분량이 맞는다.

백지 재현 — 복습 프로토콜#

이번 주의 5일 루틴. 원서와 교안을 번갈아 쓰는 순서다.

요일

할 일

1일차

원서 Chartrand 2.1~2.9 통독 (모르는 문장은 표시만 하고 통과)

2일차

교안 §0~§2 — 개념과 예제. 확인 상자는 연필로 먼저 답한다

3일차

원서 재독 — 1일차에 표시한 문장을 해결하고, 원서 2.1~2.9의 연습문제 몇 개를 직접 시도

4일차

교안 §3 빈칸 사다리 + §4 연습문제 20문항

5일차

백지 재현 1차(틀 카드)\(\cdot\)2차(완전 백지) + 체크리스트

3일차의 원서 재독에서 확인할 것이 하나 있다. 원서는 동치 법칙을 이번 주 §1.7의 순서나 이름으로 배열하지 않는다. 같은 항목이 다른 이름으로 나오면 그 이름을 §1.7의 어느 줄에 대응시킬지 여백에 적어 둔다 — 이름의 대조가 3일차의 과제다. 대조 대상은 원서만이 아니다. 1권 9주차 §1.6과 S15주차는 §1.7의 ‘조건문 전개’를 ‘조건문 분해’로 부르므로, 그 두 이름이 같은 줄을 가리킨다는 것도 여백에 적어 둔다.

1차 시도 — 틀 카드 허용. 다음 두 상자만 옮겨 적은 카드를 펴 놓는다: §1.7의 동치 법칙 목록, §2의 두 3단 틀. §1.6의 네 걸음은 ‘동치 유도의 3단 틀’에 압축되어 있으므로 카드에 따로 옮기지 않는다. 그 상태에서 예제 2.2를 (a)와 (b) 양쪽으로 처음부터 끝까지 적는다. 예제 본문과 확인 상자는 보지 않는다.

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

  • 다섯 연산의 진리표를 네 행으로 썼다 (정의 3.2).

  • 명제와 열린 문장의 정의를 문장으로 쓰고, 열린 문장이 왜 아직 명제가 아닌지 예로 보였다(정의 3.1).

  • 항진명제\(\cdot\)모순명제\(\cdot\)논리 동치의 정의와 정리 3.1을 문장으로 썼다.

  • §1.7의 동치 법칙 목록을 이름과 식을 짝지어 전부 썼다.

  • 아직 검증되지 않은 세 항목을 각자 진리표로 확인했다 — 교환의 \(\vee\) 쪽(\(P \vee Q\)와 \(Q \vee P\)의 두 열, 4행), 결합 두 줄(성분이 셋이므로 8행), 항등 두 줄(\(C\) 자리에 모순명제 \(P \wedge (\sim P)\)를, \(V\) 자리에 항진명제 \(P \vee (\sim P)\)를 넣어 4행). 확인을 마친 항목만 근거 ④에 등록한다.

  • §1.6의 동치 변형 절차 네 걸음과 각 걸음을 빼면 무엇이 무너지는지를 사례와 함께 적었다.

  • §1.6의 대치 원리를 한 문장으로 쓰고, 그것이 근거 몇 번에 대응하는지 밝혔다.

  • §2의 두 3단 틀(진리표 판정 / 동치 유도)을 각각 백지에 썼다.

  • 예제 2.1의 네 행 표를 재현하고 마지막 열의 판정 문장을 적었다.

  • 예제 2.2(b)의 세 줄 유도를 법칙 이름과 함께 재현했다.

  • 예제 2.3의 표를 보조 열까지 재현하고 두 동치쌍을 밝혔다.

  • §3 훈련 1~3을 백지에서 완성했다(훈련 3은 다섯 줄 유도와 법칙 이름까지).

  • S10주차 N1~N4가 §1.7의 어느 항목인지 대응표로 적었다.

  • 원서 2.1~2.9를 완독했고, 1일차에 표시한 문장이 전부 해결되었다.

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

막힌 지점

처방

진리표의 행이 몇 개인지 헷갈린다

§2 관찰의 3단 틀 ① — 성분 명제를 세어 \(2^n\)을 먼저 확정한다

조건문 열의 3\(\cdot\)4행에서 손이 멈춘다

정의 3.2 아래의 둘째 항목과 확인 3 — 거짓인 행은 2행 하나뿐이다

법칙 목록이 중간에서 끊긴다

§1.7 — 조건문 전개를 축으로 삼고, 그 앞뒤에 드모르간과 이중부정을 붙여 외운다

유도의 첫 줄이 나오지 않는다

§1.6 걸음 ②(3단 틀의 ②) — 도착식에 없는 연산을 찾아 그것부터 없앤다

유도는 되는데 줄마다 이름을 못 적는다

§1.6 걸음 삭제 실험 — 이름 없는 줄이 왜 검사 불가인지 확인한다

역\(\cdot\)이\(\cdot\)대우가 서로 섞인다

§1.8과 예제 2.3 — 화살표의 방향과 부정의 유무 두 가지로만 갈린다

기호를 언제 써도 되는지 판단이 안 된다

§1.10 확인 10 — 논의 대상이면 기호, 서술의 약호이면 낱말

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

해설#

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

빈칸 사다리 — 훈련 1#

(1) F (2) F (3) F (4) F (5) 동치 (6) N3

각 칸의 근거는 이렇다. (1) 1행에서 \(\sim P\)와 \(\sim Q\)가 둘 다 F이므로 \(\wedge\)는 F. (2) 2행에서 \(\sim P\)가 F이므로 \(\wedge\)는 F. (3) 3행에서 \(P \vee Q\)가 T이므로 그 부정은 F. (4) 4행에서 \(P\)와 \(Q\)가 둘 다 F이므로 \(\vee\)는 F. 두 열이 (F, F, F, T)로 일치하므로 동치이고, 이 항목이 S10주차의 N3(드모르간, \(\vee\))이다.

빈칸 사다리 — 훈련 2#

(1) \(\sim(\sim Q)\) (2) 드모르간 2 (3) \(Q\) (4) 이중부정 (5) 4 (6) 0 (7) T

첫 줄은 바깥 부정을 \(\vee\) 안으로 미는 자리이므로 드모르간 2이고, 그 결과 두 성분 각각에 부정이 붙어 \((\sim P) \wedge \sim(\sim Q)\)가 된다. 둘째 줄에서 \(\sim(\sim Q)\)가 이중부정으로 \(Q\)가 된다. (5)의 행 수는 성분이 \(P\), \(Q\) 둘이므로 \(2^2 = 4\)이고, (6)이 0인 것이 이 훈련의 요점이다 — 유도는 표를 그리지 않는다. (7)의 검산은 \(P\) 거짓\(\cdot\)\(Q\) 참인 행에서 \(P \vee (\sim Q)\)가 \(F \vee F = F\)이므로 왼쪽은 T, 오른쪽은 \(T \wedge T = T\)로 같다.

빈칸 사다리 — 훈련 3#

(1) 출발식은 \((P \wedge Q) \Rightarrow R\), 도착식은 \(P \Rightarrow (Q \Rightarrow R)\).

(2) 유도는 다섯 줄이다.

\[ (P \wedge Q) \Rightarrow R \equiv \sim(P \wedge Q) \vee R \qquad [\text{조건문 전개}] \]
\[ \equiv \big((\sim P) \vee (\sim Q)\big) \vee R \qquad [\text{드모르간 1}] \]
\[ \equiv (\sim P) \vee \big((\sim Q) \vee R\big) \qquad [\text{결합}] \]
\[ \equiv (\sim P) \vee (Q \Rightarrow R) \qquad [\text{조건문 전개, 역방향}] \]
\[ \equiv P \Rightarrow (Q \Rightarrow R) \qquad [\text{조건문 전개, 역방향}] \]

(3) 도착식에 닿았으므로 멈춘다. 검산은 값이 갈릴 만한 행 하나로 한다 — \(P\) 참\(\cdot\)\(Q\) 참\(\cdot\)\(R\) 거짓인 행에서 왼쪽은 \(T \Rightarrow F = F\)이고, 오른쪽은 \(Q \Rightarrow R\)가 F이므로 \(T \Rightarrow F = F\)로 같다.

※ 새 개념이라도 출발식과 도착식만 정해지면 3단 틀이 그대로 작동한다. 첫 줄이 조건문 전개인 이유는 도착식에도 \(\Rightarrow\)가 있지만 위치가 다르기 때문이고, 위치를 옮기려면 일단 전부 \(\vee\)로 풀어야 한다.

문제 1#

접근. 백지 재현은 기억력 시험이 아니라 순서의 시험이다. 적을 것이 네 덩어리이므로 순서를 먼저 정하고 시작한다 — 표(정의 3.2) \(\to\) 항상 참\(\cdot\)항상 거짓(정의 3.3) \(\to\) 동치와 정리 3.1(정의 3.4) \(\to\) 세 변형(§1.8). 이 순서는 뒤 항목이 앞 항목을 재료로 쓰는 순서이기도 하다.

풀이. 첫째, 다섯 연산의 진리표는 네 행이다.

\(P\)

\(Q\)

\(\sim P\)

\(P \wedge Q\)

\(P \vee Q\)

\(P \Rightarrow Q\)

\(P \Leftrightarrow Q\)

T

T

F

T

T

T

T

T

F

F

F

T

F

F

F

T

T

F

T

T

F

F

F

T

F

F

T

T

둘째, 항진명제는 성분의 진리값을 어떻게 정하든 항상 참인 합성명제이고, 모순명제는 항상 거짓인 합성명제다. 판정은 마지막 열이 전부 T인지 전부 F인지 보는 것이다.

셋째, 같은 성분 명제로 이루어진 두 합성명제 \(R\)와 \(S\)가 모든 진리값 조합에서 같은 진리값을 가지면 \(R \equiv S\)로 쓴다. 그리고 \(R \equiv S\)인 것과 \(R \Leftrightarrow S\)가 항진명제인 것은 같은 판정이다(정리 3.1).

넷째, \(P \Rightarrow Q\)의 역은 \(Q \Rightarrow P\), 이는 \((\sim P) \Rightarrow (\sim Q)\), 대우는 \((\sim Q) \Rightarrow (\sim P)\)이며, 원명제와 대우가 동치이고 역과 이가 동치이며 원명제와 역은 동치가 아니다.

복기. 표를 다 쓴 뒤 조건문 열에 F가 정확히 하나인지, 쌍조건문 열에 T가 정확히 둘인지 세어 본다. 이 두 번의 세기가 표 전체의 검산이 된다.

문제 2#

접근. 판정 문제이므로 §2의 진리표 3단 틀을 그대로 쓴다. 먼저 성분을 세어 행 수를 정한다 — (a)(b)는 성분이 \(P\) 하나이므로 두 행, (c)(d)는 \(P\)와 \(Q\)이므로 네 행이다. 그다음 안쪽 연산부터 열을 만들고 마지막 열을 읽는다.

풀이.

(a) \(P \vee (\sim P)\). \(P\)가 T인 행에서 \(\sim P\)는 F이므로 \(T \vee F = T\). \(P\)가 F인 행에서 \(\sim P\)는 T이므로 \(F \vee T = T\). 두 행이 모두 T이므로 항진명제이다.

(b) \(P \wedge (\sim P)\). \(P\)가 T인 행에서 \(T \wedge F = F\). \(P\)가 F인 행에서 \(F \wedge T = F\). 두 행이 모두 F이므로 모순명제이다.

(c) \((P \Rightarrow Q) \vee (Q \Rightarrow P)\). 네 행을 계산한다. 1행(\(P\)T \(Q\)T): \(T \vee T = T\). 2행(\(P\)T \(Q\)F): \(P \Rightarrow Q\)는 F이고 \(Q \Rightarrow P\)는 \(F \Rightarrow T = T\)이므로 \(F \vee T = T\). 3행(\(P\)F \(Q\)T): \(T \vee F = T\). 4행(\(P\)F \(Q\)F): \(T \vee T = T\). 네 칸이 모두 T이므로 항진명제이다.

(d) \(P \Rightarrow (P \vee Q)\). 1행: \(P \vee Q\)가 T이므로 \(T \Rightarrow T = T\). 2행: \(P \vee Q\)가 T이므로 \(T \Rightarrow T = T\). 3행: 전건 \(P\)가 F이므로 T. 4행: 전건이 F이므로 T. 네 칸이 모두 T이므로 항진명제이다.

복기. (c)가 항진인 구조적 이유는 이렇다. 두 조건문이 동시에 거짓이려면 \(P\) 참\(\cdot\)\(Q\) 거짓과 \(Q\) 참\(\cdot\)\(P\) 거짓이 한 행에서 함께 성립해야 하는데, 그런 행은 없다. 한쪽이 거짓인 행에서는 다른 쪽의 전건이 반드시 거짓이 되어 공허하게 참이 된다.

문제 3#

접근. 재현이므로 순서가 곧 답이다. 보조 열 \(\sim P\)와 \(\sim Q\)를 먼저 만들면 이와 대우의 열은 정의 3.2의 조건문 규칙을 그 두 열에 적용하는 기계적 작업이 된다. 대조는 원명제 열을 기준으로 한다.

풀이.

\(P\)

\(Q\)

\(\sim P\)

\(\sim Q\)

\(P \Rightarrow Q\)

역 \(Q \Rightarrow P\)

이 \((\sim P) \Rightarrow (\sim Q)\)

대우 \((\sim Q) \Rightarrow (\sim P)\)

T

T

F

F

T

T

T

T

T

F

F

T

F

T

T

F

F

T

T

F

T

F

F

T

F

F

T

T

T

T

T

T

원명제 열과 대우 열이 (T, F, T, T)로 네 행 모두에서 일치하므로 \(P \Rightarrow Q \equiv (\sim Q) \Rightarrow (\sim P)\)이다. 역 열과 이 열이 (T, T, F, T)로 일치하므로 역과 이가 동치이다. 이것이 두 동치쌍이다. 원명제 열과 역 열은 2행과 3행에서 갈리므로 원명제와 역은 동치가 아니다.

검산. 이 열은 원명제 열과 다르고 역 열과 같은지 두 번 대조한다. 이 열이 원명제 열과 같게 나왔다면 \(\sim P\)와 \(\sim Q\) 중 하나를 뒤집어 적은 것이다.

문제 4#

접근. 세 훈련은 요구하는 것이 각각 다르다. 훈련 1은 표의 칸을 정의 3.2로 채우는 일이고, 훈련 2는 법칙 이름을 대는 일이며, 훈련 3은 유도 전체를 짓는 일이다. 백지에서는 훈련 3부터 막히므로, 막히면 훈련 2의 첫 줄로 돌아가 “도착식에 없는 연산을 없앤다”는 판단 기준을 다시 확인한다.

풀이. 훈련 1의 답은 (1) F (2) F (3) F (4) F (5) 동치 (6) N3이다. 네 빈칸은 서로 다른 세 열에 걸쳐 있다 — (1)(2)는 \((\sim P) \wedge (\sim Q)\) 열의 1\(\cdot\)2행, (3)은 \(\sim(P \vee Q)\) 열의 3행, (4)는 \(P \vee Q\) 열의 4행이다. 값이 모두 F로 나오는 것은 우연이고, 근거는 열마다 다르다. (1)은 1행에서 \(\sim P\)와 \(\sim Q\)가 둘 다 F이므로 \(\wedge\)가 F, (2)는 2행에서 \(\sim P\)가 F이므로 \(\wedge\)가 F, (3)은 3행에서 \(P \vee Q\)가 T이므로 그 부정이 F, (4)는 4행에서 \(P\)와 \(Q\)가 둘 다 F이므로 \(\vee\)가 F다.

훈련 2의 답은 (1) \(\sim(\sim Q)\) (2) 드모르간 2 (3) \(Q\) (4) 이중부정 (5) 4 (6) 0 (7) T이다. 두 줄짜리 유도이고 표는 한 번도 그리지 않는다.

훈련 3의 답은 출발식 \((P \wedge Q) \Rightarrow R\)에서 조건문 전개 \(\to\) 드모르간 1 \(\to\) 결합 \(\to\) 조건문 전개 역방향 \(\to\) 조건문 전개 역방향의 다섯 줄로 도착식 \(P \Rightarrow (Q \Rightarrow R)\)에 닿는 것이다(위 사다리 해설의 다섯 줄 참조).

복기. 백지 재현의 채점 항목은 값이 아니라 세 가지다 — 표의 행을 빠짐없이 적었는가, 줄마다 법칙 이름을 달았는가, 도착식에서 멈췄는가. 값이 맞아도 이름이 없으면 §1.6의 기준으로 미완이다.

문제 5#

접근. 재현의 관건은 세 줄의 순서다. 왜 조건문 전개가 먼저인지 이유와 함께 외우면 순서가 흔들리지 않는다 — 도착식에 \(\Rightarrow\)가 없고, \(\Rightarrow\)가 남아 있으면 드모르간을 걸 자리가 없기 때문이다.

풀이.

\[ \sim(P \Rightarrow Q) \equiv \sim\big((\sim P) \vee Q\big) \qquad [\text{조건문 전개, 부분식에 적용}] \]
\[ \equiv \big(\sim(\sim P)\big) \wedge (\sim Q) \qquad [\text{드모르간 2}] \]
\[ \equiv P \wedge (\sim Q) \qquad [\text{이중부정}] \]

도착식에 닿았으므로 멈춘다. \(\blacksquare\)

복기. 이 유도에서 가장 자주 새는 자리는 둘째 줄에서 셋째 줄로 넘어가는 지점이다. 드모르간을 적용하면 \(\sim(\sim P)\)가 생기는데, 이것을 곧바로 \(\sim P\)로 적으면 결과가 \((\sim P) \wedge (\sim Q)\)가 되어 §1.6의 답안 Q와 같은 오류가 된다. 부정의 개수를 세는 것이 검산이다 — 출발식의 \(\sim\)은 하나, 도착식의 \(\sim\)도 하나다.

문제 6#

접근. 세 문항 모두 “진리표 없이”가 조건이므로 §1.7 목록에서 이름을 골라 대는 훈련이다. 각 문항에서 출발식의 바깥 연산이 무엇인지 보면 쓸 법칙이 정해진다 — (a)는 부정의 부정, (b)는 \(\wedge\)의 부정, (c)는 \(\vee\) 꼴이다.

풀이.

(a) \(\sim(\sim P) \equiv P\) [이중부정]. 한 줄로 끝난다.

(b) 두 걸음이다.

\[ \sim\big(P \wedge (\sim Q)\big) \equiv (\sim P) \vee \big(\sim(\sim Q)\big) \qquad [\text{드모르간 1}] \]
\[ \equiv (\sim P) \vee Q \qquad [\text{이중부정}] \]

여기서 멈춰도 되지만, 결과가 조건문 전개의 오른쪽 꼴이므로 한 걸음 더 갈 수 있다.

\[ \equiv P \Rightarrow Q \qquad [\text{조건문 전개, 역방향}] \]

(c) \((\sim P) \vee Q \equiv P \Rightarrow Q\) [조건문 전개, 역방향]. 한 줄로 끝난다.

복기. (b)의 최종 결과와 (c)의 결과가 같다는 것이 문제 16(b)의 재료다. \(\sim(P \wedge (\sim Q))\)와 \(P \Rightarrow Q\)가 동치라는 이 사실이, \(\Rightarrow\)를 \(\{\sim, \wedge\}\)만으로 적는 방법이 된다.

문제 7#

접근. (a)는 검증이므로 두 열을 만들어 대조한다. (b)는 표 없이 말로 하는 것이므로 \(P\)의 진리값으로 경우를 갈라, 각 경우에 양변이 무엇에 달렸는지 말한다. 마지막 한 줄은 S15주차의 소거법 서식이 이 동치의 어느 쪽을 쓰는지 짚는 일이다.

풀이.

(a) 진리표.

\(P\)

\(Q\)

\(P \Rightarrow Q\)

\(\sim P\)

\((\sim P) \vee Q\)

T

T

T

F

T

T

F

F

F

F

F

T

T

T

T

F

F

T

T

T

셋째 열과 다섯째 열이 (T, F, T, T)로 네 행 모두에서 일치하므로 동치이다.

(b) 표 없는 설명. \(P\)가 거짓인 경우, 왼쪽 \(P \Rightarrow Q\)는 전건이 거짓이므로 공허하게 참이고, 오른쪽은 \(\sim P\)가 참이므로 \(\vee\)가 참이다. 둘 다 참이다. \(P\)가 참인 경우, 왼쪽은 후건 \(Q\)의 값이 그대로 값이 되고, 오른쪽은 \(\sim P\)가 거짓이므로 \(\vee\)의 값이 \(Q\)의 값이 된다. 둘 다 \(Q\)에 달렸으므로 값이 같다. 두 경우가 모든 행을 덮으므로 동치이다.

S15주차 소거법의 근거는 이 동치를 역방향으로 읽는 데 있다. S15주차와 1권 9주차가 “조건문 분해”라 부르는 법칙이 §1.7의 조건문 전개이므로, 답안에는 어느 이름을 써도 같은 줄을 가리킨다. 결론이 “\(A\) 또는 \(B\)”일 때 \(\sim A\)를 가정하고 \(B\)를 얻는 서식은, \((\sim A) \vee B\)가 아니라 \(A \vee B \equiv (\sim A) \Rightarrow B\)라는 같은 동치의 다른 배치를 쓰는 것이다.

검산. 2행이 유일하게 F인 행인지 양쪽에서 확인한다. 왼쪽은 조건문의 유일한 거짓 행이고, 오른쪽은 \(\sim P\)와 \(Q\)가 둘 다 거짓인 유일한 행이다.

문제 8#

접근. 성분이 셋이므로 진리표는 여덟 행이다. 대수 쪽이 훨씬 짧다. 양변에 \(\Rightarrow\)가 있으므로 먼저 전부 \(\vee\)와 \(\wedge\)로 풀고, 한쪽을 분배로 펼쳐 다른 쪽과 같은 꼴을 만든다. 왼쪽에서 출발해 오른쪽으로 가는 편이 자연스럽다.

풀이.

\[ (P \vee Q) \Rightarrow R \equiv \sim(P \vee Q) \vee R \qquad [\text{조건문 전개}] \]
\[ \equiv \big((\sim P) \wedge (\sim Q)\big) \vee R \qquad [\text{드모르간 2}] \]
\[ \equiv \big((\sim P) \vee R\big) \wedge \big((\sim Q) \vee R\big) \qquad [\text{분배}] \]
\[ \equiv (P \Rightarrow R) \wedge (Q \Rightarrow R) \qquad [\text{조건문 전개, 역방향 두 번}] \]

도착식에 닿았으므로 멈춘다. \(\blacksquare\)

셋째 줄에서 쓴 분배는 \(\vee\)가 \(\wedge\) 위로 분배되는 쪽, 곧 \((X \wedge Y) \vee R \equiv (X \vee R) \wedge (Y \vee R)\)이다. §1.7의 분배 칸에 병기한 좌우를 바꾼 배치가 이것이고, 목록의 \(P \vee (Q \wedge R)\) 꼴과는 교환으로 이어진다. \(R\)가 결과에서 두 번 나타나야 한다는 요구가 이 방향을 정한다.

검산. 값이 갈릴 만한 행 하나로 확인한다. \(P\) 참\(\cdot\)\(Q\) 거짓\(\cdot\)\(R\) 거짓인 행에서 왼쪽은 \(P \vee Q\)가 참이므로 \(T \Rightarrow F = F\)이고, 오른쪽은 \(P \Rightarrow R\)가 \(T \Rightarrow F = F\)이므로 \(\wedge\)도 F다. 값이 같다.

복기. 이 동치는 새로 얻은 결과가 아니다. 1권 17주차 문제 20(a)가 같은 동치를 8행 진리표로 이미 증명했고, 그때 근거 ④에 등록됐다. 이번에 한 일은 같은 사실을 대수로 다시 유도해 §1.7 목록만으로도 도달할 수 있음을 확인한 것이다 — 표 여덟 행이 네 줄로 줄어든 것이 그 차이다.

이 동치가 S15주차 경우법의 논리적 근거다. 가정이 “\(P\) 또는 \(Q\)”일 때 두 경우로 쪼개 각각에서 \(R\)를 보이는 서식은, 오른쪽 식 \((P \Rightarrow R) \wedge (Q \Rightarrow R)\)를 증명하는 것과 같은 일이다. 경우가 전체를 덮어야 한다는 채점 기준이 왼쪽의 \(\vee\)에 대응한다.

문제 9#

접근. 여덟 행을 전부 계산해도 되지만, 전건이 F인 행은 바깥 조건문이 자동으로 T이므로 계산할 것이 없다. 그래서 전건 \((P \Rightarrow Q) \wedge (Q \Rightarrow R)\)가 T인 행만 골라, 그 행에서 후건 \(P \Rightarrow R\)도 T인지 확인하면 충분하다. 계산량을 줄이는 이 판단 자체가 이 문제의 요령이다.

풀이. 여덟 행을 (P, Q, R)로 적고 전건이 T인 행을 고른다. \(P \Rightarrow Q\)가 T인 행은 (T,T,T), (T,T,F), (F,T,T), (F,T,F), (F,F,T), (F,F,F)이고, 그중 \(Q \Rightarrow R\)도 T인 행은 (T,T,T), (F,T,T), (F,F,T), (F,F,F)의 네 행이다.

이 네 행에서 후건 \(P \Rightarrow R\)를 계산한다. (T,T,T): \(T \Rightarrow T = T\). (F,T,T): 전건 \(P\)가 F이므로 T. (F,F,T): 마찬가지로 T. (F,F,F): 마찬가지로 T. 네 행 모두 후건이 T이므로 바깥 조건문도 T다.

나머지 네 행 (T,T,F), (T,F,T), (T,F,F), (F,T,F)에서는 전건이 F이므로 바깥 조건문이 공허하게 참이다. 여덟 행이 모두 T이므로 항진명제이다. \(\blacksquare\)

복기. “전건이 T인 행만 검사한다”는 이 절약은 항진 판정에서 언제나 쓸 수 있다. 바깥 연산이 \(\Rightarrow\)인 식은 전건이 F인 행에서 값이 자동으로 T이므로, 검사해야 할 행은 전건이 T인 행뿐이다. 성분이 넷 이상일 때 이 절약이 결정적이 된다.

문제 10#

접근. 진단의 형식은 셋이다 — 틀린 문장의 지목, 반박, 올바른 진술. 답안이 근거로 든 문장(“조건문은 역과 동치”)이 곧 틀린 문장이므로 지목은 쉽고, 관건은 반박이다. 동치의 부정은 값이 갈리는 행 하나이므로 진리표 전체가 아니라 한 행만 제시하면 된다.

풀이. 틀린 문장은 “조건문은 역과 동치이기 때문이다”이다.

반박. \(P\)가 참이고 \(Q\)가 거짓인 행을 본다. 이 행에서 \(P \Rightarrow Q\)는 F이고 \(Q \Rightarrow P\)는 전건 \(Q\)가 거짓이므로 T다. 한 행에서 값이 갈리므로 정의 3.4에 의해 두 명제는 동치가 아니다.

올바른 진술. 조건문과 동치인 것은 역이 아니라 대우 \((\sim Q) \Rightarrow (\sim P)\) 이다(예제 2.3). 따라서 \(P \Rightarrow Q\)를 증명하려고 \(Q \Rightarrow P\)를 증명하면 원명제가 아닌 다른 명제를 증명한 것이 된다.

복기. 이 오류가 답안에서 살아남는 이유는 역이 참인 경우가 실제로 많기 때문이다. 역이 참이더라도 그것은 그 명제에 대한 별개의 사실이지 원명제의 증명이 아니다. S12주차 예제 2.3의 새는 답안이 같은 구조이고, 그 답안은 이가 마침 참이라 끝까지 완주되어 검사망을 통과했다. 참인 결론이 나왔다는 것은 올바른 명제를 증명했다는 보증이 되지 못한다.

문제 11#

접근. 성분이 셋이므로 여덟 행이다. 검증 문제이므로 양변의 열을 각각 만들어 대조한다. 열의 순서는 안쪽부터 — \(Q \wedge R\)와 \(P \vee Q\), \(P \vee R\)를 먼저 만들고 그다음 양변을 만든다. 행을 빠뜨리지 않으려면 §4의 표준 배열을 지킨다.

풀이.

\(P\)

\(Q\)

\(R\)

\(Q \wedge R\)

\(P \vee (Q \wedge R)\)

\(P \vee Q\)

\(P \vee R\)

\((P \vee Q) \wedge (P \vee R)\)

T

T

T

T

T

T

T

T

T

T

F

F

T

T

T

T

T

F

T

F

T

T

T

T

T

F

F

F

T

T

T

T

F

T

T

T

T

T

T

T

F

T

F

F

F

T

F

F

F

F

T

F

F

F

T

F

F

F

F

F

F

F

F

F

다섯째 열과 마지막 열이 여덟 행 모두에서 (T, T, T, T, T, F, F, F)로 일치하므로 두 명제는 논리적으로 동치이다. \(\blacksquare\)

복기. \(P\)가 참인 위 네 행에서는 양변이 자동으로 참이다 — 왼쪽은 \(\vee\)의 왼쪽 성분이 참이고, 오른쪽은 두 \(\vee\)가 모두 참이기 때문이다. 그래서 실제로 값이 갈릴 수 있는 곳은 \(P\)가 거짓인 아래 네 행뿐이고, 거기서는 양변이 각각 \(Q \wedge R\)와 \(Q \wedge R\)로 같아진다. 이 관찰이 여덟 행을 네 행으로 줄인다.

문제 12#

접근. 출발식이 \(\wedge\)의 부정이므로 첫 줄은 드모르간 1이다. 그러면 조건문의 부정 두 개가 나란히 놓이고, 각각에 조건문 부정을 적용하면 \(\Rightarrow\)가 모두 사라진다. 마지막에 진리표로 결과가 “값이 다른 행에서만 참”인지 확인한다.

풀이.

\[ \sim(P \Leftrightarrow Q) \equiv \sim\big((P \Rightarrow Q) \wedge (Q \Rightarrow P)\big) \qquad [\text{쌍조건문 분해}] \]
\[ \equiv \sim(P \Rightarrow Q) \vee \sim(Q \Rightarrow P) \qquad [\text{드모르간 1}] \]
\[ \equiv \big(P \wedge (\sim Q)\big) \vee \big(Q \wedge (\sim P)\big) \qquad [\text{조건문 부정, 두 번}] \]

진리표로 확인한다. 1행(\(P\)T \(Q\)T): \(F \vee F = F\). 2행(\(P\)T \(Q\)F): \(T \vee F = T\). 3행(\(P\)F \(Q\)T): \(F \vee T = T\). 4행(\(P\)F \(Q\)F): \(F \vee F = F\). 곧 (F, T, T, F)이고, 이는 \(P \Leftrightarrow Q\)의 열 (T, F, F, T)의 부정과 같다. 참이 되는 행은 \(P\)와 \(Q\)의 진리값이 다른 2\(\cdot\)3행뿐이므로, 이 명제는 배타적 또는이다. \(\blacksquare\)

복기. 배타적 또는은 정의 3.2의 다섯 연산에 없지만, 세 법칙만으로 다섯 연산의 식으로 적혔다. 새 연산을 도입하지 않고 기존 목록으로 적을 수 있다는 것이 문제 16의 완비성 논의로 이어지는 관찰이다.

문제 13#

접근. 수학 문장을 논리식으로 번역한 뒤 법칙을 적용하고, 다시 수학 문장으로 되돌리는 세 걸음이다. 관건은 번역과 되돌리기에서 부정을 정확히 옮기는 것 — “\(x > 0\)”의 부정이 “\(x < 0\)”이 아니라 “\(x \le 0\)”이다.

풀이. \(P\)를 “\(x > 0\)”, \(Q\)를 “\(x^2 > 0\)”이라 두면 원래 문장은 \(P \Rightarrow Q\)이다. 조건문 전개에 의해 \(P \Rightarrow Q \equiv (\sim P) \vee Q\)이다.

여기서 \(\sim P\)는 “\(x > 0\)이 아니다”이고, 실수의 순서 관계에서 그것은 “\(x \le 0\)”이다. \(Q\)는 그대로 “\(x^2 > 0\)”이다. 따라서 오른쪽 식을 문장으로 되돌리면 “\(x \le 0\) 또는 \(x^2 > 0\)”이 된다.

두 문장은 동치인 두 논리식의 번역이므로 모든 \(x\)에서 같은 진리값을 갖는다. 곧 같은 뜻이다. 확인해 보면 \(x = 2\)에서 왼쪽은 참이고 오른쪽도 둘째 조각이 참이며, \(x = -3\)에서 왼쪽은 전건이 거짓이라 공허하게 참이고 오른쪽은 첫째 조각이 참이다.

복기. 조건문을 \(\vee\) 꼴로 바꾸는 이 번역은 S15주차에서 소거법을 적용할 자리를 찾을 때 쓰인다. 조건문 꼴로는 소거법이 보이지 않지만 \(\vee\) 꼴로 바꾸면 결론이 “또는”이 되어 소거법의 신호가 드러난다.

문제 14#

접근. 두 부분이다. 앞부분은 항진명제와 추론 규칙의 관계를 말로 옮기는 일이고, 뒷부분은 1학기에서 그 걸음을 실제로 쓴 자리를 하나 찾아 대응시키는 일이다. 찾을 때는 “조건문 하나와 그 전건이 손에 있고 후건을 결론으로 적은 자리”를 찾는다.

풀이. 앞부분. 예제 2.1이 보인 것은 \(\big(P \wedge (P \Rightarrow Q)\big) \Rightarrow Q\)가 어떤 진리값 조합에서도 참이라는 것이다. 이 식의 전건은 “\(P\)가 참이고 \(P \Rightarrow Q\)도 참”이라는 상황이고 후건은 “\(Q\)가 참”이다. 전체가 항진이라는 말은 전건이 성립하는 어떤 상황에서도 후건이 반드시 성립한다는 뜻이므로, “\(P\)와 \(P \Rightarrow Q\)를 손에 쥐었으면 \(Q\)를 결론으로 적어도 된다”는 추론이 언제나 옳다는 보증이 된다. 이 추론이 전건 긍정이다.

뒷부분. S7주차의 특수화가 그 예다. 가정에 “모든 \(x\)에 대해 \(P(x)\)이면 \(Q(x)\)”가 있을 때, 자격을 검증한 값 \(a\)를 넣어 “\(P(a)\)이면 \(Q(a)\)”라는 조건문 하나를 얻는다. 이어서 \(P(a)\)가 참임을 확인하고 나면 \(Q(a)\)를 결론으로 적게 되는데, 이 마지막 걸음이 정확히 전건 긍정이다. 특수화가 조건문을 만들어 주고, 전건 긍정이 그 조건문에서 결론을 뽑는다.

복기. 1학기 내내 이 걸음을 근거를 대지 않고 썼다. 그것이 잘못은 아니지만, 왜 써도 되는지를 물었을 때 답할 것이 없었다. 예제 2.1의 네 칸이 그 답이다.

문제 15#

접근. “대수 법칙만으로”가 조건이므로 표를 그리지 않는다. 출발식의 바깥 연산은 부정이고 그 안이 조건문이므로, 먼저 조건문 전개로 안쪽을 \(\vee\) 꼴로 만들어야 드모르간을 걸 수 있다. 전개할 때 전건이 \(\sim P\)라는 점에 주의한다 — 그 부정이 \(\sim(\sim P)\)가 되어 이중부정 한 번이 추가로 필요하다.

풀이.

\[ \sim\big((\sim P) \Rightarrow Q\big) \equiv \sim\big(\sim(\sim P) \vee Q\big) \qquad [\text{조건문 전개}] \]
\[ \equiv \sim(P \vee Q) \qquad [\text{이중부정}] \]
\[ \equiv (\sim P) \wedge (\sim Q) \qquad [\text{드모르간 2}] \]

도착식에 닿았으므로 멈춘다. \(\blacksquare\)

검산. 진리표로 확인한다. \((\sim P) \Rightarrow Q\)가 거짓인 행은 전건 \(\sim P\)가 참이고 후건 \(Q\)가 거짓인 행, 곧 \(P\) 거짓\(\cdot\)\(Q\) 거짓인 4행 하나뿐이다. 따라서 그 부정은 4행에서만 참이다. 한편 \((\sim P) \wedge (\sim Q)\)도 두 성분이 모두 참인 4행에서만 참이다. 참이 되는 행이 같고 나머지 세 행에서 둘 다 거짓이므로 동치이다.

복기. 첫 줄에서 \(\sim(\sim P)\)를 바로 \(P\)로 적어 두 걸음을 한 줄에 합치고 싶어진다. 그렇게 적으면 답은 맞지만 §1.6 걸음 ②③(3단 틀의 ②)을 어긴 것이고, 부정이 하나 어긋났을 때 어느 법칙에서 어긋났는지 짚을 수 없게 된다.

문제 16#

접근. 두 문항 모두 오른쪽 식에서 출발해 왼쪽으로 가는 편이 짧다. 오른쪽 식의 바깥 연산이 부정이고 안이 \(\wedge\)이므로 드모르간 1이 곧바로 걸리고, 그 결과 안쪽에 생긴 이중부정들이 지워지면서 왼쪽 식이 나온다.

풀이.

(a)

\[ \sim\big((\sim P) \wedge (\sim Q)\big) \equiv \sim(\sim P) \vee \sim(\sim Q) \qquad [\text{드모르간 1}] \]
\[ \equiv P \vee Q \qquad [\text{이중부정, 두 번}] \]

따라서 \(P \vee Q \equiv \sim\big((\sim P) \wedge (\sim Q)\big)\)이고, \(\vee\)가 \(\sim\)과 \(\wedge\)만으로 적혔다.

(b)

\[ \sim\big(P \wedge (\sim Q)\big) \equiv (\sim P) \vee \sim(\sim Q) \qquad [\text{드모르간 1}] \]
\[ \equiv (\sim P) \vee Q \qquad [\text{이중부정}] \]
\[ \equiv P \Rightarrow Q \qquad [\text{조건문 전개, 역방향}] \]

따라서 \(P \Rightarrow Q \equiv \sim\big(P \wedge (\sim Q)\big)\)이고, \(\Rightarrow\)가 \(\sim\)과 \(\wedge\)만으로 적혔다.

남은 연산은 \(\Leftrightarrow\) 하나다. 쌍조건문 분해로 \(P \Leftrightarrow Q \equiv (P \Rightarrow Q) \wedge (Q \Rightarrow P)\)이고, 두 조건문 각각을 (b)로 바꿔 쓰면 \(\Leftrightarrow\)도 \(\sim\)과 \(\wedge\)만으로 적힌다. 다섯 연산 중 셋이 나머지 둘로 표현되므로 \(\{\sim, \wedge\}\)만으로 모든 논리 연산을 적을 수 있다. \(\blacksquare\)

복기. 여기서 한 일은 새 사실을 증명한 것이 아니라 목록의 항목 몇 개를 다시 배열한 것이다. 이미 확정된 동치를 방향만 바꿔 읽으면 “무엇을 무엇으로 표현할 수 있는가”라는 다른 질문의 답이 된다는 것이 이 문제의 요점이다.

문제 17#

접근. 진리표 쪽이 안전하다. 오른쪽 식은 \(\vee\)이므로 두 항 중 하나라도 참인 행에서 참이다. 왼쪽 항 \(P \wedge Q\)가 참인 행과 오른쪽 항 \((\sim P) \wedge (\sim Q)\)가 참인 행을 각각 찾으면 그 두 행이 답이다. 마지막 한 문장은 1권 25주차의 서식이 어느 동치를 근거로 삼는지 짚는 일이다.

풀이.

\(P\)

\(Q\)

\(P \Leftrightarrow Q\)

\(P \wedge Q\)

\((\sim P) \wedge (\sim Q)\)

\((P \wedge Q) \vee \big((\sim P) \wedge (\sim Q)\big)\)

T

T

T

T

F

T

T

F

F

F

F

F

F

T

F

F

F

F

F

F

T

F

T

T

셋째 열과 마지막 열이 네 행 모두에서 (T, F, F, T)로 일치하므로 동치이다. \(\blacksquare\)

1권 25주차와의 연결. 1권 25주차 정의 25.1의 iff 증명 서식이 두 방향 \(P \Rightarrow Q\)와 \(Q \Rightarrow P\)를 각각 증명하는 것은 쌍조건문 분해 \(P \Leftrightarrow Q \equiv (P \Rightarrow Q) \wedge (Q \Rightarrow P)\) 때문이고, 이 문제의 꼴은 같은 쌍조건문을 “둘 다 참인 경우와 둘 다 거짓인 경우”로 나눈 다른 분해이므로, 한 명제에 두 가지 증명 설계가 대응한다는 것을 보여 준다.

복기. 대수로 가는 길도 있다. 쌍조건문 분해와 조건문 전개로 \(\big((\sim P) \vee Q\big) \wedge \big((\sim Q) \vee P\big)\)를 만든 뒤 분배를 세 번 쓰면 네 항이 나온다 — 바깥에서 한 번(이때는 §1.7에 병기한 좌우를 바꾼 배치다), 그렇게 갈라진 두 조각 각각에 한 번씩. 네 항 중 \((\sim P) \wedge P\)와 \(Q \wedge (\sim Q)\)는 모순명제이므로 항등 법칙을 두 번 써서 지우면 나머지 두 항이 남는다. 진리표보다 길지만 표를 그리지 않는다.

문제 18#

접근. 세 주장 모두 동치 판정이므로 판단 기준은 하나다 — 두 열이 네 행 모두에서 일치하면 참, 한 행이라도 갈리면 거짓. 거짓인 경우에는 갈리는 행을 반드시 지목한다. 필요한 열은 예제 2.3의 표에 이미 다 있고, (c)의 왼쪽 열만 새로 만들면 된다.

풀이. 네 열의 값은 이렇다. \(P \Rightarrow Q\)는 (T, F, T, T), 역 \(Q \Rightarrow P\)는 (T, T, F, T), 이 \((\sim P) \Rightarrow (\sim Q)\)는 (T, T, F, T), 대우 \((\sim Q) \Rightarrow (\sim P)\)는 (T, F, T, T)이다. 그리고 \(\sim(P \Rightarrow Q)\)는 원명제 열을 뒤집은 (F, T, F, F)이다.

(a) 참. \(P \Rightarrow Q\)의 열과 대우의 열이 네 행 모두에서 (T, F, T, T)로 일치한다. 근거 행은 네 행 전부다.

(b) 거짓. 2행(\(P\)T \(Q\)F)에서 원명제는 F이고 역은 T이므로 값이 갈린다. 3행(\(P\)F \(Q\)T)에서도 원명제는 T이고 역은 F로 갈린다. 근거 행은 2행과 3행이다.

(c) 거짓. \(\sim(P \Rightarrow Q)\)는 (F, T, F, F)이고 이는 (T, T, F, T)이므로 1행에서 F와 T로 갈리고 4행에서도 F와 T로 갈린다. 근거 행은 1행과 4행이다.

복기. (c)가 답안에서 자주 나타나는 이유는 조건문의 부정을 “부정끼리의 조건문”으로 바꾸는 오해에 있다. 조건문 부정 법칙이 말하는 것은 \(\sim(P \Rightarrow Q)\)가 \(P \wedge (\sim Q)\)라는 것이고, 결과의 바깥 연산이 \(\Rightarrow\)가 아니라 \(\wedge\)다. 부정을 취하면 조건문이 조건문으로 남지 않는다는 것이 이 법칙의 핵심이다.

문제 19#

접근. 정리 3.1의 증명이고, 재료는 정의뿐이다. 양방향을 따로 적는다. 두 방향 모두 “행마다 값이 같다”와 “행마다 \(\Leftrightarrow\)가 T이다”가 같은 말임을 짚는 것이 전부이고, 그 짚기의 근거가 정의 3.2의 \(\Leftrightarrow\) 규칙 한 줄이다.

풀이. 두 합성명제 \(R\)와 \(S\)가 같은 성분 명제로 이루어졌다고 하자. 그러면 두 식은 같은 행 목록을 갖는다.

한 방향. \(R \equiv S\)라 하자. 정의 3.4에 의해 모든 행에서 \(R\)와 \(S\)의 진리값이 같다. 임의의 한 행을 잡으면 그 행에서 두 값이 같으므로, 정의 3.2의 \(\Leftrightarrow\) 규칙(두 진리값이 같은 행에서 참)에 의해 그 행에서 \(R \Leftrightarrow S\)는 T다. 행을 임의로 잡았으므로 모든 행에서 T이고, 정의 3.3에 의해 \(R \Leftrightarrow S\)는 항진명제다.

다른 방향. \(R \Leftrightarrow S\)가 항진명제라 하자. 정의 3.3에 의해 모든 행에서 그 값이 T다. 임의의 한 행을 잡으면 그 행에서 \(R \Leftrightarrow S\)가 T이므로, 정의 3.2의 \(\Leftrightarrow\) 규칙에 의해 그 행에서 \(R\)와 \(S\)의 진리값이 같다. 행을 임의로 잡았으므로 모든 행에서 값이 같고, 정의 3.4에 의해 \(R \equiv S\)이다. \(\blacksquare\)

이것이 판정 방법의 근거다. 동치를 확인할 때 실제로 하는 일은 두 열을 세로로 대조하는 것인데, 그 작업이 정당한 이유는 위 두 방향이 “열의 대조”와 “\(\Leftrightarrow\) 열이 전부 T”가 같은 판정임을 보증하기 때문이다. 어느 쪽으로 세든 결과가 같다.

복기. 증명의 두 방향이 쓴 문장이 거의 같고 순서만 뒤집혔다. 이런 대칭이 나타나는 것은 정의 3.2의 \(\Leftrightarrow\) 규칙 자체가 “값이 같다”와 “T이다”를 양방향으로 잇는 규칙이기 때문이다.

문제 20#

접근. 분량 제한이 붙은 서술 문제이므로 무엇을 넣고 무엇을 뺄지를 먼저 정한다. (a)는 §1.7의 대응표에서 한 줄을 고르고 그 줄이 예제 2.2의 어느 부분에 대응하는지 짚는 것으로 충분하며, 나머지 규칙은 “같은 방식”이라고 뭉치지 말고 항목 이름만 나열한다. (b)는 §1.10 확인 10이 갈라 놓은 두 문장을 각각 한 문장으로 줄인다.

풀이. (예시 답안)

(a) 예제 2.2에서 \(\sim(P \Rightarrow Q) \equiv P \wedge (\sim Q)\)를 진리표로 검증하고 같은 동치를 법칙 세 줄로 유도했는데, 이 동치가 S10주차의 N4다. 1학기에는 이것이 “NOT을 안으로 미는 규칙”이라는 절차로만 주어졌고 왜 그렇게 밀어도 되는지는 물을 자리가 없었다. 이번 주의 (a)가 그 근거이고, 같은 방식으로 N1은 이중부정, N2와 N3은 드모르간 두 항목이라는 진리표 근거를 얻는다.

(b) 이번 주는 논리 연산과 동치 자체가 계산 대상이므로 \(\Rightarrow\)와 \(\sim\)을 본문에 쓰는 것이 자연스럽고, 기호를 낱말로 풀면 오히려 무엇을 변형하고 있는지가 가려진다. 그러나 이 논리를 도구로 써서 수학 명제를 증명하는 산문에서는 기호가 논의 대상이 아니라 서술의 약호일 뿐이므로, 읽는 쪽이 흐름을 자연어로 따라갈 수 있도록 “…이면 …이다”로 적는다.

복기. 두 문항이 묻는 것은 같은 구분의 두 면이다. (a)는 절차에 근거가 붙는 과정이고, (b)는 그 근거를 다루는 자리와 그것을 쓰는 자리가 다르다는 것이다. 이번 주가 논리를 대상으로 삼은 유일한 주이므로, 다음 주부터는 (b)의 뒤쪽 규칙으로 돌아간다.

다음 주 예고 (C4): 열린 문장을 명제로 닫는 장치인 양화사 \(\forall\)와 \(\exists\)를 논리에 정식으로 편입한다. 이번 주 목록이 다루지 못한 N5\(\cdot\)N6이 거기서 자리를 얻고 (확인 7), 양화사가 섞인 명제의 부정이 절차로 정리된다. 이어서 정의를 동치인 다른 조건으로 갈아 끼우는 특성화를 다룬다 — 이번 주의 동치가 논리식 사이의 교체였다면, 특성화는 수학적 조건 사이의 교체다. 원서 2.10~2.11을 먼저 통독하고 온다.