我们可以在 Z3 中定义关系吗?

Can we define relations in Z3?

我是 z3 SMT 求解器的新手。我需要定义一个关系,而不是一个函数。我的意思是一个可以 return 多个值的函数。我查了教程,找不到任何东西。如果您能在这方面帮助我,我将不胜感激。

非常感谢。

使用支持 ArrayEx 理论的逻辑之一,它提供了 Array 排序和相关函数来操作数组。然后你可以让你的函数 return 数组值可以包含任意多个 Ints 或 Bools 或其他任何东西。

This SMT tutorial 是一个很好的资源,它将许多 SMT 细节收集到一个地方。

从某种意义上说,SMT"naturally"支持关系编程。您可以简单地分离参数的可能值,从而获得所需的结果。类似于:

(declare-fun foo ((Int)) Int)
(assert (or (= (foo 3) 4) (= (foo 3) 5)))
(check-sat)
(eval (foo 3))   ; might produce 4 of 5
(assert (distinct (foo 3) 4))
(check-sat)
(eval (foo 3))   ; will produce 5
(assert (distinct (foo 3) 5))
(check-sat)      ; will declare unsat 

你是说 foo 应用于 3 时,可以产生 45。然后你可以根据需要断言 "further" 事实来约束 space ;或者让它免费。您可以使用此技巧从本质上将 foo 建模为关系;使 SMT 求解器成为一种关系编程语言..

当然,您真正想要如何建模关系实际上取决于手头的问题。以上可能不是解决您问题的最佳选择。

我想下面的例子可能就是你要找的:

(define-fun sqrt ((a Int) (b Int)) Bool
    (= (* b b) a)
)
(declare-const a  Int)
(declare-const b1 Int)
(declare-const b2 Int)
(assert (sqrt a b1))
(assert (sqrt a b2))
(assert (not (= b1 b2)))
(check-sat)
(get-model)

当我调用 z3 时,我得到:

$ z3 -smt2 rel.smt
sat
(model 
  (define-fun b2 () Int
    2)
  (define-fun a () Int
    4)
  (define-fun b1 () Int
    (- 2))
)

sqrt 关系只是一组有序对:{(a,b) | a == b*b}(4,2)(4,-2) 都属于这个关系。在 SMT 措辞中, 这意味着 sqrt(4,2)sqrt(4,-2) 都是 true。这对应 您问题的措辞 4 可以有多个值。 不幸的是,其他答案,例如使用 foo 的答案并没有真正处理关系 ,而是要求求解器 在两个函数 之间进行选择。