Contents
집합론에서는 명제(Statement)라는 개념을 다룬다. 이번 글에서는 집합론에서 언급하는 명제에 대해서 간단한 예제를 통해서 알아보고자 한다.
1.1.명제(Statement)
Definition 1.1.1
시간이나 지식에 상관없이 참(True) 혹은 거짓(False)이 분명한 문장이나 식을 명제(Statement)라고 한다.
명제는 참이나 거짓이 분명해야 한다. '2+3은 5이다' 라는 문장은 2+3이 5인 것이 확실하다. '$\sqrt{2}$의 소수$10^{100}$ 번째 자리 숫자는 3이다.' 라는 문장은 계산을 하든 하지 않든 3이거나 아니거나 참과 거짓이 분명하다. 그러나, '벚꽃길이 예쁘다' 와 같은 문장은 추상적이기 때문에 명확하게 정답이 존재하지 않는다. 따라서, 명제가 아니다.
하나의 명제를 $p$라고 나타낼 때, '$p$가 아니다'를 기호로 $\sim p$로 나타내고, $p$의 부정(negation)이라 부른다. 예를 들어, '2+3은 5이다'라는 명제를 $p$라고 하면 $p$의 부정 $\sim p$는 '2+3은 5가 아니다'가 된다. 어떤 명제 $p$가 있을 때, 참이든 거짓이든 둘 중 하나이기 때문에, 참일 경우에는 T, 거짓일 경우에는 F로 나타내기로 하면 다음과 같은 진리표(Truth table)를 만들 수 있다. 이때 $T$, $F$를 진리값(Truth Value)이라 한다.
| $p$ | $\sim p$ |
| T | F |
| F | T |
Definition 1.1.2
임의의 두 명제 $p$, $q$가 있을 때, 합성명제 $p \land q$의 진리값을 다음과 같이 정의한다.
| $p$ | $q$ | $p \land q$ |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
$p \land q$는 $p$이고 $q$ 혹은 $p$와 $q$의 논리곱(conjuction)이라고 읽는다. 예를 들면 '화성에는 생명체가 없다'를 $p$, '달에는 물이 있다'를 $q$로 나타내면, $p \land q$는 화성에는 '생명체가 없고, 달에는 물이 있다'를 나타낸다.
Example
다음 합성 명제의 진리표를 만들어라.
\[ \sim [(\sim p) \land q ] \]
| $p$ | $q$ | $\sim p$ | $(\sim p) \land q$ | $\sim [(\sim p) \land q]$ |
| T | T | F | F | T |
| T | F | F | F | T |
| F | T | T | T | F |
| F | F | F | F | F |
Definition 1.1.3
임의의 두 명제 $p$, $q$가 있을 때, 합성명제 $p \lor q$의 진리값을 다음 표와 같이 정의한다.
| $p$ | $q$ | $p \lor q$ |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
$p \lor q$는 $p$ 또는 $q$, 혹은 $p$와 $q$의 논리합(disjuction)이라고 읽는다. 논리곱의 경우 하나라도 F인 경우 F가 되고, 논리 합의 경우 $p$와 $q$가 모두 F여야 F가 된다.
Definition 1.1.4
두 명제 $P$와 $Q$에 대하여, 모든 논리적 가능성의 각각의 경우에 진리값이 같으면, $P$와 $Q$는 논리적 동치(logically equivalent) 혹은 동치(equivalent)라 하고, $P \equiv Q$로 나타낸다.
Example
$p \lor q$와 $\sim ( \sim p \land \sim q)$의 진리표를 살펴보자.
| $p$ | $q$ | $p \lor q$ |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
| $p$ | $q$ | $\sim p$ | $\sim q$ | $\sim p \land \sim q$ | $\sim ( \sim p \land \sim q)$ |
| T | T | F | F | F | T |
| T | F | F | T | F | T |
| F | T | T | F | F | T |
| F | F | T | T | T | F |
위 표를 살펴보면 $p \land q$의 진리값과 $\sim ( \sim p \land \sim q)$의 진리값이 모든 경우에 같으므로 $ p \lor q \equiv \sim ( \sim p \land \sim q)$로 나타낼 수 있다.
Definition 1.1.5
두 명제 $p$, $q$가 있을 때, 합성명제 $p \rightarrow q$의 진리값을 아래의 표와 같이 정의한다.
| $p$ | $q$ | $p \rightarrow q$ |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
$p \rightarrow q$는 '$p$이면 $q$' 라고 읽는다. '$p$이면 $q$'는 우리가 일상에서 사용하는 인과관계가 반드시 있어야 되는 것이 아니다.예를 들어, '$1+1=2 \rightarrow \pi$는 무리수이다.'를 생각하면 $p$와 $q$는 인과간계가 없다. 그러나, 이 합성명제는 $p$와 $q$가 각각 T이기 때문에 T가 된다.
Example
$p \rightarrow q \equiv \sim (p \land \sim q)$이다. 이 문제를 풀기 위해서는 진리표를 만들어야 한다. 그 후 $p \rightarrow q$와 $\sim (p \land \sim q)$가 논리적 동치인지 확인하여야 한다.
| $p$ | $q$ | $\sim q$ | $ p \land \sim q$ | $ \sim (p \land \sim q)$ |
| T | T | F | F | T |
| T | F | T | T | F |
| F | T | F | F | T |
| F | F | T | F | T |
$\sim (p \land \sim q)$의 진리값이 모든 경우에 $p \rightarrow q$의 진리값과 같은 것을 확인할 수 있으므로, $p \rightarrow q$와 $\sim ( p \land \sim q)$ 는 논리적 동치임을 확인할 수 있다. 두 명제 $p$, $q$가 있을 때, 합성명제 $(p \rightarrow q) \land (q \rightarrow p)$와 동치인 명제를 $p \leftrightarrow q$로 나타내고, $p$일 필요충분조건이 $q$라고 읽는다.
Exercise
연습문제는 직접 풀어보기를 바란다. 위 내용을 통해서 충분히 풀 수 있는 수준의 예시다.
- 1441년 1월 7일에 플로리다의 어느 곳엔가 눈이 내렸다.
- 아리스토텔레스는 평발이었다.
- 사회주의는 잘못된 것이다.
- 지선과 유상은 착하다.
- 이 자동차의 값을 얼마입니까?
- 잔디밭에 들어가지 마시오.
- 당신의 안전띠를 매시오.
- 수 $2^{987654321}$은 소수이다.
- $\sim ( \sim p)$
- $\sim (\sim (\sim p ) ) $
- $p \land p$
- $ \sim ( p \land \sim p)$
- $p \land \sim q$
- $\sim p \land q$
- $(p \land q) \land \sim p $
- $ \sim ( p \land q)$
1.2 항진명제(Tautology)
Definition 1.2.1
모든 논리적 가능성에 대하여, 항상 참인 명제를 항진명제(Tautology)라고 한다.
$p \lor \sim p$에 대해서 한 번 알아보자. 이 명제는 항삼 참(T)이므로 항진 명제가 된다. 특히 두 명제, $P$, $Q$에 대하여, $P \rightarrow Q$가 항진명제일 때 $P$는 $Q$를 함의(imploication)한다고 말하고 '$P \implies Q$'로 표시한다. 수학이나 논리에 있어서 정리(Theorem)는 항진명제이다. 이러한 항진명제는 정리의 정당성을 밝히는 일을 증명(Proof$이라고 한다.
Theorem 1.2.2
임의의 두 명제 $p$, $q$에 대하여 다음이 성립한다.
합의 법칙(law of addition-Add.)
\[ p \implies p \lor q \]
단순화 법칙(law of simplication-Simp)
\[ p \land q \implies p, \quad p \lor q \implies q \]
논리합삼단법(disjunctive syllogism-D.S.)
\[ (p \lor q ) \land \sim p \implies q \]
Proof
| $p$ | $q$ | $p \lor q$ | $p \rightarrow (p \lor q)$ |
| T | T | T | T |
| T | F | T | T |
| F | T | T | T |
| F | F | F | T |
(a)의 경우 위 표를 통해서 항진명제임을 확인할 수 있다.
| $p$ | $q$ | $p \land q$ | $ ( p \land q ) \rightarrow p$ | $ ( p \land q ) \rightarrow q$ |
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | F | T | T |
| F | F | F | T | T |
(b)의 경우 위 표를 통해서 항진명제임을 확인할 수 있다. (a)와 (b)는 간단하게 증명하는 것이 가능하다. 그렇다면 (c)도 한 번 증명해보자.
| $(p$ | $\lor$ | $q)$ | $\land$ | $\sim p$ | $\rightarrow$ | $q$ |
| T | T | T | F | F | T | T |
| T | T | F | F | F | T | F |
| F | T | T | T | T | T | T |
| F | F | F | F | T | T | F |
위와 같은 표로 간략하게 정리할 수 있다. $P \leftrightarrow Q$가 항진명제일 때, $P \iff Q$로 나타내고, $P$와 $Q$는 동치라고 읽는다.
Theorem 1.2.3
임의의 두 명제 $p$, $q$에 대하여 다음이 성립한다.
(a) 이중부정법(law of double negation-D.N.)
\[ \sim (\sim p ) \equiv p \]
(b) 교환법칙(commutative laws-Com.)
\[ p \land q \equiv q \land p,\quad p \lor q \equiv q \lor p \]
(c) 멱등법칙(laws of idempotency-Idemp)
\[ p \land p \equiv p, \quad p \lor p \equiv p \]
(d) 대우법칙(contrapositive law-Contrap.)
\[ (p \rightarrow q) \equiv ( \sim q \rightarrow \sim p ) \]
(a), (b), (c)의 증명은 간단하기 때문에 생략하고, (d)에 대해서만 증명을 진리표로 알아보자.
| $(p$ | $\rightarrow$ | $q)$ | $(\sim q$ | $\rightarrow$ | $\sim p)$ |
| T | T | T | F | T | F |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | T | F | T | T | T |
Theorem 1.2.4
드 모르간 법칙(De Morgan's laws-De M.) 임의의 두 명제 $p$, $q$에 대하여 다음이 성립한다.
Proof
| $\sim$ | $(p$ | $\land$ | $q)$ | $(\sim p$ | $\lor$ | $\sim q)$ |
| F | T | T | T | F | F | F |
| T | T | F | F | F | T | T |
| T | F | F | T | T | T | F |
| T | F | F | F | T | T | T |
Theorem 1.2.5
임의의 세 명제 $p$, $q$, $t$에 대하여 다음이 성립한다.
(a) 결합법칙(associative laws-Assoc.)
\[ (p \land q) \land r \equiv p \land (q \land r) \]
\[ (p \lor q) \lor v \equiv p \lor ( q \lor r) \]
(b) 분배법칙(distributive laws-Dist.)
\[ p \land ( q \lor r) \equiv (p \land r) \]
\[ p \lor ( q \land r) \equiv (p \lor q ) \land ( p \lor r) \]
(c) 추이법칙(transitive law-Trans.)
\[ (p \rightarrow q) \land ( q \rightarrow r) \implies (p \rightarrow r) \]
앞에서 다룬 예제에서는 $p$, $q$에 대해서만 다루었기 때문에 $2^2=4$로 계산되었지만, 세 성분 $p$, $q$, $r$에 대한 논리적 가능성은 모두 $2^3 = 8$가지가 있다. 위에서 만든 간단한 표 형식으로 한 번 증명해보기를 바란다.
Theorem 1.2.6
임의의 두 명제 $p$, $q$에 대하여 다음이 성립한다.
(a) C.D. 법칙(constructive dilemmas-C.D.)
\[ (p \rightarrow q) \land (r \rightarrow s) \implies ( p \lor r \rightarrow q \lor s) \]
\[ ( p \rightarrow q) \land (r \rightarrow s) \implies ( p \land r \rightarrow q \land s ) \]
(b) D.D. 법칙(destructive dilemmas-D.D.)
\[ (p \rightarrow q) \land (r \rightarrow s) \implies ( \sim q \ \lor \sim s \rightarrow \sim p \ \lor \sim r) \]
\[ (p \rightarrow q ) \land (r \rightarrow s) \implies ( \sim q \ \lor \sim s \rightarrow \sim p \ \lor \sim r) \]
\[ (p \rightarrow q ) \land ( r \rightarrow s) \implies ( \sim q \ \land \sim s \rightarrow \sim p \ \land \sim r ) \]
Theorem 1.2.7
임의의 두 명제 $p$, $q$에 대하여 다음이 성립한다.
(a) M.P.법칙(modus pones-M.P.)
\[ (p \rightarrow q) \land p \implies q \]
(b) M.T.법칙(modus tollens-M.T.)
\[ (p \rightarrow q) \land \sim q \implies \sim p \]
(b) R.A.법칙(reductio ad absurdum-R.A.)
\[ (p \rightarrow q) \iff ( p \land \sim q \rightarrow q \land \sim q) \]
R.A. 법칙은 귀류법이라고도 부르며, 수학 전반에서 많이 사용된다. $q \land \sim q$는 $F$라고도 부르며, 진리값이 항상 거짓인 명제를 나타낸다. 위 정의도 직접 증명해보는 것을 권장한다.
Exercise
- $p \lor \sim p $
- $ \sim ( p \lor \sim p )$
- $ \sim ( \sim p \lor \sim q) $
- $ \sim p \lor q$
- $ ( \sim q) \rightarrow (\sim p ) $
- $ q \leftrightarrow p $
- $ p \land ( q \lor r ) $
- $ ( p \land q ) \lor ( p \land r) $
- $ ( p \land q ) \lor r $
- $ ( p \lor q ) \land ( p \lor r ) $
- $ p \lor ( q \lor r ) $
- Theorem 1.2.3 (a), (b), (c)를 차례로 증명해보아라.
- $ \sim ( p \land q ) \equiv \sim p \lor \sim q $임을 증명하여라.
- Theorem 1.2.5 (a)를 증명하여라.
- $p \lor ( q \land r ) \equiv (p \lor q) \land ( p \lor r ) $임을 증명하여라.
- $(p \rightarrow q) \implies (p \land r \rightarrow q \land r)$ 임을 증명하여라.
- $(p \rightarrow q) \equiv (p \land q) \lor ( \sim p \land \sim q ) $ 임을 증명하여라.
1.3 모순 명제(Contradiction)
Definition 1.3.1
모든 논리적 가능성에 대하여 항상 진리값이 거짓인 명제를 모순명제(Contradiction)라고 한다.
Theorem 1.3.2
$p$가 임의의 명제이고, $t$는 항진명제, $c$는 모순명제일 때, 다음이 성립한다.
(a) $p \land t \iff p, \quad p \lor t \iff t $
(b) $p \lor c \iff p, \quad p \land c \iff c $
(c) $c \implies p, \quad p \implies t $
1.4 연역적 추론(Deduction Method)
정의, 공리, 정리, 추론법칙 등 이미 알려진 사실들을 활용하여 결론을 이끌어 내는 방법을 연역적 추론(Deduction Method)이라고 한다. 이와 같은 증명법을 직접증명(Direct proof)이라고도 한다.
1.5 간접 증명법(Method of Indirect Proof)
간접 증명법은 논증의 결론의 부정을, 하나의 새로운 전제로서 주어진 가정에 덧붙임으로써, 모순을 이끌어 내는 방법을 의미한다. 이러한 방법을 배리법이라고도 한다.
\[ \begin{equation} \begin{split} p \land \sim q \rightarrow & \equiv \sim [ (p \land \sim q ) \land \sim c ] \\ \\ & \equiv \sim (p \land \sim q) \lor c \\ \\ & \equiv \sim (p \land \sim q) \\ \\ & \equiv p \rightarrow q \end{split} \end{equation} \]
그러므로 $p \rightarrow q \equiv p \land \sim q \rightarrow c $ 이므로 배리법을 사용하여, 명제 $p \rightarrow q$를 증명할 수 있다.
본 글은 명지대학교 수학과 김영기 교수님의 '집합론' 책을 기반으로 작성했다. 유튜브로 집합론뿐만 아니라 위상수학 현대대수학 그리고 선형대수학 강의를 녹화하고 진행하시기 때문에 참고하길 바란다. [링크]