C3주차 — 논리: 동치의 대수

내용

C3주차 — 논리: 동치의 대수#

이 주의 길잡이

핵심 문장: 논리 동치는 두 합성명제의 진리표가 모든 행에서 일치한다는 판정이고, 그 판정을 한 번씩 끝내 목록으로 굳힌 것이 등식처럼 갈아 끼울 수 있는 동치 법칙이다 — 진리표는 검증하고, 법칙은 유도한다.

이 주의 위치: 2학기(Chartrand) 20주의 C3주차. C2주차가 집합을 두 번째 언어로 다시 세웠다면 이번 주는 논리를 다시 세운다. 1권 7~9주차에서 한 건씩 진리표로 판정하던 동치들이 여기서 연쇄 변형의 부품 목록이 되고, S10주차의 부정 규칙 N1~N4가 여기서 진리표라는 근거를 얻는다. 남은 N5\(\cdot\)N6은 양화사가 진리표의 관할 밖이므로 다음 주 C4주차에서 자리를 얻는다. 그 C4주차의 양화사가 이 목록 위에 얹힌다.

원서 대응: Chartrand 2.1~2.9. 주간 루틴 1일차에 원서 2.1~2.9를 통독한 뒤 이 문서로 온다.

이번 주 목표#

다섯 논리 연산의 진리표를 Chartrand 기호(\(\sim, \wedge, \vee, \Rightarrow, \Leftrightarrow\))로 백지에 쓰고, 1권 7~9주차의 표기(\(\neg, \land, \lor\))와의 차이를 한 줄로 정리할 수 있다.
항진명제와 모순명제를 진리표로 판정하고, 논리 동치 \(R \equiv S\)의 정의와 “\(R \Leftrightarrow S\)가 항진명제”라는 판정 기준이 같은 것임을 설명할 수 있다.
동치 법칙 목록(교환\(\cdot\)결합\(\cdot\)분배\(\cdot\)드모르간\(\cdot\)이중부정\(\cdot\)조건문 전개\(\cdot\)조건문 부정\(\cdot\)대우\(\cdot\)쌍조건문 분해\(\cdot\)항등)을 백지에 쓰고, 줄마다 법칙 이름을 달아 진리표 없이 동치를 유도할 수 있다.
조건문의 세 변형(역\(\cdot\)이\(\cdot\)대우)의 동치 관계를 진리표로 완비하고, S10주차의 N1~N6이 이 목록의 어느 항목인지 대응시킬 수 있다.

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

준비 운동 (C2주차·1권 7~9주차 복습)#

노트에 먼저 적은 뒤 아래를 읽는다.

C2주차의 분할 세 조건을 쓰시오. 이번 주에는 쓰지 않지만, C11주차까지 손에서 놓지 않을 항목이다.
1권 7주차 정의 7.3의 세 연산과 1권 8주차 정의 8.1\(\cdot\)8.2의 진리표를 백지에 재현하시오 — \(\neg P\), \(P \land Q\), \(P \lor Q\), \(P \Rightarrow Q\), \(P \Leftrightarrow Q\)의 다섯 열.
S10주차의 NOT 기계 여섯 규칙 N1~N6을 기호까지 그대로 쓰시오. 이번 주에 그중 넷이 “논리 동치”라는 이름과 진리표 근거를 얻는다.

자주 나오는 세 가지 답#

세 문제를 적은 뒤 “그래서 이번 주에 새로 얻는 것이 무엇인가”에 답해 보면, 대개 다음 세 가지 중 하나가 나온다. 셋 다 1권과 1학기를 끝낸 사람에게서 나오는 답이고, 셋 다 이번 주가 메울 정확한 간격이 있다.

유형 1 — 1권 9주차에서 이미 다 했다. “드모르간도 대우도 진리표로 증명했다.”

옳은 부분이 크다. 1권 9주차 §1.6은 동치 목록 여덟 개를 확정했고, 그 목록은 이번 주에 하나도 폐기되지 않는다. 간격은 그 목록을 쓰는 방식에 있다. 1권에서 동치는 “필요할 때 한 건씩 인용하는 사실”이었다. 이번 주는 그 항목들을 한 줄에 하나씩 이어 붙여 출발식을 목표식까지 밀고 가는 연쇄 변형의 부품으로 쓴다. 판정에서 유도로 넘어가는 것이 이번 주의 전부다.

