是否可以将 bit-blast 和 soft-assert 与 z3 求解器一起使用？

Question

我正在尝试使用 z3 smt 求解器为受约束的变量分配值。除了硬约束外，我还有一些软约束（例如 a != c）。我希望能够用 assert 指定硬约束，用 soft-assert 指定软约束，如果我用 (check-sat).

求解，这会起作用

有些文件又大又复杂，如果我使用 (check-sat-using (then simplify solve-eqs bit-blast sat)) 打开位爆破，只能在合理的时间内解决。当我这样做时，软断言似乎被忽略了（下面的示例或 rise4fun）。这是预期的吗？可以同时使用bit-blast求解和soft-assert吗？

以下 SMT 代码定义了 4 个位向量，a、b、c 和 d，它们都应该能够采用唯一值，但只能强制通过软断言来做到这一点。使用 check-sat（第 39 行）按预期工作，但 check-sat-using（第 38 行）将 b 和 d 分配给相同的值。

(set-option :produce-models true)
(set-logic QF_BV)

;; Declaring all the variables
(declare-const a (_ BitVec 2))
(declare-const b (_ BitVec 2))
(declare-const c (_ BitVec 2))
(declare-const d (_ BitVec 2))

(assert (or (= a #b00)
            (= a #b01)
            (= a #b10)
            (= a #b11)))

(assert (or (= b #b00)
            (= b #b01)
            (= b #b10)
            (= b #b11)))

(assert (or (= c #b00)
            (= c #b01)
            (= c #b10)
            (= c #b11)))

(assert (or (= d #b00)
            (= d #b01)
            (= d #b10)
            (= d #b11)))

;; Soft constraints to limit reuse
(assert-soft (not (= a b)))
(assert-soft (not (= a c)))
(assert-soft (not (= a d)))
(assert-soft (not (= b c)))
(assert-soft (not (= b d)))
(assert-soft (not (= c d)))

(check-sat-using (then simplify solve-eqs bit-blast sat))
;;(check-sat)
(get-value (a
            b
            c
            d))

Answer 1

好问题！当您使用 assert-soft 时，优化引擎默认启动。您可以通过将您的程序与 (check-sat) 子句和运行更高的冗长程度一起使用来看到这一点。我已将您的程序放在一个名为 a.smt2:

的文件中

$ z3 -v:3 a.smt2
(optimize:check-sat)
(sat.solver)
(optimize:sat)
(maxsmt)
(opt.maxres [0:6])
(sat.solver)
(opt.maxres [0:0])
found optimum
sat
((a #b01)
 (b #b00)
 (c #b11)
 (d #b10))

因此，我们可以看到 z3 将此视为一个优化问题，它考虑了软约束并为您提供了您正在寻找的 "disjointness"。

让我们做同样的事情，但这次我们将使用指定要使用的策略的 check-sat 调用。我们得到：

$ z3 -v:3 a.smt2
(smt.searching)
sat
((a #b11)
 (b #b11)
 (c #b11)
 (d #b10))

这证实了您的怀疑：当您确切地告诉 z3 要做什么时，它并没有执行优化过程。事后看来，这是意料之中的，但我同意这相当令人惊讶。

接下来的问题是我们是否可以明确告诉 z3 进行优化。但是我不确定这在战术语言中是否可行。我认为这个问题非常值得在他们的问题站点 (https://github.com/Z3Prover/z3/issues) 上提问，看看是否有魔法咒语可以用来从战术语言中启动 maxres 引擎。（由于多种原因，这可能是不可能的，但没有理由在这里推测。）请在这里报告你发现了什么！

是否可以将 bit-blast 和 soft-assert 与 z3 求解器一起使用？

Is it possible to use both bit-blast and soft-assert with the z3 solver?

solver

assertion

smt

z3