이산수학 1.3 Propositional Equivalences 명제 동치

chapter 1. The Foundations: Logic and Proofs

 

1.3 Propositional Equivalences 명제 동치(section 1.3)

 

Tautologies, Contradictions, and Contingencies

• tautology : 언제나 true 값을 갖는 명제(항진 명제) ex. p ∨¬p
• contradiction : 언제나 false 값을 갖는 명제(모순 명제) ex. p ∧¬p   
• contingency : p와 같이 true가 되기도 하고 false가 되기도 하는 명제

 

Logically Equivalent

• 만약 *p ↔ q가 항진명제라면, 두 개의 결합 명제 p와 q는 논리적으로 동치이다. 
• 이를 p ⇔ q 또는 p ≡ q 로 나타낸다.
• 진리표에서 각 열의 값이 동일하다면, p와 q는 동치이다.
• ¬p ∨ q는 p → q와 동치이다.

¬ p  ∨  q는  p  →  q와 동치임을 나타내는 진리표

 

* p↔q

• 쌍방조건명제 (biconditional)
• if and only if, iff
• 오직 p인 경우에만 q이다.
• p와 q가 동치이다.
• p이면 q이고 q이면 p이다.
• (p → q) ∧ (q → p)와 동치이다. p와 q의 진리값이 같을 때만 True.

 

De Morgan’s Laws

 

Key Logical Equivalences

항등법칙 Identity Laws

p∧T ≡ p
p∨F ≡ p

지배법칙 Domination Laws
p∨T ≡ T
p∧F ≡ F

등멱법칙 Idempotent laws
p∨p ≡ p
p∧p ≡ p

이중부정법칙 Double Negation Law
￢(￢p) ≡ p

 

부정법칙 Negation Laws

p∨￢p ≡ T
p∧￢p ≡ F

교환법칙 Commutative Laws
p∨q ≡ q∨p
p∧q ≡ p∨q

결합법칙 Associative Laws
(p∨q)∨r ≡ p∨(q∨r)
(p∧q)∧r ≡ p∧(q∧r)

분배법칙 Distributive Laws
p∨(q∧r) ≡ (p∨q)∧(p∨r)
p∧(q∨r) ≡ (p∧q)∨(p∧r)

흡수법칙 Absorption Laws
p∨(p∧q) ≡ p
p∧(p∨q) ≡ p

* 항등 법칙과 지배 법칙 진리표

P	T	F	P∧T	P∧F	P∨T	P∧F
T	T	F	T	T	T	F
T	T	F	T	T	T	F
F	T	F	F	F	T	F
F	T	F	F	F	T	F

• P∧T ≡ P / P∧F ≡ P 항등법칙
• P∨T ≡ T/ P∧F ≡ F 지배 법칙

 

More Logical Equivalences

 

Equivalence Proofs

 

Questions on Propositional Satisfiability

 

Notation

 

---

출처: Discrete Mathematics and Its Applications (K. H. Rosen 저, McGraw Hill, 2007)