量化列表长度限制导致不满意

Question

在下面的示例中，我试图对所有可能列表的长度设置限制以量化的方式。这将导致“不满意”的结果，我确信这是正确的。

有人可以详细说明为什么这是不能满足的吗？如果有办法绕过这个限制而不对特定的 variable/constant 施加长度限制？

我发现 this 有趣的话题，但我的问题在那里没有得到真正的回答。此外，答案是旧的，参考 SMT-LIB 2.0 版（和一个未量化的版本）。也许Z3现在有能力以我不知道的方式做到这一点。

(set-logic ALL)
(set-option :produce-unsat-cores true)

(declare-datatypes ((List 1)) ((par (T) ((cons (head T) (tail (List T))) (nil)))))

(define-sort IntList() (List Int))

(define-fun-rec IntList.length((l IntList)) Int
    (ite
        (= l (as nil IntList))
        0
        (+ (IntList.length (tail l)) 1)
    )
)

(assert (! (forall ((this IntList)) (<= 2 (IntList.length this))) :named a10))

(check-sat)
(get-unsat-core)

我在 2021 年 1 月 12 日使用 Z3 master 的提交 8abb644378ebaf1a9699e1b2fdd32075bcfcea4e，Win10 上的 64 位。

Answer 1

这个断言：

(assert (! (forall ((this IntList)) (<= 2 (IntList.length this))) :named a10))

无法满足。正如您无疑注意到的那样， 而不是 意味着您希望 z3 仅考虑长度至少为 2 的 int 列表。它只是说可以根据您给出的定义生成的所有列表的大小至少为 2。这只是一个错误的陈述。这就是为什么这个脚本是 unsat.

简而言之，SMT 中的数据类型是“自由生成的”。有关其含义的详细说明，请参阅。如果你想对所有至少为 2 的列表建模，那么你必须修改你的数据类型以确保它确保，即，而不是 nil 情况，你的基本情况将在至少有两个元素可以完成列表。这是确保求解器仅考虑大小 >= 2 的列表的唯一方法。

明确地说，您的愿望是“我试图以量化的方式对所有可能列表的长度设置限制。”如果您坚持使用示例中定义的列表，则不能用量化公理表示。（即，使用简单的 cons 和 nil。）如果这是你想要的，你将不得不说类似（伪代码）：

(assert (forall ((x IntList)) (=> (>= (length-of x) 2) 
                              ... condition you want to prove ...)))

也就是说，你必须写一个蕴涵，并在你拥有的列表至少长度为 2 的假设下证明你想要的东西。当然，这很快就会变得非常复杂，而且 SMT 求解器通常不会做不好量化，所以要注意复杂性。

一般来说，关于递归数据类型的推理不是 SMT 求解器的强项。递归函数定义工具相对较新，对它们的支持很少，而且经常出现错误。任何使用递归数据类型的证明尝试都必须对任何有趣的属性使用归纳法，而 SMT 求解器不会开箱即用地进行归纳法。您可能最好尝试实际的定理证明器，例如 Isabelle、ACL2、Lean、HOL 等

量化列表长度限制导致不满意

Quantified list length limitation leads to unsat

z3

smt