为什么 Z3 在某些情况下无法使用均匀度信息？

Question

我有以下有效的查询：

(set-info :status unknown)
(declare-fun n () Int)
(declare-fun b () Int)
(declare-fun c () Int)
(assert (= 0 (mod c 2))) ; c is even
(assert (= b (div c 2))) ; b = c/2
(assert (not (= c (* 2 b)))) ; c != 2*b
(check-sat)

果然不出所料。但是，如果我用 (n * (n+1)) 替换 c，我会得到未知（从提交 5068d2083dc0609801f572a0e3d14df753d36a03 构建的本地 z3，大约 4.5.1）或超时（在 http://rise4fun.com/Z3 上）：

(set-info :status unknown)
(declare-fun n () Int)
(declare-fun b () Int)
(declare-fun c () Int)
(assert (= 0 (mod (* n (+ 1 n)) 2)))
(assert (= b (div (* n (+ 1 n)) 2)))
(assert (not (= (* n (+ 1 n)) (* 2 b))))
(check-sat)

知道为什么在一种情况下它能解决问题而在另一种情况下却不行吗？

谢谢！ ~迪莫

Answer 1

当你输入 n * (n+1) 时，问题就变成了非线性的。（非线性意味着你 multiply/divide 非常数。）

在这种情况下，默认求解器不太可能产生结果，因为决策算法仅针对逻辑的线性片段。你本质上是受启发式的支配：如果他们能解决你的问题，那太好了；如果没有，你会得到一个 unknown 作为答案。

话虽如此，您可以使用 "strategies" 来引导求解器。在这种情况下，以下似乎有效：

(check-sat-using (and-then qfnra-nlsat smt))

有了这个，z3 成功地 returns unsat 您的查询。

有关详细信息，请参阅 http://rise4fun.com/z3/tutorial/strategies。知道哪种策略适用于哪种问题是一门艺术，但如果您通读了本教程，您可以很好地了解要尝试什么。

为什么 Z3 在某些情况下无法使用均匀度信息？

Why is Z3 having trouble using evenness information under some conditions?

z3