유형 2 — 진리표만 그리면 다 된다. “성분이 몇 개든 표를 그리면 끝난다.”

이 관찰도 옳다. 성분 명제가 유한 개면 진리표는 언제나 유한 번에 끝나고, 그래서 진리표는 완전한 판정 도구다. 간격은 진리표가 판정만 한다는 데 있다. “간단히 하시오”라는 요구 앞에서 표는 값의 열을 내놓을 뿐 더 간단한 식을 만들어 주지 않는다. §1.1의 실패 사례가 정확히 그 자리에서 멈춘다.

유형 3 — 기호가 낯설다. “1권은 \(\neg\)를 썼는데 원서는 \(\sim\)을 쓴다.”

차이는 실제로 있다. 다만 그 차이는 표기뿐이고, 두 기호의 진리표는 같은 표다. 간격은 기호가 아니라 다루는 층에 있다 — 이번 주는 논리식을 써서 무언가를 증명하는 주가 아니라, 논리식 자체를 계산 대상으로 놓고 변형하는 주다.

개념 — 판정에서 변형으로#

1 진리표만으로 밀어붙이면 어디서 막히는가#

이번 주의 도구가 왜 필요한지부터 확인한다. 손에 진리표 하나만 쥐고 다음 과제를 밀어붙여 보자.

시도 — 진리표만으로 밀어붙이기

과제: \(\sim\big((\sim P) \Rightarrow Q\big)\)를 더 간단한 꼴로 바꿔 쓰시오.

“\(P\)와 \(Q\)의 네 조합에 대해 값을 계산한다.

\(P\) 참\(\cdot\)\(Q\) 참이면 \(\sim P\)는 거짓, \((\sim P) \Rightarrow Q\)는 참, 전체는 거짓.

\(P\) 참\(\cdot\)\(Q\) 거짓이면 전체는 거짓. \(P\) 거짓\(\cdot\)\(Q\) 참이면 전체는 거짓.

\(P\) 거짓\(\cdot\)\(Q\) 거짓이면 \((\sim P) \Rightarrow Q\)가 거짓이므로 전체는 참.

따라서 이 명제의 열은 (거짓, 거짓, 거짓, 참)이다. 그러므로 이 명제는 … “

여기서 멈춘다. 열은 나왔는데, 그 열을 갖는 더 간단한 명제가 무엇인지 표가 알려 주지 않는다.

확인 1. 진리표가 해 주는 일과 해 주지 못하는 일을 한 줄씩 갈라 적어 보자. 위 과제가 멈춘 지점은 어느 쪽인가.

답

해 주는 일 — 두 명제가 주어졌을 때 같은지 다른지 판정한다. 해 주지 못하는

일 — 명제 하나만 주어졌을 때 그것과 같은 열을 갖는 다른 명제를 만들어 낸다.

과제가 요구한 것은 뒤쪽이므로 표는 판정 직전에서 멈춘다. 진리표를 쓰려면 비교할

후보를 이미 손에 쥐고 있어야 한다는 것이 이 도구의 구조적 한계다.

“표를 보고 답을 알아맞히면 된다”고 적었다면 그 관찰도 옳다. 문제는 알아맞히기가

절차가 아니라는 것이다 — 성분이 셋이면 행이 여덟이고 넷이면 열여섯이라, 후보를

떠올리는 일 자체가 과제의 본체가 된다.

이 주 전체의 기준

진리표는 검증하고, 동치 법칙은 유도한다.

이번 주가 하는 일은 진리표로 한 번씩 검증해 둔 동치를 목록으로 굳혀,

다음부터는 표 없이 갈아 끼우는 것이다.

2 표를 채우며 — 무엇이 같은 열을 갖는가#

굳힐 목록의 첫 항목을 직접 만들어 본다. 아래 표의 빈칸을 채워 보자.

행	\(P\)	\(Q\)	\(\sim(P \wedge Q)\)	\((\sim P) \vee (\sim Q)\)
1	T	T	F	\(\underline{\quad(1)\quad}\)
2	T	F	T	\(\underline{\quad(2)\quad}\)
3	F	T	\(\underline{\quad(3)\quad}\)	T
4	F	F	T	\(\underline{\quad(4)\quad}\)

