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

Copyright (c) Levent Erkok BSD3 erkokl@gmail.com experimental None Haskell2010

Documentation.SBV.Examples.Uninterpreted.Deduce

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

# 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
 Source # Instance details Methods(==) :: B -> B -> Bool #(/=) :: B -> B -> Bool # Source # Instance details Methodsgfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> B -> c B #gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c B #toConstr :: B -> Constr #dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c B) #dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c B) #gmapT :: (forall b. Data b => b -> b) -> B -> B #gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> B -> r #gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> B -> r #gmapQ :: (forall d. Data d => d -> u) -> B -> [u] #gmapQi :: Int -> (forall d. Data d => d -> u) -> B -> u #gmapM :: Monad m => (forall d. Data d => d -> m d) -> B -> m B #gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> B -> m B #gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> B -> m B # Source # Instance details Methodscompare :: B -> B -> Ordering #(<) :: B -> B -> Bool #(<=) :: B -> B -> Bool #(>) :: B -> B -> Bool #(>=) :: B -> B -> Bool #max :: B -> B -> B #min :: B -> B -> B # Source # Instance details MethodsreadList :: ReadS [B] # Source # Instance details MethodsshowsPrec :: Int -> B -> ShowS #show :: B -> String #showList :: [B] -> ShowS # Source # Instance details Methods Source # Instance details MethodsmkSymVal :: MonadSymbolic m => Maybe Quantifier -> Maybe String -> m (SBV B) Source #fromCV :: CV -> B Source #isConcretely :: SBV B -> (B -> Bool) -> Bool Source #forall :: MonadSymbolic m => String -> m (SBV B) Source #forall_ :: MonadSymbolic m => m (SBV B) Source #mkForallVars :: MonadSymbolic m => Int -> m [SBV B] Source #exists :: MonadSymbolic m => String -> m (SBV B) Source #exists_ :: MonadSymbolic m => m (SBV B) Source #mkExistVars :: MonadSymbolic m => Int -> m [SBV B] Source #free :: MonadSymbolic m => String -> m (SBV B) Source #free_ :: MonadSymbolic m => m (SBV B) Source #mkFreeVars :: MonadSymbolic m => Int -> m [SBV B] Source #symbolic :: MonadSymbolic m => String -> m (SBV B) Source #symbolics :: MonadSymbolic m => [String] -> m [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

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.