Z3 找到有效排列

Question

我试图让 Z3 找到满足某些约束的固定大小序列的所有可能排列。但是，到目前为止我开发的代码运行出现超时错误：

(set-option :produce-unsat-cores true)
(set-option :produce-models true)

; --------------- Basic Definitions -------------------
(declare-datatypes () ((Obj A B C)))

; --------------- Predicates -------------------------------

(define-sort MyList () (Seq Obj))

(define-fun in_list ((o Obj) (l MyList)) Bool (seq.contains l (seq.unit o)))

(define-fun permutation ((l1 MyList) (l2 MyList)) Bool
                    (forall ((o Obj)) (= (in_list o l1) (in_list o l2))))


; Two difference permutations of the same list
(declare-const l0 MyList)
(declare-const l1 MyList)

(assert (= 2 (seq.len l0)))
(assert (= 2 (seq.len l1)))
(assert (not (= l1 l0)))
(assert (permutation l0 l1))

; --------------- Verify -------------------
(check-sat)
(get-model)

看起来这应该是一个非常简单的解决方案（即使是蛮力也需要几毫秒），所以我很困惑是什么导致了超时。有帮助吗？

Answer 1

您运行限制了存在量词时 Z3 的功能。

你可能想看看这个问题：Defining a Theory of Sets with Z3/SMT-LIB2

在这种情况下，问题是关于一般集合操作的，但我认为您也会找到适用于您的情况的答案。（简而言之，禁用 MBQI，看看是否可以使用函数而不是序列。）

Z3 找到有效排列

Z3 Find Valid Permutation

z3