확인 2. 네 빈칸을 채우고, 두 열을 세로로 대조해 관찰한 것을 한 줄로 적어 보자.

답

(1) F (\(\sim P\)와 \(\sim Q\)가 둘 다 F이므로 \(\vee\)는 F) (2) T (\(\sim Q\)가 T)

(3) T (\(P \wedge Q\)가 F이므로 그 부정은 T) (4) T (둘 다 T)

관찰 — 두 열이 네 행 모두에서 같다. 왼쪽 식과 오른쪽 식은 생김새가 전혀

다르지만, 어떤 진리값을 넣어도 값이 갈리지 않는다.

이 관찰에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 방금 두 열을 세로로 대조한 일을 문장으로 굳혔을 뿐이다. 굳히기 전에 비교의 재료가 되는 낱말과 연산부터 못 박는다.

정의 3.1 — 명제와 열린 문장 (statement · open sentence) [백지 암기 대상]#

참\(\cdot\)거짓이 정확히 하나로 정해지는 서술문을 명제라 한다. 변수를 담고 있어

진위가 그 변수의 값에 따라 달라지는 서술문을 열린 문장이라 한다.

열린 문장은 아직 명제가 아니다. “\(x > 3\)”은 \(x\)가 정해지기 전에는 참도 거짓도 아니다. 열린 문장을 명제로 닫는 장치가 양화사이고, 그것은 C4주차에서 다룬다. 이번 주의 계산은 전부 명제만을 재료로 한다.

표기 — 이번 주에 쓰는 기호와 읽는 법

Chartrand는 부정을 \(\sim P\)로 적는다. “물결 피”라고 읽고 뜻은 “\(P\)가 아니다”이며,

1권 7주차가 쓴 \(\neg P\)와 완전히 같은 기호다. 마찬가지로 \(\wedge\)는 1권의 \(\land\),

\(\vee\)는 1권의 \(\lor\)와 같다 — 활자의 굵기만 다르다.

읽는 법은 이렇다. \(P \wedge Q\)는 “피 그리고 큐”, \(P \vee Q\)는 “피 또는 큐”,

\(P \Rightarrow Q\)는 “피이면 큐”, \(P \Leftrightarrow Q\)는 “피일 필요충분조건은 큐”이다.

새 기호는 \(\equiv\) 하나다. “\(R \equiv S\)”는 “알과 에스는 논리적으로 동치이다”로

읽는다. 등호 \(=\)가 아니라 가로줄이 셋인 것에 뜻이 있다 — 두 식이 같은 수라는

말이 아니라, 두 명제가 모든 경우에 같은 진리값을 갖는다는 말이다.

정의 3.2 — 다섯 논리 연산 (logical connectives) [백지 암기 대상]#

다섯 연산의 값은 성분 명제의 진리값만으로 정해지며, 그 규칙 전체가 아래 표다.

