[이산수학] 동치관계

---

동치(Equivalence)

• 논리적으로 일치한다는 의미
• 흔히 동치는 같은 의미를 가진 더 쉬운 명제를 발견하는 데 사용한다.
• 굉장히 복잡해 보이는 합성명제라도 간단한 명제로 바꿀 수 있다.

논리적 동치(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
교환 법칙 (Commutative laws)	p∨q ≡ q∨p p∧q ≡ q∧p
결합 법칙 (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)
드 모르간 법칙 (De Morgan's laws)	￢(p∧q) ≡ ￢p∨￢q ￢(p∨q) ≡ ￢p∧￢q
흡수 법칙 (Absorption laws)	p∨(p∧q) ≡ p p∧(p∨q) ≡ p
부정 법칙 (Negation laws)	p∨￢p ≡ T p∧￢p ≡ F
함축 법칙(Implication law)	p → q ≡ ￢p∨q

---

예시

(p → q)∧(p → ￢q)

1. 함축 법칙
   • (￢p∨q)∧(￢p∨￢q)
2. 분배 법칙
   • ￢p∨(q∧￢q)
3. 부정 법칙
   • ￢p∨F
4. 항등 법칙
   • ￢p

---