9주차 — 논리적 동치와 대우

내용

9주차 — 논리적 동치와 대우#

이 주의 길잡이

핵심 문장: 대우는 원명제와 같은 명제이고, 역은 다른 명제다.

이 주의 위치: 50주 과정의 9주차. 진리표(7~8주차)로 “같은 명제”의 판정 기준을 세우고, 19주차 대우 증명\(\cdot\)21주차 귀류법이 딛고 설 근거를 만든다.

원서 대응: BoP(Book of Proof) 2.5–2.6. 원서 없이 읽을 수 있다.

이번 주 목표#

논리적 동치(\(\equiv\))의 정의를 백지에 쓰고, 진리표로 동치와 비동치를 판정할 수 있다.
드모르간 법칙(논리 버전)과 \(P \Rightarrow Q \equiv \neg P \lor Q\)를 포함한 동치 목록 8개를 근거 ④로 쓸 수 있다.
대우(\(\neg Q \Rightarrow \neg P\))가 원명제와 동치이고 역(\(Q \Rightarrow P\))\(\cdot\)이(\(\neg P \Rightarrow \neg Q\))는 아님을 증명하고, 막힌 직접 증명을 대우로 갈아타 완성할 수 있다.
\(\neg(P \Rightarrow Q) \equiv P \land \neg Q\)로 “조건문이 거짓”의 정체와 반례의 두 조건을 설명할 수 있다.

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

준비 운동 (8주차 복습)#

\(P \Rightarrow Q\)의 진리표를 그리시오. 거짓이 되는 행은 몇 개인가.
“P only if Q”를 화살표로 번역하시오.
“\(x > 2\)는 \(x^2 > 4\)이기 위한 \(\underline{\quad}\)조건”을 판정하시오.
“정수 \(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단계 틀로 밀어붙여 보자.

시도 — 직접 증명으로 밀어붙이기

명제: 정수 \(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\)은 홀수이다”이다. 이 명제는 위 명제의 가정과 결론을 각각 부정하고 자리를 맞바꾼 꼴이다. 이것을 증명해 두었으니 원명제도 증명된 것이라고 선언해도 되는가.

확인 1. 그 선언이 허용되려면 두 명제 사이에 무엇이 보장되어야 하는가?

“두 명제가 모든 상황에서 \(\underline{\qquad}\)” 꼴로 한 구절 적어 보자.

답

“같은 진리값을 가진다.” 한쪽이 참인 상황에서는 다른 쪽도 반드시 참이고

거짓이면 같이 거짓이어야, 한쪽의 증명이 다른 쪽의 증명을 대신할 수 있다.

“그럴 것 같다”는 느낌으로는 갈아탈 수 없다 — 같은 진리값인지 아닌지를

느낌 없이 판정하는 기준이 필요하고, 그 기준이 이번 주의 정의다.

이 주 전체의 기준

증명을 다른 명제로 갈아타려면, 두 명제가 “같은 명제”임이 먼저 판정되어야 한다.

그 판정 기준이 논리적 동치이고, 판정 도구는 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}\)

확인 2. 빈칸 (1)~(4)를 채우고, 두 열을 행별로 대조해 보자.

일치하지 않는 행이 있는가?

답

(1) F (2) T (3) T (4) T. 네 행 전부에서 두 열이 일치한다.

\(P\)와 \(Q\) 자리에 어떤 명제를 넣어도 그 진리값 조합은 이 네 행 중 하나이고,

어느 행에서든 두 복합 명제의 값이 같다 — 즉 두 명제는 **모든 상황에서 같은

진리값**을 갖는다. 확인 1에서 필요하다고 했던 바로 그 보장이다.

“모든 진리값 조합에서 같은 값”이라는 이 관찰이 정의의 전부다.

이 관찰에 정식 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 확인한 “모든 행에서 일치”를 문장으로 굳혔을 뿐이다.

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

두 복합 명제가 구성 명제들의 모든 진리값 조합에서 같은 진리값을 가지면

