[이산수학] 논리적 동치, Modus Ponens, Modus Tollens

1. Logical Equivalence(논리적 동치)

두 명제 p, q에 대하여 가능한 모든 경우에 대해 같은 진리값을 가지면 p, q는 논리적 동치라고 부른다.

기호로는 p ≡ q로 표현한다.

 

 

conditional - disjunction equivalence(조건 - 논리합 동치): 

p → q ≡ ¬p ∨ q (증명은 진리표로 가능)

문제풀때 →가 보이면 항상 바꿔주자!

 

Demorgan's Law(드 모르간 법칙):

¬(p∧q) ≡  ¬p ∨ ¬q

¬(p∨q) ≡  ¬p ∧ ¬q

전체의 부정과 각각의 부정에 관한 법칙 (증명은 진리표로 가능)

 

commutative Law(교환법칙):

p ∨ q ≡ q ∨ p 

p ∧ q ≡ q ∧ p

순서를 바꿔도 상관없다.

 

associative Law (결합법칙):

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

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

같은 기호끼리는 어떤 것을 먼저 연산해도 상관없다.

 

distribute Law (분배법칙):

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

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

 

simplification(지배법칙):

p ∧ q ≡ p 

p ∧ q ≡ q 

∧ 관계에선 둘 다 True값이어야 전체가 True이므로, 하나를 빼도 역시 True이므로 논리적 동치다.

 

absorption(흡수법칙):

p ∧ (p ∨ q) ≡ p 

p ∨ (p ∧ q) ≡ p

지배법칙의 응용

 

negation (부정법칙):

p ∧ ¬p = c (모순명제, 무조건 거짓)

p ∨ ¬p = t (항진명제, 무조건 참)

자기 자신의 부정과 and 연산시 무조건 False, or연산시 무조건 True

 

 

논리적 동치 예제: (이때 T는 True, F는 False)

(T → (r ∨ p)) → ((¬r ∨ k ) ∧ ¬k) ≡ True일때,
(T → (r ∨ p)) → ((¬r ∧ ¬k) ∨ (k ∧ ¬k)) ≡ T

(T → (r ∨ p)) → ((¬r ∧ ¬k) ∨ F) ≡ T

(T → (r ∨ p)) → ((¬r ∧ ¬k)) ≡ T

¬(T → (r ∨ p)) ∨ (¬r ∧ ¬k) ≡ T

¬(¬ T ∨ (r ∨ p)) ∨(¬r ∧ ¬k) ≡ T

¬(F ∨ (r ∨ p)) ∨ (¬r ∧ ¬k) ≡ T

(¬r ∧¬p) ∨ (¬r ∧ k ) ≡ T

¬r ∧ ¬(p ∧ k) ≡ T

 

∴ ¬r = T

 

 

 

Modus Ponens:

p 이고

p → q 이면

∴ q

 

예시:

you are in this class (p)

if you are in this class , you will get a grade (p → q)

∴you will get a grade (q)

 

 

Modus Tollens: 

¬q 이고

p → q 이면

∴ ¬p

 

예시:

you will not get a grade (¬q)

if you are in this class , you will get a grade (p → q)

∴you are not in this class (¬p)

 

 

generalization: 

p 이면

∴ p ∨ q

 

 

specialization: 

p ∧ q 이면

∴ p

 

 

 

 

 

 

 

reference: https://m.blog.naver.com/junhyuk7272/221814491510