\(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

\(\vee\)는 포함적 또는이다 — 둘 다 참인 1행에서도 값이 참이다. 일상어의 “또는”이

둘 중 하나만을 뜻하는 경우가 많으므로, 이 한 칸은 규칙으로 외운다.

\(P \Rightarrow Q\)가 거짓인 행은 2행 하나뿐이다 — \(P\)가 참인데 \(Q\)가 거짓인 경우.

나머지 세 행은 참이고, 특히 \(P\)가 거짓인 3\(\cdot\)4행은 공허하게 참이다.

\(P \Leftrightarrow Q\)는 두 진리값이 같은 행(1행과 4행)에서만 참이다.

확인 3. 조건문의 3행(\(P\) 거짓, \(Q\) 참)이 참인 이유를 1권 8주차 정의 8.1의 표현으로 한 줄 적어 보자.

답

약속이 깨지지 않았기 때문이다. 조건문은 “\(P\)가 참이면 \(Q\)도 참”이라는 약속이고,

약속이 깨졌다고 판정할 수 있는 경우는 \(P\)가 참인데 \(Q\)가 거짓인 한 가지뿐이다.

\(P\)가 거짓인 행에서는 약속이 발동조차 하지 않았으므로 깨질 수 없다 — 그래서 참이다.

“\(P\)가 거짓인데 참이라니 이상하다”고 적었다면 그 위화감은 자연스럽다. 위화감의

출처는 일상어의 “이면”이 인과를 함께 뜻한다는 데 있고, 정의 3.2의 \(\Rightarrow\)에는

인과가 들어 있지 않다. 이 연산은 표의 네 칸이 전부다.

3 항상 참인 식, 항상 거짓인 식#

정의 3.2의 표는 성분의 값에 따라 결과가 갈린다. 그런데 성분을 어떻게 정하든 값이 갈리지 않는 합성명제가 있다. \(P \vee (\sim P)\)는 \(P\)가 참이든 거짓이든 참이고, \(P \wedge (\sim P)\)는 어느 쪽이든 거짓이다. 이 두 부류에 이름을 준다.

정의 3.3 — 항진명제와 모순명제 (tautology · contradiction) [백지 암기 대상]#

성분 명제의 진리값을 어떻게 정하든 항상 참인 합성명제를 항진명제라 하고,

항상 거짓인 합성명제를 모순명제라 한다.

판정 절차는 표 하나로 끝난다. 마지막 열이 전부 T이면 항진명제, 전부 F이면 모순명제, T와 F가 섞여 있으면 둘 다 아니다. 여기서 “전부”는 정의 3.3의 “어떻게 정하든”을 그대로 옮긴 것이므로, 행을 하나라도 빠뜨리면 판정이 성립하지 않는다.

확인 4. \((P \wedge Q) \Rightarrow P\)를 판정해 보자. 네 행의 값을 각각 적고 결론을 한 줄로 쓴다.

답

1행(\(P\)T \(Q\)T): \(P \wedge Q\)는 T, 후건 \(P\)는 T이므로 \(T \Rightarrow T = T\).

2행(\(P\)T \(Q\)F): \(P \wedge Q\)는 F이므로 \(F \Rightarrow T = T\).

3행(\(P\)F \(Q\)T): \(P \wedge Q\)는 F이므로 \(F \Rightarrow F = T\).

4행(\(P\)F \(Q\)F): \(P \wedge Q\)는 F이므로 \(F \Rightarrow F = T\).

네 칸이 모두 T이므로 항진명제다. 이 항진이 뜻하는 것은 “둘 다 참이면 그중

하나는 참”이라는 추론이 언제나 옳다는 것이고, 1권 이후로 셀 수 없이 쓴

그 걸음의 정당성이 이 네 칸이다.

4 논리 동치 — 판정 하나에 두 얼굴#

§1.2에서 두 열이 네 행 모두에서 일치하는 현상을 관찰했다. 그 현상에 이름을 준다.

정의 3.4 — 논리 동치 (logical equivalence) [백지 암기 대상]#

같은 성분 명제로 이루어진 두 합성명제 \(R\)와 \(S\)가 모든 진리값 조합에서 같은

진리값을 가질 때, \(R\)와 \(S\)는 논리적으로 동치라 하고 \(R \equiv S\)로 쓴다.

이 정의는 §1.2의 관찰을 그대로 옮긴 것이다. 그런데 같은 판정을 정의 3.3의 낱말로도 말할 수 있다. 두 열이 모든 행에서 같다는 것은 그 행에서 \(R \Leftrightarrow S\)가 참이라는 뜻이고(정의 3.2의 \(\Leftrightarrow\) 규칙), 모든 행에서 참인 합성명제가 곧 항진명제다.

정리 3.1 — 동치의 두 얼굴 (logical equivalence as tautology) [백지 암기 대상]#

같은 성분 명제로 이루어진 두 합성명제 \(R\)와 \(S\)에 대하여,

\(R \equiv S\)인 것과 \(R \Leftrightarrow S\)가 항진명제인 것은 같은 판정이다.

증명은 문제 19에서 정의만으로 적는다. 지금 필요한 것은 결론이 아니라 이것이 두 얼굴이라는 사실이다 — 동치를 확인하고 싶을 때 두 열을 대조해도 되고, \(\Leftrightarrow\)로 묶은 한 열이 전부 T인지 봐도 된다. 어느 쪽을 골라도 같은 작업이다.

5 정의 해부 — 조각마다 하는 일#

정의 3.4의 한 문장은 네 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다.

조각	하는 일	판정에서의 역할
“같은 성분 명제로 이루어진”	비교 대상의 자격 제한	두 식이 같은 행 목록을 갖도록 맞춘다 — 이것이 없으면 표를 나란히 놓을 수 없다
“두 합성명제 \(R\)와 \(S\)가”	판정 대상의 선언	동치는 명제 한 개가 아니라 쌍에 대해 내려지는 판정이다
“모든 진리값 조합에서”	검사 범위의 확정	표의 전 행을 본다 — 한 행이라도 빠지면 판정이 아니다
“같은 진리값을 가진다”	판정 기준	두 열을 세로로 대조한다. 값의 이름이 아니라 값의 일치가 기준이다

조각 삭제 실험. 셋째 조각의 “모든”을 지우고 “어떤 조합에서”로 바꿔 보자. 그러면 \(P\)와 \(P \wedge Q\)가 동치가 된다 — 1행(\(P\) 참, \(Q\) 참)에서 두 값이 모두 참이기 때문이다.

확인 5. “모든”을 “어떤”으로 바꾸는 순간 정확히 무엇이 무너지는가. (\(P\)와 \(P \wedge Q\)만의 문제인지, 다른 쌍은 어떤지 함께 생각해 보자.)

답

동치의 존재 이유인 교체 가능성이 무너진다. \(P\)를 \(P \wedge Q\)로 갈아 끼울 수

있게 되면, 2행(\(P\) 참, \(Q\) 거짓)에서 참이던 명제가 거짓인 명제로 바뀐다. 진리값을

보존하지 못하는 교체는 아무 쓸모가 없다.

다른 쌍도 사정이 같다. 값이 T와 F 두 가지뿐이므로, 서로 부정 관계가 아닌 두 식은

거의 언제나 어느 한 행에서는 값이 겹친다 — 곧 대부분의 쌍이 동치가 되어 “동치”라는

말이 아무것도 구별하지 못한다. 정의의 조각 하나하나가 이런 붕괴를 막는 조건이다.

이 실험은 부정의 문법도 함께 알려 준다. 동치의 정의가 “모든 행에서 일치”이므로, “\(R \not\equiv S\)”를 보이는 데 필요한 것은 값이 갈리는 행 하나다. S10주차의 N5로 말하면 전칭의 부정이 존재이고, 그 존재의 증인이 여기서는 표의 한 행이다.

6 절차 해부 — 동치 유도의 걸음#

동치를 확인하는 일과 동치를 유도하는 일은 서로 다른 작업이다. 유도는 표를 그리지 않고 이미 확정된 동치를 한 줄에 하나씩 적용해 출발식을 목표식까지 밀고 간다. 그 절차를 네 걸음으로 못 박기 전에, 네 걸음이 모두 기대게 될 권리 하나에 먼저 이름을 붙여 둔다.

대치 원리 — 법칙은 부분식에도 걸린다

§1.7의 법칙들은 전부 식 전체의 꼴로 적혀 있지만, 적용은 식 안의 부분식에도

할 수 있다. \(R \equiv S\)이면 어떤 식 안의 \(R\)를 \(S\)로 바꿔 놓아도 전체의 진리값이

바뀌지 않기 때문이다. 이것을 대치 원리라 하고, 근거 ③(등식의 성질)이 이 권리에

대응한다 — 등식에서 같은 것을 같은 것으로 갈아 끼우던 일이 여기서 동치식으로 옮겨 온 것이다.

유도의 줄 옆에는 갈아 끼운 법칙의 이름만 적으면 근거로 충분하다. 부분식에 걸었다는

것을 함께 밝히고 싶으면 “[조건문 전개, 부분식에 적용]”처럼 덧붙인다.

백지 암기 대상

동치 변형 절차

① 출발식과 도착식을 먼저 적어 둔다.

② 지금 줄에서 없앨(또는 옮길) 연산 하나를 고른다.

③ 그 연산에 해당하는 법칙 하나만 적용하고, 줄 옆에 법칙 이름을 적는다.

④ 도착식에 닿을 때까지 ②③을 되풀이하고, 닿으면 멈춘다.

걸음마다 하는 일이 다르고, 빼면 무너지는 것도 다르다.

걸음	하는 일	이 걸음을 빼면 무엇이 무너지는가
① 출발식과 도착식 적기	변형의 기점과 종점을 고정한다	도착식이 없으면 언제 멈출지 정해지지 않아 변형이 끝나지 않는다
② 연산 하나 고르기	한 줄에 한 가지만 건드린다	한 줄에서 두 법칙을 동시에 쓰면 값이 어긋났을 때 어느 쪽이 틀렸는지 짚을 수 없다
③ 법칙 이름 달기	그 줄의 근거를 확정한다	결과가 틀렸다는 것은 진리표로 여전히 잡히지만(아래 확인 6), 어느 줄에서 틀렸는지는 지목할 수 없어 수정이 불가능해진다 — 아래 삭제 실험
④ 도착까지 반복	종료 조건을 지킨다	중간 꼴에서 멈추면 요구된 꼴이 아니므로 과제가 미완이다

걸음 삭제 실험. 걸음 ③(법칙 이름)을 지운 답안을 놓고 검사해 보자.

검사 대상 — 답안 Q

“\(\sim(P \Rightarrow Q) \equiv \sim\big((\sim P) \vee Q\big) \equiv (\sim P) \wedge (\sim Q)\)”

이름이 없으므로 각 등호가 무엇을 근거로 놓였는지 확정되지 않는다. 실제로 둘째 등호가 틀렸다. 부정을 괄호 안으로 밀어 넣으면 \(\sim(\sim P) \wedge (\sim Q)\)가 나오고 이중부정을 거쳐 \(P \wedge (\sim Q)\)가 되어야 하는데, 답안 Q는 \(\sim(\sim P)\)를 \(\sim P\)로 적어 부정 하나를 잃었다. 줄마다 이름이 달려 있었다면 “[드모르간 2]”라 적힌 줄에서 부정의 개수가 맞지 않는 것이 곧바로 드러난다.

확인 6. 답안 Q의 결론 \((\sim P) \wedge (\sim Q)\)가 틀렸음을 진리표 한 행으로 보이려 한다. 어느 행을 고르고, 두 값은 각각 무엇인가.

답

2행(\(P\) 참, \(Q\) 거짓)을 고른다. 왼쪽 — \(P \Rightarrow Q\)가 F이므로

\(\sim(P \Rightarrow Q)\)는 T. 오른쪽 — \(\sim P\)가 F이므로

\((\sim P) \wedge (\sim Q)\)는 F. 값이 갈리므로 동치가 아니다.

행 하나로 반박이 끝나는 이유는 §1.5에서 확인했다 — 동치의 정의가 “모든 행”이므로

그 부정은 “어느 한 행”이고, 그 한 행이 증인이다. 나머지 세 행은 볼 필요가 없다.

7 동치 법칙 목록 [백지 암기 대상]#

목록의 항목 대부분은 1권 8~9주차와 이번 주에 진리표로 검증됐다. 여덟 항목은 1권 9주차 §1.6의 목록이 그대로이고, 쌍조건문 분해는 1권 8주차 정의 8.2가 쌍조건문을 두 조건문의 \(\wedge\)로 선언한 데서 온다. 검증이 끝난 항목은 다음부터 표를 그리지 않고 이름만 대고 갈아 끼운다.

아직 검증하지 않은 세 항목이 남는다 — 교환의 \(\vee\) 쪽, 결합 두 줄, 항등 두 줄. 이 셋은 §5 체크리스트에서 각자 진리표로 확인한 뒤 근거 ④에 등록한다. 확인을 마치기 전까지 세 항목은 근거 ④가 아니다. 1권 9주차가 분배 두 항목에 대해 쓴 방식과 같다.

법칙	내용
교환	\(P \wedge Q \equiv Q \wedge P\) / \(P \vee Q \equiv Q \vee P\)
결합	\((P \wedge Q) \wedge R \equiv P \wedge (Q \wedge R)\) / \((P \vee Q) \vee R \equiv P \vee (Q \vee R)\)
분배	\(P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)\) / \(P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)\) / 좌우를 바꾼 배치 \((Q \wedge R) \vee P \equiv (Q \vee P) \wedge (R \vee P)\)도 같은 법칙이다(교환으로 이어진다)
드모르간 1	\(\sim(P \wedge Q) \equiv (\sim P) \vee (\sim Q)\)
드모르간 2	\(\sim(P \vee Q) \equiv (\sim P) \wedge (\sim Q)\)
이중부정	\(\sim(\sim P) \equiv P\)
조건문 전개 (1권 9주차\(\cdot\)S15주차의 ‘조건문 분해’)	\(P \Rightarrow Q \equiv (\sim P) \vee Q\)
조건문 부정	\(\sim(P \Rightarrow Q) \equiv P \wedge (\sim Q)\)
대우	\(P \Rightarrow Q \equiv (\sim Q) \Rightarrow (\sim P)\)
쌍조건문 분해	\(P \Leftrightarrow Q \equiv (P \Rightarrow Q) \wedge (Q \Rightarrow P)\)
항등	모순명제 \(C\)와 항진명제 \(V\)에 대해 \(R \vee C \equiv R\), \(R \wedge V \equiv R\)

