7주차 — 명제와 논리 연산

내용

7주차 — 명제와 논리 연산#

이 주의 길잡이

핵심 문장: 명제의 자격은 참이 아니라, 진리값이 정확히 하나로 정해진다는 것이다.

이 주의 위치: 50주 과정의 7주차. 2부(논리)의 첫 주 — 1부의 집합 정의문 안에서 말로 쓰던 “그리고 / 또는 / 아니다”를 정식 연산으로 만들고, 진리표라는 판정 도구를 얻는다. 고1 ‘명제’ 단원의 재건축이 여기서 시작된다.

원서 대응: BoP(Book of Proof) 2.1–2.2 — 병행자 참고용. 원서 없이 읽을 수 있다.

이번 주 목표#

명제(statement)와 명제가 아닌 것을 정의로 판별하고, 거짓인 문장도 명제인 이유를 설명할 수 있다.
\(\land\)(그리고), \(\lor\)(또는), \(\neg\)(부정)의 진리표를 백지에 쓰고, 복합 명제의 진리표를 절차대로 작성할 수 있다.
변수가 들어 있는 문장(열린 문장)이 왜 명제가 아닌지, 어떻게 명제로 만드는지 안다.

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

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

\(A \times B\)의 정의를 쓰시오.
\(A_i = \{i, 2i\}\) (\(i = 1, 2, 3\))일 때 \(\bigcup_{i=1}^3 A_i\)를 나열하시오.
6주차 모의시험에서 틀린 문제 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\}\). 이 “또는”을 일상어 그대로 두고 판정을 밀어붙여 보자.

시도 — 일상어 독법으로 밀어붙이기

\(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\)거짓 판정이 시작되지 않는다.

확인 1. 위 시도가 멈춘 원인과, “수학은 아름답다”가 판정되지 않는 원인은

서로 다르다. 각각 한 구절로 지목해 보자.

답

시도가 멈춘 원인: “또는”의 판정 규칙이 정해져 있지 않다 — 독법이 둘이라 판정이

갈린다. “수학은 아름답다”의 원인: 규칙 이전에 판정 대상의 자격이 없다 — 객관적

참\(\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}\)
수학은 아름답다.	확정되지 않는다 — 객관적 판정 기준이 없다

확인 2. 빈칸 (1)(2)(3)을 채우고, “확정된다” 판정을 받은 문장들의 공통점을

한 문장으로 적어 보자. 참인 문장만 통과했는가?

답

(1) 확정된다 — 거짓. 계산이 틀린 문장이지만, “거짓”이라는 판정 하나로 확정된다는

점에서는 \(2+3=5\)와 같은 자격이다.

(2) 확정되지 않는다 — 명령문에는 참\(\cdot\)거짓을 물을 수 없다.

(3) 확정되지 않는다 — \(x = 3\)이면 참, \(x = 1\)이면 거짓으로 값에 따라 오락가락한다.

공통점: 참이든 거짓이든 진리값이 정확히 하나로 정해진다는 것이다. 참인 문장만

통과한 것이 아니다 — 거짓으로 확정된 문장도 통과했다.

이 심사 기준에 정식 이름을 붙인다. 기준 자체에 새로운 것은 없다 — 방금 표에서 한 심사를 문장으로 굳혔을 뿐이다.

정의 7.1 — 명제 (statement) [백지 암기 대상]#

명제란 참(True) 또는 거짓(False) 중 정확히 하나의 진리값을 갖는 문장이다.

거짓인 문장도 명제다 — \(1 = 2\)도 명제다(거짓인 명제). “명제 = 참인 문장”으로 새기는 경우가 많은데, 학교에서 명제를 주로 “참임을 보이는” 활동과 함께 만났기 때문이다. 정의의 기준은 참이 아니라 확정이다. 증명의 세계에서는 거짓인 명제를 다루는 일(반박\(\cdot\)반증)이 절반을 차지한다 — 1주차 문제 18에서 “\(n^2 + n + 41\)은 모든 자연수에서 소수”라는 주장을 거짓인 명제로 다뤘기에 반례로 처리할 수 있었다.

확정과 앎도 구분한다. “원주율 \(\pi\)의 소수점 아래 \(10^{15}\)번째 자리의 숫자는 7이다”는 명제다 — \(\pi\)의 소수 전개는 하나로 정해져 있으므로 진리값이 확정되어 있고, 우리가 그 값을 아는지는 별개의 문제다. 정의가 요구하는 것은 진리값의 존재이지 우리의 지식이 아니다.

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

이 한 문장은 세 조각으로 되어 있고, 조각마다 판별에서 맡는 역할이 다르다.

조각	하는 일	판정에서의 역할
“참 또는 거짓 중”	진리값 후보의 제한	후보는 둘뿐이다 — “반쯤 참” 같은 제3의 값은 없다
“정확히 하나의 진리값을”	확정의 요구	미정(열린 문장)도, 배정 불능(역설)도 걸러 낸다
“갖는 문장이다”	대상의 자격	명령문\(\cdot\)질문\(\cdot\)감탄처럼 판정 자체가 없는 문장을 걸러 낸다

조각 삭제 실험. 둘째 조각의 “정확히 하나”를 지워 보자. 그러면 \(x + 2 = 5\)(값에 따라 참도 거짓도 되는 문장)가 명제로 들어오고, “이 문장은 거짓이다”(참이라 해도 거짓이라 해도 충돌해 어느 값도 배정할 수 없는 문장 — 문제 17에서 해부한다)도 들어온다.

