選言正規形

Standard form of a boolean function

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

意味

論理式は、1 つ以上のリテラルの1 つ以上の連言の選言である場合に DNF であるとみなされます。^{[2] [3] [4]} DNF 式が完全な選言標準形である場合は、その変数のそれぞれがすべての連言で正確に 1 回出現し、各連言が最大で 1 回出現します (変数の順序まで)。連言標準形(CNF) と同様に、DNF の命題演算子はand ( )、or ( )、not ( ) のみです。not演算子はリテラルの一部としてのみ使用できます。つまり、命題変数の前に置くことができます。 ${\displaystyle \wedge }$ ${\displaystyle \vee }$ ${\displaystyle \neg }$

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

DNF (分離) (分離) DNF ${\displaystyle \,\to \,}$ ${\displaystyle \,\mid \,}$ ${\displaystyle \,\lor \,}$

分離 リテラルリテラル分離リテラル ${\displaystyle \,\to \,}$ ${\displaystyle \,\mid \,}$ ${\displaystyle \,\land \,}$

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

ここで、Variableは任意の変数です。

たとえば、次の数式はすべて 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)}$

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

次の数式はDNF ではありません。

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

DNFへの変換

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

選言正規形のカルノー図(¬ A ∧¬ B ∧¬ D ) ∨ (¬ A ∧ B ∧ C ) ∨ ( A ∧ B ∧ D ) ∨ ( A ∧¬ B ∧¬ C )

選言正規形(¬ A ∧ C ∧¬ D ) ∨ ( B ∧ C ∧ D ) ∨ ( A ∧¬ C ∧ D ) ∨ (¬ B ∧¬ C ∧¬ D )のカルノー図。グループ化は異なりますが、前のマップと同じフィールドに「1」が含まれています。

...統語論的な手段によって

この変換には、二重否定消去、ド・モルガンの法則、分配法則といった論理的同値性の利用が含まれる。原始接続詞^{[7]から構築された式は、以下の}標準的な項書き換えシステムによってDNFに変換できる。^[8] ${\displaystyle \{\land ,\lor ,\lnot \}}$

${\displaystyle {\begin{array}{rcl}(\lnot \lnot x)&\rightsquigarrow &x\\(\lnot (x\lor y))&\rightsquigarrow &((\lnot x)\land (\lnot y))\\(\lnot (x\land y))&\rightsquigarrow &((\lnot x)\lor (\lnot y))\\(x\land (y\lor z))&\rightsquigarrow &((x\land y)\lor (x\land z))\\((x\lor y)\land z)&\rightsquigarrow &((x\land z)\lor (y\land z))\\\end{array}}}$

...意味論的な手段によって

式の完全なDNFはその真理値表から読み取ることができる。^{[9] [10]}例えば、次の式を考えてみよう。

${\displaystyle \phi =((\lnot (p\land q))\leftrightarrow (\lnot r\uparrow (p\oplus q)))}$. ^[11]

対応する真理値表は

${\displaystyle p}$	${\displaystyle q}$	${\displaystyle r}$		${\displaystyle (}$	${\displaystyle \lnot }$	${\displaystyle (p\land q)}$	${\displaystyle )}$	${\displaystyle \leftrightarrow }$	${\displaystyle (}$	${\displaystyle \lnot r}$	${\displaystyle \uparrow }$	${\displaystyle (p\oplus q)}$	${\displaystyle )}$
T	T	T			F	T		F		F	T	F
T	T	F			F	T		F		T	T	F
T	F	T			T	F		T		F	T	T
T	F	F			T	F		F		T	F	T
F	T	T			T	F		T		F	T	T
F	T	F			T	F		F		T	F	T
F	F	T			T	F		T		F	T	F
F	F	F			T	F		T		T	T	F

• 完全なDNFは ${\displaystyle \phi }$

${\displaystyle (p\land \lnot q\land r)\lor (\lnot p\land q\land r)\lor (\lnot p\land \lnot q\land r)\lor (\lnot p\land \lnot q\land \lnot r)}$

• 完全なDNFは ${\displaystyle \lnot \phi }$

${\displaystyle (p\land q\land r)\lor (p\land q\land \lnot r)\lor (p\land \lnot q\land \lnot r)\lor (\lnot p\land q\land \lnot r)}$

述べる

命題式は、ただ一つの完全なDNFでしか表現できません。^[13]一方、単純なDNFは複数存在する可能性があります。例えば、この規則を3回適用すると、上記の完全なDNFはと簡略化されます。しかし、この規則では互いに変換できない等価なDNF式も存在します。例として図を参照してください。 ${\displaystyle ((a\land b)\lor (\lnot a\land b))\rightsquigarrow b}$ ${\displaystyle \phi }$ ${\displaystyle (\lnot p\land \lnot q)\lor (\lnot p\land r)\lor (\lnot q\land r)}$

選言正規形定理

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

選言標準形定理：命題言語で書かれた文を と仮定し、文文字を と表記する。 が矛盾でない場合、 は、、の形式を持つ連言の選言と真理関数的に同値である。^[15] ${\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}}$

証明は、真理値表からDNFを生成するための上記手順に従う。正式には、証明は以下の通りである。

が命題言語の文で、文の文字が であるとする。 の真理値表の各行について、対応する連言を書き出す。ここで、 がその行で値を取る場合、は と定義され、 がその行で値を取る場合、 は と定義される。 、、などについても同様である（連言におけるのアルファベット順は任意であり、他の順序を選ぶこともできる）。ここで、 の真理値表の行に対応するこれらすべての連言の選言を形成する。この選言は における文であり、^[18]上記の推論により、これは真理機能的に と同値である。この構成は明らかに、 がその真理値表の少なくとも 1 つの行で値を取ることを前提としている。 が値を持たない場合、すなわちが矛盾 である場合、 は と同値であり、これももちろん における文である。^[15] ${\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 ]}$ ${\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 \}}$

