8주차 — 조건문과 필요·충분조건

내용

8주차 — 조건문과 필요·충분조건#

이 주의 길잡이

핵심 문장: \(P \Rightarrow Q\)가 거짓이 되는 경우는 단 하나 — \(P\)는 참인데 \(Q\)가 거짓일 때.

이 주의 위치: 50주 과정의 8주차. “이면”에 진리표를 부여하고, 진리집합으로 논리와 집합의 다리를 완성한다. 고1 명제 단원(필요조건\(\cdot\)충분조건\(\cdot\)진리집합)과 가장 직결되는 주다.

원서 대응: BoP(Book of Proof) 2.3 (Conditional Statements), 2.4 (Biconditional Statements) — 원서 없이 읽을 수 있다.

이번 주 목표#

\(P \Rightarrow Q\)의 진리표를 백지에 쓰고, F\(\Rightarrow\)무엇이든 = T로 정할 수밖에 없는 이유를 설명할 수 있다.
“이면 / only if / 충분조건 / 필요조건”을 화살표 기호로 정확히 번역할 수 있다.
진리집합으로 “\(P \Rightarrow Q\) 참”과 “\(P \subseteq Q\)”를 연결할 수 있다 (집합 \(\leftrightarrow\) 논리 다리의 완성).
\(P \iff Q\)(쌍조건문)가 화살표 두 개의 “그리고”임을 알고, 판정에 쓸 수 있다.

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

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

\(\land, \lor, \neg\)의 진리표를 백지에 그리시오.
\(P\): 참, \(Q\): 거짓일 때 \(\neg(P \land Q) \lor Q\)의 진리값은?
논리–집합 대응표(\(\land\)–\(\cap\), \(\lor\)–\(\cup\), \(\neg\)–\(^c\))를 쓰시오.
(이번 주의 진단) “모든 실수 \(x\)에 대해, \(x > 3\)이면 \(x^2 > 9\)이다”는 참인 명제로 보인다.

그런데 \(x = 1\)을 넣으면 가정(\(1 > 3\))도 결론(\(1 > 9\))도 거짓이다. 이 \(x = 1\)에서 “\(x > 3\)이면 \(x^2 > 9\)”의 진리값은 무엇이라고 해야 하는가? 답을 노트에 적어 둔다.

자주 나오는 세 가지 답 — 4번 문항#

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

유형 1 — “무관하다”. “\(x = 1\)은 가정에 해당하지 않으므로 무관하다”라고 적는다.

감각은 정확하다 — 가정 밖의 \(x\)가 명제를 흔들면 안 된다. 빠진 것은 처리다: 정의 7.1에 의해 명제는 참\(\cdot\)거짓 중 정확히 하나를 가져야 하므로 “무관”이라는 제3의 값은 허용되지 않는다. 이 감각을 둘 중 하나로 번역하는 것이 이번 주의 첫 임무다.

유형 2 — “판정 불능”. “가정이 성립하지 않으니 정할 수 없다”라고 적는다.

신중함은 옳다. 문제는 유형 1과 같다 — 진리값 미정인 문장은 명제가 아니게 되고, “모든 실수 \(x\)에 대해”라는 문장 전체의 진리값도 정할 수 없게 된다. 수학은 이 자리에 값을 정해 둔다. 무엇으로, 왜 그쪽인지를 §1.2에서 본다.

유형 3 — “거짓이다”. “가정이 안 맞으니 그 \(x\)에서는 거짓”이라고 적는다.

“성립하지 않는다 = 거짓”이라는 규칙을 적용한 것인데, 이 규칙을 채택하면 참이어야 마땅한 위 명제 자체가 \(x = 1\) 때문에 거짓이 된다. 무엇이 무너지는지를 §1.2와 문제 20에서 정확히 추적한다.

개념 — “이면”의 진리표#

1 일곱 주 동안 쓴 낱말, 아직 없는 규칙#

