- ベストアンサー
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/lecture/comp-intro98/compsys4/sld065.htm） これはただ単に間違えているだけなのでしょうか。
- chromium_ai
- お礼率100% (8/8)
- 数学・算数
- 回答数2
- ありがとう数5
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
DNF の()の中は基本積 []∧[]∧・・・ CNF の()の中は基本和 []∨[]∨・・・ の形をしていて，さらに [] は，リテラル（文字 または 文字の否定） です。 なお，() も [] も１個だけでいいです。 リテラルの例：p, ￢q, r 基本積の例： p, ￢q, p∧￢q∧r ＤＮＦの例： p, ￢q, p∧￢q∧r, p∨￢q, p∨(p∧￢q∧r)∨￢q
その他の回答 (1)
- yuntanach
- ベストアンサー率72% (13/18)
指摘にある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
- 数式の変形過程の解説をお願いします。
「社団法人日本電気技術者協会 音声付き電気技術解説講座 > 計測・試験 > ダブルブリッジで、なぜ低抵抗が測れるか」 http://www.jeea.or.jp/course/contents/02101/ の、(7)式 Rx = (P/Q)・[Rs + { q・r /( p + q + r )}] - { p・r /( p + q + r )} = (P/Q)・Rs + { q・r /( p + q + r )}・{(P/Q) - (p/q)} ---(7) 上の式がどう云う変形過程を以て下の式になるのか、どなたか解説をしていただけないでしょうか。 = (P/Q)Rs + (P/Q){ q・r /( p + q + r )} - { p・r /( p + q + r )} と３項にバラしてから後の２項を括りなおすのだと考えますが、頭が固く、その先が解りません。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 積和標準形と和積標準形について
積和標準形と和積標準形について質問があります。 (1)和積標準形は(P∨Q)∧(S∨R)と読みました。 さらに、((￢X∨Y)∧￢Z)∨(X∨Z)は和積でもなく積和でもないと 書いてあります。 この場合、((￢X∨Y)∧￢Z)∨(X∨Z)ではなく、((￢X∨Y)∨￢Z)∧(X∨Z) であれば、和積標準形なのでしょうか。 和積標準形・積和標準形 (2)P∧Q∧Rは和積標準形に入るのでしょうか。 また、P∨Q∨Rは積和標準形に入るのでしょうか。 (3)定義として、 ○リテラルから∨のみで作られる式を基本和という。 ○基本和から∧のみで作られる式を和積標準形という。 ということが書いてあります。 そこで、基本和やリテラルについて調べてみると、￢P∨Qのようなものが 基本和ということは分かりました。 ですが、２番目の定義の意味が分かりませんでした。 ○基本和から∧のみで作られる式を和積標準形という これを、今は基本和を∧でくっつけてできた式を和積標準形という、 ということで認識しておりますが、そうなると(2)について、 基本和が含まれていない式であるので、和積標準形とは呼ばないの ではないかと考えているのですが、これについて解説をお願いします。 積和標準形についても質問があったのですが、和積でのこれらの質問が 理解できれば何とかなりそうに思えるので、和積標準形の質問だけに させていただきました。
- 締切済み
- 数学・算数
- 次の計算をお教えください。
p,q=1-pともに定数の時 \sum_{k=0}^n(k+1)p^{2}(1-p)^2 上の式が下の式にどうすればなるのかわかりません。 =p\left[\tfrac{1-q^{n+1}}{p}-(n+1)q^{n+1} \right] よろしくお願いします。
- 締切済み
- 数学・算数
- 論理学の問題なのですが
この問題のときかたを教えてください。 論理式が真か偽か、偶然的かを判定して真式にはＡ，偽式にはＢ、偶然式にはＣを。 (1) ～pVq⊃ｑ (2) ～(pVq)≡(p＆q） (3) (p⊃q)V(～q⊃～p) (4) ～(p＆q⊃(～p⊃q)) (5) (～pVq)＆(q⊃r)⊃(p⊃r)
- 締切済み
- 数学・算数
- 恒真式の真理表について
質問させていただきます。 真理表についてわからなくて、大変困ってしまっています。下記の論理式を真理表にするのでうが…わかる方、教えてください。よろしくお願い致します。 １ ((P → Q)・(-P → R)) → ((Q・-P) v (R・P)) ２ ((P・Q) v (P・R)) → (Q・R)
- ベストアンサー
- 数学・算数
- 命題論理式の真理表ってなんですか？
次の命題論理式の真理表を教えてください。 ３－１（ＰかつＱかつＲ）ならばг（￢ＰかつГＱかつ￢Ｒ） ３－２（ＰならばＱ）かつ（￢ＰならばＲ）ならば（ＱまたはＲ） この問題を解くのにはどうしたらいいのでしょう
- ベストアンサー
- 哲学・倫理・宗教学
- 等式を満たす値
p,q,rは不等式p≦q≦rを満たす正の整数とする。 (1)1/p＋1/q=1を満たすp,qをすべて求めよ (2)1/p＋1/q+1/r=1を満たすp,q,rをすべて求めよ という問題です。 (1)のヒントとして分母を払って(p-1)(q-1)=1と変形するとあるのですが、どうやってこうなったのでしょうか？それともうひとつのヒントがp-1とq-1は０以上であるとあるのですが、これはなぜなのでしょうか？ また、どうやってp,qの値を出すのでしょうか？ (2)はどうすればいいのでしょうか？何かに変形するのでしょうか？ 初歩的な質問かとは思いますが、回答よろしくお願いします。
- ベストアンサー
- 数学・算数
- mathematicaについての質問です
mathematicaの出力で、p && q || r と出たら、これは(p AND q) OR r の意味でしょうか、それとも、p AND (q OR r)の意味でしょうか？ p || q && r と出たら、 p OR (q AND r) の意味でしょうか、それとも (p OR q) AND r の意味でしょうか？ && と||のいずれを優先した論理式を表しているかわからず、困っているのですが。お分かりの方、よろしくお願いします。
- ベストアンサー
- 情報工学
- 離散数学についての質問です！
例えば、 集合Ｘ＝｛（ｐならばｑ）ならば（ｐ∧ｒ）、（ｐならばｑ）ならばｒ、（ｐでないならばｒ）∧（ｑならばｒ）、ｐ∧（ｑならばｒ）｝ といった論理式があるとき、論理的同値関係≡による、集合Ｘの商集合（Ｘ／≡）は、どうなるのでしょうか？ これと類似した問題を考えているのですが、ちょっと分からないんです・・良ければ、解説をしていただけないでしょうか。
- 締切済み
- 数学・算数
お礼
御回答ありがとうございます。 ()も[]も一つでいいということで、やっと理由がわかりました。 だからCNFでありDNFでもあるわけですね。 例とともにありがとうございました。