带阵列的 Z3 Forall

Question

Z3 提供未知的简单问题：

(assert
(forall ((y (Array Int Int)))
   (= (select y 1) 0))
 )
(check-sat)

我发现如果对forall取反就变成sat了，但是这个好像是特别简单的事情无法解决。

这引起了问题，因为我想解决的 class 个问题更像是

(declare-fun u () Int)
(assert
 (forall ((y (Array Int Int)) )
     (=> 
        (= u 0) (<= (select y 1) 0))
 )
)
(check-sat)

单独否定 forall 不是同一个问题，所以不能在这里完成。有什么方法可以将这种类型的问题提交给 Z3 以获得 un/sat 结果吗？

Answer 1

SMT 求解器总是存在量词问题，尤其是当它们涉及数组和交替量词时（如您的示例）。你基本上有 exits u. forall y. P(u, y)。 Z3 或任何其他 SMT 求解器将很难处理这类问题。

当你有一个量化的断言时，就像你在 top-level 处或嵌套 exists 处有 forall 一样，逻辑就变成了 semi-decidable。 Z3 使用 MBQI（model-based 量词实例化）来启发式地解决此类问题，但往往无法解决。问题不只是z3不行：这种问题没有决策程序，z3已经尽力了。

您可以尝试为此类问题提供量词模式以帮助 z3，但我没有看到将其应用于您的问题的简单方法。（当你有未解释的函数和量化的公理时，量词模式适用。参见 https://rise4fun.com/z3/tutorialcontent/guide#h28）。所以，我不认为它会为你工作。即使是这样，模式在编程时也非常挑剔，并且对于您的规范中可能看起来无害的更改并不健壮。

如果您要处理此类量词，SMT 求解器可能不太适合。查看 semi-automated 定理证明器，例如 Lean、Isabelle、Coq 等，它们旨在以更加规范的方式处理量词。当然，您失去了完全自动化，但这些工具中的大多数都可以使用 SMT 求解器来执行足够“简单”的子目标。这样，您仍然手动执行“heavy-lifting”，但大多数子目标由 z3 自动处理。（特别是精益的情况，请看这里：https://leanprover.github.io/）

Answer 2

有一个额外的右（右）括号，需要将其删除。另外，在forall语句前加上assert。

(assert ( forall ( (y (Array Int Int) ) ) 
   (= (select y 1) 0) 
))
(check-sat)

运行以上代码，你应该得到不满意的答案。

对于第二个程序，别名的回答可能对你有用。

带阵列的 Z3 Forall

Z3 Forall with array

arrays

quantifiers

z3