1주차부터 지금까지 “이면”을 계속 써 왔다 — “\(n\)이 짝수이면 \(n^2\)도 짝수”. 7주차에서 \(\land, \lor, \neg\)에 진리표를 부여했지만, 정작 가장 많이 쓴 “이면”의 진리표는 아직 없다. 있는 도구로 조립이 되는지부터 시도해 보자.

시도 — \(\land\)로 조립하기

\(P(n)\): “\(4 \mid n\)”, \(Q(n)\): “\(2 \mid n\)”으로 두고, “4의 배수이면 짝수이다”를

\(P \land Q\)로 적어 보자. \(n = 8\)에서는 \(P\) 참, \(Q\) 참으로 \(\land\)가 참 — 좋아

보인다. 그런데 \(n = 2\)를 넣으면 …

여기서 멈춘다.

확인 1. \(n = 2\)에서 \(P \land Q\)의 진리값은 무엇인가. 그 값은 “4의 배수이면

짝수이다”라는 문장에 대한 판정으로 적절한가?

답

\(P(2)\): “\(4 \mid 2\)”는 거짓, \(Q(2)\): “\(2 \mid 2\)”는 참 — \(\land\)는 거짓이다.

그러나 2는 4의 배수가 아니어서 이 문장이 2에 대해 약속한 것이 없으므로,

“4의 배수이면 짝수”가 \(n = 2\) 때문에 거짓이 될 수는 없다. \(\land\)는 “둘 다

참”의 주장이라 “이면”과 다르고, \(\lor\)도 \(n = 3\)(둘 다 거짓)에서 실패한다.

“이면”에는 자기만의 진리표가 필요하다.

필요한 것이 분명해졌다. 진리값 네 조합(TT, TF, FT, FF) 각각에서 “\(P\)이면 \(Q\)”의 진리값을 정하는 표다. TT와 TF 두 행은 직관이 바로 정해 준다 — 가정이 실현됐는데 결론이 나오면 참, 안 나오면 거짓. 문제는 준비 운동 4번에서 만난 F 행 둘이다.

2 깨졌는가, 안 깨졌는가 — 표를 채우며 F 행 정하기#

일상의 조건문 하나로 네 행을 전부 판정해 보자. 어떤 사람이 아이에게 말했다: “시험에 합격하면(\(P\)) 자전거를 사 주마(\(Q\)).” 네 상황 각각에 대해 “약속이 깨졌는가”를 채워 보자.

합격?	자전거?	약속은 깨졌는가
합격 (T)	사 줌 (T)	안 깨짐
합격 (T)	안 사 줌 (F)	\(\underline{\quad(1)\quad}\)
불합격 (F)	사 줌 (T)	\(\underline{\quad(2)\quad}\)
불합격 (F)	안 사 줌 (F)	\(\underline{\quad(3)\quad}\)

확인 2. 빈칸 (1)(2)(3)을 채우고, “깨짐”이 등장하는 행이 몇 개인지 세어 보자.

답

(1) 깨짐 — 합격했는데 자전거가 없다. 위반이 실제로 일어난 유일한 상황이다.

(2) 안 깨짐 — 약속에 없던 선물을 한 것일 뿐, 약속을 어긴 것은 아니다.

(3) 안 깨짐 — 불합격이면 약속이 요구하는 것이 없으므로 어길 방법 자체가 없다.

“깨짐”은 한 행뿐이다. 조건문은 “가정이 실현됐는데 결론이 안 나오는 일은

없다”는 보증이고, 가정이 실현되지 않으면 보증은 자동으로 유지된다.

수학 문장에서도 같은 판정이 강제된다. 준비 운동 4번의 명제 “모든 실수 \(x\)에 대해, \(x > 3 \Rightarrow x^2 > 9\)”에 몇 개의 \(x\)를 대입해 보면 —

\(x\)	\(x > 3\)	\(x^2 > 9\)	이 \(x\)에서의 행
\(4\)	T	T	T\(\Rightarrow\)T
\(1\)	F	F	F\(\Rightarrow\)F
\(-5\)	F	T	F\(\Rightarrow\)T

