定理证明中的归纳证明（Z3，Vampire，使用 TPTP 语法）

Question

我正在使用 TPTP 语法测试一些定理证明器（例如 Z3、Alt-Ergo、Vampire 等）的归纳能力。令我惊讶的是，none 他们成功证明了以下简单的猜想：

tff(t1, type, (fun: $int > $int )).

tff(ax1, axiom, ( 
    ! [A: $int] : (
        $less(A, 1) => (fun(A) = 123)
    )
)).

tff(ax2, axiom, ( 
    ! [A: $int] : (
        $greatereq(A, 1) => (fun(A) = fun($difference(A, 1))) 
    )
)).

tff(conj1, conjecture, ! [A: $int] : ($greatereq(A, 1) => (fun(A) = 123))).

% END OF SYSTEM OUTPUT
% RESULT: SOT_EWCr1V - Z3---4.8.9.0 says Timeout - CPU = 60.09 WC = 35.47 
% OUTPUT: SOT_EWCr1V - Z3---4.8.9.0 says None - CPU = 0 WC = 0

这个猜想可以很容易地通过归纳法证明，但是对于我测试过的绝大多数定理证明者来说，情况似乎并非如此。显然，如果我将域限制为仅一个元素而不是整组整数，则 ATP 会成功，因为它只需要检查一组有限的数字：

tff(t1, type, (fun: $int > $int )).

tff(ax1, axiom, ( 
    ! [A: $int] : (
        $less(A, 1) => (fun(A) = 123)
    )
)).

tff(ax2, axiom, ( 
    ! [A: $int] : (
        $greatereq(A, 1) => (fun(A) = fun($difference(A, 1))) 
    )
)).

tff(conj1, conjecture, ! [A: $int] : ((A = 5) => (fun(A) = 123))).

% END OF SYSTEM OUTPUT
% RESULT: SOT_j9liHr - Z3---4.8.9.0 says Theorem - CPU = 0.00 WC = 0.08 
% OUTPUT: SOT_j9liHr - Z3---4.8.9.0 says Proof - CPU = 0.00 WC = 0.09

这是自动定理证明器的一般限制吗？有什么工具可以很好地进行归纳吗？

PS: 您可以使用以下在线工具进行尝试：https://tptp.org/cgi-bin/SystemOnTPTP

PS2: 可在此处找到 TPTP 语法手册：https://www.tptp.org/TPTP/TR/TPTPTR.shtml

Answer 1

这是意料之中的。 SMT 求解器不进行归纳 out-of-the-box。您可以通过证明基本情况“哄”他们进行归纳，然后提出 induction-hypothesis 并让他们使用量词证明它；但这通常是徒劳的。 SMT 求解器根本不是进行归纳证明的正确选择。以下是有关此问题的一些关于 Whosebug 的相关先前讨论：

list concat in z3

还有许多其他人。

话虽如此，SMTLib 中的新 define-fun-rec 构造允许递归定义，其证明自然通过归纳完成。所以，我希望社区会朝着那个方向前进；随着时间的推移增加归纳能力。例如，参见：

http://lara.epfl.ch/~reynolds/VMCAI2015-ind/smt-ind-RK.pdf

有关如何在 SMT 求解器中正确执行此操作的论文。据我所知，CVC5 已经包含了其中的一些想法，但在这一点上期待 out-of-the-box 归纳证明是天真的。（参见 https://github.com/cvc5/cvc5/issues/1796）

所以，长话短说：不，SMT 求解器不进行归纳。您可以哄骗他们这样做，并且最近的工作增加了更多功能，但是 push-button 体验不太可能。如果您的目标是对递归定义进行推理，因此您依赖于归纳法，那么最好的办法是使用 semi-automated 定理证明器，例如 Isabelle、Coq、HOL、HOL-Light、ACLL2、Lean 等。 . 所有这些都有强大的感应设施。此外，他们将 SMT 求解器作为“策略”，因此您可以在这个意义上获得两全其美。（即，使用手动策略将您的证明分解为足够简单的子目标，处理归纳等，并将其余部分发送到 SMT-solver。）

Answer 2

正如上面的评论所指出的，Vampire 支持归纳法。然而，与其他定理证明者一样，让 Vampire 做你想做的事有时有点棘手。在这种情况下，要让它使用归纳法，你必须运行和 options

--mode portfolio --schedule induction

设置了这些选项后，Vampire 很快就找到了上述证明（在我的机器上是 0.04 秒）

TPTP 网站不允许您在运行证明时设置特定选项，因此如果您想尝试以上内容，则必须从 here 获取 Vampire 版本或从来源。

定理证明中的归纳证明（Z3，Vampire，使用 TPTP 语法）

Inductive proofs in theorem provers (Z3, Vampire, with TPTP syntax)

logic

formal-verification

logic-programming

theorem-proving

z3