# 9주차 — 논리적 동치와 대우 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 대우는 원명제와 같은 명제이고, 역은 다른 명제다. **이 주의 위치**: 50주 과정의 9주차. 진리표(7~8주차)로 "같은 명제"의 판정 기준을 세우고, 19주차 대우 증명$\cdot$21주차 귀류법이 딛고 설 근거를 만든다. **원서 대응**: BoP(Book of Proof) 2.5–2.6. 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. 논리적 동치($\equiv$)의 **정의**를 백지에 쓰고, 진리표로 동치와 비동치를 판정할 수 있다. 1. 드모르간 법칙(논리 버전)과 $P \Rightarrow Q \equiv \neg P \lor Q$를 포함한 동치 목록 8개를 근거 ④로 쓸 수 있다. 1. 대우($\neg Q \Rightarrow \neg P$)가 원명제와 동치이고 역($Q \Rightarrow P$)$\cdot$이($\neg P \Rightarrow \neg Q$)는 아님을 증명하고, 막힌 직접 증명을 대우로 갈아타 완성할 수 있다. 1. $\neg(P \Rightarrow Q) \equiv P \land \neg Q$로 "조건문이 거짓"의 정체와 반례의 두 조건을 설명할 수 있다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (8주차 복습) 1. $P \Rightarrow Q$의 진리표를 그리시오. 거짓이 되는 행은 몇 개인가. 1. "P only if Q"를 화살표로 번역하시오. 1. "$x > 2$는 $x^2 > 4$이기 위한 $\underline{\quad}$조건"을 판정하시오. 1. "정수 $n$에 대해, $n^2$이 짝수이면 $n$은 짝수이다"를 증명해 보자. (지금 아는 방식 그대로, 몇 줄이든. 끝까지 가지 못해도 어디서 멈췄는지를 적어 둔다.) ### 자주 나오는 세 가지 답 — 4번 문항 방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — 직접 증명 시도 후 정지.** "$n^2$이 짝수라 가정하자. $n^2 = 2k$인 정수 $k$가 존재한다"까지 적고 멈춘다. 여기까지는 규정 그대로다 — 가정을 선언하고 정의를 풀었다. 문제는 $n^2 = 2k$에서 $n$의 등식을 만들 도구가 없다는 것이다. 제곱근을 씌우는 순간 계산이 정수 세계를 벗어난다. 이 막힘의 우회로를 여는 것이 이번 주의 대우다. - **유형 2 — 역을 증명.** "$n$이 짝수이면 $n^2$도 짝수"(1주차 문제 9)를 증명하고 끝낸다. 그 증명 자체는 완결이다. 문제는 증명한 것이 원명제가 아니라 화살표가 뒤집힌 **역**이라는 점이다. 역의 증명이 원명제를 보장하는지 — 이번 주에 진리표로 판정하고, 답은 "보장하지 않는다"로 나온다(예제 2.2). - **유형 3 — 예시 확인.** $2^2 = 4$, $4^2 = 16$, $6^2 = 36$ 같은 사례 몇 개를 확인하고 "그러니까 성립한다"고 적는다. 확인한 사례에 대해서는 옳다. 남은 간격은 1주차 준비 운동의 유형 1과 같다 — 확인하지 않은 무한히 많은 $n$은 무엇이 보장하는가. 이번 주 끝에서 이 명제는 사례 확인 없이, 새 계산조차 없이 증명된다(예제 2.3). ## 개념 — 같은 명제, 다른 명제 ### 1 이미 증명한 것으로 갈아탈 수 있는가 — 막히는 자리 준비 운동 4번의 막힘을 실제로 재현해 본다. 1주차의 3단계 틀로 밀어붙여 보자. :::{admonition} 시도 — 직접 증명으로 밀어붙이기 :class: quotebox 명제: 정수 $n$에 대해, $n^2$이 짝수이면 $n$은 짝수이다. "$n^2$이 짝수라 가정하자. 정의에 의해 $n^2 = 2k$인 정수 $k$가 존재한다. 목표는 $n = 2 \times (\text{정수})$ 꼴인데, $n^2 = 2k$에서 $n$을 꺼내려면 … " ::: 여기서 멈춘다. 3단계 틀은 가정의 등식을 변형해 목표 꼴을 만드는 절차인데, $n^2 = 2k$에서 $n$의 등식을 얻는 유일한 길은 제곱근이고, $\sqrt{2k}$가 정수라는 보장은 어디에도 없다 — 계산이 정수 세계를 떠난다. 1주차 문제 11의 해설 끝에서 예고한 것과 같은 종류의 막힘이다 — 그곳의 예고는 홀수 버전 ("$n^2$이 홀수이면 $n$도 홀수")이었고, 제곱의 등식에서 $n$을 꺼낼 수 없다는 막힘의 구조는 지금과 같다. 그런데 손에 이미 있는 것이 하나 있다. 1주차 문제 11에서 증명한 "**$n$이 홀수이면 $n^2$은 홀수이다**"이다. 이 명제는 위 명제의 가정과 결론을 각각 부정하고 자리를 맞바꾼 꼴이다. 이것을 증명해 두었으니 원명제도 증명된 것이라고 선언해도 되는가. :::{container} quotebox **확인 1.** 그 선언이 허용되려면 두 명제 사이에 무엇이 보장되어야 하는가? "두 명제가 모든 상황에서 $\underline{\qquad}$" 꼴로 한 구절 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown "같은 진리값을 가진다." 한쪽이 참인 상황에서는 다른 쪽도 반드시 참이고 거짓이면 같이 거짓이어야, 한쪽의 증명이 다른 쪽의 증명을 대신할 수 있다. "그럴 것 같다"는 느낌으로는 갈아탈 수 없다 — 같은 진리값인지 아닌지를 느낌 없이 판정하는 기준이 필요하고, 그 기준이 이번 주의 정의다. ::: :::{admonition} 이 주 전체의 기준 :class: quotebox 증명을 다른 명제로 갈아타려면, 두 명제가 "같은 명제"임이 먼저 판정되어야 한다. 그 판정 기준이 **논리적 동치**이고, 판정 도구는 7~8주차에 만들어 둔 진리표다. ::: ### 2 "같은 말"을 표로 — 정의를 만들어 보기 판정 기준의 재료는 이미 두 번 마주쳤다. 7주차 예제 2.2에서 $\neg(P \land Q)$의 진리표 열을 계산했고, 7주차 문제 4에서 $\neg P \lor \neg Q$의 열을 계산해 둘을 비교했다. 그 표를 다시 채워 보자. | **$P$** | **$Q$** | **$\neg(P \land Q)$** | **$\neg P \lor \neg Q$** | |---|---|---|---| | T | T | F | $\underline{\quad(1)\quad}$ | | T | F | T | $\underline{\quad(2)\quad}$ | | F | T | T | $\underline{\quad(3)\quad}$ | | F | F | T | $\underline{\quad(4)\quad}$ | :::{container} quotebox **확인 2.** 빈칸 (1)~(4)를 채우고, 두 열을 행별로 대조해 보자. 일치하지 않는 행이 있는가? ::: :::{admonition} 답 :class: quotebox dropdown (1) F (2) T (3) T (4) T. 네 행 전부에서 두 열이 일치한다. $P$와 $Q$ 자리에 어떤 명제를 넣어도 그 진리값 조합은 이 네 행 중 하나이고, 어느 행에서든 두 복합 명제의 값이 같다 — 즉 두 명제는 **모든 상황에서 같은 진리값**을 갖는다. 확인 1에서 필요하다고 했던 바로 그 보장이다. "모든 진리값 조합에서 같은 값"이라는 이 관찰이 정의의 전부다. ::: 이 관찰에 정식 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 확인한 "모든 행에서 일치"를 문장으로 굳혔을 뿐이다. ### 정의 9.1 — 논리적 동치 (logical equivalence) [백지 암기 대상] :::{container} quotebox 두 복합 명제가 구성 명제들의 **모든 진리값 조합에서 같은 진리값**을 가지면 두 명제는 **논리적으로 동치**라 하고, 기호 $\equiv$로 쓴다. ::: 기호 $P \equiv Q$는 "$P$와 $Q$는 동치이다"로 읽는다. 등호(=)가 아니라 가로줄 세 개다 — 수의 같음이 아니라 **명제의 같음**을 나타내는 별도의 기호다. 읽는 법까지가 정의다. 방금 표로 확인한 것을 이 기호로 적으면 $\neg(P \land Q) \equiv \neg P \lor \neg Q$가 된다. ### 3 정의 해부 — 조각마다 하는 일 이 한 문장은 네 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다. | **조각** | **하는 일** | **판정에서의 역할** | |---|---|---| | "두 복합 명제가" | 판정 대상의 선언 | 동치는 명제 **두 개 사이의 관계**다 — 명제 하나의 성질이 아니다 | | "구성 명제들의 모든 진리값 조합에서" | 검사 범위의 지정 | 변수 $n$개면 $2^n$행 전부 — 한 행도 빼놓지 않는다 | | "같은 진리값을 가지면" | 합격 기준 | 행마다 두 열을 대조한다 — 전 행 일치만 합격이다 | | "$\equiv$로 쓴다" | 기호의 약속 | 판정 결과를 기호 하나로 기록한다 | **조각 삭제 실험.** 둘째 조각의 "모든"을 지워 보자. "어떤 진리값 조합에서 같은 진리값을 가지면 동치"가 된다. 그러면 $P \Rightarrow Q$와 $Q \Rightarrow P$도 동치가 된다 — 첫 행($P$ = T, $Q$ = T)에서 둘 다 T이므로. :::{container} quotebox **확인 3.** "모든"을 지우는 순간 정확히 무엇이 무너지는가? (역과 원명제만의 문제인지, 임의의 두 명제 쌍은 어떤지 함께 생각해 보자.) ::: :::{admonition} 답 :class: quotebox dropdown 거의 모든 명제 쌍이 동치가 되어 버린다. 진리값이 겹치는 행이 하나라도 있으면 합격이므로, 모든 행에서 값이 정반대인 쌍($P$와 $\neg P$ 같은)을 빼면 전부 "같은 말"로 판정된다. 그러면 $\equiv$는 아무것도 **구별하지 못하고**, §1.1에서 필요했던 "증명 갈아타기의 보증" 역할도 함께 무너진다 — 보증의 내용이 정확히 "**모든** 상황에서 같다"였기 때문이다. 정의의 조각 하나하나가 이런 붕괴를 막는 조건이다. ::: ### 4 판정 절차 — 기계적으로 정의 9.1을 절차로 옮기면 세 걸음이다. 1. 등장하는 명제 변수를 확인한다 ($n$개 $\to$ $2^n$행). 1. 양쪽 명제의 진리표 열을 각각 계산한다 (중간 재료 열을 거쳐서). 1. 두 열이 완전히 일치하면 $\equiv$. 한 행이라도 다르면 동치가 아니다. :::{container} quotebox **확인 4.** 변수 3개짜리 판정($P \lor (Q \land R)$ 등이 등장하는)을 하려면 표의 행이 몇 개 필요한가. 왜 그런가. ::: :::{admonition} 답 :class: quotebox dropdown $2^3 = 8$행. 변수마다 T$\cdot$F 두 가지가 서로 독립으로 조합되므로, 2를 변수 개수만큼 곱한 가짓수가 "모든 진리값 조합"이다. 변수 2개면 4행, 3개면 8행 — 이번 주 문제 9와 8주차 문제 16의 8행 표가 이 계산에서 나온 것이다. ::: :::{container} quotebox **확인 5.** 목록에 오르기 전에 하나를 직접 판정해 보자. $\neg(\neg P) \equiv P$ (이중부정). 행은 몇 개이고, 각 행의 값은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown 변수가 $P$ 하나이므로 $2^1 = 2$행. $P$ = T이면 $\neg P$ = F, $\neg(\neg P)$ = T. $P$ = F이면 $\neg P$ = T, $\neg(\neg P)$ = F. 두 행 모두에서 $\neg(\neg P)$ 열과 $P$ 열이 일치하므로 동치다. 판정 절차가 2행짜리 표에서도 8행짜리 표에서도 같은 세 걸음으로 작동한다. ::: ### 5 근거 목록 갱신 — ④ 칸에 동치 법칙이 들어온다 1주차 §1.6에서 세운 근거 목록의 칸은 그대로 네 개다. 이번 주에 ① 칸에 정의 9.1이 추가되고, ④ 칸에 새 종류의 부품 — **진리표로 증명한 동치** — 이 들어오기 시작한다. | **근거** | **내용** | **이번 주에는 이렇게 쓴다** | |---|---|---| | ① 정의 | 지난 주까지의 정의 + **정의 9.1** | "동치" $\leftrightarrow$ "모든 행에서 진리값 일치" 사이를 번역한다 | | ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | 이번 주의 증명 문제(문제 11)에서 1주차 그대로 쓴다 | | ③ 등식의 성질 | 대입 / 전개 / 묶기 | 문제 11의 대우 증명에서 1주차 그대로 쓴다 | | ④ 이미 증명한 명제 | 1~8주차의 문제들 + **진리표로 증명한 동치 법칙** | 명제를 동치인 명제로 **교체**한다 — "드모르간에 의해" | 동치가 근거 ④가 되는 이유는 정의 그대로다. 동치인 두 명제는 모든 상황에서 같은 진리값을 가지므로, 증명의 어느 자리에서든 한쪽을 다른 쪽으로 바꿔도 참$\cdot$거짓이 변하지 않는다. 막힌 명제를 같은 명제의 다루기 쉬운 꼴로 바꿔 타는 것 — 이것이 대우 증명(19주차)과 귀류법(21주차)이 하는 일의 전부이고, 그 허가의 출처가 이번 주의 판정이다. ### 6 꼭 알아야 할 동치 목록 [백지 암기 대상] 이번 주 이후 계속 쓸 동치 여덟 개를 목록으로 못 박는다. | **이름** | **동치식** | |---|---| | 이중부정 | $\neg(\neg P) \equiv P$ | | 드모르간 1 | $\neg(P \land Q) \equiv \neg P \lor \neg Q$ | | 드모르간 2 | $\neg(P \lor Q) \equiv \neg P \land \neg Q$ | | 조건문 분해 | $P \Rightarrow Q \equiv \neg P \lor Q$ | | **대우 (contrapositive)** | $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$ | | 조건문의 부정 | $\neg(P \Rightarrow Q) \equiv P \land \neg Q$ | | 분배 1 | $P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$ | | 분배 2 | $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$ | 목록의 각 줄은 선언이 아니라 **증명 대상**이다. 증명되는 순간 근거 ④에 등록된다. 진행 상황을 정리하면 — 이중부정은 확인 5에서, 드모르간 1은 §1.2(정식 표는 문제 1)에서, 조건문 분해는 8주차 문제 15에서 이미 증명됐다. 대우는 예제 2.1, 조건문의 부정은 문제 7, 드모르간 2는 훈련 1에서 처리된다. 분배 두 개는 확인 4의 요령대로 **각자 8행 표를 만들어 검증한다** — 변수가 $P, Q, R$ 세 개이므로 행은 $2^3 = 8$개이고, 좌변 열과 우변 열이 모든 행에서 일치함을 확인하는 순간 등록이다. 검증을 마치기 전까지 분배 두 개는 근거 ④가 아니다 (§5의 체크리스트에 이 검증이 들어 있다). 드모르간 두 개를 말로 요약하면 — **부정이 괄호를 뚫고 들어가면 $\land$와 $\lor$가 서로 뒤집힌다.** 5주차에서 벤 다이어그램으로 관찰만 해 두었던 $(A \cup B)^c = A^c \cap B^c$가 이 법칙의 집합 버전이다 — 그 연결은 문제 8(d)에서 논리 계산으로 직접 확인한다. ### 7 역, 이, 대우 [백지 암기 대상] 원명제 $P \Rightarrow Q$에서 세 가지 변형을 기계적으로 만들 수 있다. **역**은 $P$와 $Q$의 자리만 바꾸고, **이**는 자리를 두고 양쪽을 부정하고, **대우**는 자리를 바꾸고 양쪽을 부정한다. 이름을 외우기 전에, 일상 명제로 각 변형의 진리값부터 가늠해 보자. 원명제: "서울에 살면 한국에 산다" (참). - **대우**: "한국에 살지 않으면 서울에 살지 않는다" — 참이다. 원명제와 같은 정보를 반대쪽에서 읽었을 뿐이다. - **역**: "한국에 살면 서울에 산다" — 거짓이다. 부산 거주자가 반례다. 원명제가 참인데 역은 거짓이다 — 둘은 별개의 명제다. :::{container} quotebox **확인 6.** 남은 변형인 **이**를 같은 예로 만들어 참$\cdot$거짓을 판정해 보자: "서울에 살지 않으면 $\underline{\qquad}$." ::: :::{admonition} 답 :class: quotebox dropdown "서울에 살지 않으면 한국에 살지 않는다" — 거짓이다. 부산 거주자는 서울에 살지 않지만 한국에 산다. 역을 무너뜨린 것과 **같은 반례**가 통했다 — 우연이 아니다. 역과 이는 서로가 서로의 대우라서 진리값이 항상 같다 (문제 12에서 재확인한다). 그래서 원명제와 동치가 아닌 것도 함께다. ::: 관찰을 표로 굳힌다. "동치?" 열의 세 판정이 이번 주의 증명 대상이다. | **이름** | **식** | **원명제와 동치?** | |---|---|---| | 역 (converse) | $Q \Rightarrow P$ | **아니오** (예제 2.2에서 증명) | | 이 (inverse) | $\neg P \Rightarrow \neg Q$ | **아니오** (문제 13에서 증명) | | 대우 (contrapositive) | $\neg Q \Rightarrow \neg P$ | **예** — $\equiv$ (예제 2.1에서 증명) | **자주 하는 판정.** 참인 명제의 역을 검증 없이 참으로 취급하는 경우가 많다 (affirming the converse, 역 긍정의 오류 — 문제 10). 원인은 일상 언어의 습관이다 — "밥 먹으면 나갈게" 같은 일상의 "~이면"은 종종 양방향 약속으로 쓰이고, 그 습관이 수학의 한 방향 화살표에 과잉 적용된 것이다. 8주차 문제 8에서 역이 거짓인 사례($2 \mid n$이지만 $8 \nmid n$)를 이미 확인했다. 규칙으로 삼을 것은 하나다 — 참인 명제의 역은 검증 전까지 진리값 미정의 **별개 명제**로 둔다. ### 8 조건문의 부정 — 거짓의 정체 목록의 여섯째 줄을 만들 차례다. 재료는 8주차의 진리표에 이미 있다. :::{container} quotebox **확인 7.** 8주차의 진리표에서 $P \Rightarrow Q$가 거짓인 행은 몇 개인가. 그 행에서 $P$와 $\neg Q$의 진리값은 각각 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown 단 하나 — $P$ = T, $Q$ = F인 행이다. 그 행에서 $P$ = T이고 $\neg Q$ = T 이므로 $P \land \neg Q$가 참이다. 거꾸로 나머지 세 행에서는 $P$가 거짓이거나 $\neg Q$가 거짓이라 $P \land \neg Q$도 거짓이다. "조건문이 거짓"인 행과 "$P \land \neg Q$가 참"인 행이 정확히 일치한다 — 이 관찰이 아래 동치의 내용 전부이고, 표 전체의 대조는 문제 7에서 완성한다. ::: $$ \neg(P \Rightarrow Q) \equiv P \land \neg Q $$ "P이면 Q"가 거짓이라는 것은 "P**인데** Q가 아닌 사례가 존재한다"는 것이다. 조건문의 부정은 조건문이 아니라 **"그리고" 문장**이다. (변수가 든 명제에서 "모든 …에 대해"와 그 부정 "사례가 존재한다"의 정확한 문법은 10주차 양화사에서 만든다 — 지금은 이 읽기를 인정하고 쓴다.) - "$n$이 소수이면 $n$은 홀수이다"의 부정 $\to$ "$n$이 소수**인데** 홀수가 아닌 경우가 있다". 실제로 $n = 2$가 그런 경우이므로 원명제는 거짓이다. - **반례**(counterexample)란 정확히 $P \land \neg Q$를 만족하는 대상이다. 1주차 문제 18부터 써 온 반례가 논리적 정의를 얻는 자리다 — 문제 20에서 두 조건을 명시적으로 분리한다. **자주 나오는 오답.** $\neg(P \Rightarrow Q)$를 "$P \Rightarrow \neg Q$"로 적는 경우가 많다. 원인은 부정을 "결론만 뒤집기"로 처리하는 습관이다 — 그러나 조건문 전체의 부정은 결론 수정이 아니라 조건 구조의 해체다. 점검 규칙은 간단하다: "이면"의 부정에 "이면"이 남아 있으면 그 자리에서 다시 본다. :::{container} quotebox **확인 8.** "$x > 0$이면 $x^2 > 0$이다"의 부정을 $P \land \neg Q$ 꼴의 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown "$x > 0$**인데** $x^2 \le 0$인 사례가 존재한다." 부등호의 부정은 여집합 방향($>$ $\leftrightarrow$ $\le$)까지 정확해야 한다. 그런 실수 $x$는 없으므로 이 부정은 거짓이고, 곧 원명제는 참이다 — 부정을 정확히 적는 기술은 명제의 참$\cdot$거짓과 무관하게 작동하는 문법이다. 문제 6과 8에서 이 문법을 반복 훈련한다. :::