Z3 中的唯一变量名称

Question

我需要依赖两个 Z3 变量可以不同名吗？可以肯定的是，我使用了 tuple_example1() from test_capi.c in z3/examples/c 并更改了原始代码：

// some code before that ...
x    = mk_real_var(ctx, "x");
y    = mk_real_var(ctx, "y"); // originally y is called "y"
// some code after that ...

至：

// some code before that ...
x    = mk_real_var(ctx, "x");
y    = mk_real_var(ctx, "x"); // but now both x and y are called "x"
// some code after that ...

并且（如预期的那样）输出更改为：

tuple_example1
tuple_sort: (real, real)
prove: get_x(mk_pair(x, y)) = 1 implies x = 1
valid
disprove: get_x(mk_pair(x, y)) = 1 implies y = 1
invalid
counterexample:
y -> 0.0
x -> 1.0

至：

tuple_example1
tuple_sort: (real, real)
prove: get_x(mk_pair(x, y)) = 1 implies x = 1
valid
disprove: get_x(mk_pair(x, y)) = 1 implies y = 1
valid
BUG: unexpected result.

然而，当我仔细观察时，我发现 Z3 并没有真正失败或任何东西，它只是一个天真的（驱动程序）打印到控制台。所以我继续写了 完全相同的测试，其中 y 是一个名为 "x" 的 int 类型。令我惊讶的是，Z3 可以处理 两个具有 相同名称 的变量 当它们具有不同的种类时：

tuple_example1
tuple_sort: (real, real)
prove: get_x(mk_pair(x, y)) = 1 implies x = 1
valid
disprove: get_x(mk_pair(x, y)) = 1 implies y = 1
invalid
counterexample:
x -> 1.0
x -> 0

真的是这样吗？还是只是巧合？？非常感谢任何帮助，谢谢！

Answer 1

一般来说，SMT-Lib 允许重复的变量名，只要它们有不同的种类。请参阅 the standard 的第 27 页。特别是，它说：

Concretely, a variable can be any symbol, while a function symbol can be any identifier (i.e., a symbol or an indexed symbol). As a consequence, contextual information is needed during parsing to know whether an identifier is to be treated as a variable or a function symbol. For variables, this information is provided by the three binders which are the only mechanism to introduce variables. Function symbols, in contrast, are predefined, as explained later. Recall that every function symbol f is separately associated with one or more ranks, each specifying the sorts of f’s arguments and result. To simplify sort checking, a function symbol in a term can be annotated with one of its result sorts σ. Such an annotated function symbol is a qualified identifier of the form (as f σ).

同样在同一份文件的第31页，它进一步阐明了"ambiguity"，因此：

Except for patterns in match expressions, every occurrence of an ambiguous function symbol f in a term must occur as a qualified identifier of the form (as f σ) where σ is the intended output sort of that occurrence

因此，在 SMT-Lib 术语中，您应该这样写：

(declare-fun x () Int)
(declare-fun x () Real)

(assert (= (as x Real) 2.5))
(assert (= (as x Int) 2))

(check-sat)
(get-model)

这会产生：

sat
(model
  (define-fun x () Int
    2)
  (define-fun x () Real
    (/ 5.0 2.0))
)

您在 C 接口中观察到的本质上是相同的渲染。当然，接口强制执行多少 "checking" 完全是特定于求解器的，因为 SMT-Lib 对其他语言的 C API 或 API 只字未提。这实际上解释了您在输出中看到的 BUG 行。在这一点上，行为完全是特定于求解器的。

但长话短说，SMT-Lib 确实允许两个变量使用相同的名称，只要它们具有不同的类别即可。

Z3 中的唯一变量名称

Unique variable names in Z3

variables

z3