확인 3. 이 명제가 “모든 실수 \(x\)에 대해” 참이려면, F\(\Rightarrow\)F 행과

F\(\Rightarrow\)T 행의 진리값을 무엇으로 정할 수밖에 없는가?

답

둘 다 참으로 정할 수밖에 없다. 어느 한쪽이라도 거짓으로 정하면 \(x = 1\)이나

\(x = -5\)가 명제를 무너뜨린다(준비 운동 유형 3의 결말). 명제가 “참”이라는 것은

명제를 무너뜨리는 \(x\) — T\(\Rightarrow\)F 행이 되는 \(x\) — 가 하나도 없다는

뜻이고, 가정에 해당하지 않는 \(x\)들은 전부 자동으로 통과시켜야 한다.

이 판정에 정식 이름과 형식을 붙인다. 표 자체에 새로운 것은 없다 — 방금 두 표에서 내린 판정을 네 행으로 굳혔을 뿐이다.

정의 8.1 — 조건문 (conditional statement) [백지 암기 대상]#

명제 \(P, Q\)에 대해, 조건문 \(P \Rightarrow Q\)(“P이면 Q이다”, if P then Q)는

\(P\)가 참이고 \(Q\)가 거짓일 때만 거짓이고, 나머지 경우에는 참인 명제이다.

\(P\)를 가정(hypothesis), \(Q\)를 결론(conclusion)이라 한다.

\(P\)	\(Q\)	\(P \Rightarrow Q\)
T	T	T
T	F	F \(\leftarrow\) 유일한 거짓
F	T	T \(\leftarrow\) 공허한 참
F	F	T \(\leftarrow\) 공허한 참

기호 \(\Rightarrow\)는 “이면”, 전체는 “\(P\)이면 \(Q\)이다”로 읽는다. 가정이 거짓이어서 자동으로 참이 되는 아래 두 행의 참을 공허한 참(vacuously true)이라 부른다 — 보증할 내용이 비어 있어서 얻는 참이라는 뜻이다. 읽는 법까지가 정의다.

3 정의 해부 — 행마다 하는 일#

이 진리표는 네 행으로 되어 있고, 행마다 판정에서 맡는 역할이 다르다.

행(조각)	하는 일	판정에서의 역할
T\(\Rightarrow\)T = T	보증 이행의 확인	가정이 실현되고 결론이 나온 사례를 통과시킨다
T\(\Rightarrow\)F = F	보증 파기의 판정	조건문을 무너뜨리는 유일한 행 — 반례 탐색은 이 행만 찾는다
F\(\Rightarrow\)T = T	가정 밖 사례의 통과	가정에 해당하지 않는 대상이 명제를 훼방하지 못하게 막는다
F\(\Rightarrow\)F = T	가정 밖 사례의 통과	위와 같다 — “모든 \(x\)” 명제의 참을 지키는 안전판

행 변경 실험. 넷째 행 F\(\Rightarrow\)F를 F로 바꿔 보자. 그러면 “\(4 \mid x \Rightarrow 2 \mid x\)”가 \(x = 3\)(가정 거짓, 결론 거짓)에서 거짓이 된다.

확인 4. F\(\Rightarrow\)F를 F로 바꾸는 순간 정확히 무엇이 무너지는가?

(1주차의 “홀수이면 \(n^2\)이 홀수” 같은 명제들은 어떻게 되는지 함께 생각해 보자.)

답

가정과 결론이 동시에 거짓이 되는 대상이 하나라도 있는 “모든 \(x\)” 조건문이

전부 거짓이 된다. “\(n\)이 홀수이면 \(n^2\)이 홀수”는 \(n = 2\)(가정 거짓, 결론

거짓)에서, 추이성은 예컨대 \((a, b, c) = (2, 3, 5)\)(가정 거짓 — \(2 \nmid 3\),

결론 \(2 \mid 5\)도 거짓)에서 무너진다 — 1~2주차에 증명한 명제 상당수가 거짓이