확인 3. “정확히 하나”를 지우는 순간 정확히 무엇이 무너지는가?

(\(x + 2 = 5\) 하나의 문제인지, 명제를 재료로 하는 이후의 작업은 어떤지 함께 생각해 보자.)

답

진리값이 확정되지 않은 문장이 명제 행세를 하게 된다. 그러면 §1.5에서 세울 연산이

무너진다 — \(P \land Q\)의 진리값은 \(P\)와 \(Q\)의 진리값에서 계산되는데, 재료의 진리값이

미정이면 결과도 미정이다. 판정을 이어 붙여 쌓는 활동(증명) 전체가 첫 칸부터 무너지는

것이다. 1주차 §1.3에서 “정수”를 지우자 짝수가 무너진 것과 같은 사정이다.

4 열린 문장 — 변수가 살아 있는 문장#

\(x + 2 = 5\)는 명제 심사에서 탈락했지만 버릴 문장이 아니다 — 1부 내내 조건제시법 \(\{x \in S : P(x)\}\)의 조건 자리에서 일해 온 문장이다. 정식 이름을 붙인다.

정의 7.2 — 열린 문장 (open sentence)#

변수를 포함하여, 변수 값이 정해져야 진리값이 정해지는 문장. \(P(x)\)처럼 쓴다.

기호 \(P(x)\)는 “\(x\)에 관한 열린 문장 \(P\)”로 읽는다 — \(x\) 자리에 값이 들어오면 진리값이 나오는, 명제의 재료다. 3주차 조건제시법의 \(P(x)\)가 정확히 이것이었다.

확인 4. \(P(x)\): “\(x + 2 = 5\)”라 하자. \(P(3)\)과 \(P(1)\)은 각각 무엇이고,

진리값은 무엇인가. 그리고 열린 문장을 명제로 만드는 방법을 하나 말해 보자.

답

\(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}\)

확인 5. 빈칸 (1)(2)(3)을 채우고, “그리고” 문장이 참이 되는 조합이 넷 중

몇 개인지 세어 보자.

답

(1) 거짓 (2) 거짓 (3) 거짓. 참인 조합은 (참, 참) 하나뿐이다 — 한쪽이라도

거짓이면 전체가 거짓이다. 조합이 네 개뿐이므로 이 네 줄이 “그리고”의 판정 규칙

전부다. 접속사의 뜻이 유한한 표 하나로 완전히 적힌다 — 이번 주의 중심 발견이다.

다음은 문제의 “또는”이다. 일상어에는 두 독법이 있었다(§1.1) — 수학은 “적어도 하나가 참이면 참, 둘 다 참이어도 참” 쪽으로 못 박는다. 이유는 정합성이다: 5주차의 \(A \cup B\)는 양쪽 모두에 속하는 원소도 받아들이므로, 그 정의문 속 “또는”도 같은 독법이어야 두 정의가 어긋나지 않는다.

확인 6. 이 독법으로 §1.1의 판정을 끝내 보자. “6은 2의 배수이거나 3의 배수이다”의

진리값은 무엇이고, 따라서 \(6 \in A \cup B\)인가?

답

두 원자(“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) [백지 암기 대상]#

명제 \(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

확인 7. \(P\) = F, \(Q\) = T인 행(셋째 행)에서 \(\neg P \lor Q\)와 \(\neg(P \lor Q)\)의

값을 각각 계산해 보자. 같은가?

답

\(\neg P \lor Q\): \(\neg P\) = T이므로 T \(\lor\) T = T. \(\neg(P \lor Q)\):

\(P \lor Q\) = T이므로 부정하면 F. 다르다 — 괄호의 위치가 명제 자체를 바꾼다.

진리표를 만들기 전에 부정의 범위부터 확정하는 것이 절차 ②의 이유다.

확인 8. 변수 3개짜리 복합 명제의 진리표는 몇 행인가. 그리고 절차 ①의 나열

방식대로라면 첫 변수 \(P\)의 열은 어떻게 적는가?

답

\(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의 규칙을 한 행에 적용한 결과이므로, 진리표 전체가 근거 ①의 기계적 사용이다. 완성된 진리표는 근거 ④의 재료가 된다: 한 번 만든 표의 열은 다시 계산하지 않고 인용한다.

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

허용된다면 몇 번 근거인가.

(가) “\(P\)가 참이므로, \(\lor\)의 규칙에 의해 \(P \lor Q\)는 참”

(나) “상식적으로 둘 다 맞는 말이니까 참”

(다) “예제 2.2의 표에 의해 이 행에서 \(\neg(P \land Q)\)는 T”

답

(가) 허용 — 근거 ① 정의. 정의 7.3의 \(\lor\) 규칙을 그대로 적용했다.

(나) 불허 — 목록 밖이다. “상식”은 §1.1에서 본 대로 독법이 갈리는 판정 기준이다.

같은 내용을 정의 7.3의 규칙 인용으로 바꿔 적어야 근거가 된다.

(다) 허용 — 근거 ④. 이미 완성해 검사를 마친 표의 재사용이다.

정의는 외운다 — [백지 암기 대상] 표시가 그 대상이다. 문장을 통째로만 외우지 말고 §1.3의 조각별 이유와 함께 외운다. 조각을 잊어도 이유에서 재구성할 수 있다.