목록에서 가장 많이 쓰이는 것은 조건문 전개다. \(\Rightarrow\)가 들어간 식은 그대로는 드모르간이 걸리지 않으므로, 대부분의 유도가 조건문 전개로 \(\Rightarrow\)를 \(\vee\)로 바꾸는 데서 시작한다. 방향을 거꾸로 써서 \(\vee\) 꼴을 \(\Rightarrow\) 꼴로 되돌리는 것도 같은 법칙이고, 그때는 “[조건문 전개, 역방향]”이라 적는다.

이름 하나는 대조해 두어야 한다. 1권 9주차 §1.6의 동치 목록과 S15주차는 같은 법칙을 조건문 분해로 부른다 — 이름만 다르고 식은 같다. 이번 주가 ‘분해’라는 낱말을 쌍조건문 쪽에 쓰기 때문에 조건문 쪽은 ‘전개’로 적는다. 1권이나 1학기 문서를 펴 놓고 대조할 때는 두 이름이 같은 줄을 가리킨다는 것만 기억하면 된다.

1권에서 감각으로 하던 것이 여기서 이름을 얻는다. 1권 9주차 §1.6의 동치 목록 여덟 개는 “진리표로 판정된 사실”의 목록이었고, 필요할 때 근거 ④로 한 건씩 인용하는 방식으로 썼다. 같은 항목들이 여기서 연쇄 변형의 부품이라는 역할과 줄마다 이름을 다는 서식을 얻는다.

