[이산수학] 논리적 동치 (logical equivalance)

논리적 동치 (logical equivalence)

논리적 동치 (logical equivalence): 두 개의 명제 $p, q$의 쌍방 조건 $p ↔ q$가 항진 명제이면, 두 명제 $p, q$는 논리적 동치라 하고 $p ≡ q$ 또는 $p ⇔ q$라고 표시한다. 즉, 명제 $p$와 $q$는 같은 논리값을 가진다는 의미이다.

• 두 명제가 논리적 동치일 경우는 두 명제의 논리값이 서로 같으므로 하나의 명제가 다른 명제를 대신해서 사용할 수 있습니다. 이를 이용해 어떤 복잡한 명제를 더 간단한 명제로 만들어 주기 위해 논리적 동치 관계인 다른 명제를 사용할 수 있습니다.

 

드 모르간 법칙과 같이 명제들의 동치 관계에 대한 여러 가지 기본 법칙들이 있습니다. 이런 기본 법칙들을 이용하면 복잡한 합성 명제를 간단하게 나타낼 수 있습니다.

법칙 이름	논리적 동치 관계
교환 법칙 (Commutative laws)	$p \lor q \iff q \lor p$ $p \land q \iff q \land p$ $p ↔ q \iff q ↔ p$
결합 법칙 (Associative laws)	$(p \lor q) \lor r \iff p \lor (q \lor r)$ $(p \land q) \land r \iff p \land (q \land r)$
분배 법칙 (Distributive laws)	$p \lor (q \land r) \iff (p \land q) \lor (p \land r)$ $p \land (q \lor r) \iff (p \land q) \lor (p \land r)$
항등 법칙 (Identity laws)	$p \lor T \iff T$ $p \lor F \iff p$ $p \land T \iff T$ $p \land F \iff F$
부정 법칙 (Negation laws)	$\sim T \iff F$ $\sim F \iff T$ $p \land (~p) \iff T$ $p \lor (~p) \iff F$
이중 부정 법칙 (Double negative laws)	$\sim(\sim p) \iff p$
멱등 법칙 (Idempotent laws)	$p \lor p \iff p$ $p \land p \iff p$
드 모르간 법칙 (De morgan's laws)	$\sim(p \lor q) \iff (\sim p) \land (\sim q)$ $\sim(p \land q) \iff (\sim p) \lor (\sim q)$
흡수 법칙 (Absorption laws)	$p \lor (p \land q) \iff p$ $p \land (p \lor q) \iff p$