2.. 명제의 증명
항진(항상 참, tautology): 모든 논리적 가능성에 대하여 참인 명제를 항진이라 한다.
|
p ∼q |
p∨∼q |
|
T F F T |
T T |
이 표를 보면 명제 p∨∼q는 각 경우 즉 모든 논리적 가능성에 대하여 항상 참인 것을 알 수 있다. 이런 명제를 항진이라 부른다. P→Q가 항진일 때 이것을 함의(implication)라 하고 P⇒Q 라고 표시한다.
예 1. (p→q)∧p⇒q를 진리표로써라.
|
p q |
p→q |
∧ |
p |
→ |
q |
|
T T T F F T F F |
T F T T |
T F F F |
T T F F |
T T T T |
T F T F |
|
순서 |
1 |
3 |
2 |
5(항진) |
4 |
내가 학기말 시험에 A를 맞으면 이 과목에 A를 주겠다고 교수가 말했다.
나는 학기말고사에 A를 맞았다. 나는 이 과목에 A를 맞을 수 있는가?
이런 것을 3단 긍정법(정리 5 가)이라고 말 한다.
예 2. (p→q)∧(q→r)⇒(p→r)를 진리표를 써서 증명하라.
|
p q r |
p→q |
∧ |
q→r |
→ |
p→r |
|
T T T T T F T F T T F F F T T F T F F F T F F F |
T T F F T T T T |
T F F F T F T T |
T F T T T F T T |
T T T T T T T T |
T F T F T T T T |
|
순서 |
1 |
3 |
2 |
5 |
4 |
여름이면 풀들이 파랗게 된다. 풀이 파랗게 되면 날씨가 따뜻해진다.
따라서 여름이면 날씨가 따뜻해 진다. 이런 논법을 삼단논법 또는 추이법칙(정리 4 다)이라고 한다.
p → q 라는 조건 문네 대해 ∼p → ∼q를 역(inverse)이라 하고, ∼q → ∼p를 대우 (contrapositive)라고 한다.
p와 q의 진리값이 같으면 p와 q는 동치(equivalent)라 하고 p≡q로 나타낸다.
조건문과 그 역 및 대우가 서로 동치인지 알아 보아라.
예 3. 조건문: 오늘 날씨가 좋으면 나는 고기 잡으러 간다.
역 : ?
대우 : ?
수학이나 논리에서 정리(theorem)는 참인 명제이다. 이런 참인 정리의 정당성을 밝히는 것을 증명(proof)라 한다.
정리 1.
가. 합의 법칙: p⇒ p∨q
나. 단순화 법칙: p∧q⇒ p, p∧q⇒ q
다. 논리적 3단법: (p∨q)∧∼p⇒ q
정리 2.
가. 2중 부정법: ∼(∼p)≡p
나. 교환법칙: p∧q≡q∧p, p∨q≡q∨p
다. 멱등법칙: p∧p≡p, p∨p≡p
라. 대우법칙: (p→q)≡(∼q→∼p)
정리 3. 드 모르간의 법칙(De Morgan's laws)
∼ (p∧q)≡∼p∨∼q, ∼(p∨q)≡∼p∧∼q
정리 4.
가. 결합법칙: (p∨q)∨r≡p∨(q∨r), (p∧q)∧r≡p∧(q∧r)
나. 분배법칙: p∧(q∨r)≡(p∧q)∨(p∧r), p∨(q∧r)≡ (p∨q)∧(p∨r)
다. 추이법칙: (p→q)∧(q→r)⇒(p→r)
정리 5.
가. 삼단긍정법: (p→q)∧p⇒q
나. 삼단부정법: (p→q)∧∼q⇒∼p
연습문제 2.1.
다음을 증명하여라.
1. ∼ (p∧q)≡∼p∨∼q (드 모르간의 법칙)
2. p∧(p∨r)≡p, p∨(p∧r)≡ p (흡수법칙)
3. (p∧q)∧r≡p∧(q∧r)
4. (p→q)⇒(p∧r→q∧r)
5. 드모르간의 법칙을 써서 명제 "신이 존재하지 않거나 나는 바보이다"의 부정을 일상 용어로 써라.
항진에 반하여 모든 논리적 가능성의 각 경우마다 진리값이 거짓인 명제를 항위(항상 거짓) 또는 모순(contradiction)이라고 한다. 이를테면 p∧∼p는 항상 모순이다. 진은 t, 항위는 c로 나타낸다.
정리 6.
가. p∧t ⇔ p, p∨t ⇔ t
나. p∨c ⇔ p, p∧c ⇔ c
다. c⇒p, p⇒t
연습문제 2.2.
진리표를 이용하여 다음 1-5를 증명하라.
1. p∨t⇔t와 p∧c⇔c 2. ??t⇔c와 ??c⇔t
3. (p∧q→c)⇔(p→q) 4. p∧(p→q)∧(p→??q)⇔c
5. 임의의 r에 대하여 (p→q)⇒(p∨r→q∨r)
명제의 증명을 진리표에 의하지 않고 이미 증명한 정리들을 이용하여 연역적으로 추론(deductive reasoning)할 수가 있다.
예 (p→q)≡(∼q→∼p)를 연역적 추리방법으로 증명하라.
(p→q)≡∼(p∧∼q) 조건문의 정의
≡∼(∼q∧p) 교환법칙
≡∼[∼q∧∼(∼p)] 이중 부정법
≡(∼q→∼p) 조건문의 정의
∴ (p→q)≡(∼q→∼p)
연습문제 2.3.
연역적 추론을 이용하여1-5를 증명하라.
1. 삼단긍정법: (p→q)∧p⇒q 2. 삼단부정법: (p→q)∧∼q⇒∼p
3. 배리법: (p→q)⇔[(p∧∼q)→c] 4. 이출법칙: (p∧q→r)≡[p→(q→r)]
5. (p→r)∨(q→s)≡(p∧q→r∨s)
종합정리
1. 항진, 함의 , 항위, 두 명제가 동치라는 용어의 뜻을 아는가?
2. 여러 가지 정리나 명제를 진리표로 그 진위를 밝힐 수가 있는가?
3. 연역적 추론이란 무슨 뜻인가?
4. 진리표를 사용하지 않고 연역적 추론으로 정리를 증명할 수 있는가?