用 Python z3 API 简化方程

Question

我正在尝试学习如何在 Python z3 API.

中使用表达式来完成一些事情

我希望能够 simplify/reduce 包含中间变量的方程组。假设我有方程 (A = B && C) 和 (C = D || E)。在 z3 中，这些将表示为 (Bool('A') == And(Bool('B'), Bool('C')) 和 (Bool('C') == Or(Bool('D'), Bool('E'))。是否有一些函数或函数系列可用于生成简化和简化的方程 (A = B && (D || E))?
我希望能够将 z3 表达式转换为乘积总和形式（即 Or(minterm1, minterm2,...)。
一种确定两个布尔方程逻辑等价性的有效方法。
一种将布尔方程作为格式化字符串返回的方法（即不在用于声明函数的嵌套函数形式中。）

如果有人对这些项目有任何见解，我们将不胜感激。另外，如果需要进一步说明需要什么，请告诉我。

谢谢，

Answer 1

很好的问题。

不，一般不会。您可以获得 z3 来简化方程式，但是您的 "simple" 概念不太可能与其内部目的相匹配。人们经常要求这个功能，但它通常是一个非常困难的问题，并且根本不清楚简单的含义。话虽如此，z3 确实有 Goal 和 Tactic 的概念，甚至还有一个 simplify 策略可以使用。它会简化公式，但让它完全按照您希望的方式运行是徒劳的。

看看这个关于战术的重要资源，也许你可以四处看看以获得适合你的东西：http://www.cs.tau.ac.il/~msagiv/courses/asv/z3py/strategies-examples.htm
简化策略确实有一个 som 选项，我相信。这可能会成功。同样，请参阅上面的 link，其中有示例：
```
s = Then(With('simplify', arith_lhs=True, som=True),
     'normalize-bounds', 'lia2pb', 'pb2bv', 
     'bit-blast', 'sat').solver()
```
块 som=True 告诉求解器使用最小项求和。同样，您的里程数可能会因公式的确切结构而异，并且 z3 可能会引入可能会破坏目的的新名称。
当然可以！这就是 z3 excels 的作用。只需断言 f != g 其中 f 和 g 是您的方程式。如果 z3 说 unsat，那么您就知道它们对于所有变量赋值都是等价的。如果它给你一个模型，那就形成了它们等价性的反例。（否定相等技巧在 SMT 求解中很常见：当公式的否定不可满足时，公式就是重言式。因此，您可以断言您想要的否定并查看它是否返回 unsat。）

请注意，这就是 SMT（和 SAT）求解器 excel 处的内容。
对于您构建的任何公式 f，您可以发出 print f 并打印出来。但是正如您可能已经观察到的那样，它 不像教科书上的逻辑公式那样 。漂亮的打印机有一些选项来控制它的行为，但它可能不是你想要的。

但是，API 提供了一些功能，可以按照您的意愿遍历 AST 并提取节点。因此，如果您愿意，您可以编写自己的漂亮打印机。这样做并不十分困难，但这并不意味着它很简单：有很多情况需要考虑，根据我的经验，这样的打印机通常不难被愚弄；即，对于输入的微小变化会产生更糟糕的结果。

从实用的角度来看，虽然 z3 及其在 Python、C、Java 等中的高级 APIs 能够做你想做的一切，但它除了#3 之外不会开箱即用。我的建议是自己编写其他所有代码，并依靠 z3 检查 excel 所在的相等性。当然，这完全取决于您要做什么。祝你好运！

用 Python z3 API 简化方程

Simplifying Equations with Python z3 API

python

logic

solver

z3

z3py