選言標準形
この形式は、真理値表で出力が「真」となる行を最小項として取り出したものを論理和で繋いだものであり、その真理値表に対応する論理式となっている。つまり、真理値表で表されるものは全て選言標準形の論理式で表せ、組み合わせ回路も選言標準形で表せる。
任意の論理式を DNF に変換するには、二重否定の除去、ド・モルガンの法則、分配法則といった論理的に等価な変換を行う法則を使う。全ての論理式は選言標準形に変換できる。しかし、元の論理式によっては、DNF への変換によって論理式が極めて長大になることもある。例えば、次の論理式を DNF に変換すると、2 個の項を書き連ねることになる。
( X 1 ∨ Y 1 ) ∧ ( X 2 ∨ Y 2 ) ∧ ⋯ ∧ ( X n ∨ Y n ) {\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}
以下は、DNF の形式文法である:
<or> → ∨
<and> → ∧
<not> → ¬
<disjunct> → <conjunct>
<disjunct> → <disjunct> <or> <conjunct>
<conjunct> → <literal>
<conjunct> → (<conjunct> <and> <literal>)
<literal> → <term>
<literal> → <not><term>
ここで <term> は任意の変項である。