解決策は完全ですか、それとも反論のみが完全ですか?
-
16-10-2019 - |
質問
を通過する いくつかの知識表現チュートリアル 現時点での解決策と私は出会いました スライド05.kr、no77.
そこには、「手順も完了している」と言及されています。
この完全性は、文がKBによって伴う場合、解像度によって導き出されることを意味するものではないと思います。たとえば、解像度は$(q lor neg q)$を1つの句$ neg p $を使用してkbから導出することはできません。 (KRR、Brachman、Levesqueの例、53ページ)。
誰かがこのスライドの意味を理解するのを手伝ってくれますか?スライドの完全性は、完全な証明手順ではなく、反論が完全であることを指すのでしょうか?
解決
解決は反論システムとして完了します。つまり、$ s $が矛盾した条項のセットである場合、解像度は$ s $、すなわち$ s vdash bot $に反論できます。
$ t vdash a $は$ t cup { lnot a } vdash bot $に相当するため、これで十分です。したがって、フォーミュラ$ A $が$ t $から派生可能であることを確認する場合、解像度を使用してチェックできる$ t cup { lnot a } $の反論証明があるかどうかを確認する必要があります。
他のヒント
あなたが言ったように、解決は反論的にのみ完了します。これは 意図されました そして、非常に便利です。なぜなら、それは検索空間を大幅に減らすからです。最終的に可能なすべての結果を導き出さなければならない(何らかの推測の証拠を見つけるために)、解決は空の句を導き出そうとするだけです。
それはまた、次の意味で非常に完全に完了しています:
条項$ f $のセットが非活用条項$ c $を意味する場合、$ c $(すなわち$ c ' subseteq c $)を包含する単一の条項$ c' $を導き出すことが常に可能です。
ソース:
Christian G.Fermüller、署名された決議の暗示的な完全性、2002年
元の結果は次のように言及されていることに注意してください。
rct lee。与えられた公理から派生可能な定理を導入するための完全性定理とコンピュータープログラム。博士号論文、カリフォルニア大学、バークリー、1967年。