Z3 检查数组中的所有值是否唯一

Question

因此我尝试使用以下 Z3 代码检查数组中的所有值是否唯一。

(declare-const A (Array Int Int))
(declare-const n Int)
(assert (forall ((i Int) (j Int)) (and (and (and (>= i 0) (< i n)) (and (>= j 0) (< j n)))
                                       (implies (= (select A i) (select A j)) (= i j)))))
(check-sat)

我对 Z3 很陌生，所以我不太了解语法和其他东西，但是谁能告诉我这段代码是否正确，如果不正确，问题出在哪里？

Answer 1

你写的问题是unsat，因为它说只要0 <= i < n和0 <= j < n，如果A[i] = A[j]，那么i = j。没有数组，您可以选择一个特定的 n 来满足此约束。

您真正想写的是以下内容：

(declare-const A (Array Int Int))
(declare-const n Int)
(assert (forall ((i Int) (j Int)) (implies (and (>= i 0) (< i n)
                                                (>= j 0) (< j n)
                                                (= (select A i) (select A j)))
                                           (= i j))))
(check-sat)
(get-model)

上面说的If是这样的，i和j在范围内，数组元素相同，那么i一定等于j.并且这个变体对于任何 n 都是可满足的；事实上，这就是 z3 报告的内容：

sat
(
  (define-fun n () Int
    0)
  (define-fun A () (Array Int Int)
    ((as const (Array Int Int)) 0))
)

但请注意，z3 只是选择了 n = 0，这很容易满足公式。让我们确保我们得到一个更有趣的模型，通过添加：

(assert (> n 2))

现在我们得到：

sat
(
  (define-fun n () Int
    3)
  (define-fun A () (Array Int Int)
    (lambda ((x!1 Int))
  (let ((a!1 (ite (and (<= 1 x!1) (not (<= 2 x!1))) 7 8)))
    (ite (<= 1 x!1) (ite (and (<= 1 x!1) (<= 2 x!1)) 6 a!1) 5))))
)

并且我们看到 z3 选择的数组在我们关心的位置有 3 个具有不同值的元素。

请注意，这种带有量词的推理是 SMT 求解器的 soft-spot；虽然 z3 能够为这些情况找到模型，但如果您继续添加量化公理，您可能会得到 unknown 作为答案，或者 z3（或与此相关的任何其他 SMT 求解器）将花费越来越长的时间来回应。

Z3 检查数组中的所有值是否唯一

Z3 Checking whether all values in array are unique

smt

z3