[집합론] 1. 초등논리(1: 명제, 항진, 함의, 동치, 모순)
참 또는 거짓을 구분할 수 있는 문장을 명제(statement)라고 한다. 다음은 명제인 것과 명제가 아닌 것의 예시들이다.
명제인 예:
1. 2019년을 기준으로 마산은 창원시의 일부이다.(참)
2. 2+2는 5와 같다.(거짓)
3. OO역에 KTX가 오고 있다.(상황에 따라 참 또는 거짓)
명제가 아닌 것의 예:
1. 이 참치초밥은 맛있다.(한 개인의 주관)
2. 좋은 아침이야.(한 개인의 주관)
3. x+1=3.(x에 대한 언급이 없다.)
문장을 더 이상 분해할 수 없는 하나의 문장으로 이루어진 명제를 단순명제(simple statement), 둘 이상의 단순명제들로 결합된 명제를 합성명제(compound statement)라고 한다.
합성명제의 예: 2+2는 5와 같고, √3을 십진법으로 전개할 때 105번째 자릿수는 7이다.
명제를 나타낼 때는 p,q,r,⋯로 나타내고, 소문자는 단순명제를, 대문자는 합성명제를 나타낸다.
명제 p,q,r,⋯들을 연결하여 합성명제를 구성하는 도구를 결합자(connectives)라 한다. 다음은 주로 사용되는 결합자들이다.
"아니다(not)":∼
"이고(and)":∨
"또는(or)":∧
"...이면...(if)":...→...
"...이면 그리고 그때에만...(if and only if)":...↔...
명제의 참, 거짓의 관계를 다음과 같이 진리표(truth table)에 나타내면 편리하다.
p |
∼p |
T |
F |
F | T |
임의의 명제 p,q사이에 결합자 ∨를 붙여서 정의한 합성명제 p∨q의 진리표는 다음과 같다.
p |
q |
p∨q |
T |
T |
T |
T |
F |
F |
F |
T |
F |
F |
F |
F |
기호 p∨q는 "p이고(and) q" 또는 "p와 q의 논리곱(conjuction)"이라고 한다. p∨q와 같은 합성명제에 대해 각각의 명제 p,q를 성분(components)이라고 한다. 이때 p∨q의 논리적 가능성(logical possibilities)은 다음의 2×2=4가지 이다.
1. p:참, q:참
2. p:거짓, q:참
3. p:참, q:거짓
4. p:거짓, q:거짓
예를 들어 ∼[(∼p)∨(∼q)]의 진리표는 다음과 같다.
p |
q |
∼p |
∼q |
(∼p)∨(∼q) |
∼[(∼p)∨(∼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 |
단계 |
1 |
1 |
2 |
3 |
임의의 두 명제 p,q사이에 결합자 ∧를 붙인 합성명제 p∧q는 "p 또는(or) q" 또는 "p와 q의 논리합(disjunction)"이라고 하고, 진리표는 다음과 같다.
p |
q |
p∧q |
T |
T |
T |
T |
F |
T |
F |
T |
T |
F |
F |
F |
논리곱과 논리합의 차이는 p,q가 모두 참일때만 p∨q는 참이 되지만 p,q가 모두 거짓일때만 p∧q는 거짓이 된다.
단순명제(p, q) 또는 합성명제(P, Q)에 대한 모든 논리적 가능성에 대한 진리값이 모두 같으면 P와 Q는 논리적 동치(logically equivalent) 또는 간단히 동치(equivalent)라 하고 P≡Q로 나타낸다. 앞에서 다루었던 p∧q와 ∼(∼p∨∼q)의 진리표는 동일하므로 p∧q≡∼(∼p∨∼q)이다.
임의의 명제 p,q사이에 조건부(conditional) 결합자 →를 붙여서 조건문 p→q(p이면 q)를 구성한다. 이때 다음의 표와 같이 p→q는 ∼(∼p∨∼q)와 동치인 명제로 정의한다.
p |
q |
∼q |
p∨∼q |
p→q≡∼p∧q |
T |
T |
F |
F |
T |
T |
F |
T |
T |
F |
F |
T |
F |
F |
T |
F |
F |
T |
F |
T |
이것은 p이면 q이고 p인데 q가 아닐 수 없다라는 의미이다. 따라서 이 조건문의 진리값은 p가 참이고 q가 거짓인 경우에만 거짓이고 나머지 경우는 모두 참이다.
예를들어 p:햇빛이 빛나고 있다, q: 나는 테니스를 치고 있다, 일 때 p→q는 "햇빛이 빛나고 있으면 나는 테니스를 치고 있다"이다.
임의의 명제 p,q 사이에 쌍조건부(biconditional) 결합자 ↔를 붙여서 합성명제 p↔q를 구성한다. 이 명제는 다음의 표와 같이 합성명제 (p→q)∨(q→p)와 동치인 것으로 정의한다.
p |
q |
p→q |
q→p |
p↔q≡(p→q)∨(q→p) |
T |
T |
T |
T |
T |
T |
F |
F |
T |
F |
F |
T |
T |
F |
F |
F |
F |
T |
T |
T |
단계 |
1 |
1 |
2 |
모든 논리적 가능성에 대해 참인 명제를 항진(tautology) 또는 항진명제라고 한다.
단순명제 또는 합성명제인 P, Q에 대한 조건문 P→Q가 항진일 때 이것을 함의(implication) 또는 함의명제라 하고 P⇒Q(P는 Q를 함의한다)와 같이 나타낸다. 예를들어 다음 조건문들은 모두 함의이다.
(1) p→p
(2) p∨q→q∨p
(3) p→p∨p
(4) p∨q→q
수학 또는 논리의 명제 중 참인 것을 정리(theorem), 정리의 타당성 여부를 밝히는 과정을 증명(proof)이라고 한다.
임의의 명제 p,q에 대해 다음이 성립하고 증명은 진리표를 이용한다.
(a) 합의 법칙(law of addition) p⇒p∧q
(b) 단순화법칙(laws of simplification) p∨q⇒q,p∨q⇒p
(c) 논리합의 삼단논법(disjunctive syllogism) (p∧q)∨∼q⇒q
쌍조건문 P↔Q가 항진일 때 P, Q는 동치(equivalent)라 하고 P⇔Q로 나타낸다. 즉 P, Q에 대한 모든 논리적 가능성의 각 경우마다 이 두 명제의 진리값이 같으면 그리고 그때에만 P⇔Q이다.
임의의 명제 p,q에 대해 다음이 성립하고 증명은 진리표를 이용한다.
(a) 이중부정법칙(이중부정, law of double negation) ∼(∼p)≡p
(b) 교환법칙(commutative laws) p∨q≡q∨p,p∧q≡q∧p
(c) 멱등법칙(laws of idempotency) p∨p≡p,p∧p≡p
(d) 대우법칙(대우, contrapositive law) (p→q)≡(∼q→∼p)
드 모르간의 법칙(De Morgan's law)
임의의 명제 p,q에 대하여 다음이 성립하고 증명은 진리표를 이용한다.
∼(p∧q)≡∼p∨∼q,∼(p∨q)≡∼p∧∼q
임의의 명제 p,q,r,s에 대하여 다음이 성립하고 증명은 진리표를 이용한다.
(a) 결합법칙(associative laws) (p∨q)∨r≡p∨(q∨r),(p∧q)∧r≡p∧(q∧r)
(b) 분배법칙(distributive laws) p∨(q∧r)≡(p∨q)∧(p∨r),p∧(q∨r)≡(p∧q)∨(p∧r)
(c) 추이법칙(추이율, transitive law) (p→q)∨(q→r)⇒(p→r)
(d) 구성적 양도논법(constructive dilemmas)
(p→q)∨(r→s)⇒(p∧r→q∧s),(p→q)∨(r→s)⇒(p∨r)→(q∨s)
(e) 파괴적 양도논법(destructive dilemmas)
(p→q)∨(r→s)⇒(∼q∨∼s→∼p∨∼r),(p→q)∨(r→s)⇒(∼q∨∼s→∼p∨∼r)
(f) 긍정식 삼단논법(modus ponens) (p→q)∨p⇒q
(g) 부정식 삼단논법(modus tollens) (p→q)∨∼q⇒∼p
(h) 귀류법(배리법, reductio ad absurdum) (p→q)⇔(p∨∼q→q∨∼q)
(i) 흡수법칙(absorption laws) p∨(p∧q)≡p,p∧(p∨q)≡p
모든 논리적 가능성의 각 경우마다 진리값이 거짓인 명제를 모순(항위명제, contradiction)이라고 한다. 예를들어 p∨∼p는 모순이다.
항진명제 t, 모순명제 c, 임의의 명제 p에 대하여 다음이 성립한다.
(a) p∨t⇔p
(b) p∧t⇔t,p∨c⇔c
(c) c⇒p,p⇒t
참고자료:
집합론, You-Feng Lin, Shwu-Yeng T. Lin 저, 이흥천 옮김, 경문사
집합론, 한상언, 경문사
'미적분학과 해석학 > 집합론' 카테고리의 다른 글
[집합론] 6. 관계와 함수(1. 데카르트곱, 관계) (0) | 2019.11.04 |
---|---|
[집합론] 5. 집합의 개념(3: 첨수집합족, 러셀의 역설) (0) | 2019.11.03 |
[집합론] 4. 집합의 개념(2: 합집합, 교집합, 여집합) (0) | 2019.11.02 |
[집합론] 3. 집합의 개념(1. 집합과 부분집합, 집합의 규정) (0) | 2019.11.01 |
[집합론] 2. 초등논리(연역적 추론, 한정규칙, 타당성 밝힘, 수학적 귀납법) (0) | 2019.10.31 |