Z3 中的幂和对数

Question

我正在尝试学习 Z3，但以下示例让我感到困惑：

from z3 import *
a = Int("a")
b = Int("b")
print(solve(2**a <= b))
print(solve(a > 0, b > 0, 2**a <= b))

我希望它 returns “[a = 1, b = 2]” 但它 returns “未能解决”。

为什么解决不了？

是否可以在 Z3 中使用幂和对数进行计算？我如何找到一个数字的二进制字符串表示的长度（log base 2）？

Answer 1

长话短说，z3（或一般的 SMT 求解器）无法处理这样的非线性约束。 Exponentiation/Logs 等很难处理，并且没有对它们进行整数判定的程序。即使超过实数，它们也很难处理。也就是说，求解器将应用一些试探法，这些试探法可能有效也可能无效。但是对于这些类型的约束，SMT 求解器并不是合适的工具。

有关 z3 中非线性算术的较早答案，请参阅此答案：

如果您有兴趣，这里有更多详细信息。首先，SMTLib 或 z3 中没有整数的幂运算符。如果查看生成的程序，您会发现它实际上超过了实际值：

from z3 import *
a = Int("a")
b = Int("b")

s = Solver()
s.add(2**a <= b)
print(s.sexpr())
print(s.check())

这会打印：

(declare-fun b () Int)
(declare-fun a () Int)
(assert (<= (^ 2 a) (to_real b)))

unknown

注意转换为 to_real。 ^ 运算符自动创建一个实数。解决这个问题的方法是，如果求解器可以提出一个实数的解决方案，然后检查结果是否为整数。让我们看看如果我们尝试 Reals:

会发生什么

from z3 import *
a = Real("a")
b = Real("b")

s = Solver()
s.add(2**a <= b)
print(s.check())
print(s.model())

这会打印：

sat
[b = 1, a = 0]

太棒了！但是你也想要 a > 0, b > 0;所以让我们补充一下：

from z3 import *
a = Real("a")
b = Real("b")

s = Solver()
s.add(2**a <= b)
s.add(a > 0)
s.add(b > 0)
print(s.check())

这会打印：

unknown

所以，求解器也无法处理这种情况。您可以玩弄战术 (qfnra-nlsat)，但一般情况下不太可能处理此类问题。同样，请参阅了解详细信息。

Z3 中的幂和对数

Power and logarithm in Z3

z3

z3py