有没有一种方法可以在Z3中表达假设(我使用Z3Py库),这样引擎就不会检查它们的有效性,而是将它们作为基础理论,就像在定理证明中一样?
例如,假设我有两个参数类型为Real的一元函数。我想告诉Z3引擎,对于所有输入值,f1(t)等于f2(t)。
在Z3Py中编码,看起来如下所示:
t=实数("t")
假设1=ForAll(t,f1(t)=f2(t))。
给出的代码的问题是,我的断言集很大,并且我使用了量词(我试图证明实时系统的可满足性)。如果我将上述断言添加到其他断言的集合中,则检查过程不会终止。
有没有一种方法可以在Z3中表达假设(我使用的是Z3Py库),这样引擎就不会检查它们的有效性,而是将它们作为基础理论,就像在定理证明中一样?
事实上,添加到Z3中的所有断言都被视为所谓的假设。Z3检查断言的可满足性,它不检查有效性。若要检查公式F的有效性,您可以断言(not F),并检查(not F)的可满足性。如果(非F)未被设置,则F是有效的。如果你有背景公理,你本质上是在检查背景=>F的有效性,所以你可以检查背景&(不是F)。
Z3是否终止于您的查询取决于您使用的理论和量词的组合。查询组合的功能越多,难度就越大。对于纯线性算术或多项式实算术上的公式,在SMT-LIB分类中,这些被称为LRA、LIA和NRA(见smtlib.org)Z3使用了最近添加的专门决策程序。
是的,正如你所描述的那样,这是可能的,但你最终会使用量词,这当然意味着你正在解决一个更难的问题,Z3的行为会有所不同(你最终可能会使用完全不同的解算器,它们甚至不共享太多源代码)。
对于给定的特定示例,可以廉价地消除量词,因为它具有函数定义的形式(ForAll x.f(x)=…),也就是说,我们可以用右手边替换f的所有出现,然后该量词被平凡地满足。在Z3中,这是由宏查找器完成的,它可以作为一种策略(名称为"宏查找器")应用,或者如果您正在使用"smt"策略(通过其他人隐式或直接),则可以设置smt.macro_finder=true.