Z3有一个prove()
方法,可以证明两个公式的等价性。
但是,我找不到此prove()
方法的技术文档。 prove()
在幕后使用的“等价”的定义是什么?那是“部分等价”(在“回归验证”论文中提出),还是更强大的东西?
提醒一下,“部分等价”保证两个公式等价,如果给定相同的输入,它们产生相同的输出。
最佳答案
在“回归验证”中,我们正在检查一个较新版本的程序是否产生与早期版本相同的输出。也就是说,它是一种检查程序等效性 的方法。
在这种方法中,使用了诸如 Z3 之类的定理证明器(SMT 求解器)。话虽这么说,我们不应该混淆一阶逻辑中的程序等价和公式等价。 Z3 处理一阶逻辑公式。 First-order logic具有明确定义的语义。一个关键概念是可满足性。例如,公式 p 或 q
是可满足的,因为我们可以通过将 p
或 q
赋值为真来使其为真。另一方面,p and (not p)
是不可满足的。我们可以在 this section of the Z3 tutorial 中找到更多信息。 .
Z3 API 提供了检查一阶公式可满足性的程序。 Z3 Python 接口(interface)有一个prove
过程。它通过证明公式的否定是不可满足的来表明公式是有效的。这是一个建立在 Z3 API 之上的简单函数。 Here is a link到它的文档。文档是从代码中的 PyDoc 注释自动生成的。
请注意,prove(F)
正在检查公式 F
是否有效。因此,我们可以使用 prove(F == G)
来尝试证明两个 一阶 公式 F
和 G
是等价的。也就是说,我们实质上是在证明 F iff G
是一个有效的公式。
关于z3 - Z3 的 Prove() 方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14038210/