我正在尝试使用 Z3Py 证明函数,但它似乎返回了一个不正确的反例。 问题是什么?? (Z3-4.7.1-x86-win, Python-2.7.15)
>>> import z3
>>> A = z3.BitVec('A', 8)
>>> B = z3.BitVec('B', 8)
>>> C = z3.BitVec('C', 8)
>>> z3.prove((A*B)/C == A*(B/C))
counterexample
[A = 67, B = 86, C = 2]
>>> ((67*86)%256)/2
65
>>> (67*(86/2))%256
65
请您参考如下方法:
让我们看看 Z3 在做什么:
import z3
A = z3.BitVec('A', 8)
B = z3.BitVec('B', 8)
C = z3.BitVec('C', 8)
s = z3.Solver()
s.add((A*B)/C == A*(B/C))
print s.sexpr()
当你运行这个脚本时,你会得到:
$ python a.py
(declare-fun C () (_ BitVec 8))
(declare-fun B () (_ BitVec 8))
(declare-fun A () (_ BitVec 8))
(assert (= (bvsdiv (bvmul A B) C) (bvmul A (bvsdiv B C))))
啊,它在 8 位向量上使用 bvmul 和 bvsdiv。事实证明,乘法对于有符号-无符号无关紧要,但除法却很重要。因此,实际上完成映射是为了将结果映射到 -128 到 127 的范围,而不是(正如我怀疑您可能已经预料到的那样)到 0 到 255。
因此,如果您进行数学计算,左侧会减少到 -63,因为乘法会产生 5762,它会映射到 -126 在带符号的 8 位表示中。然而,右侧被缩减为 65;从而给你合法的反例。
为了避免这种情况,您可以使用旧的 Int 类型;或者通过 UDiv 告诉 Python 不要使用带符号的除法,参见这里:https://z3prover.github.io/api/html/namespacez3py.html#a64c02a843a4ac8781dd666a991797906
如果使用UDiv,可以得到更好的反例:
>>> import z3
>>> A = z3.BitVec('A', 8)
>>> B = z3.BitVec('B', 8)
>>> C = z3.BitVec('C', 8)
>>> z3.prove(z3.UDiv(A*B, C) == A*z3.UDiv(B, C))
counterexample
[A = 95, B = 140, C = 41]
>>> ((95*140)%256/41)%256
5
>>> (95*((140/41)%256))%256
29
我想这更符合您的预期。
