使用 Z3py 对 horn 子句进行不变归纳

Question

我目前正在使用 Z3py 来推导一些不变量，这些不变量被编码为 horn-clauses 的结合，同时还为不变量提供模板。如果您看到下面的代码片段，我首先从一个简单的示例开始。

x = 0;
while(x < 5){
  x += 1
}
assert(x == 5)

这转化为号角子句

x = 0 => Inv(x)

x < 5 /\ Inv(x) => Inv(x +1)

不是( x < 5) /\ Inv(x) => x = 5

这里的不变量是 x <= 5。

我已经为 a*x + b <= c 形式的不变量提供了一个模板因此求解器所要做的就是猜测 a、b 和 c 的一组值，这些值可以减少到 x <= 5.

然而，当我对它进行编码时，我总是感到不满意。如果尝试断言 Not (x==5) 我得到 a=2 、 b = 1/8 和 c = 2 作为反例对我来说意义不大。

我在下面提供了我的代码，如果您能帮助我更正我的编码，我将不胜感激。

x = Real('x')
x_2 = Real('x_2')
a = Real('a')
b = Real('b')
c = Real('c')
s = Solver()
s.add(ForAll([x],And(
Implies(x == 0 , a*x + b <= c),
Implies(And(x_2 == x + 1, x < 5, a*x + b <= c), a*x_2 + b <= c),
Implies(And(a*x + b <= c, Not(x < 5)), x==5)
)))
if (s.check() == sat):
    print(s.model())

编辑：它对我来说变得陌生了。如果我删除 x_2 定义并在第二个 horn 子句中将 x_2 替换为 (x + 1) 并删除 x_2 = x_2 + 1，我得到不满意我在最后的 horn 子句中写 Not( x==5) 还是 x==5。

Answer 1

有两件事阻止了您的原始编码工作：

1) 对于 x_2 的单个值，不可能满足所有 x 的 x_2 == x + 1。因此，如果你要写 x_2 == x + 1，x 和 x_2 都需要被普遍量化。

2) 有点令人惊讶的是，这个问题在整数上是可以解决的，但在实数上却不行。您可以看到子句 x < 5 /\ Inv(x) => Inv(x + 1) 的问题。如果 x 是整数，则 x <= 5 满足。但是，如果允许 x 是任何实数，那么您可以得到 x == 4.5，它同时满足 x < 5 和 x <= 5，但不满足 x + 1 <= 5，所以Inv(x) = (x <= 5)现实中不满足这个问题

此外，您可能会发现定义 Inv(x) 很有帮助，它可以大大清理代码。以下是这些更改对您的问题的编码：

from z3 import *

# Changing these from 'Int' to 'Real' changes the problem from sat to unsat.
x = Int('x')
x_2 = Int('x_2')
a = Int('a')
b = Int('b')
c = Int('c')

def Inv(x):
    return a*x + b <= c

s = Solver()

# I think this is the simplest encoding for your problem.
clause1 = Implies(x == 0 , Inv(x))
clause2 = Implies(And(x < 5, Inv(x)), Inv(x + 1))
clause3 = Implies(And(Inv(x), Not(x < 5)), x == 5)
s.add(ForAll([x], And(clause1, clause2, clause3)))

# Alternatively, if clause2 is specified with x_2, then x_2 needs to be
# universally quantified.  Note the ForAll([x, x_2]...
#clause2 = Implies(And(x_2 == x + 1, x < 5, Inv(x)), Inv(x_2))
#s.add(ForAll([x, x_2], And(clause1, clause2, clause3)))

# Print result all the time, to avoid confusing unknown with unsat.
result = s.check()
print result
if (result == sat):
    print(s.model())

还有一件事：将 a*x + b <= c 写成模板对我来说有点奇怪，因为对于某些整数 d，这与 a*x <= d 相同。

使用 Z3py 对 horn 子句进行不变归纳

Invariant induction over horn-clauses with Z3py

logic

logic-programming

z3

z3py