# C3주차 — 논리: 동치의 대수 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 논리 동치는 두 합성명제의 진리표가 모든 행에서 일치한다는 판정이고, 그 판정을 한 번씩 끝내 목록으로 굳힌 것이 등식처럼 갈아 끼울 수 있는 동치 법칙이다 — 진리표는 검증하고, 법칙은 유도한다. **이 주의 위치**: 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를 통독한 뒤 이 문서로 온다. ::: ## 이번 주 목표 1. 다섯 논리 연산의 진리표를 Chartrand 기호($\sim, \wedge, \vee, \Rightarrow, \Leftrightarrow$)로 백지에 쓰고, 1권 7~9주차의 표기($\neg, \land, \lor$)와의 차이를 한 줄로 정리할 수 있다. 1. **항진명제**와 **모순명제**를 진리표로 판정하고, 논리 동치 $R \equiv S$의 정의와 "$R \Leftrightarrow S$가 항진명제"라는 판정 기준이 같은 것임을 설명할 수 있다. 1. **동치 법칙 목록**(교환$\cdot$결합$\cdot$분배$\cdot$드모르간$\cdot$이중부정$\cdot$조건문 전개$\cdot$조건문 부정$\cdot$대우$\cdot$쌍조건문 분해$\cdot$항등)을 백지에 쓰고, 줄마다 법칙 이름을 달아 진리표 없이 동치를 유도할 수 있다. 1. 조건문의 세 변형(역$\cdot$이$\cdot$대우)의 동치 관계를 진리표로 완비하고, S10주차의 N1~N6이 이 목록의 어느 항목인지 대응시킬 수 있다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (C2주차·1권 7~9주차 복습) 노트에 먼저 적은 뒤 아래를 읽는다. 1. C2주차의 **분할** 세 조건을 쓰시오. 이번 주에는 쓰지 않지만, C11주차까지 손에서 놓지 않을 항목이다. 1. 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$의 다섯 열. 1. S10주차의 NOT 기계 여섯 규칙 N1~N6을 기호까지 그대로 쓰시오. 이번 주에 그중 넷이 "논리 동치"라는 이름과 진리표 근거를 얻는다. ### 자주 나오는 세 가지 답 세 문제를 적은 뒤 "그래서 이번 주에 새로 얻는 것이 무엇인가"에 답해 보면, 대개 다음 세 가지 중 하나가 나온다. 셋 다 1권과 1학기를 끝낸 사람에게서 나오는 답이고, 셋 다 이번 주가 메울 정확한 간격이 있다. - **유형 1 — 1권 9주차에서 이미 다 했다.** "드모르간도 대우도 진리표로 증명했다." 옳은 부분이 크다. 1권 9주차 §1.6은 동치 목록 여덟 개를 확정했고, 그 목록은 이번 주에 하나도 폐기되지 않는다. 간격은 그 목록을 **쓰는 방식**에 있다. 1권에서 동치는 "필요할 때 한 건씩 인용하는 사실"이었다. 이번 주는 그 항목들을 한 줄에 하나씩 이어 붙여 출발식을 목표식까지 밀고 가는 **연쇄 변형**의 부품으로 쓴다. 판정에서 유도로 넘어가는 것이 이번 주의 전부다. - **유형 2 — 진리표만 그리면 다 된다.** "성분이 몇 개든 표를 그리면 끝난다." 이 관찰도 옳다. 성분 명제가 유한 개면 진리표는 언제나 유한 번에 끝나고, 그래서 진리표는 완전한 판정 도구다. 간격은 진리표가 **판정만** 한다는 데 있다. "간단히 하시오"라는 요구 앞에서 표는 값의 열을 내놓을 뿐 더 간단한 식을 만들어 주지 않는다. §1.1의 실패 사례가 정확히 그 자리에서 멈춘다. - **유형 3 — 기호가 낯설다.** "1권은 $\neg$를 썼는데 원서는 $\sim$을 쓴다." 차이는 실제로 있다. 다만 그 차이는 표기뿐이고, 두 기호의 진리표는 같은 표다. 간격은 기호가 아니라 다루는 층에 있다 — 이번 주는 논리식을 **써서** 무언가를 증명하는 주가 아니라, 논리식 자체를 계산 대상으로 놓고 변형하는 주다. ## 개념 — 판정에서 변형으로 ### 1 진리표만으로 밀어붙이면 어디서 막히는가 이번 주의 도구가 왜 필요한지부터 확인한다. 손에 진리표 하나만 쥐고 다음 과제를 밀어붙여 보자. :::{admonition} 시도 — 진리표만으로 밀어붙이기 :class: quotebox 과제: $\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$가 거짓이므로 전체는 참. 따라서 이 명제의 열은 (거짓, 거짓, 거짓, 참)이다. 그러므로 이 명제는 … " ::: 여기서 멈춘다. 열은 나왔는데, 그 열을 갖는 **더 간단한 명제**가 무엇인지 표가 알려 주지 않는다. :::{container} quotebox **확인 1.** 진리표가 해 주는 일과 해 주지 못하는 일을 한 줄씩 갈라 적어 보자. 위 과제가 멈춘 지점은 어느 쪽인가. ::: :::{admonition} 답 :class: quotebox dropdown 해 주는 일 — 두 명제가 **주어졌을 때** 같은지 다른지 판정한다. 해 주지 못하는 일 — 명제 하나만 주어졌을 때 그것과 같은 열을 갖는 **다른 명제를 만들어** 낸다. 과제가 요구한 것은 뒤쪽이므로 표는 판정 직전에서 멈춘다. 진리표를 쓰려면 비교할 후보를 이미 손에 쥐고 있어야 한다는 것이 이 도구의 구조적 한계다. "표를 보고 답을 알아맞히면 된다"고 적었다면 그 관찰도 옳다. 문제는 알아맞히기가 절차가 아니라는 것이다 — 성분이 셋이면 행이 여덟이고 넷이면 열여섯이라, 후보를 떠올리는 일 자체가 과제의 본체가 된다. ::: :::{admonition} 이 주 전체의 기준 :class: quotebox 진리표는 검증하고, 동치 법칙은 유도한다. 이번 주가 하는 일은 진리표로 한 번씩 검증해 둔 동치를 목록으로 굳혀, 다음부터는 표 없이 갈아 끼우는 것이다. ::: ### 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}$ | :::{container} quotebox **확인 2.** 네 빈칸을 채우고, 두 열을 세로로 대조해 관찰한 것을 한 줄로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (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) [백지 암기 대상] :::{container} quotebox 참$\cdot$거짓이 정확히 하나로 정해지는 서술문을 **명제**라 한다. 변수를 담고 있어 진위가 그 변수의 값에 따라 달라지는 서술문을 **열린 문장**이라 한다. ::: 열린 문장은 아직 명제가 아니다. "$x > 3$"은 $x$가 정해지기 전에는 참도 거짓도 아니다. 열린 문장을 명제로 닫는 장치가 양화사이고, 그것은 C4주차에서 다룬다. 이번 주의 계산은 전부 명제만을 재료로 한다. :::{admonition} 표기 — 이번 주에 쓰는 기호와 읽는 법 :class: quotebox 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) [백지 암기 대상] :::{container} quotebox 다섯 연산의 값은 성분 명제의 진리값만으로 정해지며, 그 규칙 전체가 아래 표다. ::: | **$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행)에서만 참이다. :::{container} quotebox **확인 3.** 조건문의 3행($P$ 거짓, $Q$ 참)이 참인 이유를 1권 8주차 정의 8.1의 표현으로 한 줄 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 약속이 깨지지 않았기 때문이다. 조건문은 "$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) [백지 암기 대상] :::{container} quotebox 성분 명제의 진리값을 어떻게 정하든 항상 참인 합성명제를 **항진명제**라 하고, 항상 거짓인 합성명제를 **모순명제**라 한다. ::: 판정 절차는 표 하나로 끝난다. 마지막 열이 전부 T이면 항진명제, 전부 F이면 모순명제, T와 F가 섞여 있으면 둘 다 아니다. 여기서 "전부"는 정의 3.3의 "어떻게 정하든"을 그대로 옮긴 것이므로, 행을 하나라도 빠뜨리면 판정이 성립하지 않는다. :::{container} quotebox **확인 4.** $(P \wedge Q) \Rightarrow P$를 판정해 보자. 네 행의 값을 각각 적고 결론을 한 줄로 쓴다. ::: :::{admonition} 답 :class: quotebox dropdown 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) [백지 암기 대상] :::{container} quotebox 같은 성분 명제로 이루어진 두 합성명제 $R$와 $S$가 모든 진리값 조합에서 같은 진리값을 가질 때, $R$와 $S$는 **논리적으로 동치**라 하고 $R \equiv S$로 쓴다. ::: 이 정의는 §1.2의 관찰을 그대로 옮긴 것이다. 그런데 같은 판정을 정의 3.3의 낱말로도 말할 수 있다. 두 열이 모든 행에서 같다는 것은 그 행에서 $R \Leftrightarrow S$가 참이라는 뜻이고(정의 3.2의 $\Leftrightarrow$ 규칙), 모든 행에서 참인 합성명제가 곧 항진명제다. ### 정리 3.1 — 동치의 두 얼굴 (logical equivalence as tautology) [백지 암기 대상] :::{container} quotebox 같은 성분 명제로 이루어진 두 합성명제 $R$와 $S$에 대하여, $R \equiv S$인 것과 $R \Leftrightarrow S$가 항진명제인 것은 같은 판정이다. ::: 증명은 문제 19에서 정의만으로 적는다. 지금 필요한 것은 결론이 아니라 이것이 **두 얼굴**이라는 사실이다 — 동치를 확인하고 싶을 때 두 열을 대조해도 되고, $\Leftrightarrow$로 묶은 한 열이 전부 T인지 봐도 된다. 어느 쪽을 골라도 같은 작업이다. ### 5 정의 해부 — 조각마다 하는 일 정의 3.4의 한 문장은 네 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다. | **조각** | **하는 일** | **판정에서의 역할** | |---|---|---| | "같은 성분 명제로 이루어진" | 비교 대상의 자격 제한 | 두 식이 같은 행 목록을 갖도록 맞춘다 — 이것이 없으면 표를 나란히 놓을 수 없다 | | "두 합성명제 $R$와 $S$가" | 판정 대상의 선언 | 동치는 명제 한 개가 아니라 **쌍**에 대해 내려지는 판정이다 | | "모든 진리값 조합에서" | 검사 범위의 확정 | 표의 전 행을 본다 — 한 행이라도 빠지면 판정이 아니다 | | "같은 진리값을 가진다" | 판정 기준 | 두 열을 세로로 대조한다. 값의 이름이 아니라 값의 일치가 기준이다 | **조각 삭제 실험.** 셋째 조각의 "모든"을 지우고 "어떤 조합에서"로 바꿔 보자. 그러면 $P$와 $P \wedge Q$가 동치가 된다 — 1행($P$ 참, $Q$ 참)에서 두 값이 모두 참이기 때문이다. :::{container} quotebox **확인 5.** "모든"을 "어떤"으로 바꾸는 순간 정확히 무엇이 무너지는가. ($P$와 $P \wedge Q$만의 문제인지, 다른 쌍은 어떤지 함께 생각해 보자.) ::: :::{admonition} 답 :class: quotebox dropdown 동치의 존재 이유인 **교체 가능성**이 무너진다. $P$를 $P \wedge Q$로 갈아 끼울 수 있게 되면, 2행($P$ 참, $Q$ 거짓)에서 참이던 명제가 거짓인 명제로 바뀐다. 진리값을 보존하지 못하는 교체는 아무 쓸모가 없다. 다른 쌍도 사정이 같다. 값이 T와 F 두 가지뿐이므로, 서로 부정 관계가 아닌 두 식은 거의 언제나 어느 한 행에서는 값이 겹친다 — 곧 대부분의 쌍이 동치가 되어 "동치"라는 말이 아무것도 **구별하지 못한다**. 정의의 조각 하나하나가 이런 붕괴를 막는 조건이다. ::: 이 실험은 부정의 문법도 함께 알려 준다. 동치의 정의가 "모든 행에서 일치"이므로, "$R \not\equiv S$"를 보이는 데 필요한 것은 값이 갈리는 **행 하나**다. S10주차의 N5로 말하면 전칭의 부정이 존재이고, 그 존재의 증인이 여기서는 표의 한 행이다. ### 6 절차 해부 — 동치 유도의 걸음 동치를 확인하는 일과 동치를 **유도**하는 일은 서로 다른 작업이다. 유도는 표를 그리지 않고 이미 확정된 동치를 한 줄에 하나씩 적용해 출발식을 목표식까지 밀고 간다. 그 절차를 네 걸음으로 못 박기 전에, 네 걸음이 모두 기대게 될 권리 하나에 먼저 이름을 붙여 둔다. :::{admonition} 대치 원리 — 법칙은 부분식에도 걸린다 :class: quotebox §1.7의 법칙들은 전부 식 **전체**의 꼴로 적혀 있지만, 적용은 식 **안의 부분식**에도 할 수 있다. $R \equiv S$이면 어떤 식 안의 $R$를 $S$로 바꿔 놓아도 전체의 진리값이 바뀌지 않기 때문이다. 이것을 **대치 원리**라 하고, 근거 ③(등식의 성질)이 이 권리에 대응한다 — 등식에서 같은 것을 같은 것으로 갈아 끼우던 일이 여기서 동치식으로 옮겨 온 것이다. 유도의 줄 옆에는 갈아 끼운 법칙의 이름만 적으면 근거로 충분하다. 부분식에 걸었다는 것을 함께 밝히고 싶으면 "[조건문 전개, 부분식에 적용]"처럼 덧붙인다. ::: :::{admonition} 백지 암기 대상 :class: keybox **동치 변형 절차** ① 출발식과 도착식을 먼저 적어 둔다. ② 지금 줄에서 없앨(또는 옮길) 연산 하나를 고른다. ③ 그 연산에 해당하는 법칙 **하나만** 적용하고, 줄 옆에 법칙 이름을 적는다. ④ 도착식에 닿을 때까지 ②③을 되풀이하고, 닿으면 멈춘다. ::: 걸음마다 하는 일이 다르고, 빼면 무너지는 것도 다르다. | **걸음** | **하는 일** | **이 걸음을 빼면 무엇이 무너지는가** | |---|---|---| | ① 출발식과 도착식 적기 | 변형의 기점과 종점을 고정한다 | 도착식이 없으면 언제 멈출지 정해지지 않아 변형이 끝나지 않는다 | | ② 연산 하나 고르기 | 한 줄에 한 가지만 건드린다 | 한 줄에서 두 법칙을 동시에 쓰면 값이 어긋났을 때 어느 쪽이 틀렸는지 짚을 수 없다 | | ③ 법칙 이름 달기 | 그 줄의 근거를 확정한다 | 결과가 틀렸다는 것은 진리표로 여전히 잡히지만(아래 확인 6), **어느 줄에서** 틀렸는지는 지목할 수 없어 수정이 불가능해진다 — 아래 삭제 실험 | | ④ 도착까지 반복 | 종료 조건을 지킨다 | 중간 꼴에서 멈추면 요구된 꼴이 아니므로 과제가 미완이다 | **걸음 삭제 실험.** 걸음 ③(법칙 이름)을 지운 답안을 놓고 검사해 보자. :::{admonition} 검사 대상 — 답안 Q :class: quotebox "$\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]"라 적힌 줄에서 부정의 개수가 맞지 않는 것이 곧바로 드러난다. :::{container} quotebox **확인 6.** 답안 Q의 결론 $(\sim P) \wedge (\sim Q)$가 틀렸음을 진리표 **한 행**으로 보이려 한다. 어느 행을 고르고, 두 값은 각각 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown 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 존재의 반전 | 이 목록에 없다 | :::{container} quotebox **확인 7.** N5와 N6에 대응하는 항목이 이번 주 목록에 없는 이유는 무엇인가. 정의 3.2의 첫 줄을 근거로 한 줄 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 정의 3.2는 "값은 **성분 명제의 진리값만으로** 정해진다"고 못 박았다. 다섯 연산은 성분이 T인지 F인지만 알면 값이 나오므로 유한한 표로 전부 적을 수 있다. $\forall$와 $\exists$는 그렇지 않다 — 값을 정하려면 변수의 범위 전체를 훑어야 하고, 그 범위가 무한이면 훑는 일이 유한한 표에 들어가지 않는다. 그래서 N5$\cdot$N6은 진리표의 관할 밖이고, 양화사를 정식으로 편입하는 C4주차에서 다룬다. ::: ### 8 조건문의 세 변형 — 역·이·대우 [백지 암기 대상] :::{container} quotebox 조건문 $P \Rightarrow Q$에 대하여, **역**은 $Q \Rightarrow P$, **이**는 $(\sim P) \Rightarrow (\sim Q)$, **대우**는 $(\sim Q) \Rightarrow (\sim P)$이다. ::: 넷 사이의 관계는 두 쌍으로 갈린다. 원명제와 대우가 동치이고, 역과 이가 동치이며, 원명제와 역은 동치가 아니다. 진리표 완비는 예제 2.3에서 한다. :::{container} quotebox **확인 8.** 역과 이가 동치임을 진리표를 새로 그리지 않고 §1.7의 법칙 두 개로 설명해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 이 $(\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** | 변형의 각 줄 옆에 법칙 이름을 단다 | :::{container} quotebox **확인 9.** 어떤 유도에 다음 두 근거 표시가 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) "[드모르간 1]" (나) "괄호를 풀면 당연히" ::: :::{admonition} 답 :class: quotebox dropdown (가) 허용 — 근거 ④. 목록에 이름이 있는 항목이므로 그 이름만으로 줄의 근거가 된다. (나) 불허 — 목록 밖이다. "당연히"는 어떤 규칙을 적용했는지 지목하지 않으므로, §1.6의 삭제 실험대로 그 줄은 검사될 수 없다. 실제로 답안 Q가 부정 하나를 잃은 자리가 정확히 이런 줄이었다. ::: ### 10 원칙 3의 예외 구역 C1주차의 기호 사용 원칙 3은 "논리 자체를 논의하는 자리가 아니면 $\Rightarrow$, $\forall$, $\exists$, $\ni$ 를 본문에 쓰지 않는다"였다. 이번 주는 그 예외 구역이다 — 논리 연산과 동치 자체가 논의 대상이므로 기호를 본문에 정면으로 쓴다. 예외는 이번 주 본문에 한정된다. 이 논리를 도구로 **써서** 수학 명제를 증명하는 산문에서는 여전히 낱말로 적는다. 구분의 기준은 기호가 계산의 대상인가, 아니면 서술의 약호인가이다. :::{container} quotebox **확인 10.** 다음 두 문장 중 이번 주 본문에서 허용되는 것은 어느 쪽인가. 이유를 한 줄로 적는다. (가) "$P \Rightarrow Q$의 대우는 $(\sim Q) \Rightarrow (\sim P)$이다." (나) "$n$이 짝수 $\Rightarrow$ $n^2$이 짝수이다." ::: :::{admonition} 답 :class: quotebox dropdown (가)가 허용된다. $\Rightarrow$가 붙은 식 자체를 논의 대상으로 놓고 그 대우가 무엇인지 말하고 있으므로 원칙 3의 예외에 해당한다. (나)는 허용되지 않는다. 여기서 $\Rightarrow$는 논의 대상이 아니라 "이면"의 약호로 쓰였고, 이런 자리는 수학 명제를 서술하는 산문이므로 "$n$이 짝수이면 $n^2$도 짝수이다"로 적는다. C1주차 문제 17이 요구한 구분이 이것이다. :::