是否可以在 z3 中定义一个具有全量化断言的函数（使用 SMT-LIB2 接口）？

Question

我的目标是定义一个函数，它接受一个输入整数序列并输出一个相同长度但仅包含第一个元素的整数序列input 序列的。例如（在伪代码中）：

f([7,5,6]) = [7,7,7]

为此，我在 z3 中声明了一个函数：

(declare-fun f ((Seq Int)) (Seq Int))

并尝试使用断言强制执行预期的行为：

(assert 
    (forall ((arr (Seq Int)))
        (and
            (=
                (seq.len arr)
                (seq.len (f arr))
            )
            (forall ((i Int))
                (implies
                    (and
                        (>= i 0)
                        (< i (seq.len arr))
                    )
                    (=
                        (seq.at arr 0)
                        (seq.at (f arr) i)
                    )
                )
            )
        )
    ))

问题是程序没有终止，我怀疑这是由 all-quantifier 引起的。为了测试我的条件是否正确，我声明了两个常量并看到对于 concrete 值，条件是正确的：

(define-const first (Seq Int)
    (seq.++ (seq.unit 1) (seq.unit 2))
)
(declare-const second (Seq Int))
(assert 
    (and
        (=
            (seq.len first)
            (seq.len second)
        )
        (forall ((i Int))
            (implies
                (and
                    (>= i 0)
                    (< i (seq.len first))
                )
                (=
                    (seq.at first 0)
                    (seq.at second i)
                )
            )
        )
    )
)
(check-sat)
(get-model)

我的问题： 如何将断言中的条件与 f 函数的预期行为相结合？该函数应该是总函数，这意味着它应该为所有可能的输入序列定义，但这让我认为在我的情况下绝对需要一个 all 量词。

Answer 1

使用这种递归推理 data-types/values 不适合 SMT 求解器。大多数问题都需要归纳，而 SMT 求解器不会开箱即用地进行归纳。

话虽如此，您可以使用新的 declare-fun-rec 结构编写您想要的代码：

(define-fun-rec copyHeadAux ((x (Seq Int)) (l (Seq Int))) (Seq Int)
   (ite (= 0 (seq.len l))
        (as seq.empty (Seq Int))
    (seq.++ x (copyHeadAux x (seq.extract l 1 (seq.len l))))))


(define-fun copyHead ((l (Seq Int))) (Seq Int)
   (ite (= 0 (seq.len l))
        (as seq.empty (Seq Int))
    (copyHeadAux (seq.at l 0) l)))

(define-fun test () (Seq Int) (seq.++ (seq.unit 7) (seq.unit 5) (seq.unit 6)))
(declare-const out (Seq Int))
(assert (= out (copyHead test)))
(check-sat)
(get-model)

当我运行这个时，我得到：

sat
(
  (define-fun out () (Seq Int)
    (seq.++ (seq.unit 7) (seq.unit 7) (seq.unit 7)))
  (define-fun test () (Seq Int)
    (seq.++ (seq.unit 7) (seq.unit 5) (seq.unit 6)))
  (define-fun copyHead ((x!0 (Seq Int))) (Seq Int)
    (ite (= 0 (seq.len x!0))
         (as seq.empty (Seq Int))
         (copyHeadAux (seq.at x!0 0) x!0)))
)

这是您正在寻找的正确答案。但是除非您的约束只涉及“常量折叠”情况（即 copyHead 始终应用于常量已知值），否则您可能会得到 unknown 作为答案，或者让求解器进入无限电子匹配循环。

最好使用适当的定理证明器（Isabelle、HOL、Lean、ACL2 等）来推理这些递归定义。当然，随着时间的推移，SMT 求解器会变得更好，也许有一天他们能够开箱即用地处理更多这样的问题，但我不会屏住呼吸。

是否可以在 z3 中定义一个具有全量化断言的函数（使用 SMT-LIB2 接口）？

Is it possible to define a function with an all quantified assertion in z3 (with SMT-LIB2 interface)?

z3