哪种编码更适合使用 Z3 来求解偏序理论？

Question

我正在考虑对偏序关系进行编码以将其提供给 Z3 的多种方式。

问题已经以各种方式受到限制，并使用 QF_ 逻辑变体（主要是 LIA 或 LRA）。

我有额外的约束可以表达，以部分顺序改进解决方案，形式为，if variable ei>0 => a0 precedes ai，其中 ei 是我存在的问题的变量 ai 变量是新的，表示 "precedes" 偏序约束。

所以这个偏序将以不同的方式限制根据 ei 获得的解决方案。

一种解决方案可能是使用未解释的函数，例如此示例： https://rise4fun.com/Z3/fZQc

; Coding a partial order precedes relation with UF
(declare-sort A)
(declare-fun pre (A A) Bool)
; non reflexive
(assert (forall ((x A)) (not (pre x x))))
; transitive
(assert (forall ((x A) (y A) (z A))
          (=> (and (pre x y) (pre y z)) 
              (pre x z)))) 
; anti symetric
(assert (forall ((x A) (y A))
          (=> (pre x y)  
              (not (pre y x)))))
; an UNSAT example
(declare-const a0 A)
(declare-const a1 A)
(declare-const a2 A)
(assert (pre a0 a1))
(assert (pre a1 a2))
(assert (pre a2 a0))
(check-sat)

这正好表达了我想要的，但这也引入了一个带有量词的新逻辑。

另一种选择是将我的元素放入一个具体的域中，例如 Real 或 Int ： https://rise4fun.com/Z3/U0Hp

; Coding a partial order precedes relation with Real
; an UNSAT example
(declare-const a0 Real)
(declare-const a1 Real)
(declare-const a2 Real)
(assert (< a0 a1))
(assert (< a1 a2))
(assert (< a2 a0))
(check-sat)

代码更简单并且不使用量词，但它迫使（也许？）求解器过度思考，因为 Real 比第一个版本中的抽象域 A 具有更多的属性。

那么通常应该首选哪种编码来编码偏序？是否有我应该考虑的其他参数，或者我可以配置的策略来帮助解决此类问题？

Answer 1

尽可能避免使用量词。 SMT 求解器不适合它们，尤其是在理论组合方面。如果你能坚持 Int 或 Real，那就太好了。如果你可以使用位向量，那就更好了，因为即使存在非线性函数，逻辑也将保持可判定性。

如果您的模型确实需要量词，我认为 SMT 求解器根本不是一个很好的匹配项。在那种情况下，看看像 Isabelle、Coq、HOL 等半自动化系统

Answer 2

您也可以试试内置的特殊关系功能。至少他们改进了实例化的二次开销偏序公理。内置的偏序关系是自反的，所以如果你想要一个反身版本然后定义一个排除的宏自反情况。 (_ partial-order 0) 是一种关系，它接受两个相同类型的参数和 returns 一个布尔值。 (_ partial-order 1) 将是不同的关系，因此您可以使用参数索引不同的偏序。

(declare-sort A)
(define-fun pre ((x A) (y A)) Bool (and (not (= x y)) ((_ partial-order 0) x y)))
; an UNSAT example
(declare-const a0 A)
(declare-const a1 A)
(declare-const a2 A)
(assert (pre a0 a1))
(assert (pre a1 a2))
(assert (pre a2 a0))
(check-sat)

哪种编码更适合使用 Z3 来求解偏序理论？

Which encodings are preferable to use Z3 to solve a partial order theory?

z3

smt

partial-ordering