[이산수학] 1.2 명제의 동치

며칠 동안 글이 없었는데요.

 

하기 싫어서 그랬습니다.

 

그래도 전 끝까지 할거에요.

 

 

 

먼저 '동치'는 '같다' 라고 봐도 무방합니다.

 

그래서 두 명제가 모든 경우에 대하여 같은 진리값을 가지면 그 명제들을 '논리적으로 동치' 라고 말합니다.

 

그리고 두 복합명제 p, q에 대하여 p↔q가 항진이면, p와 q는 논리적으로 동치라 하고, p≡q(p⇔q) 로 나타냅니다.

 

아 그리고 항진과 모순을 설명 하자면 항진은 p∨￢p 처럼 항상 참인것을 항진이라 하고,

p∧￢p 처럼 항상 거짓인 식을 모순이라 합니다.

 

p	q	p∨￢p	p∧￢p
T	F	T	F
F	T	T	F

 

 

예제들을 한번 풀어볼게요.

 

1) ￢(p∨q) 와 ￢p∧￢q 가 논리적 동치임을 보여라.

 

p	q	p∨q	￢(p∨q)	￢p	￢q	￢p∧￢q
T	T	T	F	F	F	F
T	F	T	F	F	T	F
F	T	T	F	T	F	F
F	F	F	T	T	T	T

 

이 증명은 드모르간 법칙중 하나입니다. 알면 좋아요.

 

2) p→q 와 ￢p∨q 가 논리적 동치임을 보여라.

 

p	q	￢p	p→q	￢p∨q
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

 

여기서 p→q ≡ ￢p∨q 이거 외워두면 편합니다.

ps) p↔q ≡ (p→q)∧(q→p)

 

 

 

많이 쓰이는 논리적 동치식도 알아둡시다.

 

 

동치식	명칭
p∧T ≡ p p∨F ≡ p	동일법칙
p∨T ≡ T p∧F ≡ F	지배법칙
p∨p ≡ p p∧p ≡ p	등멱법칙
￢(￢p) ≡ p	이중부정법칙
p∨q ≡ q∨p p∧q ≡ p∨q	교환법칙
(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∨(p∧q) ≡ p p∧(p∨q) ≡ p	흡수법칙
￢(p∧q) ≡ ￢p∨￢q ￢(p∨q) ≡ ￢p∧￢q	드 모르간법칙
p∨￢p ≡ T p∧￢p ≡ F	부정법칙

 

꽤 많은데 그래도 몇개는 보면 당연한 말인것들도 많습니다. ㅎㅎ

 

 

 

조건문을 포함한 논리적 동치

 

p→q ≡ ￢p∨q

p→q ≡ ￢q→￢p

p∨q ≡ ￢p→q

p∧q ≡ ￢(p→￢q)

￢(p→q) ≡ p∧￢q

 

(p→q)∧(p→r) ≡ p→(q∧r)

(p→r)∧(q→r) ≡ (p∨q)→r

(p→q)∨(p→r) ≡ p→(q∨r)

(p→r)∨(q→r) ≡(p∧q)→r

 

 

 

상호조건문을 포함한 논리적 동치

 

p↔q ≡ (p→q)∧(q→p)

p↔q ≡ ￢p↔￢q

p↔q ≡ (p∧q)∨(￢p∧￢q)

￢(p↔q) ≡ p↔￢q

 

 

 

뭐 한것도 없지만 마지막으로 명제의 만족 가능성 입니다.

 

어떤 복합명제에 대하여 그 명제가 참이 되도록 그 명제의 변수들에 진리값을 할당 할 수 있을때, 그 명제가 '만족가능'하다 라고 합니다. 그렇지 않으면 '만족불가능'입니다.

 

복합명제가 참이 되도록 하는 진리값의 할당을 찾았으면 만족가능함을 증명한 것이다.

 

복합명제가 만족불가능함을 보일라면 변수들에 어떤값을 할당 하더라도 거짓임을 보여야합니다.

 

하지만 고려해야 할 상황들이 많아지면 진리표는 비효율적이다.

 

예를 들면

 

1. (p∨￢q)∧(q∨￢r)∧(r∨￢p)

2. (p∨q∨r)∧(￢p∨￢q∨￢r)

3. (p∨￢q)∧(q∨￢r)∧(r∨￢p)∧(p∨q∨r)∧(￢p∨￢q∨￢r)

 

이 명제들을 살펴 본다.

1번은 p,q,r 이 모두 같은 진리값이면 이 명제가 참이므로 만족가능하다.

2번은 p,q,r 3개의 변수중 적어도 하나가 참이면 명제가 참이므로 만족가능하다.

3번은 1번 과 2번을 보면 벌써 답이 나온다. 만족 불가능하다.

 

 

 

 

 

블로그 글 하나 쓰기 참 어렵네여

 

다음에 봅시다.

 

 

 ㅃ