Z3 / CVC4 / SMT-LIB 中的离散时间步长

Question

我在 SMT-LIB 中使用 Int 定义时间步长，这迫使我断言事情以确保在否定中没有任何事情发生：

(declare-sort Pkg) ; A package
(define-sort Time () Int) ; The installation step
; ...
(assert (forall ((t Time) (p Pkg)) (=> (< t 0) (not (installed p t)))))

我看到在 Z3 中我们可以用通常的风格定义归纳 Nats。使用 Nat 的归纳定义会好还是有更好的方法来做我上面想做的事情？

Answer 1

你真的应该坚持 Int，并适当地加入 >= 0 限制条件。 Z3 对 Int 了解很多，有各种证明规则和技巧来处理它。虽然您确实可以定义一个归纳 Nat 类型，但您将失去处理整数的所有内部机制，并且由于递归定义，Z3 的决策过程将效率较低；特别是与其他理论相结合。

话虽如此，除非您尝试，否则不可能知道：可能存在一些问题领域，归纳定义可能更适合。但单纯看你要处理的问题类型，旧 Int 似乎是你的正确选择。

另请参阅此相关问题： 这在您的上下文中绝对相关。