在有限域上枚举 Z3 中的模型

Question

我正在用 Python 在 Z3 中试验 FD。

我有以下代码：

F = FiniteDomainSort('F', 3)
u=Const('u', F)
v=Const('v', F)
s = Solver()
s.add(u !=v )

因此，FD 上的变量 {u,v} 排序 {1,2,3}，并且它们需要不同..

目标：我想枚举所有可能的模型。

我先写了这段代码，打印'first'三个模型：

i = 0
while s.check()==CheckSatResult(Z3_L_TRUE) and i<3:
    m=s.model()
    print(m)
    s.add(Or(u != m.get_interp(u), v != m.get_interp(v)))
    print(s.sexpr())
    i = i+1

不过，好像不行。尽管正确添加了新约束，但我总是得到相同的模型：

[v = 1, u = 0]
(declare-fun v () F)
(declare-fun u () F)
(assert (distinct u v))
(assert (or (distinct 0 u) (distinct 1 v)))
(rmodel->model-converter-wrapper
v -> 1
u -> 0
)

[v = 1, u = 0]
(declare-fun v () F)
(declare-fun u () F)
(assert (distinct u v))
(assert (or (distinct 0 u) (distinct 1 v)))
(assert (or (distinct 0 u) (distinct 1 v)))
(rmodel->model-converter-wrapper
v -> 1
u -> 0
)

[v = 1, u = 0]
(declare-fun v () F)
(declare-fun u () F)
(assert (distinct u v))
(assert (or (distinct 0 u) (distinct 1 v)))
(assert (or (distinct 0 u) (distinct 1 v)))
(assert (or (distinct 0 u) (distinct 1 v)))
(rmodel->model-converter-wrapper
v -> 1
u -> 0
)

我从这个 answer:

中找到了以下代码

def get_models(F, M):
    result = []
    s = Solver()
    s.add(F)
    while len(result) < M and s.check() == sat:
        m = s.model()
        result.append(m)
        # Create a new constraint the blocks the current model
        block = []
        for d in m:
            # d is a declaration
            if d.arity() > 0:
                raise Z3Exception("uninterpreted functions are not supported")
            # create a constant from declaration
            c = d()
            if is_array(c) or c.sort().kind() == Z3_UNINTERPRETED_SORT:
                raise Z3Exception("arrays and uninterpreted sorts are not supported")
            block.append(c != m[d])
        s.add(Or(block))
    return result

但它似乎遇到了与我的代码相同的问题：

F = FiniteDomainSort('F', 3)
u=Const('u', F)
v=Const('v', F)
s = Solver()
F = [u!=v]
print(get_models(F,3))

[[v = 0, u = 1], [v = 0, u = 1], [v = 0, u = 1]]

问题：在处理有限域时枚举所有模型的工作方法是什么？

谢谢

Answer 1

Finite-domain z3 中的排序仅供 Datalog 引擎使用。其他用途无效且不受支持。理想情况下，您希望 z3 能够捕获此类用途并拒绝它们；唉，它并没有这样做，导致了这些混乱。

详情见https://github.com/Z3Prover/z3/issues/4842。

如上述问题单所述，推荐的解决方案是改用枚举。

在有限域上枚举 Z3 中的模型

Enumerating models in Z3 over finite domains

z3

z3py