되는 붕괴다. 진리표의 행 하나하나가 이 붕괴를 막는 조건이다.

(F\(\Rightarrow\)T 쪽은 확인 3의 \(x = -5\)가 같은 방식으로 강제했고, 문제 20에서

서술로 정리한다.)

공허한 참은 초면이 아니다. 4주차의 \(\emptyset \subseteq A\)를 조건문으로 다시 쓰면 “모든 \(x\)에 대해, \(x \in \emptyset \Rightarrow x \in A\)” — 가정이 항상 거짓이므로 전부 공허한 참이다. “어길 원소가 없어서 참”이라던 그 논리의 정체가 이 진리표의 아래 두 행이다(문제 18에서 완성한다).

진리표가 1주차의 첫 문장을 정당화한다. 1주차 예제 2.1의 증명은 “\(m\)과 \(n\)을 짝수라 하자”로 시작했다 — 짝수가 아닌 정수는 검토조차 하지 않았다.

확인 5. 조건문 “\(m, n\)이 짝수이면 \(m + n\)이 짝수”를 증명하면서 짝수가 아닌

\(m, n\)을 검토하지 않아도 되는 이유를, 진리표의 행으로 설명해 보자.

답

가정이 거짓인 대상들은 F 행이므로 자동으로 참이다(공허한 참). 거짓이 될

수 있는 행은 T\(\Rightarrow\)F뿐이므로, 증명이 할 일은 “가정이 참인 경우에

결론도 참”임을 보이는 것이 전부다. 그래서 조건문 증명의 첫 문장은 언제나

가정을 참이라 선언하고 시작한다 — 1주차부터 써 온 서식의 논리적 근거가 이

진리표다(증명 서식으로의 정식 승격은 15주차).

4 조건문의 여러 표현 — 같은 화살표, 다른 문장#

수학 문헌은 \(P \Rightarrow Q\)를 여러 문형으로 적는다. 다음은 전부 같은 명제다.

표현	예 (\(P\): \(n\)은 4의 배수, \(Q\): \(n\)은 짝수)
P이면 Q	4의 배수이면 짝수다
Q if P	\(n\) is even if \(n\) is a multiple of 4
P only if Q	4의 배수인 것은 오직 짝수일 때뿐
P는 Q이기 위한 충분조건	4의 배수임은 짝수이기 위한 충분조건
Q는 P이기 위한 필요조건	짝수임은 4의 배수이기 위한 필요조건
Q whenever P	whenever \(n\) is a multiple of 4, it is even

여섯 줄 중 두 곳에서 번역 사고가 집중적으로 일어난다. 하나씩 해부한다.

only if. “P only if Q”를 \(Q \Rightarrow P\)로 옮겨 적는 경우가 많다 — “if”가 보이니 if 규칙(if 뒤 = 가정)을 적용한 것인데, “only”가 규칙을 뒤집는다. “P only if Q” = “Q 없이 P 없다” = “P가 참인데 Q가 거짓일 수는 없다” — T\(\Rightarrow\)F의 금지이므로 정확히 \(P \Rightarrow Q\)다. if는 화살표가 들어오고, only if는 화살표가 나간다.

확인 6. “정수 \(n\)이 8의 배수인 것은 only if \(n\)이 4의 배수일 때다”를

화살표로 번역해 보자. 화살표는 어느 쪽을 향하는가?

답

(\(n\)은 8의 배수) \(\Rightarrow\) (\(n\)은 4의 배수). only if 뒤가 결론이다.

검산: \(8k = 4(2k)\)이므로 이 번역은 참인 명제다. 반대 번역은 \(n = 4\)가

무너뜨리는 거짓 명제 — 번역이 옳은 명제를 주는지 검산하는 습관이 사고를 막는다.

