否定標準形

否定標準形︵ひていひょうじゅんけい、英: negation normal form, NNF︶とは、否定記号 $\lnot$$\lnot$が原子論理式のみにかかり、他には選言記号 $\lor$$\lor$と連言記号 $\land$$\land$のみが論理記号として用いられる形の論理式を指す。

命題論理もしくは述語論理においては、いかなる論理式も、ド・モルガンの法則を用い否定演算子を内側に押し込む操作を繰り返すことによって、論理的に等価な否定標準形に置き換えることができる。この操作の具体例を次に示す。

$\lnot (\forall x.G)\to \exists x.\lnot G$$\lnot (\forall x.G)\to \exists x.\lnot G$
$\lnot (\exists x.G)\to \forall x.\lnot G$$\lnot (\exists x.G)\to \forall x.\lnot G$
$\lnot \lnot G\to G$$\lnot \lnot G\to G$
$\lnot (G_{1}\land G_{2})\to (\lnot G_{1})\lor (\lnot G_{2})$$\lnot (G_{1}\land G_{2})\to (\lnot G_{1})\lor (\lnot G_{2})$
$\lnot (G_{1}\lor G_{2})\to (\lnot G_{1})\land (\lnot G_{2})$$\lnot (G_{1}\lor G_{2})\to (\lnot G_{1})\land (\lnot G_{2})$
連言標準形(conjunctive normal form)と選言標準形(disjunctive normal form)は否定標準形の性質を満たしている。任意の否定標準形の論理式は、論理式の結合法則と分配法則による操作によって、論理的に等価な連言標準形や選言標準形に変形することができる。

関連項目

• 連言標準形
• 選言標準形