接続詞の最大数

あらゆる命題式は変数から構築されます。 ${\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}$空でない部分集合を持つ。 ^[19] ${\displaystyle (2^{2n}-1)}$

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

完全な DNF には、真理値表の各行に 1 つずつ、最大で接続詞を含めることができます。 ${\displaystyle 2^{n}}$

例1

2 つの変数とを持つ式を考えます。 ${\displaystyle p}$ ${\displaystyle q}$

最も長いDNFには接続詞が含まれる：^[13] ${\displaystyle 2^{(2\times 2)}-1=15}$

${\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 つの接続詞があり、それらは下線が引かれています。

この式はトートロジーです。または に簡略化できますが、これらもトートロジーであり、有効なDNFです。 ${\displaystyle (\neg p\lor p)}$ ${\displaystyle (\neg q\lor q)}$

例2

eg 式の各 DNF には接続詞があります。 ${\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}$ ${\displaystyle 2^{n}}$

計算の複雑さ

連言正規形論理式におけるブール充足可能性問題はNP完全である。双対性原理により、DNF論理式における反証可能性問題も同様にNP完全である。したがって、DNF論理式がトートロジーであるかどうかを判断することは共NP困難である。

逆に、DNF 式が充足可能であるのは、その論理積のいずれかが充足可能である場合のみです。これは、少なくとも 1 つの論理積に矛盾するリテラルが含まれていないことを単純に確認するだけで、多項式時間で判定できます。

変種

計算複雑性の研究において重要なバリエーションとしてk-DNFがある。式がDNFであり、各接続詞が最大k個のリテラルを含む場合、その式はk-DNFである。 ^[20]

参照

• 代数正規形– AND句のXOR
• ブレイク標準形– すべての主項を含むDNF
  • クワイン・マクラスキーアルゴリズム– 主項を計算するアルゴリズム
• 連言/選言の双対性
• 命題論理
• 真理値表

注記

1. 1921年以降。
2. Davey & Priestley 1990、153ページ。
3. グリース&シュナイダー、1993年、p. 67.
4. ホワイトシット 2012年、33～37頁。
5. ただし、これは否定正規形です。
6. Davey & Priestley 1990、152-153ページ。
7. 他の接続詞を含む式は、まず否定正規形にすることができます。
8. ダーショウィッツとジュアンノー、1990 年、p. 270、セクション5.1。
9. Smullyan 1968, p. 14: 「この式の真理値表を作成しなさい。表の中で「T」となる行は、選言正規形の基本接続詞の1つとなる。」
10. ソボレフ 2020.
11. = (( NOT (p AND q)) IFF (( NOT r) NAND (p XOR q))) ${\displaystyle \phi }$
12. いいね ${\displaystyle (a\land b)\lor (b\land a)\lor (a\land b\land b)}$
13. の交換法則と結合法則に基づく繰り返しや変化^[12]は発生しないと仮定します。 ${\displaystyle \lor }$ ${\displaystyle \land }$
14. Halbeisen, Lorenz; Kraph, Regula (2020). Gödel´s theorems and zermelo´s axioms: a firm foundation of math . Cham: Birkhäuser. p. 27. ISBN 978-3-030-52279-7。
15. ハウソン、コリン (1997).木による論理：記号論理入門. ロンドン; ニューヨーク: ラウトレッジ. p. 41. ISBN 978-0-415-13342-5。
16. センツァー, ダグラス; ラーソン, ジーン; ポーター, クリストファー; ザプレタル, イインドリッヒ (2020).集合論と数学の基礎：数理論理学入門. ニュージャージー: ワールドサイエンティフィック. pp.  19– 21. ISBN 978-981-12-0192-9。
17. ハルヴァーソン、ハンス (2020). 『ロジックの仕組み：ユーザーズガイド』 プリンストン・オックスフォード：プリンストン大学出版局. p. 195. ISBN 978-0-691-18222-3。
18. つまり、命題変数と接続詞を持つ言語です。 ${\displaystyle A,B,C,\ldots }$ ${\displaystyle \{\land ,\lor ,\neg \}}$
19. ${\displaystyle \left|{\mathcal {P}}(L)\right|=2^{2n}}$
20. アローラ＆バラク 2009.

参考文献

• アローラ、サンジーヴ、バラク、ボアズ（2009年4月20日）『計算複雑性：現代的アプローチ』ケンブリッジ大学出版局、p. 579、doi :10.1017/CBO9780511804090、ISBN 9780521424264。
• Davey, BA; Priestley, HA (1990).格子と秩序入門. ケンブリッジ数学教科書. ケンブリッジ大学出版局.
• ダーショウィッツ、ナハム、ジュノー、ジャン＝ピエール(1990)「書き換えシステム」、ヴァン・レーウェン、ヤン(編) 『形式モデルと意味論』、エルゼビア社、理論計算機科学ハンドブック、第B巻、pp.  243– 320、ISBN 0-444-88074-7。
• グリース、デイビッド、シュナイダー、フレッド・B.（1993年10月22日）『離散数学への論理的アプローチ』Springer Science & Business Media. 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プレス
• ホワイトシット、J.エルドン（2012年5月24日）[1961]. ブール代数とその応用. クーリエ社. ISBN 978-0-486-15816-7。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Disjunctive_normal_form&oldid=1318378980"