選言標準形のソースを表示

{{Expand English|Disjunctive normal form|date=2024-04}}
'''選言標準形'''（せんげんひょうじゅんけい、{{lang-en-short|Disjunctive normal form, DNF}}）は、[[数理論理学]]において[[ブール論理]]での[[論理式 (数学)|論理式]]の標準化（正規化）の一種であり、[[連言]]節(AND)の[[選言]](OR)の形式で論理式を表す。'''加法標準形'''、'''主加法標準形'''、'''積和標準形'''とも呼ぶ。正規形としては、[[自動定理証明]]で利用されている。

== 概要 ==
選言標準形の論理式は、1つ以上のリテラルの[[論理積]]を1つ以上含む[[論理和]]の形式になっている論理式を選言標準形と呼ぶ。[[連言標準形]](CNF)と同様、DNF における演算子は[[論理積]]、[[論理和]]、[[否定]]だけである。

以下の論理式は DNF の一種である。
:<math>A \lor B</math>
:<math>A\!</math>
:<math>(A \land B) \lor C</math>
:<math>(A \land \neg B \land \neg C) \lor (\neg D \land E \land F)</math>

しかし、以下の論理式は DNF ではない。

:<math>\neg(A \lor B)</math> &mdash; NOT が最も外側の演算子になっている
:<math>A \lor (B \land (C \lor D))</math> &mdash; OR が AND の内側にある

'''リテラル'''は、変項（命題）か変項の[[否定]]であり、否定演算子はこの形でのみ出現する。全ての変項（またはその否定）を含む論理式を'''標準項'''と呼び、特に全ての変項（またはその否定）の[[論理積]]の形式になっている項を'''最小項'''と呼ぶ。従って、最小項の[[論理和]]の形式になっている論理式は、DNF である。この形式は、[[真理値表]]で出力が「真」となる行を最小項として取り出したものを論理和で繋いだものであり、その真理値表に対応する論理式となっている。つまり、真理値表で表されるものは全て選言標準形の論理式で表せ、[[論理回路#組み合わせ回路|組み合わせ回路]]も選言標準形で表せる。

任意の論理式を DNF に変換するには、[[二重否定の除去]]、[[ド・モルガンの法則]]、[[分配法則]]といった論理的に等価な変換を行う法則を使う。全ての論理式は選言標準形に変換できる。しかし、元の論理式によっては、DNF への変換によって論理式が極めて長大になることもある。例えば、次の論理式を DNF に変換すると、2<sup>n</sup> 個の項を書き連ねることになる。

:<math>(X_1 \lor Y_1) \land (X_2 \lor Y_2) \land \dots \land (X_n \lor Y_n)</math>

以下は、DNF の[[形式文法]]である:
# &lt;or&gt; &rarr; &or;
# &lt;and&gt; &rarr; &and;
# &lt;not&gt; &rarr; &not;
# &lt;disjunct&gt; &rarr; &lt;conjunct&gt;
# &lt;disjunct&gt; &rarr; &lt;disjunct&gt; &lt;or&gt; &lt;conjunct&gt;
# &lt;conjunct&gt; &rarr; &lt;literal&gt;
# &lt;conjunct&gt; &rarr; (&lt;conjunct&gt; &lt;and&gt; &lt;literal&gt;)
# &lt;literal&gt; &rarr; &lt;term&gt;
# &lt;literal&gt; &rarr; &lt;not&gt;&lt;term&gt;

ここで &lt;term&gt; は任意の変項である。

==関連項目==
* [[ブール関数#リード-マラー標準形|リード-マラー標準形]]
* [[ブール関数]]
* [[ブール値関数]]
* [[連言標準形]]
* [[ホーン節]]
* [[クワイン・マクラスキー法]]
* [[真理値表]]

{{logic}}

{{DEFAULTSORT:せんけんひようしゆんけい}}
[[Category:標準形 (論理)]]
[[Category:数学に関する記事]]