DNF CNF （選言標準形 連言標準形）

DNF：()∨()∨()・・・　
CNF：()∧()∧()・・・
と理解しているのですが、例えば

　￢p∨￢q∨r ：CNF,DNF
　p∧q∧￢p：CNF,DNF

の理由がわかりません。さらに

　（p∧￢q）∨r：CNF
　≡（p∨r）∧（￢q∨r）：DNF

なのですが、何故上の式がCNF,下の式がDNFなのでしょうか（下のサイトの上の式です。
http://pfp7.cc.yamaguchi-u.ac.jp/~ichikawa/albus …）
これはただ単に間違えているだけなのでしょうか。

No.1 ベストアンサー 回答者： take008 回答日時： 2006/05/27 12:28

DNF の()の中は基本積 []∧[]∧・・・

CNF の()の中は基本和 []∨[]∨・・・
の形をしていて，さらに
[] は，リテラル（文字 または 文字の否定）　
です。

なお，() も [] も１個だけでいいです。

リテラルの例：p, ￢q, r
基本積の例： p, ￢q, p∧￢q∧r
ＤＮＦの例： p, ￢q, p∧￢q∧r, p∨￢q, p∨(p∧￢q∧r)∨￢q

この回答へのお礼

御回答ありがとうございます。

()も[]も一つでいいということで、やっと理由がわかりました。
だからCNFでありDNFでもあるわけですね。
例とともにありがとうございました。　

お礼日時：2006/05/27 13:05

No.2 回答者： yuntanach 回答日時： 2006/05/27 12:28

指摘にあるURLの内容をざっと見してみましたが、

質問の後半にある
>　（p∧￢q）∨r：CNF
>　≡（p∨r）∧（￢q∨r）：DNF
はCNFとDNFが逆になっているようにしかみえません。
他の部分につい逆になっているようなところはない
ので、おそらく質問の部分についてはURLの
ドキュメントの作者の間違いではないかと思われます。

前半の
>　￢p∨￢q∨r ：CNF,DNF
>　p∧q∧￢p：CNF,DNF
については、￢p∨￢q∨rは￢(p∧q)∨rと書換え
られるからCNFで表された(p∧q)と、
DNFで表された…∨rということなのでしょうか。
同様にp∧q∧￢pはp∧q∧￢rだったとすると
￢(￢(p∧q)∨r)ということで上記の否定と
考えられます。

というわけで部分的にCNFで表されたものが
全体としてDNFで表されたということを表現するために
CNF,DNFと表しているのではないかと思われます。

この回答へのお礼

御回答ありがとうございます。

やはり後半の質問はドキュメントの間違いだったのですね。
鵜呑みにしてしまうとずっと理解できないままだったと思います。

前半の問題は、節や項がリテラル一つでも良い かつ 節や項一つでもCNF,DNFと言える ということで、理解できました。

前回の質問とともに、また回答して頂きありがとうございました。

お礼日時：2006/05/27 13:12