2

我正在使用 Z3 的 ELIM_QUANTIFIERS 功能从位向量的公式中消除量词。我遇到了以下情况，Z3 产生了正确但过于复杂的结果，我想知道是否存在重写我的问题的方法，或者是否有配置选项会导致我期望的简单结果。

首先，这是一个按预期工作的示例。它指出，对于长度为 4 的位向量，存在一个与其相等的位向量。

(set-option ELIM_QUANTIFIERS true)
(declare-fun a () BitVec[4])
(simplify (exists ((x BitVec[4])) 
          (= a x)))

Z3 为本示例生成以下输出。

success
success
true

但是，如果我添加一个否定：

(set-option ELIM_QUANTIFIERS true)
(declare-fun a () BitVec[4])
(simplify (exists ((x BitVec[4])) 
          (not (= a x))))

然后 Z3 产生以下输出，其中列出了向量的所有可能值，而不是只返回“true”。

success
success
(let (($x54 (= (_ bv0 4) a)))
(let (($x55 (not $x54)))
(let (($x61 (= (_ bv2 4) a)))
(let (($x62 (not $x61)))
(let (($x68 (= (_ bv6 4) a)))
(let (($x69 (not $x68)))
(let (($x75 (= (_ bv4 4) a)))
(let (($x76 (not $x75)))
(let (($x82 (= (_ bv12 4) a)))
(let (($x83 (not $x82)))
(let (($x89 (= (_ bv8 4) a)))
(let (($x90 (not $x89)))
(let (($x95 (= (_ bv1 4) a)))
(let (($x96 (not $x95)))
(let (($x102 (= (_ bv5 4) a)))
(let (($x103 (not $x102)))
(let (($x109 (= (_ bv13 4) a)))
(let (($x110 (not $x109)))
(let (($x116 (= (_ bv9 4) a)))
(let (($x117 (not $x116)))
(let (($x123 (= (_ bv3 4) a)))
(let (($x124 (not $x123)))
(let (($x130 (= (_ bv7 4) a)))
(let (($x131 (not $x130)))
(let (($x137 (= (_ bv14 4) a)))
(let (($x138 (not $x137)))
(let (($x144 (= (_ bv10 4) a)))
(let (($x145 (not $x144)))
(let (($x151 (= (_ bv11 4) a)))
(let (($x152 (not $x151)))
(let (($x158 (= (_ bv15 4) a)))
(let (($x159 (not $x158)))
(or $x159 $x152 $x145 $x138 $x131 $x124 $x117 $x110 $x103 $x96 $x90 $x83 $x76 $x69 $x62 $x55)))))))))))))))))))))))))))))))))

对于较长的位向量，例如大小为 32 或更大，Z3 不会在合理的时间内产生结果，因为它可能会枚举 32 位变量的所有可能值。

请注意，在这种特殊情况下，我可以只使用 check-sat 来检查公式的有效性；但是，在一般情况下，我有兴趣获得与原始公式等效的无量词表达式，而不仅仅是检查其有效性。

我正在为 Linux 使用 Z3 v3.2。

4

1 回答 1

1

谢谢，这是一个很好的简单示例，显示了用于位向量的方法的局限性。它实际上只适用于解决方案数量相对较少的公式。以这种方式在消除过程中无法打开/关闭位向量。这是在 Z3 中改进的一个有效点。有几个潜在的解决方法：首先，布尔量词消除，虽然它也是初级的（它只是枚举可满足的实例并消除布尔变量），但它确实产生了更简单的结果“真”。当你从这个例子中对你的位向量进行位爆破时。第二个途径是考虑您的问题是否可以在 UFBV 片段中重新表述，其中可满足性不需要量词消除。

于 2012-04-12T05:12:15.610 回答