2つの和積形命題論理式が与えられています。
この2つの式に含意関係が成り立つか判定したいのです。
この問題はco-NP完全問題でまともにやるととても時間がかかります。そこで次のような条件を満たすアルゴリズムを考えてください。
1.アルゴリズムが含意関係がなりたつと答えたときは必ず含意関係が成り立つ。
2.アルゴリズムが含意関係が成り立たないと答えたときは含意関係が成り立ってても成り立たなくてもよい。
3.入力の多項式時間で停止する。
この条件だけだと常に含意関係が成り立たないと
答えるアルゴリズムでもOKになってしまいますが
もちろん本当に含意関係が成り立つときはなるたけ含意関係が成り立つと答えてほしいわけです。
私が考えたのは和積形の論理式f、gがあたえられたとしてfのすべての和項に対してgにそれを含意する和項があったらgはfを含意するというものです。
これよりもよい方法を考えてください。
よろしくお願いします。
No.2ベストアンサー
- 回答日時:
和積形のSATはNP完全問題なので、ご指摘にあるように指数時間かかってしまうのですが、任意の i において、g_i'' に含まれる命題記号の数がある自然数 k より小さくなる場合のみ(十分に記号の数が少ないとき)、2のk乗の真偽値の組み合わせすべてを g_i'' 代入して、充足可能性を確認する、というつもりで「可能な場合のみ、充足可能を強引に調べる」と書きました。
不明瞭な記述で失礼しました。l_j (0<=j<=m) に偽を代入する部分など、問題文中最後にある解法とほぼ同じ考えであるとは思ったのですが、可能な場合さらにリテラルに真値を代入することで和項が消えるので、以上のように強引にSATの解を求めることのできる場合も比較的多くなるかと考えました。式をさらに decomposition することなども有効かと考えたのですが、実をいうと、投稿が全くなかったので、とりあえず関心を持って問題を読んでいます、という意味をこめて投稿してみました。
専門の方にとっては、ある程度標準的な解法がある問題かもしれないと思ったのですが、ユニークな解法である程度平易なものが投稿されるかもしれないと思い楽しみにしていました。
私には他にあまりいい考えが浮かびそうにないのですが、よい解法が寄せられるとされるといいですね。
No.1
- 回答日時:
質問の回答に関心をよせていたのですが、投稿がないようなので、質問の確認の意味もこめて投稿させていただきます。
質問としては、和積形論理式 f、g が与えられたとき、論理式g=>fがトートロジーであるかを判定する発見的アルゴリズム(のうち条件1,2,3を満たすもの)を求める、ということでよいのでしょうか?
このとき、f をn個の和項 f_1,f_2,...,f_n の積であるとすると(f=f_1^f_2^...^f_n)、g=>f がトートロジーとなるのは、g=>f_1, g=>f_2, ..., g=>f_n の各式がトートロジーであることが必要十分条件になります。したがって、この問題は、「和積形命題論理式 g が任意の和項 f_i を含意するか」を判定するアルゴリズムを n回利用することで解くことができます。
そこで任意の式 g=>f_i に注目すると、g=>f_i がトートロジーでなく偽になり得るとすると、それは f_i が偽、かつ g が真のときのみです。f_i がm個のリテラル l_1, l_2, ..., l_m の和であるとすると(f_i=l_1vl_2v...vl_m)、f_i が偽になるのは、l_1, l_2, ..., l_m がすべて偽であるときだけなので、g 内のこれらリテラルに偽を代入した時に得られる和積形論理式 g_i' が充足可能であるとき、またそのときのみ、g=>f_i が偽になり得る、つまりトートロジーでない、といえることがわかります。
これらのことから、はじめに与えられた問題は、和積形論理式が充足可能であるか判定する問題(SAT)を解くアルゴリズムを用いることで解くことができる、とわかります。
SATのためのアルゴリズムについてはすでに深い研究がされてきたと思うのですが、私が思いつく単純なものとしては、g_i' のリテラル l のうち、~l が g_i' 内に無いものに真を代入して得られるより単純な式 g_i''(g_i''=>g_i' を満たす)に関して、それが可能な場合のみ、充足可能を強引に調べるというものです。
質問された方が書かれているアルゴリズムとあまりかわらないのですが、以上のような回答でもよいのでしょうか? また、誤りがある場合、どなたか指摘してくださると幸いです。
回答ありがとうございます。
もう回答がつかないものとあきらめかけていました。
うれしいです。
SATに帰着されるということですが、SATを解こうとすると指数時間かかってしまいそうです。
充足可能を強引に調べるとありますが、具体的にはどのように調べるのでしょうか。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
0.1は10パーセントなら1.0は何...
-
大,中,小3個のさいころを投げ...
-
1から9までの番号をつけた9枚の...
-
大小2つのサイコロを投げる時...
-
エナメル線の電流容量 教えて...
-
周の長さは同じなのに面積が違...
-
「和と積がともに3である2数」...
-
代数学の質問です(偶置換と奇...
-
高校数学です。0は全ての整数...
-
数学Aです。大中小3個のさいこ...
-
因数分解
-
数学についての質問です。(2つ...
-
数列1.2.3.....nにおいて、n≧2...
-
(2)ですが、どう考えればいい...
-
行列の二項定理???
-
記号について2
-
積の微分法と合成関数の微分法...
-
円錐の側面積
-
素数の調べ方
-
5角形の面積の求め方について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
大小2つのサイコロを投げる時...
-
0.1は10パーセントなら1.0は何...
-
大,中,小3個のさいころを投げ...
-
1から9までの番号をつけた9枚の...
-
数学Aです。大中小3個のさいこ...
-
エナメル線の電流容量 教えて...
-
周の長さは同じなのに面積が違...
-
高1です!次の問題を分かりやす...
-
40秒は何分?の計算式を教え...
-
一の読み方でかずと読むかなぁ?
-
測量図で、周囲の長さを算出す...
-
高校数学です。0は全ての整数...
-
周囲の長さが一定の二等辺三角...
-
デルタ関数について
-
算数の和・差・積
-
nを奇数とするとき、n^2-1は8...
-
素数の調べ方
-
最大公約数や最小公倍数をだす...
-
小学6年生算数の比の文章問題...
-
「aとbを入れ替えても同じ」を...
おすすめ情報