1학기와의 대응도 그대로 맞는다. S10주차에서 “NOT을 안으로 미는 규칙”이라 부르며 절차로만 익힌 여섯 규칙 중 넷이 이 목록의 항목이다.

S10주차 규칙	이번 주 법칙
N1 이중부정	이중부정
N2 드모르간 (\(\wedge\))	드모르간 1
N3 드모르간 (\(\vee\))	드모르간 2
N4 조건문 부정	조건문 부정
N5 전칭의 반전	이 목록에 없다
N6 존재의 반전	이 목록에 없다

확인 7. N5와 N6에 대응하는 항목이 이번 주 목록에 없는 이유는 무엇인가. 정의 3.2의 첫 줄을 근거로 한 줄 적어 보자.

답

정의 3.2는 “값은 성분 명제의 진리값만으로 정해진다”고 못 박았다. 다섯 연산은

성분이 T인지 F인지만 알면 값이 나오므로 유한한 표로 전부 적을 수 있다.

\(\forall\)와 \(\exists\)는 그렇지 않다 — 값을 정하려면 변수의 범위 전체를 훑어야 하고,

그 범위가 무한이면 훑는 일이 유한한 표에 들어가지 않는다. 그래서 N5\(\cdot\)N6은 진리표의

관할 밖이고, 양화사를 정식으로 편입하는 C4주차에서 다룬다.