충분과 필요. \(P \Rightarrow Q\)가 참이라 하자. \(P\)를 확인하는 순간 \(Q\)는 따라 나온다 — \(P\)의 성립은 \(Q\)를 보장하기에 충분하다. 한편 \(Q\)가 거짓이면 T\(\Rightarrow\)F 금지에 의해 \(P\)도 참일 수 없다 — \(Q\)의 성립은 \(P\)이기 위해 필요하다. 두 용어가 화살표 하나에서 나온다.

암기 문장: 충분조건은 화살표의 꼬리, 필요조건은 화살표의 머리. (\(P \Rightarrow Q\): \(P\)가 충분, \(Q\)가 필요)

확인 7. “\(x > 5\)임은 \(x > 0\)이기 위한 \(\underline{\quad}\)조건이고,

\(x > 0\)임은 \(x > 5\)이기 위한 \(\underline{\quad}\)조건이다.” 두 빈칸을 채우고,

어느 방향 화살표가 참이어서 그런지 적어 보자.

답

충분 / 필요. 참인 화살표는 (\(x > 5\)) \(\Rightarrow\) (\(x > 0\)) 하나다 — \(x > 5\)는

꼬리이므로 충분조건, \(x > 0\)은 머리이므로 필요조건. 역방향은 \(x = 1\)(가정 참,

결론 거짓)이 무너뜨리는 거짓 명제다.

5 진리집합 — 논리와 집합의 다리 완성#

7주차에서 \(\land\)–\(\cap\), \(\lor\)–\(\cup\), \(\neg\)–\(^c\)의 대응을 세웠다. 화살표에 대응하는 집합 관계가 이 절의 주제다.

열린 문장 \(P(x)\)에 대해, \(P(x)\)를 참으로 만드는 원소 전체의 집합

\[ P = \{x \in U : P(x) \text{ 참}\} \]

을 \(P(x)\)의 진리집합(truth set)이라 한다. 문장과 그 진리집합을 같은 문자로 적는 것이 관례다.

구체 사례로 채워 보자. \(U = \mathbb{Z}\), \(P(x)\): “\(4 \mid x\)”, \(Q(x)\): “\(2 \mid x\)”.

\(x\)	\(P(x)\)	\(Q(x)\)	이 \(x\)에서 \(P(x) \Rightarrow Q(x)\)는
\(8\)	참	참	T\(\Rightarrow\)T = T
\(6\)	거짓	참	\(\underline{\quad(1)\quad}\)
\(3\)	거짓	거짓	\(\underline{\quad(2)\quad}\)

확인 8. 빈칸 (1)(2)를 채우고, 두 진리집합 \(P = \{x \in \mathbb{Z} : 4 \mid x\}\)와

\(Q = \{x \in \mathbb{Z} : 2 \mid x\}\)를 원소 나열로 적은 뒤 포함 관계를 판정해 보자.

답

(1) F\(\Rightarrow\)T = T (2) F\(\Rightarrow\)F = T.

\(P = \{\dots, -8, -4, 0, 4, 8, \dots\}\), \(Q\) = 짝수 전체. 4의 배수 \(4k\)는 전부

\(2(2k)\) 꼴이므로 \(P \subseteq Q\)이다. 그리고 어느 \(x\)에서도 T\(\Rightarrow\)F가

없었다 — 포함 관계와 “무너뜨리는 \(x\) 없음”이 함께 성립하고 있다. 우연인지

필연인지를 다음 확인에서 따진다.

확인 9. 다음 유도의 빈칸을 채워 보자.

“모든 \(x\)에 대해 \(P(x) \Rightarrow Q(x)\)”가 참 = T\(\Rightarrow\)F가 되는 \(x\)가

없다 = \(P(x)\)는 참인데 \(Q(x)\)는 \(\underline{\quad(1)\quad}\)인 \(x\)가 없다

= \(P\)의 원소 중 \(Q\) \(\underline{\quad(2)\quad}\)에 있는 것이 없다

= \(P\ \underline{\quad(3)\quad}\ Q\).

답

(1) 거짓 (2) 밖 (3) \(\subseteq\).

조건문의 참(유일한 거짓 행의 부재)과 부분집합의 정의가 **같은 문장의 두

