罗宾逊的解决程序的缺点是什么？

Question

Paulson等。从lcf到isabelle / hol 说：

一阶逻辑的分辨率，原则上完成，但在实践中经常令人失望。

我认为完整意味着他们可以按一阶逻辑正确证明任何真正的公式。在自动推理手册我发现：

分辨率是一种透露完整的定理证明方法：可以从任何不可选择的条款集中推断出矛盾（即空条款）。

来自维基百科：

试图证明满足的一阶公式作为不可履行的公式可能导致不确定的计算

为什么这令人失望？

Answer 1

虽然“在实践中令人失望”肯定是不可思议的，与“完整”（这确实意味着“最终可以证明每个真正的公式），但很容易找到 Naive 分辨率的例子甚至不是远程足够的，即应该是易于证明的例子，但哪个分辨率非常慢。

一个名的例子是鸽子孔原理 命题逻辑中的$ n $ 孔（这是语句“=”math-container“> $ n + 1 $ 鸽子不能适用于 $ n $ 孔而无需重复）。在 $ n $ 中，只有在时间子指数中使用分辨率没有解决该声明的证明。

在谓词逻辑中甚至更差，在那里它很容易找到没有任何快速分辨率的语句。

请注意，决议的任何实施必须实施挑选的策略，该策略已经是一个非常困难的问题，以及一个活跃的研究领域，因为最实用的定理算法是增强天真的分辨率，例如 hyper-catevery 。