[이산수학] 1.5 추론 규칙

증명... 정말... 하....

 

증명 싫어요.

 

시작하겠습니다

 

여기서는 증명애 대하여 살펴 볼 건데 수학에서 증명이란 수학적 진술의 참을 입증하는 정당한 논증을 말합니다.

 

논증이란 명제들의 순열 입니다.

 

논증의 최종 명제를 빼고 나머지 모든 명제들은 전제라고 하고, 최종 명제를 결론이라 합니다.

 

전제가 모두 참일 때 결론이 참이면 그 논증의 형식은 정당하다고 할 수 있습니다.

 

명제 논리에 대한 추론 규칙들을 보겠습니다.

 

 

이 규칙들을 활용한 증명방법을 보여드리겠습니다.

 

"It is not sunny this afternoon and it is colder than yesterday"

 

"We will go swimming only if it is sunny"

 

"If we do not go swimming, then we will take a canoe trip"

 

"If we take a canoe trip, then we will be home by sunset"

 

이 가정들이 "We will be home by sunset" 이라하는 결론을 도출 함을 보여라.

 

p가 "It is sunny this afternoon"

 

q가 "it is colder than yesterday"

 

r이 "We will go swimming"

 

s가 "We will take a canoe trip"

 

t가 "We will be home by sunset"

 

이라 하면 가정들은 ￢p ∧ q, r → p, ￢r → s, s → t 이가 되고 결론은 t가 된다.

 

단계            이유

 

1. ￢p ∧ q          가정

2. ￢p                단계 1을 사용하여 단순화

3.  r → p            가정

4. ￢r                 단계 2, 3을 사용하여 부정 논법

5. ￢r → s           가정

6.  s                   단계 4, 5를 사용하여 긍정 논법

7. s → t             가정

8.  t                   단계 6, 7를 사용하여 긍정 논법

 

이렇게 됩니다.

 

그냥 형태를 보고 쓸 수 있는 추론 규칙을 쓰면 됩니다.

 

이걸 일일이 진리표를 써서 하려면 변수가 5개니까 32줄을 써야겠지요.

 

하지만 짜증나는 증명을 하면 금방 뚝딱 해버립니다.

 

 

 

이런 증명도 하다보면 오류가 납니다.

 

오류에 대해 알아볼게요.

 

오류는 먼저 '결론 단언의 오류' 가 있습니다.

 

이 오류는 예를 들겠습니다.

 

두 명제 A(x) 와 B(x) 가 있는데

 

A(x)가 참이면 B(x)가 참인데, B(x)가 참이라고 A(x)를 참이라고 생각하는 오류 입니다.

 

역은 반드시 참이 될 수 없는거랑 같습니다.

 

두번째로 '가정 부정의 오류'가 있습니다.

 

이 오류도 예를 들어볼게요.

 

두 명제 p, q가 있을 때, "p이면 q인데 p가 아니니까 q도 아니겠지?"

 

이렇게 생각하는 겁니다.

 

어떻게 보면 얼척 없는데 실수 할 수도 있겠죠

 

 

 

한정기호를 사용한 명제에 대한 추론규칙과 예를 들고 끝내겠습니다.

 

 

이렇게 있고 좀 까다로워 보이는데 쓰는건 되게 간단합니다.

 

예를 들게요.

 

"A student in this class has not read the book"

 

"Everyone in this class passed the first exam"

 

이라고 하는 가정들이 있으면 "Someone who passed the first exam has not read the book"

 

이라는 결론을 도출함을 보여라.

 

C(x)가 "x is in this class"

 

B(x)가 "x has read the book"

 

P(x)가 "x passed the first exam"

 

이라고 하면 가정들은 ∃x(C(x) ∧ ￢B(x)) 이고 ∀x(C(x) → P(x)) 로 나타낼 수 있다.

 

단계                        이유

 

1. ∃x(C(x) ∧ ￢B(x))           가정으로부터

2. C(a) ∧ ￢B(a)               1 로부터 단순화

3. C(a)                           2 로부터 단순화

4.∀x(C(x) → P(x))              가정으로부터

5. C(a) → P(a)                 4 로부터 전칭 예시화

6. P(a)                           3과 5로부터 긍정 논법

7. ￢B(a)                        2 로부터 단순화

8. P(a) ∧ ￢B(a)               6과 7로부터 논리곱

9. ∃x(P(x) ∧ ￢B(x))           8 로부터 존재 일반화

 

 

감사합니다