표기**임이 확인됐다. 고1 때 “충분조건 \(\subseteq\) 필요조건”으로 외운 규칙이

이것이다 — 이제는 외울 필요가 없다. 정의 두 개를 붙이면 저절로 나온다.

방금 유도한 것을 못 박아 둔다.

백지 암기 대상

진리집합의 다리

\[ \text{"모든 } x \text{에 대해 } P(x) \Rightarrow Q(x)\text{"가 참} \iff P \subseteq Q \]

좌변은 논리의 문장, 우변은 집합의 문장이다. 조건 판정 문제는 이 다리로

집합의 포함 판정 문제가 된다.

6 쌍조건문 — 화살표 두 개의 “그리고”#

양방향이 모두 참인 경우가 있다 — 확인 7의 사례와 달리 “\(x = 3\)”과 “\(3x = 9\)”는 서로가 서로를 함의한다. 이 관계에 이름을 붙인다.

정의 8.2 — 쌍조건문 (biconditional) [백지 암기 대상]#

\(P \iff Q\)(“P일 필요충분조건은 Q”, P if and only if Q)는

\((P \Rightarrow Q) \land (Q \Rightarrow P)\)의 축약이다.

\(P\)	\(Q\)	\(P \iff Q\)
T	T	T
T	F	F
F	T	F
F	F	T

기호 \(\iff\)는 “필요충분” 또는 “동치”로 읽고, 영어 문헌은 iff로 줄여 쓴다. 이 진리표를 \(\land\) 식에서 유도하는 작업은 문제 4에서 직접 한다.

확인 10. 위 표에서 \(P \iff Q\)가 참인 두 행의 공통점은 무엇인가.

그리고 진리집합의 다리(§1.5)를 양방향에 적용하면, “\(P \iff Q\)가 모든 \(x\)에서

참”은 진리집합 \(P\)와 \(Q\)의 어떤 관계로 번역되는가?

답

참인 행은 TT와 FF — \(P\)와 \(Q\)의 진리값이 같은 행이다. 양방향에 다리를

놓으면 \(P \subseteq Q\)와 \(Q \subseteq P\)가 동시에 성립하는 것 — 서로가 서로의

부분집합이면 상등이므로(5주차의 상등 판정) \(P = Q\)다. 필요충분 = 진리집합의 상등.

7 근거 목록 갱신 — 판정 규칙이 늘었다#

근거 ①~④(①정의 ②닫힘성 ③등식의 성질 ④이미 증명한 명제)는 증명에서 쓸 수 있는 것의 전체 목록이다. 이번 주의 갱신은 다음과 같다.

근거	이번 주의 갱신
① 정의	정의 8.1(조건문), 8.2(쌍조건문), 진리집합이 추가된다
② 닫힘성	변화 없음
③ 등식의 성질	변화 없음
④ 이미 증명한 명제	진리표로 확정한 사실들이 이후 주차의 부품이 된다 — \(P \Rightarrow Q\)와 \(\neg P \lor Q\)의 일치(문제 15)는 9주차 부정 계산의 재료다

칸의 개수는 늘지 않는다. 실제로 늘어난 것은 목록 밖의 기반 — 명제의 참\(\cdot\)거짓을 계산하는 규칙(진리표)이다.

확인 11. 어떤 판정 답안에 다음 두 근거 문장이 나왔다. 각각 허용되는가?

(가) “가정이 거짓이므로 이 행은 공허한 참이다”

(나) “가정이 성립 안 하니 말이 안 되는 문장이고, 따라서 거짓이다”

답

(가) 허용 — 정의 8.1의 F 행(근거 ①)을 정확히 인용했다.

(나) 불허 — 정의 8.1에 없는 규칙이다. 준비 운동 유형 3의 규칙이고, 확인 4에서

본 대로 채택하는 순간 1~2주차의 명제 전부가 무너진다. 판정의 근거는 느낌이

아니라 진리표의 행이다.