resolution の完全性についての疑問
一階述語論理の resolution の規則って, として を の MGU としたときに
と書けて(resolution に を使うのはあまり普通ではないかもしれないけど),これだけで反駁完全なのだと思っていました。しかしどうもそうではないようだという気がしてきて,どうやったら本当に完全になるんだろうかということを最近考えました。
まず完全でないと思う理由ですが,例えば (p は述語記号,x, y, u, v は変数)という節集合を考えます。これが充足不能なのは,論理式で書くと だから明らかでしょう。一方,この節集合からは上の規則を使っても しか(変数の名前の違いを除いて)新しい節は出てきません。だから空節を導くことはできません。
いくつか見てみた本の中で「論理と計算のしくみ」では違う規則を採用していて,この本では一つずつではなく複数のリテラルをまとめて取り出して unify してよいことになっています。具体的には を の MGU として
のようにしています。これだとさっきの例は をまとめて unify してやれば空節が出てくるので OK,ということになります。この形の規則だと確かに反駁完全性が成り立つようです。
でもそういう形の規則になっている本は他に見かけないので,これはどういうことだろうかと疑問に思い調べてみました。以下の記述は "Handbook of Automated Reasoning" の Chapter 2 の冒頭(を読んだ記憶)に基づいています。どうやら resolution の手法を最初に考えた Robinson は,確かに最初の形を resolution として定式化していたようですが,それに加えて別にもう一つ規則を用意していたらしいです。その規則は factoring といって, を D の unifier として
という形をしています(たぶん)。これがあると,
なので,最初の形の resolution と合わせて空節が導けます。厳密には確かめていませんが,こちらも反駁完全性が成り立ちそうです。
ということは,もともとは resolution と factoring を合わせて反駁完全であるという話だったのに,factoring の方は何らかの理由であまり教科書に書かれなくなってしまったのでしょうか(実際,handbook を読むまで factoring という名前を知らなかった)。https://en.wikipedia.org/wiki/Resolution_(logic) には "The resolution rule, as defined by Robinson, also incorporated factoring, .... The resulting inference rule is refutation-complete, ...." と書いてあるので,そんなに知られていない事実でもなくて,たまたま僕がそのあたりのことが書いてある教科書を読まなかっただけかもしれませんが。