안녕하세요, 오늘은 집합론의 항진, 함의, 동치에 관한 내용을 다뤄보겠습니다. 어렵지 않은 내용이니 천천히 따라오시면 됩니다!
제 1장) 초등논리
1.3 항진, 함의, 동치
합성명제 p∨~p의 진리표를 확인해 보자.
| p | ~p | p∨~p |
| T | F | T |
| F | T | T |
이 진리표를 보면, 모든 경우에서 참인 것을 알 수 있다. 이와 같은 명제에서는 특별한 이름을 붙인다. 모든 논리적 가능성에 대해 참이라면 그 명제를 "항진" 또는 "항진 명제"라고 한다.
특히, P, Q에 대한 조건문 P→Q가 항진일 때, 이를 "함의" 또는 "함의 명제"라고 하고, 다음과 같이 쓴다.
P⇒Q (P는 Q를 함의한다.)
다음 조건문들은 모두 함의이다.
(직접 진리표로 알아봄으로써 확인해 보겠습니다.)
(a) p→p
p→p ≡ ~(p∧~p)
| p | ~p | p∧~p | ~(p∧~p) |
| T | F | F | T |
| F | T | F | T |
(b) p∧q → q∧p
p∧q → q∧p ≡ ~((p∧q)∧~(q∧p) )
| p | q | p∧q | q∧p | ((p∧q)∧~(q∧p) ) | ~((p∧q)∧~(q∧p) ) |
| T | T | T | F | F | T |
| T | F | F | T | F | T |
| F | T | F | T | F | T |
| F | F | F | T | F | T |
(c)와 (d)는 직접 한 번 풀어보세요.
(c) p→p∧p
(d) p∧q→q^3
수학이나 논리의 명제 중 참인 것을 정리라고 하며, 정리의 타당성을 밝히는 과정을 증명이라고 한다.
<정리> 명제 p, q에 대해 성립한다.
(a) 합의 법칙 : p⇒p∨q
(b) 단순화법칙 : p∧q⇒p, p∧q⇒q
(c) 논리합의 삼단논법 (p∨q)∧~p⇒q
(c)만 증명해 보도록 하겠습니다. 같은 방식으로 (a)와 (b)도 직접 증명해보시길 권장합니다.
[증명]
우선 명제를 진리표로 나타내보겠습니다.
| p | ∨ | q | ∧ | ~p | → | 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 |
| 1 | 2 | 1 | 3 | 2 | 4 | 1 |
그런데, 지금까지 봐왔던 진리표와는 약간 달라 보입니다. 이런 식으로 간단한 꼴의 진리표를 나타낼 수 있으며, 단계를 작성함으로써 보기 쉽고 시간 또한 절약할 수 있습니다. 작성 방법은 아래와 같습니다.
1. 우리가 증명해야 할 명제를 진리표에 적는다.
2. 끝 행에 순서에 따른 단계를 표시한다.
3. 좌측과 우측을 비교하며 마지막 단계의 진리값을 구한다.
4. 모두 참이라면, 조건문은 함의인 것을 알 수 있다.
위 진리표의 경우에도, 좌측 명제의 3단계와 우측 명제의 1단계를 비교합니다. 모든 경우에서 참이 되므로, 이 조건문은 함의임을 알 수 있습니다.
쌍조건문 PQ가 항진이면, P와 Q는 "동치"라 하며 다음과 같이 표기합니다.
P ⇔ Q ( P와 Q의 진리값이 같으면, 그리고 그때에만 P ⇔ Q)
이 때, P≡Q와 P⇔Q 는 같은 뜻을 갖기 때문에 두 기호를 상황에 맞게 사용하시면 됩니다.
<정리> 명제 p, q에 대해 성립한다.
(a) 이중부정법칙 : ~(~p) ≡ p
(b) 교환법칙 : p∧q ≡ q∧p, p∨q ≡ q∨p
(c) 멱등법칙 : p∧p ≡ p, p∨p ≡ p
(d) 대우법칙 : p→q ≡ (~q→~p)
이 역시 (d)만 증명해 보도록 하겠습니다. 같은 방법으로 나머지도 증명이 가능합니다.
진리표를 우선 작성해 보겠습니다.
| p | → | q | ↔ | ~q | → | ~p |
| T | T | T | T | F | T | F |
| T | F | F | T | T | F | F |
| F | T | T | T | F | T | T |
| F | T | F | T | T | T | T |
| 1 | 2 | 1 | 4 | 2 | 3 | 2 |
우리가 궁극적으로 구해야 하는 값은 ↔ 에서 T가 나오는지이므로 좌측과 우측을 비교하면 됩니다. 이 때, ~p와 ~q는 p와 q의 부정이므로 단계 1이 아닌, 단계 2라고 생각하셔야 합니다. 모두 참이므로 동치임을 알 수 있습니다.
<정리> 드모르간의 법칙, 명제 p,q에 대해 성립한다.
~(p∧q)≡~p∨~q
~(p∨q)≡~p∧~q
둘이 증명 과정이 같으므로, 첫 번째만 증명하겠습니다. 마찬가지로 진리표를 작성하게 되면 다음과 같습니다.
| ~ | p | ∨ | q | ↔ | ~p | ∧ | ~q |
| F | T | T | T | T | F | F | F |
| T | T | F | F | T | F | T | T |
| T | F | F | T | T | T | T | F |
| T | F | F | F | T | T | T | T |
| 3 | 1 | 2 | 1 | 4 | 2 | 3 | 2 |
따라서 동치관계가 됩니다.
<정리> 명제 p,q,r에 대해 성립한다.
(a) 결합법칙 : (p∧q)∧r≡p∧(q∧r), (p∨q)∨r≡p∨(q∨r)
(b) 분배법칙 : p∧(q∨r)≡(p∧q)∨(p∧r), p∨(q∧r)≡(p∨q)∧(p∨r)
(c) 추이법칙 : (p→q)∧(q→r)⇒(pr)
증명은 넘어가겠습니다. 위와 같은 방식으로 증명이 가능합니다.
<정리> 명제 p,q,r,s에 대해 성립한다.
(a) 구성식 양도논법
(p→q)∧(r→s)⇒(p∨r→q∨s)
(p→q)∧(r→s)⇒(p∧r→q∧s)
(b) 파괴식 양도논법
(p→q)∧(r→s)⇒(~q∨~s→~p∨~r)
(p→q)∧(r→s)⇒(~q∧~s→~p∧~r)
<정리> 명제 p,q에 대해 성립한다.
(a) 긍정식 삼단논법 : (p→q)∧p⇒q
(b) 부정식 삼단논법 : (p→q)∧~q⇒~p
(c) 귀류법 : (p→q)⇒(p∧~q→q∧~q)
시간 들여 한 번씩 증명해 보시는 것을 권장합니다. 왜 이런 결과가 나오는지 쉽게 알 수 있다고 생각됩니다.
오늘의 내용은 여기까지입니다.
중, 고등학교 과정에서 배우는 내용이 많아 가볍게 넘기실 수 있는 내용이라고 생각됩니다. 하지만 앞으로 이 정리와 정의들이 있어야 풀 수 있는 문제가 많아지고, 특히 이번 장은 모든 문제 풀이의 기초가 되기 때문에 자주 복습해 보시는 것을 권장 드립니다. 오늘은 여기서 마치겠습니다. 다음은 모순과 연역적 추론, 한정규칙에 대해 다뤄보겠습니다. 글 끝까지 봐주셔서 감사합니다!
'수학 > 집합론' 카테고리의 다른 글
| [집합론] 1.1~1.2 초등논리 - 명제와 결합자 (1) | 2023.11.18 |
|---|