두 명제는 논리적으로 동치라 하고, 기호 \(\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이므로.

확인 3. “모든”을 지우는 순간 정확히 무엇이 무너지는가?

(역과 원명제만의 문제인지, 임의의 두 명제 쌍은 어떤지 함께 생각해 보자.)

답

거의 모든 명제 쌍이 동치가 되어 버린다. 진리값이 겹치는 행이 하나라도 있으면

합격이므로, 모든 행에서 값이 정반대인 쌍(\(P\)와 \(\neg P\) 같은)을 빼면 전부

“같은 말”로 판정된다. 그러면 \(\equiv\)는 아무것도 구별하지 못하고,

§1.1에서 필요했던 “증명 갈아타기의 보증” 역할도 함께 무너진다 — 보증의

내용이 정확히 “모든 상황에서 같다”였기 때문이다. 정의의 조각 하나하나가

이런 붕괴를 막는 조건이다.

4 판정 절차 — 기계적으로#

정의 9.1을 절차로 옮기면 세 걸음이다.

등장하는 명제 변수를 확인한다 (\(n\)개 \(\to\) \(2^n\)행).
양쪽 명제의 진리표 열을 각각 계산한다 (중간 재료 열을 거쳐서).
두 열이 완전히 일치하면 \(\equiv\). 한 행이라도 다르면 동치가 아니다.

확인 4. 변수 3개짜리 판정(\(P \lor (Q \land R)\) 등이 등장하는)을 하려면

표의 행이 몇 개 필요한가. 왜 그런가.

답

\(2^3 = 8\)행. 변수마다 T\(\cdot\)F 두 가지가 서로 독립으로 조합되므로, 2를 변수

개수만큼 곱한 가짓수가 “모든 진리값 조합”이다. 변수 2개면 4행, 3개면 8행 —

이번 주 문제 9와 8주차 문제 16의 8행 표가 이 계산에서 나온 것이다.

확인 5. 목록에 오르기 전에 하나를 직접 판정해 보자.

\(\neg(\neg P) \equiv P\) (이중부정). 행은 몇 개이고, 각 행의 값은 무엇인가.

답

변수가 \(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\)의 자리만 바꾸고, 이는 자리를 두고 양쪽을 부정하고, 대우는 자리를 바꾸고 양쪽을 부정한다.

이름을 외우기 전에, 일상 명제로 각 변형의 진리값부터 가늠해 보자. 원명제: “서울에 살면 한국에 산다” (참).

대우: “한국에 살지 않으면 서울에 살지 않는다” — 참이다. 원명제와 같은

정보를 반대쪽에서 읽었을 뿐이다.

역: “한국에 살면 서울에 산다” — 거짓이다. 부산 거주자가 반례다.

원명제가 참인데 역은 거짓이다 — 둘은 별개의 명제다.

확인 6. 남은 변형인 이를 같은 예로 만들어 참\(\cdot\)거짓을 판정해 보자:

“서울에 살지 않으면 \(\underline{\qquad}\).”

답

“서울에 살지 않으면 한국에 살지 않는다” — 거짓이다. 부산 거주자는 서울에

살지 않지만 한국에 산다. 역을 무너뜨린 것과 같은 반례가 통했다 —

우연이 아니다. 역과 이는 서로가 서로의 대우라서 진리값이 항상 같다

(문제 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주차의 진리표에 이미 있다.

확인 7. 8주차의 진리표에서 \(P \Rightarrow Q\)가 거짓인 행은 몇 개인가.

그 행에서 \(P\)와 \(\neg Q\)의 진리값은 각각 무엇인가.

답

단 하나 — \(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\)”로 적는 경우가 많다. 원인은 부정을 “결론만 뒤집기”로 처리하는 습관이다 — 그러나 조건문 전체의 부정은 결론 수정이 아니라 조건 구조의 해체다. 점검 규칙은 간단하다: “이면”의 부정에 “이면”이 남아 있으면 그 자리에서 다시 본다.

확인 8. “\(x > 0\)이면 \(x^2 > 0\)이다”의 부정을 \(P \land \neg Q\) 꼴의

문장으로 적어 보자.

답

“\(x > 0\)인데 \(x^2 \le 0\)인 사례가 존재한다.” 부등호의 부정은 여집합

방향(\(>\) \(\leftrightarrow\) \(\le\))까지 정확해야 한다. 그런 실수 \(x\)는 없으므로 이 부정은

거짓이고, 곧 원명제는 참이다 — 부정을 정확히 적는 기술은 명제의 참\(\cdot\)거짓과

무관하게 작동하는 문법이다. 문제 6과 8에서 이 문법을 반복 훈련한다.