是否有可能证明这个定义的函数是 z3 中的对合？

Question

我正在尝试了解如何以证明已定义函数的某些数学特性的方式定义断言。正如中所讨论的，SMT 求解器不太适合归纳法，而归纳法通常需要证明数学质量。

在我的例子中，我有一个递归函数定义 identity function f(x) = x（作为一个简单的例子）：

(define-fun-rec identity-rec ((l String)) String
   (ite (= 0 (str.len l))
      ""
      (str.++ (str.at l 0) (identity-rec (str.substr l 1 (seq.len l))))))



(define-fun identity ((l String)) String
   (ite (= 0 (str.len l))
      ""
      (identity-rec l)))

表明这些特性不能开箱即用。但是，我很想知道 z3 中如何证明一般数学性质。我尝试使用所有量词来证明函数的 involution 但 z3 不会终止：

(assert
(forall ((a String))
    (=
        a
        (indentity (identity a))
    )
)

我的问题： 我们可以用什么断言来证明这样的递归函数是z3的对合？

Answer 1

您在这里无能为力。理想情况下，该策略是分别定义和证明基本情况和归纳步骤，然后（在元级别）论证属性对于所有字符串都是正确的。

对于基本情况，事情很简单。我会定义：

(define-fun check-inv ((x String)) Bool (= (identity (identity x)) x))

(define-fun base_case () Bool (check-inv ""))

然后：

(assert (not base_case))

如果你这样做，z3 会很高兴地说 unsat，即基本情况为真。对于归纳步骤，我定义：

(define-fun inductive_step () Bool
   (forall ((x String) (c String))
        (implies (and (= 1 (str.len c)) (check-inv x))
                 (check-inv (str.++ c x)))))

并希望证明：

(assert (not inductive_step))

唉，您会发现 z3 会阻塞这个查询，即不会终止。假设它做了一秒钟，然后您会得出结论（在元级别） identity 确实是一个内卷。但这必须在 z3 以上一级完成；由人或其他使用 z3 作为子引擎的证明工具。

那么，自然而然的问题就是问z3证明inductive_step的希望是什么？它绝对不会开箱即用。但也许您可以使用模式来诱导它这样做，有关详细信息，请参阅 https://rise4fun.com/z3/tutorialcontent/guide#h28。然而，请注意，即使您可以通过非常巧妙的模式实例化获得此证明，该证明也将非常脆弱：即使对您的定理或 z3 的实际实现进行微小更改也会影响结果，因为您将受无数启发式的支配。

长话短说：如果您的目标是证明递归函数的属性，那么您使用的工具是错误的。使用ACL2、HOL、伊莎贝尔等；是有目的地设计和构建来处理此类定理。 SMT 求解器不适合这里的要求。

是否有可能证明这个定义的函数是 z3 中的对合？

Is it possible to prove this defined function is an involution in z3?

smt

z3