使用 z3 的模块化算法

Question

我正在尝试证明如下陈述：

(assert (=
    (mod i n)
    (mod j n)))

(assert (> n 0))
    
(assert (not (=
    (mod (+ i 1) n)
    (mod (+ j 1) n))))

(check-sat)
(get-model)

其他是：

(((i % n) + j) % n) == ((i + j) % n)
((i - n + 1) % n) == ((i + 1) % n)
((((a - 1) % n) + 1) % n) == (a % n)

但是z3在证明这些陈述时似乎并没有终止。它们是否超出了 z3/smt 求解器的能力范围？

如果这是唯一的方法，我不介意做更明确的证明步骤，但这些规则看起来太初级了，我不知道从哪里开始。即使在使用归纳法时，我也会快速运行进入我期望为真的案例（如最初的示例），但似乎无法用 z3 证明。

我正在使用 z3 4.8.6，物有所值。任何人都可以阐明为什么这很难，或者可以指出 papers/z3 使这可行的标志的方向吗？

Answer 1

长话短说，是的。这些种类的属性对于 SMT 求解器来说太难处理了。它们本质上涉及非线性整数运算，没有判定过程。求解器有一堆内置的启发式方法，可能会或可能不会回答您的查询；但更多时候它会进入无限循环，正如您无疑观察到的那样。

详情请看这个回答： How does Z3 handle non-linear integer arithmetic?

你能做什么

如果您想坚持使用纯按钮解决方案，您实际上无能为力。在某些情况下，以下行会有所帮助：

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

这使用实数理论来解决您的查询（NRA：非线性实数算术 - 恰好是可判定的），然后查看解决方案是否实际上是整数。显然，这并不总是有效。特别是像mod这样的操作，用这个策略会比较难处理。

在实践中，我建议改为证明您的属性的特定实例。即运行一堆情况，每次固定n：

(assert (= n 10))

然后

(assert (= n 27))

等显然，这不会证明 all n，但在实际系统中，如果你仔细选择 n 的值，你可以剔除很多非定理这样。

如果你真的想为所有 n 证明这一点，那么请改用定理证明器。显然，这不会是按钮，但这是最先进的。这里有很多选择：Isabelle、HOL、HOL-Light、ACL2、Coq、Lean，.. 仅举几例。请注意，这些定理证明器中的大多数都内置了在引擎盖下使用 SMT 求解器来实现许多子目标的策略。所以，你有点两全其美，当然证明本身需要在这样的系统中手动分解。

使用 z3 的模块化算法

Modular arithmetic using z3

integer

z3

modulo

smt

你能做什么