명제의 동치(equivalent)

항진명제, 모순, 불확정명제

 

항진명제(tautology): 항상 참인 명제

모순(contradiction): 항상 거짓인 명제

불확정명제(contingency): 항진명제도 아니고 모순도 아닌 명제

 

예)

$p$	$\neg q$	$p \lor\neg q$	$p \land \neg q$
$T$	$F$	$T$	$F$
$F$	$T$	$T$	$F$

$p \lor\neg q$는 항상 참이므로 항진명제이고, $p \land \neg q$는 항상 거짓이므로 모순이다.

 

---

 

논리적 동치

 

두 명제 $p$, $q$에 대하여 $p \leftrightarrow q$가 항진명제이면 $p$와 $q$는 논리적 동치이며, $p \equiv q$는 $p$와 $q$가 논리적 동치(logically equvalent)임을 나타낸다.

 

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

$p \rightarrow q \equiv \neg p \lor q$

 

$p$	$q$	$\neg p$	$\neg p \lor q$	$p \rightarrow q$
$T$	$T$	$F$	$T$	$T$
$T$	$F$	$F$	$F$	$F$
$F$	$T$	$T$	$T$	$T$
$F$	$F$	$T$	$T$	$T$

 

기타 논리적 동치

항등 법칙(Identiry Laws)	$p \land T \equiv p$ $p \lor F \equiv p$
지배 법칙(Domination Laws)	$p \lor T \equiv T$ $p \land F \equiv F$
등멱 법칙(Idempotent Laws)	$p \lor p \equiv p$ $p \land p \equiv p$
이중 부정 법칙(Double Negation Law)	$\neg (\neg p) \equiv p$
부정 법칙(Negation Laws)	$p \lor \neg p \equiv T$ $p \land \neg p \equiv F$
교환 법칙(Commutative Laws)	$p \lor q \equiv q \lor p$ $p \land q \equiv q \land p$
결합 법칙(Associative Laws)	$(p \lor q) \lor r \equiv p \lor (q \lor r)$ $(p \land q) \land r \equiv p \land (q \land r)$
분배 법칙(Distributive Laws)	$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
드 모르간 법칙(De Morgan's Laws)	$\neg (p \land q) \equiv \neg p \lor \neg q$ $\neg (p \lor q) \equiv \neg p \land \neg q$
흡수 법칙(Absorption Laws)	$p \lor (p \land q) \equiv p$ $p \land (p \lor q) \equiv p$

 

위의 알려진 동치를 활용하면 진리표를 사용하지 않아도 새로운 논리적 동치를 만들어낼 수 있다. 

 

---

명제의 만족 가능성

 

복합명제가 참이 되도록 명제 변수에 진리값을 할당할 수 있으면 그 명제는 만족가능(satisfiable)하다.

명제 변수에 값을 주더라도 명제가 거짓이면 만족불가능(unsatisfiable)하다.

 

다양한 분야의 많은 문제들이 만족가능성 문제로 모형화될 수 있다. n-여왕 문제, 스도쿠 같은 퍼즐이 만족가능성 문제를 모형화 한 예시다.