sbv-5.9: SMT Based Verification: Symbolic Haskell theorem prover using SMT solving.

Copyright | (c) Levent Erkok
License | BSD3
Maintainer | erkokl@gmail.com
Stability | experimental
Safe Haskell | None
Language | Haskell2010

Data.SBV.Examples.Uninterpreted.Deduce

Contents

- Representing uninterpreted booleans
- Uninterpreted connectives over `B`
- Axioms of the logical system
- Demonstrated deduction

Description

Demonstrates uninterpreted sorts and how they can be used for deduction. This example is inspired by the discussion at http://stackoverflow.com/questions/10635783/using-axioms-for-deductions-in-z3, essentially showing how to show the required deduction using SBV.

Synopsis

- data B = B ()
- type SB = SBV B
- and :: SB -> SB -> SB
- or :: SB -> SB -> SB
- not :: SB -> SB
- ax1 :: [String]
- ax2 :: [String]
- ax3 :: [String]
- test :: IO ThmResult

# Representing uninterpreted booleans

data B Source

The uninterpreted sort `B`, corresponding to the carrier. To prevent SBV from translating it to an enumerated type, we simply attach an unused field

Constructors

B () |

Instances

Eq B Source |
Data B Source |
Ord B Source |
Read B Source |
Show B Source |
HasKind B Source |
SymWord B Source |

type SB = SBV B Source

Handy shortcut for the type of symbolic values over `B`

# Uninterpreted connectives over `B`

and :: SB -> SB -> SB Source

Uninterpreted logical connective `and`

or :: SB -> SB -> SB Source

Uninterpreted logical connective `or`

not :: SB -> SB Source

Uninterpreted logical connective `not`

# Axioms of the logical system

ax1 :: [String] Source

Distributivity of OR over AND, as an axiom in terms of the uninterpreted functions we have introduced. Note how variables range over the uninterpreted sort `B`.

ax2 :: [String] Source

One of De Morgan's laws, again as an axiom in terms of our uninterpeted logical connectives.

ax3 :: [String] Source

Double negation axiom, similar to the above.

# Demonstrated deduction

test :: IO ThmResult Source

Proves the equivalence `NOT (p OR (q AND r)) == (NOT p AND NOT q) OR (NOT p AND NOT r)`, following from the axioms we have specified above. We have:

    >>> test
    Q.E.D.