FC2ブログ
--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

03.02
Sat
ある論理式集合が矛盾してるのか充足可能なのかを調べる方法にタブローというのがあります

例えば以下の論理式が充足可能でないかはどう考えるでしょうか

{P⊃Q , ¬Q , P}

これはモーダストレンスが以下なので

{P⊃Q , ¬Q} |= ¬P

矛盾してることがわかるのですが

タブローというのを使ってみます

考え方はこうです

充足可能ってことは全部の論理式が1になる時があるってことですが

ということはまずPはそのまま1になんなきゃいけなくて

¬Qが1になると言う事はQが0にならなきゃいけなくて

P⊃Qが1になるにはPが0でQがどうでもいいか、PQのどちらもが1になる時ですが

すでにみた論理式の関係からPが1でQが0でなきゃいけないので

全てが同時に1になることはないという事がわかります

これを木でやるのがタブローです

まず論理式を並べて、でつながった論理式があったら

それをばらしてまた並べでつながった論理式があったら分岐します

末端からルートまでのパスに自分の論理式の否定があったら、失敗です

全部失敗したら充足不可能ということがわかります

簡単に言うとこんな感じですがいくつか例を


①{P⊃Q , ¬Q , P}

tab1.png

ということで矛盾

②{P∨Q , Q⊃R , P⊃S , ¬(R∨S)}


tab2.png

これも矛盾しています

注意が必要なのは、うまいこと論理式を選んでいかないとなかなか難しくなることがあります

どのように選んでも結果は同じらしいですが、計算量を増やさないためにも片方の枝は行き止まりになるように

選ぶ必要がありますね


また、普遍例化と存在例化をつかって述語論理にも使えます

ただし多重量化のある論理式だとタブローが終わらなくなる時があるみたいです



③{∀x(P(x)⊃Q(x)) , ∃xP(x) , ¬∃xQ(x)}

tab3.png




スポンサーサイト

comment 0 trackback 0
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/166-4ff70020
トラックバック
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。