8 조건문의 세 변형 — 역·이·대우 [백지 암기 대상]#

조건문 \(P \Rightarrow Q\)에 대하여, 역은 \(Q \Rightarrow P\), 이는

\((\sim P) \Rightarrow (\sim Q)\), 대우는 \((\sim Q) \Rightarrow (\sim P)\)이다.

넷 사이의 관계는 두 쌍으로 갈린다. 원명제와 대우가 동치이고, 역과 이가 동치이며, 원명제와 역은 동치가 아니다. 진리표 완비는 예제 2.3에서 한다.

확인 8. 역과 이가 동치임을 진리표를 새로 그리지 않고 §1.7의 법칙 두 개로 설명해 보자.

답

이 \((\sim P) \Rightarrow (\sim Q)\)의 대우를 만들면

\(\sim(\sim Q) \Rightarrow \sim(\sim P)\)이고 [대우], 두 이중부정을 지우면

\(Q \Rightarrow P\) — 곧 역이다 [이중부정]. 대우 법칙에 의해 원식과 그 대우는

동치이므로 이 \(\equiv\) 역이다.

표를 그리지 않고 법칙 두 줄로 끝났다는 것이 §1.6 절차가 하는 일이다. 같은 결론을

진리표로 얻으려면 네 행짜리 열 두 개를 만들어 대조해야 한다.

