Robinsonの解決手続きの欠点は何ですか?
-
29-09-2020 - |
質問
Paulsonら。 LCFからISABELLE / HOL と言う:
一次論理の解像度は、原則として完全ですが、実際にはがっかりしている。
私は完全なことを彼らが一次論理正しい形式でも真の式を証明することができると思います。自動推論のハンドブック私は見つけました:
解像度は、反論的に完全な定理証明方法です。矛盾(すなわち、空の節)は、どんな任意の不満足な句のセットから推定することができる。
ウィキペディアから:
満足できる一次式を満足不可能なものとして証明しようとすると、非末端計算が発生する可能性があります。
その残念なのはなぜですか?
解決
「完全な」とは異なり、「完全な」とは異なり、「完全な式」とは異なり、「完全な式」とは異なり、確かに定式的には定められていません。 Naive 解像度を見つけるのは非常に簡単です。リモートでさえ適切ではありません。すなわち、が証明するのが簡単であるが、どの解像度が極端に遅いのかが
有名な例は、 $ n $ 穴の穴(これは述べた; span class="math-container"> $ n + 1 $ ハトは、 $ n $ 穴のない穴に合わせることはできません)。 $ n $ 。
の時間的な範囲内での解像度のみを使用してこのステートメントの証明はありません。定理証明のための最も困難な問題であるところでは、すでに非常に困難な問題である解像者を選ぶための戦略を実装しなければならないことに注意して、定理証明のための最も実用的なアルゴリズムがの強化です。素朴な解像度、例えばハイパー解像度。
所属していません cs.stackexchange