无法在 Z3 中为 GADT 创建抽象加法运算

Question

问题

我正在使用 Z3 中的以下 Datatype 定义。我的 objective 本质上是 "overload" 加法运算符。我使用 ForAll 尝试了以下技巧，但 Z3 似乎认为它无效。

问题

这是怎么回事？为什么这不起作用？

代码

import pytest
from z3 import Datatype, IntSort, Solver, Ints

def test_Whosebug():
    FooBar = Datatype('FooBar')
    FooBar.declare('foo', ('unfoo', IntSort()))
    FooBar.declare('bar', ('unbar', FooBar))
    FooBar.declare('plus', ('left', FooBar), ('right', FooBar))
    FooBar = FooBar.create()

    foo = FooBar.foo
    unfoo = FooBar.unfoo
    bar = FooBar.bar
    unbar = FooBar.unbar
    plus = FooBar.plus

    solver = Solver()
    x, y = Ints('x y')
    solver.add(ForAll[x, y], plus(foo(x), foo(y)) == foo(x + y))
    assert str(solver) == "sat"

这没有通过，因为结果是 "unsat"。

Answer 1

系统是 unsat，因为你本质上说：

  forall x, y => foo (x+y) = plus (foo x, foo y)

这显然是错误的，因为 foo 和 plus 是您的数据类型的两个不同的构造函数，因此无论您传递什么，它们永远不会相等。请注意，数据类型是自由生成的：每个构造函数定义一个不同的值。

我怀疑你想说的是 plus 生成了一些 "number" 之类的东西使得 foo (x+y) = plus (foo x, foo y) 成立。如果是这种情况，那么 not 使 plus 成为构造函数。相反，使它成为一个未解释的函数，它接受一个 FooBar 并产生一个 Int；并适当断言上述内容。在 SMTLib 表示法中，它看起来像：

(declare-datatypes ((FooBar 0)) (((foo (unfoo Int)) (bar (unbar FooBar)))))
(declare-fun plus (FooBar FooBar) Int)
(assert (forall ((x Int) (y Int)) (= (plus (foo x) (foo y)) (unfoo (foo (+ x y))))))
(check-sat)
(get-model)

唉，虽然这是非常好的编码，但 z3 只是出去吃午饭而已：

$ z3 -v:3 a.smt2
... many lines of verbose output showing quantifier instantiation ...

在这种情况下，电子匹配引擎很难找到模型。当然，如果您有额外的约束，您可能会得到有用的结果，或者您可以尝试模式来帮助 z3。但是，根据我的经验，其中 none 确实会真正起作用，因为量词只会使问题对于当前的 SMT 解决技术来说太难了。

注意。您的程序中有一个小错字，倒数第二行应该是：

    solver.add(ForAll([x, y], plus(foo(x), foo(y)) == foo(x + y)))

（注意括号。）

无法在 Z3 中为 GADT 创建抽象加法运算

Cannot create abstract addition operation for GADT in Z3

python

z3

z3py