使用 SBV 和 Haskell 证明的符号理论

Question

我在 Haskell 中使用 SBV（带有 Z3 后端）来创建一些理论证明。我想检查所有 x 和 y 是否具有给定的约束（如 x + y = y + x，其中 + 是 "plus operator"，而不是加法）其他一些术语是否有效.我想定义关于 + 表达式的公理（如结合律、恒等式等），然后检查进一步的等式，比如检查 a + (b + c) == (a + c) + b 是否有效，形式 a、b和 c.

我试图用类似的东西来完成它：

main = do
    let x = forall "x"
    let y = forall "y"
    out <- prove $ (x .== x)
    print "end"

但似乎我们不能对符号值使用 .== 运算符。这是缺少的功能还是错误的用法？我们可以使用 SBV 以某种方式做到这一点吗？

Answer 1

您对 API 的使用不太正确。证明数学等式的最简单方法是使用简单函数。例如，无界整数的结合律可以这样表示：

prove $ \x y z -> x + (y + z) .== (x + y) + (z :: SInteger)

如果您需要一个更具编程性的界面（有时您会需要），那么您可以使用 Symbolic monad，因此：

plusAssoc = prove $ do x <- sInteger "x"
                       y <- sInteger "y"
                       z <- sInteger "z"
                       return $ x + (y + z) .== (x + y) + z

我建议浏览黑客网站中提供的许多示例以熟悉 API：https://hackage.haskell.org/package/sbv

Answer 2

通过使用未解释的排序和函数，这种推理确实是可能的。但是请注意，对此类结构进行推理通常需要量化公理，而 SMT 求解器通常不太擅长使用量词进行推理。

话虽如此，这就是我使用 SBV 的方法。

首先，一些用于获取未解释类型的样板代码T:

{-# LANGUAGE DeriveDataTypeable #-}

import Data.Generics
import Data.SBV

-- Uninterpreted type T
data T = TBase () deriving (Eq, Ord, Data, Typeable, Read, Show)
instance SymWord T
instance HasKind T
type ST = SBV T

完成此操作后，您将可以访问未解释的类型 T 及其对应的符号类型 ST。让我们再次声明 plus 和 zero，只是具有正确类型的未解释常量：

-- Uninterpreted addition
plus :: ST -> ST -> ST
plus = uninterpret "plus"

-- Uninterpreted zero
zero :: ST
zero = uninterpret "zero"

到目前为止，我们只告诉 SBV 存在一个类型 T、一个函数 plus 和一个常量 zero；明确地未被解释。也就是说，SMT 求解器除了它们具有给定类型这一事实外不做任何假设。

我们先尝试证明 0+x = x:

bad = prove $ \x -> zero `plus` x .== x

如果您尝试此操作，您将收到以下响应：

*Main> bad
Falsifiable. Counter-example:
  s0 = T!val!0 :: T

SMT 求解器告诉您的是属性不成立，这是一个不成立的值。值 T!val!0 是 Z3 特定响应；其他求解器可以 return 其他东西。它本质上是 T 类型居民的内部标识符；除此之外，我们对此一无所知。这当然不是很有用，因为你真的不知道它与 plus 和 zero 有什么关联，但这是可以预料的。

为了证明属性，让我们再告诉 SMT 求解器两件事。首先，plus 是可交换的。其次，右侧添加的 zero 没有任何作用。这些是通过 addAxiom 调用完成的。不幸的是，您必须使用 SMTLib 语法编写公理，因为 SBV（至少目前）不支持使用 Haskell 编写的公理。另请注意，我们在这里切换到使用 Symbolic monad：

good = prove $ do
         addAxiom "plus-zero-axioms"
                  [ "(assert (forall ((x T) (y T)) (= (plus x y) (plus y x))))"
                  , "(assert (forall ((x T)) (= (plus x zero) x)))"
                  ]
         x <- free "x"
         return $ zero `plus` x .== x

注意我们如何告诉求解器 x+y = y+x 和 x+0 = x，并要求它证明 0+x = x。以这种方式编写公理看起来非常难看，因为您必须使用 SMTLib 语法，但这就是当前的情况。现在我们有：

*Main> good
Q.E.D.

量化公理和 uninterpreted-types/functions 不是通过 SBV 界面使用的最简单的东西，但您可以通过这种方式获得一些好处。如果您在公理中大量使用量词，求解器就不太可能回答您的问题；并且可能会回应 unknown。这完全取决于您使用的求解器，以及要证明的属性的难易程度。

使用 SBV 和 Haskell 证明的符号理论

Symbolic theory proving using SBV and Haskell

haskell

z3

sbv