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ベストアンサー
- 回答日時:
DNF の()の中は基本積 []∧[]∧・・・
CNF の()の中は基本和 []∨[]∨・・・
の形をしていて,さらに
[] は,リテラル(文字 または 文字の否定)
です。
なお,() も [] も1個だけでいいです。
リテラルの例:p, ¬q, r
基本積の例: p, ¬q, p∧¬q∧r
DNFの例: p, ¬q, p∧¬q∧r, p∨¬q, p∨(p∧¬q∧r)∨¬q
御回答ありがとうございます。
()も[]も一つでいいということで、やっと理由がわかりました。
だからCNFでありDNFでもあるわけですね。
例とともにありがとうございました。
No.2
- 回答日時:
指摘にある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と言える ということで、理解できました。
前回の質問とともに、また回答して頂きありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- UNIX・Linux fedoraのリポジトリのインストールで下記コマンドで$(rpm -E %fedora)の部分が分か 1 2023/01/29 15:38
- UNIX・Linux Fedoraのupgradeで、libruby.so.3.0()がinstallできないという 1 2023/03/30 16:42
- 数学 オートマトンの問題がわかりません。 2 2022/07/13 12:47
- 物理学 標準モデルの数式 2 2023/03/09 23:25
- 統計学 t分布導出時のヤコビ行列式について教えて下さい。 1 2022/07/04 21:36
- 統計学 統計検定2級の過去問について 1 2023/01/04 16:40
- 物理学 角運動量の式変形が分かりません。 4 2022/08/03 21:04
- 数学 線形代数の曲線の標準形と概形についての問題がわからないです。 2 2022/07/18 17:48
- 国産車 H25年くらいのアクアの仕様に怖しい方、教えて下さい 2 2022/09/03 08:30
- 加湿器・除湿機 加湿器の水量? 1 2023/04/26 03:59
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
周の長さは同じなのに面積が違...
-
1から9までの番号をつけた9枚の...
-
0.1は10パーセントなら1.0は何...
-
大小2つのサイコロを投げる時...
-
高校数学です。0は全ての整数...
-
最大公約数や最小公倍数をだす...
-
上三角行列同士をかけたときの...
-
大,中,小3個のさいころを投げ...
-
測量図で、周囲の長さを算出す...
-
いくつかの数字があるとき、「...
-
二次関数が-2<x<0の範囲でx軸と...
-
数学A
-
積付と積込の違い。
-
文字を使った最大公約数の求め...
-
高1です!次の問題を分かりやす...
-
行列の二項定理???
-
正則行列×正則行列は正則になり...
-
行列の積ABの逆行列(AB)^-1をカ...
-
当たり前のようでなんとなく腑...
-
数列1.2.3.....nにおいて、n≧2...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
1から9までの番号をつけた9枚の...
-
0.1は10パーセントなら1.0は何...
-
周の長さは同じなのに面積が違...
-
大小2つのサイコロを投げる時...
-
高校数学です。0は全ての整数...
-
大,中,小3個のさいころを投げ...
-
測量図で、周囲の長さを算出す...
-
数学Aです。大中小3個のさいこ...
-
エナメル線の電流容量 教えて...
-
小学6年生算数の比の文章問題...
-
最小公倍数と最大公約数の違い...
-
数学の問題です 正の約数が28個...
-
「和と積がともに3である2数」...
-
数学A
-
ダムのような形の体積の求め方...
-
確率の問題です。 1個のサイコ...
-
40秒は何分?の計算式を教え...
-
高1です!次の問題を分かりやす...
-
積数計算になると思うのですが...
-
群論、「部分集合の元による語(...
おすすめ情報