プロが教える店舗&オフィスのセキュリティ対策術

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 …
これはただ単に間違えているだけなのでしょうか。

A 回答 (2件)

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


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

なお,() も [] も1個だけでいいです。

リテラルの例:p, ¬q, r
基本積の例: p, ¬q, p∧¬q∧r
DNFの例: p, ¬q, p∧¬q∧r, p∨¬q, p∨(p∧¬q∧r)∨¬q
    • good
    • 1
この回答へのお礼

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

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

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

指摘にある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と表しているのではないかと思われます。
    • good
    • 1
この回答へのお礼

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

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

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

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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!