選言標準形
選言標準形(せんげんひょうじゅんけい、英: Disjunctive normal form, DNF)は、数理論理学においてブール論理での論理式の標準化(正規化)の一種であり、連言節(AND)の選言(OR)の形式で論理式を表す。加法標準形、主加法標準形、積和標準形とも呼ぶ。正規形としては、自動定理証明で利用されている。
選言標準形の論理式は、1つ以上のリテラルの論理積を1つ以上含む論理和の形式になっている論理式を選言標準形と呼ぶ。連言標準形(CNF)と同様、DNF における演算子は論理積、論理和、否定だけである。
以下の論理式は DNF の一種である。
A ∨ B {\displaystyle A\lor B}
A {\displaystyle A\!}
( A ∧ B ) ∨ C {\displaystyle (A\land B)\lor C}
( A ∧ ¬ B ∧ ¬ C ) ∨ ( ¬ D ∧ E ∧ F ) {\displaystyle (A\land \neg B\land \neg C)\lor (\neg D\land E\land F)}
しかし、以下の論理式は DNF ではない。
¬ ( A ∨ B ) {\displaystyle \neg (A\lor B)} — NOT が最も外側の演算子になっている
A ∨ ( B ∧ ( C ∨ D ) ) {\displaystyle A\lor (B\land (C\lor D))} — OR が AND の内側にある
リテラルは、変項(命題)か変項の否定であり、否定演算子はこの形でのみ出現する。全ての変項(またはその否定)を含む論理式を標準項と呼び、特に全ての変項(またはその否定)の論理積の形式になっている項を最小項と呼ぶ。従って、最小項の論理和の形式になっている論理式は、DNF である。