列出 Z3 中的 "contains" 函数

Question

给定一个典型的列表数据类型：

(declare-datatypes (X)(
  (Lst
    (nil)
    (insert
      (head X)
      (tail Lst)))))

我正在尝试创建一个函数，该函数 returns 给定元素是否在给定列表中。看起来我必须使用一个未解释的函数。我尝试了不同的方法但没有成功。例如：

(declare-fun is-in-lst ((Int)(Lst Int)) Bool)

(assert (forall((elem Int)(lst (Lst Int)))
  (=
    (is-in-lst elem lst)
    (and
      (is-insert lst)
      (or
        (= elem (head lst))
        (is-in-lst elem (tail lst)))))))

(declare-const l1 (Lst Int))

(assert (is-in-lst 6 l1))
(assert (is-in-lst 5 l1))

这在 Z3 中可行吗？如果是这样，解决问题的最佳方法是什么？谢谢

Answer 1

最新的 SMTLib 标准允许递归定义。另外 List 在 Z3 中是预定义的，所以你不需要自己定义它。您可以将函数编码为：

(define-fun-rec elem ((e Int) (l (List Int))) Bool
   (ite (= l nil) false (or (= e (head l)) (elem e (tail l)))))

(declare-const l1 (List Int))
(assert (elem 6 l1))
(assert (elem 5 l1))

(check-sat)
(get-value (l1))

对此z3回应：

sat
((l1 (let ((a!1 (insert 6 (insert 4 (insert 7 (insert 5 nil))))))
  (insert 0 (insert 1 (insert 3 (insert 2 a!1)))))))

您可能需要从他们的夜间构建中获取 Z3 的最新版本，因为对递归函数的支持相当新，因此最新的官方版本 (4.6.0) 可能适用也可能不适用于此。（您可以从 https://github.com/Z3Prover/bin/tree/master/nightly 获得夜间构建。）

列出 Z3 中的 "contains" 函数

List "contains" function in Z3

smt

z3