sbv-7.13: 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

Documentation.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

- newtype 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

newtype 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 # |
Instance details Defined in Documentation.SBV.Examples.Uninterpreted.Deduce Methods (==) :: B -> B -> Bool Source # (/=) :: B -> B -> Bool Source #
Data B Source # |

Instance details

Defined in Documentation.SBV.Examples.Uninterpreted.Deduce

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> B -> c B Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c B Source #

toConstr :: B -> Constr Source #

dataTypeOf :: B -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c B) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c B) Source #

gmapT :: (forall b. Data b => b -> b) -> B -> B Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> B -> r Source #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> B -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> B -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> B -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> B -> m B Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> B -> m B Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> B -> m B Source #

Ord B Source # |
Instance details Defined in Documentation.SBV.Examples.Uninterpreted.Deduce Methods compare :: B -> B -> Ordering Source # (<) :: B -> B -> Bool Source # (<=) :: B -> B -> Bool Source # (>) :: B -> B -> Bool Source # (>=) :: B -> B -> Bool Source # max :: B -> B -> B Source # min :: B -> B -> B Source #
Read B Source # |
Instance details Defined in Documentation.SBV.Examples.Uninterpreted.Deduce Methods readsPrec :: Int -> ReadS B Source # readList :: ReadS [B] Source # readPrec :: ReadPrec B Source # readListPrec :: ReadPrec [B] Source #
Show B Source # |
Instance details Defined in Documentation.SBV.Examples.Uninterpreted.Deduce Methods showsPrec :: Int -> B -> ShowS Source # show :: B -> String Source # showList :: [B] -> ShowS Source #
HasKind B Source # |

Instance details

Defined in Documentation.SBV.Examples.Uninterpreted.Deduce

Methods

kindOf :: B -> Kind Source #

hasSign :: B -> Bool Source #

intSizeOf :: B -> Int Source #

isBoolean :: B -> Bool Source #

isBounded :: B -> Bool Source #

isReal :: B -> Bool Source #

isFloat :: B -> Bool Source #

isDouble :: B -> Bool Source #

isInteger :: B -> Bool Source #

isUninterpreted :: B -> Bool Source #

isChar :: B -> Bool Source #

isString :: B -> Bool Source #

isList :: B -> Bool Source #

showType :: B -> String Source #

SymWord B Source # |

Instance details

Defined in Documentation.SBV.Examples.Uninterpreted.Deduce

Methods

forall :: String -> Symbolic (SBV B) Source #

forall_ :: Symbolic (SBV B) Source #

mkForallVars :: Int -> Symbolic [SBV B] Source #

exists :: String -> Symbolic (SBV B) Source #

exists_ :: Symbolic (SBV B) Source #

mkExistVars :: Int -> Symbolic [SBV B] Source #

free :: String -> Symbolic (SBV B) Source #

free_ :: Symbolic (SBV B) Source #

mkFreeVars :: Int -> Symbolic [SBV B] Source #

symbolic :: String -> Symbolic (SBV B) Source #

symbolics :: [String] -> Symbolic [SBV B] Source #

literal :: B -> SBV B Source #

unliteral :: SBV B -> Maybe B Source #

fromCW :: CW -> B Source #

isConcrete :: SBV B -> Bool Source #

isSymbolic :: SBV B -> Bool Source #

isConcretely :: SBV B -> (B -> Bool) -> Bool Source #

mkSymWord :: Maybe Quantifier -> Maybe String -> Symbolic (SBV 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.