阵列上的 Z3 ForAll
Z3 ForAll on Arrays
我已经成功地使用 Z3 创建了一个记录数组,但现在我很难看到我需要在数组上执行 $\forall$ 操作的语法...这是 SMT-LIB2 的片段示例我到目前为止的代码。
(declare-datatypes () ((rec (mk-R5 (age Int) (area Int) (married Bool)))))
(declare-const recs (Array Int rec))
(declare-const r1 rec)
(assert(= (age r1) 15))
(assert(= (area r1) 10001))
(assert(= (married r1) true))
(declare-const r2 rec)
(assert(= (age r2) 35))
(assert(= (area r2) 2845))
(assert(= (married r2) true))
(declare-const x Int)
(declare-const y Int)
(assert (= recs (store recs x r1)))
(assert (= recs (store recs y r2)))
(assert(forall ((i rec)) (= (married i) true)))
(check-sat)
(get-model)
我想倒数第三行应该对数组有一些参考,但我已经尝试了所有方法,教程没有帮助我解决这个问题。
如何对此处的数组执行 $\forall$ 操作?
您似乎正试图将两条记录放入一个数组中,然后对这些元素进行说明。不幸的是,您的编码并不完全意味着那个。
首先要注意的是下面这行的意思:
(declare-const recs (Array Int rec))
这表示 recs
是一个由 所有 整数索引的数组。也就是说,域是所有 Int 值的集合。这可能不是你的意思。
此外,行:
(assert (= recs (store recs x r1)))
(assert (= recs (store recs y r2)))
这样写比较好:
(assert (= (select recs x) r1))
(assert (= (select recs y) r2))
把它想象成你对索引 x
和 y
的了解;与您尝试编写的 "modify" recs
的一些命令式赋值语句相反。没有修改 smt-lib 中任何值的概念;你只需陈述你所知道的关于你正在构建的模型的真实情况。
修复 forall-assertion 的一种方法是这样写:
(assert (forall ((i Int))
(implies (or (= i x) (= i y))
(= (married (select recs i)) true))))
我们对索引进行量化,如果索引是 i
或 y
,那么这些记录有 married
人。通过这些修改,Z3 响应:
sat
(model
(define-fun r2 () rec
(mk-R5 35 2845 true))
(define-fun recs () (Array Int rec)
(_ as-array k!0))
(define-fun y () Int
1)
(define-fun x () Int
0)
(define-fun r1 () rec
(mk-R5 15 10001 true))
(define-fun k!0!2 ((x!0 Int)) rec
(ite (= x!0 1) (mk-R5 35 2845 true)
(mk-R5 15 10001 true)))
(define-fun k!1 ((x!0 Int)) Int
(ite (= x!0 0) 0
1))
(define-fun k!0 ((x!0 Int)) rec
(k!0!2 (k!1 x!0)))
)
这有点难读,但它确实为您提供了指定的模型。
然而,在我看来,这并不是您真正想要建模的;但很难从你的问题中分辨出来。如果您描述了您试图解决的实际问题,答案可能会更有帮助。
我已经成功地使用 Z3 创建了一个记录数组,但现在我很难看到我需要在数组上执行 $\forall$ 操作的语法...这是 SMT-LIB2 的片段示例我到目前为止的代码。
(declare-datatypes () ((rec (mk-R5 (age Int) (area Int) (married Bool)))))
(declare-const recs (Array Int rec))
(declare-const r1 rec)
(assert(= (age r1) 15))
(assert(= (area r1) 10001))
(assert(= (married r1) true))
(declare-const r2 rec)
(assert(= (age r2) 35))
(assert(= (area r2) 2845))
(assert(= (married r2) true))
(declare-const x Int)
(declare-const y Int)
(assert (= recs (store recs x r1)))
(assert (= recs (store recs y r2)))
(assert(forall ((i rec)) (= (married i) true)))
(check-sat)
(get-model)
我想倒数第三行应该对数组有一些参考,但我已经尝试了所有方法,教程没有帮助我解决这个问题。
如何对此处的数组执行 $\forall$ 操作?
您似乎正试图将两条记录放入一个数组中,然后对这些元素进行说明。不幸的是,您的编码并不完全意味着那个。
首先要注意的是下面这行的意思:
(declare-const recs (Array Int rec))
这表示 recs
是一个由 所有 整数索引的数组。也就是说,域是所有 Int 值的集合。这可能不是你的意思。
此外,行:
(assert (= recs (store recs x r1)))
(assert (= recs (store recs y r2)))
这样写比较好:
(assert (= (select recs x) r1))
(assert (= (select recs y) r2))
把它想象成你对索引 x
和 y
的了解;与您尝试编写的 "modify" recs
的一些命令式赋值语句相反。没有修改 smt-lib 中任何值的概念;你只需陈述你所知道的关于你正在构建的模型的真实情况。
修复 forall-assertion 的一种方法是这样写:
(assert (forall ((i Int))
(implies (or (= i x) (= i y))
(= (married (select recs i)) true))))
我们对索引进行量化,如果索引是 i
或 y
,那么这些记录有 married
人。通过这些修改,Z3 响应:
sat
(model
(define-fun r2 () rec
(mk-R5 35 2845 true))
(define-fun recs () (Array Int rec)
(_ as-array k!0))
(define-fun y () Int
1)
(define-fun x () Int
0)
(define-fun r1 () rec
(mk-R5 15 10001 true))
(define-fun k!0!2 ((x!0 Int)) rec
(ite (= x!0 1) (mk-R5 35 2845 true)
(mk-R5 15 10001 true)))
(define-fun k!1 ((x!0 Int)) Int
(ite (= x!0 0) 0
1))
(define-fun k!0 ((x!0 Int)) rec
(k!0!2 (k!1 x!0)))
)
这有点难读,但它确实为您提供了指定的模型。
然而,在我看来,这并不是您真正想要建模的;但很难从你的问题中分辨出来。如果您描述了您试图解决的实际问题,答案可能会更有帮助。