使用数据类型和 forall 在 SMT-LIB 中对小型编程语言进行建模和分析

Question

我正在尝试在 SMT-LIB 2 中为一种小型编程语言建模。我的意图是表达一些程序分析问题并用 Z3 解决它们。不过，我认为我误解了 forall 声明。这是我的代码片段。

; barriers.smt2

(declare-datatype Barrier ((barrier (proc Int) (rank Int) (group Int) (complete-time Int))))

; barriers in the same group complete at the same time
(assert
  (forall ((b1 Barrier) (b2 Barrier))
          (=> (= (group b1) (group b2))
              (= (complete-time b1) (complete-time b2)))))
(check-sat)

当我运行 z3 -smt2 barriers.smt2 我得到 unsat 作为结果。我认为我的分析问题的一个实例将是一系列 forall 断言，如上文和一系列带有描述输入程序的断言的 const 声明。

(declare-const b00 Barrier)
(assert (= (proc b00) 0))
(assert (= (rank b00) 0))
...

但显然我错误地使用了 forall 表达式，因为我希望 z3 确定该断言有一个令人满意的模型。我错过了什么？

Answer 1

对于它的价值，我能够通过使用排序和未解释的函数而不是数据类型来向前推进。

(declare-sort Barrier 0)
(declare-fun proc (Barrier) Int)
(declare-fun rank (Barrier) Int)
(declare-fun group (Barrier) Int)
(declare-fun complete-time (Barrier) Int)

然后 forall 断言成立。我仍然希望解释为什么此更改会有所不同。

Answer 2

当你像这样声明一个 datatype 时：

(declare-datatype Barrier 
      ((barrier (proc Int) 
                (rank Int) 
                (group Int) 
                (complete-time Int))))

您正在生成一个 "freely" 生成的宇宙。这只是一个花哨的词，表示笛卡尔积 Int x Int x Int x Int.

中每个可能的元素都有一个 Barrier 的值

稍后，当你说：

(assert
  (forall ((b1 Barrier) (b2 Barrier))
          (=> (= (group b1) (group b2))
              (= (complete-time b1) (complete-time b2)))))

您正在对 b1 和 b2 的所有可能值进行断言，并且您是说如果组相同，则完成时间必须相同。但请记住，数据类型是自由生成的，因此 z3 告诉您 unsat，这意味着您的断言显然违反了从该笛卡尔积中获取 b1 和 b2 的正确值，其中有很多违反此断言的居民对。

当然，你想说的是："I just want you to pay attention to those elements that satisfy this property. I don't care about the others." 但这不是你说的。为此，只需将您的断言转换为一个函数：

(define-fun groupCompletesTogether ((b1 Barrier) (b2 Barrier)) Bool
   (=> (= (group b1) (group b2))
       (= (complete-time b1) (complete-time b2))))

然后，将其用作您的含义的假设。这是一个愚蠢的例子：

(declare-const b00 Barrier)
(declare-const b01 Barrier)

(assert (=> (groupCompletesTogether b00 b01)
            (> (rank b00) (rank b01))))
(check-sat)
(get-model)

这会打印：

sat
(model
  (define-fun b01 () Barrier
    (barrier 3 0 2437 1797))
  (define-fun b00 () Barrier
    (barrier 2 1 1236 1796))
)

这不是一个特别有趣的模型，但它仍然是正确的。我希望这能解释问题并让您走上正确的建模之路。您也可以将该谓词与其他事实结合使用，我怀疑在 sat 场景中，这正是您想要的。所以，你可以说：

(assert (distinct b00 b01))
(assert (and (= (group b00) (group b01))
             (groupCompletesTogether b00 b01)
             (> (rank b00) (rank b01))))

你会得到以下模型：

sat
(model
  (define-fun b01 () Barrier
    (barrier 3 2436 0 1236))
  (define-fun b00 () Barrier
    (barrier 2 2437 0 1236))
)

现在越来越有趣了！

一般来说，虽然 SMTLib 确实支持量词，但您应该尽量远离它们，因为它会使逻辑变得半可判定。通常，您只想像为未解释的常量那样编写量化公理。（也就是说，引入一个新的 function/constant，让它不加解释，但要断言它应该满足的普遍量化公理。）这可以让你建模一堆有趣的函数，尽管量词可以让求解器响应 unknown，因此最好避免使用它们。

[旁注：根据经验，当您在自由生成的数据类型（如 Barrier）上编写量化公理时，它要么是平凡的，要么永远不会满足，因为宇宙确实会包含可以以这种方式构建的所有内容。把它想象成 Haskell/ML 等中的数据类型；它只不过是所有可能值的容器。]

使用数据类型和 forall 在 SMT-LIB 中对小型编程语言进行建模和分析

Modeling a small programming language and analysis in SMT-LIB using datatypes and forall

smt

z3