1권 9주차 §1.7에서 “참인 명제의 역은 검증 전까지 별개 명제”라고 못 박은 판정이 여기서 진리표로 완결된다. S12주차 예제 2.3이 해부한 새는 답안 — 대우를 쓴다고 선언하고 실제로는 이를 증명한 답안 — 이 왜 원명제의 증명이 아닌지도 같은 표가 답한다. 이는 역과 동치이고 역은 원명제와 동치가 아니기 때문이다.

9 근거 목록 갱신 — ④ 칸에 법칙 목록이 들어온다#

근거	이번 주까지의 내용	이번 주에 이렇게 쓴다
① 정의	앞선 주차의 정의 + 정의 3.1~3.4	“동치” \(\leftrightarrow\) “모든 행에서 진리값 일치” 사이를 번역한다
② 닫힘성	정수\(\cdot\)집합 연산의 닫힘성	이번 주 계산에는 등장하지 않는다 — 재료가 수가 아니라 진리값이다
③ 등식의 성질	양변에 같은 연산 / 전개 / 묶기	§1.6의 대치 원리 — 동치인 부분식을 통째로 갈아 끼우는 권리가 여기에 대응한다
④ 이미 증명한 명제	앞선 주차의 결과 + §1.7 동치 법칙 목록(교환의 \(\vee\) 쪽\(\cdot\)결합\(\cdot\)항등 세 항목은 §5에서 검증한 뒤 등록), 정리 3.1	변형의 각 줄 옆에 법칙 이름을 단다

확인 9. 어떤 유도에 다음 두 근거 표시가 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가.

(가) “[드모르간 1]” (나) “괄호를 풀면 당연히”

답

(가) 허용 — 근거 ④. 목록에 이름이 있는 항목이므로 그 이름만으로 줄의 근거가 된다.

(나) 불허 — 목록 밖이다. “당연히”는 어떤 규칙을 적용했는지 지목하지 않으므로,

§1.6의 삭제 실험대로 그 줄은 검사될 수 없다. 실제로 답안 Q가 부정 하나를 잃은

자리가 정확히 이런 줄이었다.

10 원칙 3의 예외 구역#

C1주차의 기호 사용 원칙 3은 “논리 자체를 논의하는 자리가 아니면 \(\Rightarrow\), \(\forall\), \(\exists\), \(\ni\) 를 본문에 쓰지 않는다”였다. 이번 주는 그 예외 구역이다 — 논리 연산과 동치 자체가 논의 대상이므로 기호를 본문에 정면으로 쓴다.

예외는 이번 주 본문에 한정된다. 이 논리를 도구로 써서 수학 명제를 증명하는 산문에서는 여전히 낱말로 적는다. 구분의 기준은 기호가 계산의 대상인가, 아니면 서술의 약호인가이다.

확인 10. 다음 두 문장 중 이번 주 본문에서 허용되는 것은 어느 쪽인가. 이유를 한 줄로 적는다.

(가) “\(P \Rightarrow Q\)의 대우는 \((\sim Q) \Rightarrow (\sim P)\)이다.”

(나) “\(n\)이 짝수 \(\Rightarrow\) \(n^2\)이 짝수이다.”

답

(가)가 허용된다. \(\Rightarrow\)가 붙은 식 자체를 논의 대상으로 놓고 그 대우가

무엇인지 말하고 있으므로 원칙 3의 예외에 해당한다.

(나)는 허용되지 않는다. 여기서 \(\Rightarrow\)는 논의 대상이 아니라 “이면”의 약호로

쓰였고, 이런 자리는 수학 명제를 서술하는 산문이므로 “\(n\)이 짝수이면 \(n^2\)도

짝수이다”로 적는다. C1주차 문제 17이 요구한 구분이 이것이다.