| 항진명제, 모순, 불확정명제 |
항진명제(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-여왕 문제, 스도쿠 같은 퍼즐이 만족가능성 문제를 모형화 한 예시다.