# 7주차 — 명제와 논리 연산 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 명제의 자격은 참이 아니라, 진리값이 정확히 하나로 정해진다는 것이다. **이 주의 위치**: 50주 과정의 7주차. 2부(논리)의 첫 주 — 1부의 집합 정의문 안에서 말로 쓰던 "그리고 / 또는 / 아니다"를 정식 연산으로 만들고, 진리표라는 판정 도구를 얻는다. 고1 '명제' 단원의 재건축이 여기서 시작된다. **원서 대응**: BoP(Book of Proof) 2.1–2.2 — 병행자 참고용. 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. 명제(statement)와 명제가 아닌 것을 정의로 판별하고, 거짓인 문장도 명제인 이유를 설명할 수 있다. 1. $\land$(그리고), $\lor$(또는), $\neg$(부정)의 진리표를 백지에 쓰고, 복합 명제의 진리표를 절차대로 작성할 수 있다. 1. 변수가 들어 있는 문장(열린 문장)이 왜 명제가 아닌지, 어떻게 명제로 만드는지 안다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (6주차 복습) 1. $A \times B$의 정의를 쓰시오. 1. $A_i = \{i, 2i\}$ ($i = 1, 2, 3$)일 때 $\bigcup_{i=1}^3 A_i$를 나열하시오. 1. 6주차 모의시험에서 틀린 문제 1개를 백지에 다시 푸시오. 1. (진단) 다음 두 문장이 "명제"인지 판단하고, 이유를 한 문장씩 쓰시오. (가) $2 + 3 = 6$ (나) $x + 2 = 5$ 1~3번은 1부의 마감 점검이다. 4번은 이번 주의 진단 문제다 — 답을 적어 두고, §1을 마친 뒤 같은 물음에 다시 답해 본다. ### 자주 나오는 세 가지 답 — 4번 문항 방금 쓴 4번의 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — "(가)는 틀린 문장이므로 명제가 아니다."** $2 + 3 \neq 6$이라는 계산은 옳다. 간격은 자격 기준에 있다 — 명제의 자격은 참이 아니라 **진리값의 확정**이고, "거짓으로 확정"도 확정이다. 거짓인 문장을 내쫓으면 무엇이 무너지는지는 문제 20에서 다룬다. - **유형 2 — "(나)는 $x = 3$이면 참이므로 명제다."** 대입하면 참이라는 계산은 옳다. 간격은 "값에 따라 진리값이 바뀐다"는 사실의 처리다 — 참이 되기도 거짓이 되기도 하는 문장은 진리값이 **하나로** 정해지지 않았으므로 아직 명제가 아니다. 정식 이름(열린 문장)과 명제로 만드는 방법을 §1.4에서 세운다. - **유형 3 — 판단 기준이 없어 감으로 답했다.** 지금까지 "명제"의 정의를 세운 적이 없기 때문이다. 이번 주의 첫 일이 그 기준(정의 7.1)을 세우는 것이고, 기준이 생기면 판별은 기계적 절차가 된다. ## 개념 — 명제와 논리 연산 ### 1 일상어로 판정을 시도하면 어디서 막히는가 1부 내내 집합 연산의 정의문 안에는 일상어 접속사가 살고 있었다: $A \cup B = \{x : x \in A \ \text{또는} \ x \in B\}$. 이 "또는"을 일상어 그대로 두고 판정을 밀어붙여 보자. :::{admonition} 시도 — 일상어 독법으로 밀어붙이기 :class: quotebox $A = \{x \in \mathbb{Z} : 2 \mid x\}$, $B = \{x \in \mathbb{Z} : 3 \mid x\}$일 때, $6 \in A \cup B$인가? "6은 2의 배수 **또는** 3의 배수인가 — 그런데 6은 둘 **다**이다. 식당에서 '커피 또는 차'는 하나만 고르라는 뜻이었다. 그 독법이면 6은 탈락이고, '적어도 하나'라는 독법이면 6은 통과다. 따라서 $6 \in A \cup B$는 … " ::: 여기서 멈춘다. 읽는 사람마다 판정이 갈리는 문장으로는 수학을 쌓을 수 없다 — 증명이란 누구나 같은 결론에 도달하도록 검사 가능한 판정을 이어 붙이는 일이기 때문이다. 5주차 확인 4에서는 이 갈림에서 "둘 다여도 참" 쪽을 못 박는 선택만 해 두고, 그 이유의 정면 취급은 이번 주로 미뤄 두었다. 이번 주는 그 미룬 일을 맡아 접속사 자체를 **판정 규칙**으로 정의한다. 그 전에 먼저 정할 것이 있다 — 판정의 **대상**이 될 자격이다. "수학은 아름답다" 같은 문장은 어떤 독법을 정해도 참$\cdot$거짓 판정이 시작되지 않는다. :::{container} quotebox **확인 1.** 위 시도가 멈춘 원인과, "수학은 아름답다"가 판정되지 않는 원인은 서로 다르다. 각각 한 구절로 지목해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 시도가 멈춘 원인: "또는"의 **판정 규칙**이 정해져 있지 않다 — 독법이 둘이라 판정이 갈린다. "수학은 아름답다"의 원인: 규칙 이전에 **판정 대상의 자격**이 없다 — 객관적 참$\cdot$거짓이 애초에 없는 문장이다. 그래서 이번 주의 일은 두 가지다. ① 판정 대상의 자격을 정의한다(§1.2, 명제) ② 접속사의 판정 규칙을 정의한다(§1.5, 논리 연산). ::: ### 2 판별 표를 채워 보기 — 자격의 기준 찾기 문장 여러 개를 놓고 "참$\cdot$거짓 중 하나로 판정이 확정되는가"만 심사해 보자. | **문장** | **진리값이 정확히 하나로 확정되는가** | |---|---| | $2 + 3 = 5$ | 확정된다 — 참 | | $2 + 3 = 6$ | $\underline{\quad(1)\quad}$ | | $\pi \in \mathbb{Q}$ | 확정된다 — 거짓 ($\pi$가 무리수임은 알려져 있다) | | 창문을 닫아라. | $\underline{\quad(2)\quad}$ | | $x + 2 = 5$ | $\underline{\quad(3)\quad}$ | | 수학은 아름답다. | 확정되지 않는다 — 객관적 판정 기준이 없다 | :::{container} quotebox **확인 2.** 빈칸 (1)(2)(3)을 채우고, "확정된다" 판정을 받은 문장들의 공통점을 한 문장으로 적어 보자. 참인 문장만 통과했는가? ::: :::{admonition} 답 :class: quotebox dropdown (1) 확정된다 — **거짓**. 계산이 틀린 문장이지만, "거짓"이라는 판정 하나로 확정된다는 점에서는 $2+3=5$와 같은 자격이다. (2) 확정되지 않는다 — 명령문에는 참$\cdot$거짓을 물을 수 없다. (3) 확정되지 않는다 — $x = 3$이면 참, $x = 1$이면 거짓으로 값에 따라 오락가락한다. 공통점: 참이든 거짓이든 **진리값이 정확히 하나로 정해진다**는 것이다. 참인 문장만 통과한 것이 아니다 — 거짓으로 확정된 문장도 통과했다. ::: 이 심사 기준에 정식 이름을 붙인다. 기준 자체에 새로운 것은 없다 — 방금 표에서 한 심사를 문장으로 굳혔을 뿐이다. ### 정의 7.1 — 명제 (statement) [백지 암기 대상] :::{container} quotebox **명제**란 참(True) 또는 거짓(False) 중 **정확히 하나**의 진리값을 갖는 문장이다. ::: 거짓인 문장도 명제다 — $1 = 2$도 명제다(거짓인 명제). "명제 = 참인 문장"으로 새기는 경우가 많은데, 학교에서 명제를 주로 "참임을 보이는" 활동과 함께 만났기 때문이다. 정의의 기준은 참이 아니라 확정이다. 증명의 세계에서는 거짓인 명제를 다루는 일(반박$\cdot$반증)이 절반을 차지한다 — 1주차 문제 18에서 "$n^2 + n + 41$은 모든 자연수에서 소수"라는 주장을 **거짓인 명제**로 다뤘기에 반례로 처리할 수 있었다. 확정과 앎도 구분한다. "원주율 $\pi$의 소수점 아래 $10^{15}$번째 자리의 숫자는 7이다"는 명제다 — $\pi$의 소수 전개는 하나로 정해져 있으므로 진리값이 확정되어 있고, 우리가 그 값을 **아는지**는 별개의 문제다. 정의가 요구하는 것은 진리값의 존재이지 우리의 지식이 아니다. ### 3 정의 해부 — 조각마다 하는 일 이 한 문장은 세 조각으로 되어 있고, 조각마다 판별에서 맡는 역할이 다르다. | **조각** | **하는 일** | **판정에서의 역할** | |---|---|---| | "참 또는 거짓 중" | 진리값 후보의 제한 | 후보는 둘뿐이다 — "반쯤 참" 같은 제3의 값은 없다 | | "**정확히 하나**의 진리값을" | 확정의 요구 | 미정(열린 문장)도, 배정 불능(역설)도 걸러 낸다 | | "갖는 문장이다" | 대상의 자격 | 명령문$\cdot$질문$\cdot$감탄처럼 판정 자체가 없는 문장을 걸러 낸다 | **조각 삭제 실험.** 둘째 조각의 "정확히 하나"를 지워 보자. 그러면 $x + 2 = 5$(값에 따라 참도 거짓도 되는 문장)가 명제로 들어오고, "이 문장은 거짓이다"(참이라 해도 거짓이라 해도 충돌해 어느 값도 배정할 수 없는 문장 — 문제 17에서 해부한다)도 들어온다. :::{container} quotebox **확인 3.** "정확히 하나"를 지우는 순간 정확히 무엇이 무너지는가? ($x + 2 = 5$ 하나의 문제인지, 명제를 재료로 하는 이후의 작업은 어떤지 함께 생각해 보자.) ::: :::{admonition} 답 :class: quotebox dropdown 진리값이 확정되지 않은 문장이 명제 행세를 하게 된다. 그러면 §1.5에서 세울 연산이 무너진다 — $P \land Q$의 진리값은 $P$와 $Q$의 진리값에서 계산되는데, 재료의 진리값이 미정이면 결과도 미정이다. 판정을 이어 붙여 쌓는 활동(증명) 전체가 첫 칸부터 무너지는 것이다. 1주차 §1.3에서 "정수"를 지우자 짝수가 무너진 것과 같은 사정이다. ::: ### 4 열린 문장 — 변수가 살아 있는 문장 $x + 2 = 5$는 명제 심사에서 탈락했지만 버릴 문장이 아니다 — 1부 내내 조건제시법 $\{x \in S : P(x)\}$의 조건 자리에서 일해 온 문장이다. 정식 이름을 붙인다. ### 정의 7.2 — 열린 문장 (open sentence) :::{container} quotebox 변수를 포함하여, 변수 값이 정해져야 진리값이 정해지는 문장. $P(x)$처럼 쓴다. ::: 기호 $P(x)$는 "$x$에 관한 열린 문장 $P$"로 읽는다 — $x$ 자리에 값이 들어오면 진리값이 나오는, 명제의 재료다. 3주차 조건제시법의 $P(x)$가 정확히 이것이었다. :::{container} quotebox **확인 4.** $P(x)$: "$x + 2 = 5$"라 하자. $P(3)$과 $P(1)$은 각각 무엇이고, 진리값은 무엇인가. 그리고 열린 문장을 명제로 만드는 방법을 하나 말해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $P(3)$은 "$3 + 2 = 5$" — 참인 명제. $P(1)$은 "$1 + 2 = 5$" — 거짓인 명제. 값을 대입하는 순간 변수가 사라지고 진리값이 확정된다 — 첫째 방법이다. 둘째 방법은 "모든/어떤"을 붙여 변수를 묶는 것이다: "$x + 2 = 5$인 정수 $x$가 존재한다"는 확정된 명제다(참 — $x = 3$). 정식 도구(양화사)는 10주차에서 다루지만, 1주차 정의 1.1의 "$n = 2k$인 정수 $k$가 **존재한다**"가 정확히 이 방식으로 열린 문장을 명제로 만들어 온 것이다. ::: ### 5 접속사를 판정 규칙으로 — 정의를 만들어 보기 판정 대상의 자격(명제)이 정해졌으니 §1.1에서 멈춘 자리 — 접속사의 판정 규칙 — 로 돌아간다. 먼저 "그리고"부터. 진리값이 확정된 명제 두 개를 "그리고"로 이은 문장의 판정을, 가능한 네 조합 전부에 대해 심사해 보자. | **"그리고" 문장** | **두 원자의 진리값** | **전체의 판정** | |---|---|---| | 2는 짝수이고 $9 = 3^2$이다 | 참, 참 | 참 | | 2는 짝수이고 7은 짝수이다 | 참, 거짓 | $\underline{\quad(1)\quad}$ | | 7은 짝수이고 2는 짝수이다 | 거짓, 참 | $\underline{\quad(2)\quad}$ | | 7은 짝수이고 9는 짝수이다 | 거짓, 거짓 | $\underline{\quad(3)\quad}$ | :::{container} quotebox **확인 5.** 빈칸 (1)(2)(3)을 채우고, "그리고" 문장이 참이 되는 조합이 넷 중 몇 개인지 세어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) 거짓 (2) 거짓 (3) 거짓. 참인 조합은 (참, 참) **하나뿐**이다 — 한쪽이라도 거짓이면 전체가 거짓이다. 조합이 네 개뿐이므로 이 네 줄이 "그리고"의 판정 규칙 **전부**다. 접속사의 뜻이 유한한 표 하나로 완전히 적힌다 — 이번 주의 중심 발견이다. ::: 다음은 문제의 "또는"이다. 일상어에는 두 독법이 있었다(§1.1) — 수학은 "적어도 하나가 참이면 참, **둘 다 참이어도 참**" 쪽으로 못 박는다. 이유는 정합성이다: 5주차의 $A \cup B$는 양쪽 모두에 속하는 원소도 받아들이므로, 그 정의문 속 "또는"도 같은 독법이어야 두 정의가 어긋나지 않는다. :::{container} quotebox **확인 6.** 이 독법으로 §1.1의 판정을 끝내 보자. "6은 2의 배수이거나 3의 배수이다"의 진리값은 무엇이고, 따라서 $6 \in A \cup B$인가? ::: :::{admonition} 답 :class: quotebox dropdown 두 원자("6은 2의 배수", "6은 3의 배수")가 모두 참이고, 둘 다 참이어도 참이 규칙이므로 전체는 **참**이다. 따라서 $6 \in A \cup B$ — 5주차의 판정($x \in A \cap B$여도 $x \in A \cup B$)과 정확히 맞아떨어진다. 판정이 갈리던 문장이 규칙 하나로 확정됐다. ::: 거꾸로 "둘 다 참이어도 참"이라는 조각을 빼면 — 배타적 독법을 택하면 — 6이 $A \cup B$에서 탈락해 5주차의 합집합과 어긋난다. 이 갈림은 문제 8과 11에서 정면으로 다룬다. 마지막으로 "아니다"는 진리값을 뒤집는 것 — 참을 거짓으로, 거짓을 참으로 — 뿐이다. 세 규칙에 정식 이름과 기호를 붙인다. 규칙 자체에 새로운 것은 없다 — 방금 표에서 심사한 판정을 기호로 굳혔을 뿐이다. ### 정의 7.3 — 논리 연산 $\land, \lor, \neg$ (logical connectives) [백지 암기 대상] :::{container} quotebox 명제 $P, Q$에 대해: - $P \land Q$ ("P 그리고 Q", and): 둘 **다** 참일 때만 참. - $P \lor Q$ ("P 또는 Q", or): 적어도 하나가 참이면 참. **둘 다 참이어도 참** (포함적 or). - $\neg P$ ("P가 아니다", not): 진리값을 뒤집는다. ::: 기호는 각각 $\land$ "그리고", $\lor$ "또는", $\neg$ "…가 아니다"로 읽는다. 읽는 법까지가 정의다. 그리고 이 규칙을 표로 적은 것을 **진리표**(truth table)라 한다 — 가능한 모든 진리값 조합을 행으로 나열하고 각 행에서의 판정을 적은 표다. T는 참(True), F는 거짓(False)으로 읽는다. | **$P$** | **$Q$** | **$P \land Q$** | **$P \lor Q$** | |---|---|---|---| | T | T | **T** | **T** | | T | F | F | T | | F | T | F | T | | F | F | F | F | | **$P$** | **$\neg P$** | |---|---| | T | F | | F | T | $P \lor Q$의 첫 행(둘 다 참 $\to$ 참)이 일상어와 갈라지는 지점이다 — §1.5에서 못 박은 그 선택이다. **논리–집합 대응.** 백지 재현 대상이다. | **논리** | **$\land$** | **$\lor$** | **$\neg$** | |---|---|---|---| | 집합 | $\cap$ | $\cup$ | $^c$ (여집합) | 이 대응은 우연이 아니다 — 집합 연산의 정의문 안에 논리 연산이 살고 있기 때문이다: $A \cap B = \{x : x \in A \land x \in B\}$. 1부에서 말로 적던 정의문의 접속사 자리에 기호가 들어간 것뿐이다. 이 사전은 문제 9, 14의 실전 번역에 쓰고, 27주차에서 집합 항등식 전체를 논리로 계산하는 엔진이 된다. ### 6 복합 명제의 진리표 — 작성 절차 $\neg P \lor Q$처럼 연산이 여러 개 겹친 명제의 진리표는 **안쪽 연산부터 열을 하나씩 추가**해 만든다. 절차는 세 걸음이다. ① **행 수를 정하고 원자 열을 나열한다.** 명제 변수가 $n$개면 $2^n$행 — 변수마다 T/F 2택이 겹치기 때문이다(4주차에서 멱집합의 크기 $2^n$을 셌던 것과 같은 셈이다). 조합을 빠뜨리지 않으려면 기계적으로 나열한다: 첫 변수 열은 T 절반$\cdot$F 절반, 다음 열은 그 절반씩을 다시 반으로, 마지막 변수 열은 T와 F를 번갈아 적는다. ② **안쪽 연산의 열부터 추가한다.** $\neg P \lor Q$에서 안쪽은 $\neg P$다. 여기서 규약 하나 — $\neg$는 바로 뒤의 명제에만 적용된다. $\neg P \lor Q$는 $(\neg P) \lor Q$이지 $\neg(P \lor Q)$가 아니다. 부정의 범위를 넓히려면 괄호를 직접 쓴다. ③ **바깥 연산의 열을 완성한다.** 이미 만든 열들을 재료로 정의 7.3의 규칙을 행마다 적용한다. $\neg P \lor Q$에 이 절차를 적용하면 — | **$P$** | **$Q$** | **$\neg P$** | **$\neg P \lor Q$** | |---|---|---|---| | T | T | F | T | | T | F | F | F | | F | T | T | T | | F | F | T | T | :::{container} quotebox **확인 7.** $P$ = F, $Q$ = T인 행(셋째 행)에서 $\neg P \lor Q$와 $\neg(P \lor Q)$의 값을 각각 계산해 보자. 같은가? ::: :::{admonition} 답 :class: quotebox dropdown $\neg P \lor Q$: $\neg P$ = T이므로 T $\lor$ T = **T**. $\neg(P \lor Q)$: $P \lor Q$ = T이므로 부정하면 **F**. 다르다 — 괄호의 위치가 명제 자체를 바꾼다. 진리표를 만들기 전에 부정의 범위부터 확정하는 것이 절차 ②의 이유다. ::: :::{container} quotebox **확인 8.** 변수 3개짜리 복합 명제의 진리표는 몇 행인가. 그리고 절차 ①의 나열 방식대로라면 첫 변수 $P$의 열은 어떻게 적는가? ::: :::{admonition} 답 :class: quotebox dropdown $2^3 = 8$행. $P$ 열은 T 4개, F 4개 — 다음 $Q$ 열은 TTFF를 반복, 마지막 $R$ 열은 TF를 반복한다. 이 기계적 나열이 여덟 조합을 빠짐없이, 겹침 없이 훑는다는 보장이다. 문제 3과 19의 8행 표가 이 방식으로 만들어진다. ::: ### 7 근거 목록 갱신 — 칸은 그대로 네 개 1주차 §1.6에서 세우고 2주차 §1.6에서 갱신한 근거 목록이 이번 주에 다시 갱신된다. 칸의 개수는 늘지 않는다 — ① 칸에 정의 세 개가 추가될 뿐이다. | **근거** | **내용** | **이번 주에는 이렇게 쓴다** | |---|---|---| | ① 정의 | 정의 1.1~6.2, **7.1~7.3** | 명제 판별과 진리표의 매 칸이 정의 7.1, 7.3의 적용이다 | | ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | 이번 주는 출동할 자리가 거의 없다 — 대기 | | ③ 등식의 성질 | 대입 / 전개 / 묶기 | 문제 9의 생성형 표기에서 쓴다 | | ④ 이미 증명한 명제 | 이전 주차의 문제들, 이번 주에 완성한 진리표 | 예제 2.2의 표를 문제 4가, 문제 8의 표를 문제 16이 재사용한다 | 이번 주의 새 도구인 진리표는 목록 밖의 다섯째 근거가 아니다 — 매 칸이 정의 7.3의 규칙을 한 행에 적용한 결과이므로, 진리표 전체가 근거 ①의 기계적 사용이다. 완성된 진리표는 근거 ④의 재료가 된다: 한 번 만든 표의 열은 다시 계산하지 않고 인용한다. :::{container} quotebox **확인 9.** 어떤 답안에 다음 세 근거 문장이 나왔다. 각각 허용되는가? 허용된다면 몇 번 근거인가. (가) "$P$가 참이므로, $\lor$의 규칙에 의해 $P \lor Q$는 참" (나) "상식적으로 둘 다 맞는 말이니까 참" (다) "예제 2.2의 표에 의해 이 행에서 $\neg(P \land Q)$는 T" ::: :::{admonition} 답 :class: quotebox dropdown (가) 허용 — 근거 ① 정의. 정의 7.3의 $\lor$ 규칙을 그대로 적용했다. (나) 불허 — 목록 밖이다. "상식"은 §1.1에서 본 대로 독법이 갈리는 판정 기준이다. 같은 내용을 정의 7.3의 규칙 인용으로 바꿔 적어야 근거가 된다. (다) 허용 — 근거 ④. 이미 완성해 검사를 마친 표의 재사용이다. ::: 정의는 외운다 — [백지 암기 대상] 표시가 그 대상이다. 문장을 통째로만 외우지 말고 §1.3의 조각별 이유와 함께 외운다. 조각을 잊어도 이유에서 재구성할 수 있다.