在 Z3 中检查 N 向方程等价性的最有效方法是什么？

Question

假设我有一组 Z3 表达式：

exprs = [A, B, C, D, E, F]

我想检查它们是否等效，如果是，确定哪个。最明显的方法就是 N×N 比较（假设 exprs 由一些任意复杂的布尔表达式组成，而不是示例中的简单数字）：

from z3 import *
exprs = [IntVal(1), IntVal(2), IntVal(3), IntVal(4), IntVal(3)]
for i in range(len(exprs) - 1):
  for j in range(i+1, len(exprs)):
    s = Solver()
    s.add(exprs[i] != exprs[j])
    if unsat == s.check():
      quit(f'{(i, j)} are equivalent')

这是最有效的方法，还是有某种方法可以量化一组任意表达式？这是一个两步过程也是可以接受的，我首先了解 any 表达式是否等效，然后进行更长的检查以查看哪些特定表达式等效。

Answer 1

对于与性能相关的任何事情，答案是“视情况而定”。不过，在深入研究选项之前，请注意 z3 支持 Distinct，它可以检查是否有任意数量的表达式都不同：https://z3prover.github.io/api/html/namespacez3py.html#a9eae89dd394c71948e36b5b01a7f3cd0

当然，您在这里有一个更复杂的查询。我认为以下两种算法是您的选择：

显式成对检查

根据您的限制，最简单的做法可能是多次调用求解器，正如您提到的那样。首先，使用 Distinct 并调用以查看其否定是否可满足。（即，检查这些表达式中的某些表达式是否可以相等。）如果答案是 unsat，您就知道您不能相等。否则，像以前一样继续循环，直到找到可以使彼此相等的对。

一起进行多项检查

您也可以使用修改后的算法来解决您的问题，尽管约束条件更复杂，但希望速度更快。

为此，创建 Nx(N-1)/2 个布尔值，每对一个，等于那对不等价。为了说明这一点，假设您有表达式 A、B 和 C。创建：

X0 = A != B
X1 = A != C
X2 = B != C

现在循环：

询问 X0 || X1 || X2 是否可满足。
如果求解器返回unsat，那么A、B、C都是等价的。大功告成。
如果求解器返回 sat，则析取项 X0、X1 或 X2 中至少有一个为真。使用求解器给你的模型来确定哪些是错误的，并继续这些直到你得到 unsat.

这是一个简单的具体示例。假设表达式是 {1, 1, 2}:

询问 1 != 1 || 1 != 2 || 1 != 2 是否坐着。
会坐的。在模型中，这些析取至少有一个为真，而且它不会是第一个！在这种情况下，最后两个。将它们从您的列表中删除，留下 1 != 1.
再次询问 1 != 1 是否可满足。答案将是 unsat，您就完成了。

在最坏的情况下，您将对求解器进行 Nx(N-1)/2 次调用，如果碰巧其中 none 次可以等同于您一次消除一个。这是第一次调用 Not (Distinct(A, B, C, ...)) 很重要的地方；即，您将开始知道某对是等价的；希望迭代更快。

总结

我最初的预感是上面的第二种算法会更高效；虽然这真的取决于你的表达方式。我建议进行一些实验，找出最适合您的特定情况的方法。

一个Python解决方案

这是编码的算法：

from z3 import *

exprs = [IntVal(i) for i in [1, 2, 3, 4, 3, 2, 10, 10, 1]]

s = Solver()

bools = []
for i in range(len(exprs) - 1):
  for j in range(i+1, len(exprs)):
    b = Bool(f'eq_{i}_{j}')
    bools.append(b)
    s.add(b == (exprs[i] != exprs[j]))

# First check if they're all distinct
s.push()
s.add(Not(Distinct(*exprs)))
if(s.check()== unsat):
    quit("They're all distinct")
s.pop()

while True:
    # Be defensive, bools should not ever become empty here.
    if not bools:
        quit("This shouldn't have happened! Something is wrong.")

    if s.check(Or(*bools)) == unsat:
        print("Equivalent expressions:")
        for b in bools:
          print(f'   {b}')
        quit('Done')
    else:
        # Use the model to keep bools that are false:
        m = s.model()
        bools = [b for b in bools if not(m.evaluate(b, model_completion=True))]

这会打印：

Equivalent expressions:
   eq_0_8
   eq_1_5
   eq_2_4
   eq_6_7
Done

这对我来说是正确的！请注意，即使您有 3 个（或更多）相同的项目，这也应该正常工作；当然，您一次只能看到一对输出。因此，根据上游算法的需要，可能需要一些 post 处理来清理它。

请注意，我只测试了几个测试值；可能存在角落案例陷阱。如果有任何错误，请进行更彻底的测试并报告！

在 Z3 中检查 N 向方程等价性的最有效方法是什么？

What is the most efficient way of checking N-way equation equivalence in Z3?

z3

z3py

显式成对检查

一起进行多项检查

总结

一个Python解决方案