Module 02

同値変形と標準形

含意の消去・ド・モルガン・二重否定・分配法則を一段階ずつ適用し、CNF / DNF への変形手順を体験する。

主要な同値変形

含意の消去: $A \to B \equiv \lnot A \lor B$
ド・モルガン: $\lnot(A \land B) \equiv \lnot A \lor \lnot B$ 、 $\lnot(A \lor B) \equiv \lnot A \land \lnot B$
二重否定: $\lnot\lnot A \equiv A$
分配法則: $A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$ 、 $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$

初期式 $(P \to Q) \to R$ から出発し、適用可能なルールだけがアクティブになる。一段階ずつ操作して、最終的に CNF へ落とせるか試してみよう。

現在の式

\left(P \to Q\right) \to R

任意の命題論理式は同値変形によって、リテラルの選言の連言（CNF）または連言の選言（DNF）の形に直せる。これは反駁手続き（モジュール 4）の前段としても重要。

\text{CNF: } \bigwedge_{i} \bigvee_{j} \ell_{ij},\quad \text{DNF: } \bigvee_{i} \bigwedge_{j} \ell_{ij}