Z3 支持指数

Question

我是 Z3 的新手，我想了解它的工作原理，以及它能做什么和不能做什么。我知道 Z3 至少一些通过幂 (^) 运算符支持指数（参见 , How to represent logarithmic formula in z3py, and Use Z3 and SMT-LIB to define sqrt function with a real number）。我不清楚这种支持有多广泛，以及 z3 可以对指数做出什么样的推论。

这是一个涉及 z3 可以分析的指数的简单示例。我们定义一个指数函数，然后要求它验证 exp(0) == 1:

(define-fun exp ((x Real)) Real
  (^ 2.718281828459045 x))
(declare-fun x1 () Real)
(declare-fun y1 () Real)
(assert (= y1 (exp x1)))
(assert (not (=> (= x1 0.0) (= y1 1.0))))
(check-sat)
(exit)

Z3 returns 不满意，符合预期。另一方面，这是 Z3 无法分析的一个简单示例：

(define-fun exp ((x Real)) Real
  (^ 2.718281828459045 x))
(declare-fun x1 () Real)
(declare-fun y1 () Real)
(assert (= y1 (exp x1)))
(assert (not (< y1 0.0)))
(check-sat)
(exit)

这应该是可以满足的，因为从字面上看，x1 的任何值都会使 y1 > 0。但是，Z3 returns 未知。天真地我可能期望 Z3 能够分析这个，因为它可以分析第一个例子。

我意识到这个问题有点宽泛，但是：谁能告诉我 Z3 如何处理指数的任何见解，以及（更具体地说）为什么它可以解决我给出的第一个示例而不是第二个示例？

Answer 1

笼统的不好说，因为非线性求解是有挑战性的，但是你介绍的这个案例其实没有那么神秘。您写道：

(assert (= y (exp x)))
(assert (not (=> (= x 0) (= y 1))))

Z3 将简化第二个断言，产生：

(assert (= y (exp x)))
(assert (= x 0))
(assert (not (= y 1)))

然后它将传播第一个相等性，产生：

(assert (= y (exp 0)))
(assert (not (= y 1)))

现在当 exp 被扩展时，你有一个常量^常量的情况，Z3 可以处理它（对于整数指数等）。

对于第二种情况，你问的是一个非常非常基本的关于变量指数的问题，Z3 马上就吐了。这并不奇怪，因为关于变量指数的许多问题要么已知无法计算，要么未知但很难。

Z3 支持指数

Z3 support for exponentials

smt

z3