選言標準形

ブール論理では、選言標準形（DNF）は、論理式の選言からなる標準形です。また、 ANDのOR、積の和、または哲学的論理 ではクラスター概念として記述することもできます。^{[ 1 ]}選言標準形とその対義語である連言標準形は、ブール式を表す最も一般的な標準化された方法です。これらは、回路設計や自動定理証明などのさまざまなアプリケーションで広く使用されています。

論理式は、1つ以上のリテラルの1つ以上の論理積の選言である場合、DNFであるとみなされます。^{[ 2 ] [ 3 ] [ 4 ]} DNF式は、各変数がすべての論理積にちょうど1回出現し、各論理積が（変数の順序を除いて）最大1回出現する場合、完全な選言標準形です。論理積標準形（CNF）と同様に、DNFの命題演算子は、および（${\displaystyle \wedge }$）、または（${\displaystyle \vee }$)、ではなく(${\displaystyle \neg }$）。否定演算子はリテラルの一部としてのみ使用できます。つまり、命題変数の前にのみ置くことができます。

以下は、DNFの文脈自由文法です。

DNF${\displaystyle \,\to \,}$（選言）${\displaystyle \,\mid \,}$（選言）${\displaystyle \,\lor \,}$DNF

選言的${\displaystyle \,\to \,}$リテラル${\displaystyle \,\mid \,}$リテラル${\displaystyle \,\land \,}$選言的

リテラル${\displaystyle \,\to \,}$変数${\displaystyle \,\mid \,}$${\displaystyle \,\neg \,}$変数

ここで「変数」は任意の変数です。

例えば、以下の数式はすべてDNF形式です。

• ${\displaystyle (A\land \neg B\land \neg C)\lor (\neg D\land E\land F\land D\land F)}$
• ${\displaystyle (A\land B)\lor (C)}$
• ${\displaystyle (A\land B)}$
• ${\displaystyle (A)}$

式${\displaystyle A\lor B}$は DNF 形式ですが、完全な DNF 形式ではありません。同等の完全な DNF バージョンは${\displaystyle (A\land B)\lor (A\land \lnot B)\lor (\lnot A\land B)}$。

以下の数式はDNF形式ではありません。

• ${\displaystyle \neg (A\or B)}$ORがNOTの中にネストされているため
• ${\displaystyle \neg (A\land B)\lor C}$AND は NOT の中にネストされているため
• ${\displaystyle A\lor (B\land (C\lor D))}$OR は AND の中にネストされているため^{[ 5 ]}

古典論理では、各命題論理式は DNF に変換できます^{[ 6 ]} ...

命題論理におけるすべての無矛盾な式は選言標準形に変換できる という定理がある。 ^{[ 14 ] [ 15 ] [ 16 ] [ 17 ]}これは選言標準形定理と呼ばれる。^{[ 14 ] [ 15 ] [ 16 ] [ 17 ]}正式な記述は以下のとおりである。

選言標準形定理：${\displaystyle X}$命題言語の文である${\displaystyle {\mathcal {L}}}$と${\displaystyle n}$文文字は、${\displaystyle A_{1},...,A_{n}}$。 もし${\displaystyle X}$が矛盾でない場合、それは次の形式の論理積の選言と真理関数的に同値である。${\displaystyle \pm A_{1}\land ...\land \pm A_{n}}$、 どこ${\displaystyle +A_{i}=A_{i}}$、 そして${\displaystyle -A_{i}=\neg A_{i}}$[ ^{15 ]​}

証明は、真理値表からDNFを生成するために上述した手順から導かれる。正式には、証明は以下のとおりである。

仮定する${\displaystyle X}$は命題言語の文であり、その文文字は${\displaystyle A,B,C,\ldots }$.各行について${\displaystyle X}$の真理値表から、対応する論理積を書き出す。${\displaystyle \pm A\land \pm B\land \pm C\land \ldots }$、 どこ${\displaystyle \pm A}$と定義される${\displaystyle A}$もし${\displaystyle A}$値を取る${\displaystyle T}$その列で、そして${\displaystyle \neg A}$もし${\displaystyle A}$値を取る${\displaystyle F}$その行で。同様に${\displaystyle \pm B}$、${\displaystyle \pm C}$など（アルファベット順）${\displaystyle A,B,C,\ldots }$接続詞の は完全に任意です。代わりに他の を選択することもできます。次に、に対応するこれらの接続詞の選言を形成します。${\displaystyle T}$列${\displaystyle X}$の真理値表。この論理和は、${\displaystyle {\mathcal {L}}[A,B,C,\ldots$ ;\land ,\lor ,\neg ]} , ^{[ 18 ]}上記の推論により、真理関数的に等価なのは${\displaystyle X}$この構成は明らかに次のことを前提としている。${\displaystyle X}$値を取る${\displaystyle T}$真理値表の少なくとも１行に、${\displaystyle X}$そうでない、つまり、もし${\displaystyle X}$矛盾しているならば、${\displaystyle X}$と同等${\displaystyle A\land \neg A}$もちろん、これも文です${\displaystyle {\mathcal {L}}[A,B,C,\ldots$ ;\land ,\lor ,\neg ]} . ^{[ 15 ]}

この定理は、命題論理における多くの有用なメタ論理的結果を導出する便利な方法であり、例えば、自明なことに、結合子の集合が${\displaystyle \{\land ,\lor ,\neg \}}$機能的に完全である。^{[ 15 ]}

命題論理式は以下から構築される${\displaystyle n}$変数、ここで${\displaystyle n\geq 1}$。

がある${\displaystyle 2n}$可能なリテラル:${\displaystyle L=\{p_{1},\lnot p_{1},p_{2},\lnot p_{2},\ldots ,p_{n},\lnot p_{n}\}}$。

${\displaystyle L}$もっている${\displaystyle (2^{2n}-1)}$空でない部分集合。^{[ 19 ]}

これは、DNFが持つことができる接続詞の最大数です。^{[ 13 ]}

完全なDNFは最大で${\displaystyle 2^{n}}$真理値表の各行に対応する論理積。

例１

2つの変数を含む数式を考えてみましょう。${\displaystyle p}$そして${\displaystyle q}$。

最長のDNFは${\displaystyle 2^{(2\times 2)}-1=15}$接続詞: ^{[ 13 ]}

${\displaystyle {\begin{array}{lcl}(\lnot p)\lor (p)\lor (\lnot q)\lor (q)\lor \\(\lnot p\land p)\lor {\underline {(\lnot p\land \lnot q)}}\lor {\underline {(\lnot p\land q)}}\lor {\underline {(p\land \lnot q)}}\lor {\underline {(p\land q)}}\lor (\lnot q\land q)\lor \\(\lnot p\land p\land \lnot q)\lor (\lnot p\land p\land q)\lor (\lnot p\land \lnot q\land q)\lor (p\land \lnot q\land q)\lor \\(\lnot p\land p\land \lnot q\land q)\end{array}}}$

可能な限り最長の完全な DNF には 4 つの接続詞があり、それらは下線で示されています。

この式はトートロジーです。これを簡略化すると次のようになります。${\displaystyle (\neg p\lor p)}$または${\displaystyle (\neg q\lor q)}$これらは同義反復であると同時に、有効なDNFでもある。

例２

例式の各DNF${\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}$もっている${\displaystyle 2^{n}}$接続詞。

連言標準形（ DNF）式の充足可能性問題はNP完全である。双対性原理により、DNF式の反証可能性問題もNP完全である。したがって、DNF式がトートロジーであるかどうかを判定することはco-NP困難である。

逆に、DNF式は、その連言のうちの1つが充足可能である場合に限り充足可能である。これは、少なくとも1つの連言に矛盾するリテラルが含まれていないことを確認するだけで、多項式時間で判定できる。

計算複雑性の研究で用いられる重要な変種の一つにk-DNFがある。式がk-DNFであるのは、それがDNFであり、かつ各論理積が最大でk個のリテラルを含む場合である。^{[ 20 ]}

• 代数正規形– AND節のXOR
• ブレイクの正準形式– すべての主項を含む DNF
  • クワイン・マクラスキーアルゴリズム– 素インプリカントを計算するためのアルゴリズム
• 結合／分離の二重性
• 命題論理
• 真理値表

• Arora, Sanjeev ; Barak, Boaz (2009年4月20日).計算複雑性：現代的アプローチ. Cambridge University Press . p.  579. doi : 10.1017/CBO9780511804090 . ISBN 9780521424264。
• Davey, BA; Priestley, HA (1990). 『格子と順序入門』 . Cambridge Mathematical Textbooks. Cambridge University Press.
• ダーショウィッツ、ナフム；ジュアナウ、ジャン＝ピエール（1990）。「書き換えシステム」。ヴァン・レーウェン、ヤン（編）。形式モデルと意味論。理論計算機科学ハンドブック。第 B巻。エルゼビア。pp . 243–320。ISBN  0-444-88074-7。
• グリース、デイビッド；シュナイダー、フレッド・B.（1993年10月22日）。離散数学への論理的アプローチ。シュプリンガー・サイエンス＆ビジネス・メディア。ISBN 978-0-387-94115-8。
• ヒルベルト、デイヴィッド；アッカーマン、ヴィルヘルム（1999）。数理論理学の原理。アメリカ数学会。ISBN 978-0-8218-2024-7。
• ハウソン、コリン（2005年10月11日）[1997]。木構造による論理：記号論理入門。ラウトレッジ。ISBN 978-1-134-78550-6。
• ポスト、エミール（ 1921年7月）。「初等命題の一般理論への序論」。アメリカ数学ジャーナル。43 （ 3）：163–185。doi：10.2307 /2370324。JSTOR 2370324。 
• スマリヤン、レイモンド M. (1968)。一次論理。 Ergebnisse der Mathematik および ihrer Grenzgebiete。 Vol.  43 (初版、1971 年第 2 刷 )。ニューヨーク ハイデルベルク ベルリン: Springer-Verlag。 p.  160.土井：10.1007/978-3-642-86718-7。ISBN 978-3-642-86718-7。
• ソボレフ、SK（2020）[1994]、「選言標準形」、数学百科事典、EMS Press
• ホワイトシット、J.エルドン（2012年5月24日）[1961]。ブール代数とその応用。クーリエ・コーポレーション。ISBN 978-0-486-15816-7。