支持 SMT 求解器中的整数除法

Question

我已经在以下 SMT 输入上执行了 z3 和 CVC4。两者都 return 未知。

;!(a,b,c).(0<=a & 0<=b & 1<=c
;               =>
;               (a+(b mod c)) mod c = (a+b) mod c)
;
;
(set-logic NIA)
(set-option :print-success false)

(declare-fun a () Int)
(declare-fun b () Int)
(declare-fun c () Int)

(assert (<= 0 a))
(assert (<= 1 c))
(assert (<= 0 b))

(assert (! (not (= (mod (+ a (mod b c)) c) (mod (+ a b) c))) :named goal))
(check-sat)
(exit)

他们不能决定可满足性有什么根本原因吗？
哪些选项或其他求解器适合解决此类问题？

Answer 1

是的，非线性整数运算对于 SMT 求解器来说很困难是有一个根本原因的。 Leo 在

中详细解释了这一点

因此，期望 SMT 求解器在这个领域表现出色是不合理的。建议使用适当的定理证明器，如 Isabelle、Coq、Lean、ACL2、HOL、HOL-Light 等。当然，证明大部分是手动的，但这些系统通常与 SMT 求解器连接以实现许多目标，就可判定性而言，让您两全其美。

请注意，即使是 Leo 描述的 (check-sat-using qfnra-nlsat) 技巧也无法解决您的问题，因为 mod 对 real 的解释根本无法帮助您。（一般来说，qfnra-nlsat 技巧可以找到模型，但永远不会产生 unsat，因为它主要是一种模型搜索策略。）

开箱即用的最佳方法是通过具体化 c 来证明问题的实例。即，添加以下形式的断言：

(assert (= c 12))

你会立即看到 z3 returns unsat。当然，这还不够，但是暂时使用按钮式求解器（除非他们为这个问题添加“自定义”启发式方法！）你不能做得更好。

支持 SMT 求解器中的整数除法

Support for integer division in SMT solvers

z3

smt

cvc4