object FormulaTools extends Logging
Tactic tools for formula manipulation and extraction.
- Alphabetic
- By Inheritance
- FormulaTools
- Logging
- LazyLogging
- LoggerHolder
- AnyRef
- Any
- Hide All
- Show All
- Public
- All
Value Members
-
final
def
!=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
final
def
##(): Int
- Definition Classes
- AnyRef → Any
-
final
def
==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
def
argsOf(fn: Function, fml: Formula): Set[Term]
Returns a set of variables that are arguments to any application of function 'fn' in the formula
fml
. -
def
argumentList(term: Term): List[Term]
Convert nested pairs to a list of its deassociated non-pair arguments.
Convert nested pairs to a list of its deassociated non-pair arguments.
Pair->List[Term]
-
final
def
asInstanceOf[T0]: T0
- Definition Classes
- Any
-
def
atomicFormulas(formula: Formula): List[AtomicFormula]
Read off all atomic subformulas of
formula
.Read off all atomic subformulas of
formula
. Will not descend into programs to find even further atomic formulas since they are not directly subformulas.- See also
negationNormalForm()
-
def
clone(): AnyRef
- Attributes
- protected[java.lang]
- Definition Classes
- AnyRef
- Annotations
- @native() @throws( ... )
-
def
closure(fml: Formula): Formula
Returns the formula in negation normal form, weakened by replacing strict inequalities with inequalities.
-
def
combinations(l: List[List[Formula]]): List[List[Formula]]
The element-wise combinations in
l
, e.g., [ [a,b,c], [p,q] ] ==> [ [a,p], [a,q], [b,p], [b,q], [c,p], [c,q] ]. -
def
conjuncts(formulas: List[Formula]): List[Formula]
- See also
conjuncts(formula: Formula)
-
def
conjuncts(formula: Formula): List[Formula]
Split a formula into its conjuncts.
Split a formula into its conjuncts. Without performing clause form or CNF or DNF transformations.
conjuncts(p() & q() & (r() & (s() | t()&u()))) == List(p(), q(), r(), s()|t()&u())
Example: -
def
disjunctiveNormalForm(fml: Formula): Formula
Turns
fml
into disjunctive normal form. -
def
disjuncts(formulas: List[Formula]): List[Formula]
- See also
disjuncts(formula: Formula)
-
def
disjuncts(formula: Formula): List[Formula]
Split a formula into its disjuncts.
Split a formula into its disjuncts. Without performing clause form or CNF or DNF transformations.
disjuncts(p() | q() | (r() | (s() & (t()|u())))) == List(p(), q(), r(), s()&(t()|u()))
Example: -
def
distributeOrOverAnd(fml: Formula): Formula
Distributes disjunctions over conjunctions, e.g., a&(b|c) ==> a&b | a&c.
-
def
dualFree(sequent: Sequent): Boolean
Check whether
sequent
is dual-free. -
def
dualFree(fml: Formula): Boolean
Check whether
fml
is dual-free. -
def
dualFree(program: Program): Boolean
Check whether given program is dual-free, so a hybrid system and not a proper hybrid game.
Check whether given program is dual-free, so a hybrid system and not a proper hybrid game.
- See also
SubstitutionPair.dualFree
-
final
def
eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
def
equals(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
def
finalize(): Unit
- Attributes
- protected[java.lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( classOf[java.lang.Throwable] )
-
final
def
getClass(): Class[_]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
def
hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
def
interior(fml: Formula): Formula
Returns the formula in negation normal form, strengthened by replacing inequalities with strict inequalities.
-
final
def
isInstanceOf[T0]: Boolean
- Definition Classes
- Any
-
def
kernel(formula: Formula): Formula
Gets the (unquantified) kernel part of a quantified formula by peeling off quantifiers.
Gets the (unquantified) kernel part of a quantified formula by peeling off quantifiers.
- Annotations
- @tailrec()
-
def
leftConjuncts(formula: Formula, length: Int = -1): List[Formula]
Split a formula into
length
left-hand side conjuncts (-1 for exhaustive splitting), keep right-hand side conjunctions (inverse reduce). -
def
literalDualFree(sequent: Sequent): Boolean
Check whether
sequent
contains literal Dual. -
def
literalDualFree(fml: Formula): Boolean
Check whether
fml
contains literal Dual. -
def
literalDualFree(program: Program): Boolean
Check whether given
program
contains literal Dual. -
lazy val
logger: Logger
- Attributes
- protected
- Definition Classes
- LazyLogging → LoggerHolder
-
final
val
loggerName: String
- Attributes
- protected
- Definition Classes
- LoggerHolder
-
def
makePolarityAt(formula: Formula, pos: PosInExpr, polarity: Int): Formula
Returns a formula with equivalences turned into implications such that the polarity of the subformula at position pos has the specified polarity.
Returns a formula with equivalences turned into implications such that the polarity of the subformula at position pos has the specified polarity. Creates a variation of this formula which has equivalences reoriented such that the polarity of the subformula at position pos in the resulting formula will be the desired polarity.
- formula
The formula.
- pos
The position within formula for which the polarity is supposed to be changed to the desired polarity.
- polarity
The desired polarity, must be either 1 (positive polarity) or -1 (negative polarity).
- returns
The formula with equivalences turned into implications.
-
final
def
ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
def
negationNormalForm(formula: Formula): Formula
Negation-normal form transforms such that there are no nested negations and that negated atomic comparisons.
Negation-normal form transforms such that there are no nested negations and that negated atomic comparisons. Also removes implications/equivalences.
-
final
def
notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
def
parentFormulaPos(pos: PosInExpr, fml: Formula): PosInExpr
Finds the closest parent to
pos
informula
that is a formula. -
def
polarityAt(formula: Formula, pos: PosInExpr): Int
Returns the polarity of the subformula at position pos in formula.
Returns the polarity of the subformula at position pos in formula.
- formula
The formula.
- pos
The position within formula for which the polarity is searched.
- returns
-1 for negative polarity, 1 for positive polarity, 0 for unknown polarity.
-
def
posOf(formula: Formula, cond: (Expression) ⇒ Boolean): List[PosInExpr]
Collects the subpositions of formula that satisfy condition cond.
Collects the subpositions of formula that satisfy condition cond. Ordered: reverse depth (deepest first).
-
def
posOf(expr: Expression, sub: Expression): Option[PosInExpr]
Returns the first (i.e., left-most) position of
sub
withinexpr
, if any.Returns the first (i.e., left-most) position of
sub
withinexpr
, if any.- expr
The expression to search for containment of
sub
.- sub
The sub-expression.
- returns
The first position, or None if
sub
is not contained inexpr
.
- def posOfTerm(term: Term, cond: (Term) ⇒ Boolean): List[PosInExpr]
-
def
quantifyExists(xs: List[Variable], fml: Formula): Formula
prepends all-quantifiers over given variables to a formula
-
def
quantifyForall(xs: List[Variable], fml: Formula): Formula
prepends all-quantifiers over given variables to a formula
-
def
reassociate(fml: Formula): Formula
Reassociates conjunctions and disjunctions into their default right-associative case.
- def singularities(program: Program): Set[Term]
- def singularities(formula: Formula): Set[Term]
- def singularities(term: Term): Set[Term]
-
def
singularities(e: Expression): Set[Term]
Read off the set of all possible singularities coming from divisors or negative powers.
Read off the set of all possible singularities coming from divisors or negative powers.
singularities("x>5/b+2".asFormula)==Set(b) singularities("x/y>z/2+8/(a+b) & [x:=a/c;]x+1/(3*d)>5/3".asFormula)==Set(y,a+b,c,3*d)
Example: -
def
sortsList(s: Sort): List[Sort]
Convert nested Tuple sorts to a list of its deassociated non-tuple arguments.
Convert nested Tuple sorts to a list of its deassociated non-tuple arguments.
Tuple->List[Sort]
-
def
symbolsDiff(fs: Seq[Formula], gs: Seq[Formula]): (Set[NamedSymbol], Set[NamedSymbol], Set[NamedSymbol])
Union of pairwise symbol difference in
fs
andgs
, returns a tuple of: symbols of fs not in gs, symbols of gs not in fs, their union -
def
symbolsDiff(f: Formula, g: Formula): (Set[NamedSymbol], Set[NamedSymbol], Set[NamedSymbol])
Difference between symbols in
f
andg
, returns a tuple of: symbols of f not in g, symbols of g not in f, their union -
final
def
synchronized[T0](arg0: ⇒ T0): T0
- Definition Classes
- AnyRef
-
def
toString(): String
- Definition Classes
- AnyRef → Any
-
def
unnaturalPowers(f: Formula): List[(Term, PosInExpr)]
Returns all terms
Returns all terms
b^e
such that e is not a natural number occurring in given formula . b^e }}}
- Note
This is soundness-critical.
-
final
def
wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @native() @throws( ... )
KeYmaera X: An aXiomatic Tactical Theorem Prover
KeYmaera X is a theorem prover for differential dynamic logic (dL), a logic for specifying and verifying properties of hybrid systems with mixed discrete and continuous dynamics. Reasoning about complicated hybrid systems requires support for sophisticated proof techniques, efficient computation, and a user interface that crystallizes salient properties of the system. KeYmaera X allows users to specify custom proof search techniques as tactics, execute tactics in parallel, and interface with partial proofs via an extensible user interface.
http://keymaeraX.org/
Concrete syntax for input language Differential Dynamic Logic
Package Structure
Main documentation entry points for KeYmaera X API:
edu.cmu.cs.ls.keymaerax.core
- KeYmaera X kernel, proof certificates, main data structuresExpression
- Differential dynamic logic expressions:Term
,Formula
,Program
Sequent
- Sequents of formulasProvable
- Proof certificates transformed by rules/axiomsRule
- Proof rules as well asUSubstOne
for (one-pass) uniform substitutions and renaming.StaticSemantics
- Static semantics with free and bound variable analysisKeYmaeraXParser
.edu.cmu.cs.ls.keymaerax.parser
- Parser and pretty printer with concrete syntax and notation for differential dynamic logic.KeYmaeraXPrettyPrinter
- Pretty printer producing concrete KeYmaera X syntaxKeYmaeraXParser
- Parser reading concrete KeYmaera X syntaxKeYmaeraXArchiveParser
- Parser reading KeYmaera X model and proof archive.kyx
filesDLParser
- Combinator parser reading concrete KeYmaera X syntaxDLArchiveParser
- Combinator parser reading KeYmaera X model and proof archive.kyx
filesedu.cmu.cs.ls.keymaerax.infrastruct
- Prover infrastructure outside the kernelUnificationMatch
- Unification algorithmRenUSubst
- Renaming Uniform Substitution quickly combining kernel's renaming and substitution.Context
- Representation for contexts of formulas in which they occur.Augmentors
- Augmenting formula and expression data structures with additional functionalityExpressionTraversal
- Generic traversal functionality for expressionsedu.cmu.cs.ls.keymaerax.bellerophon
- Bellerophon tactic language and tactic interpreterBelleExpr
- Tactic language expressionsSequentialInterpreter
- Sequential tactic interpreter for Bellerophon tacticsedu.cmu.cs.ls.keymaerax.btactics
- Bellerophon tactic library for conducting proofs.TactixLibrary
- Main KeYmaera X tactic library including many proof tactics.HilbertCalculus
- Hilbert Calculus for differential dynamic logicSequentCalculus
- Sequent Calculus for propositional and first-order logicHybridProgramCalculus
- Hybrid Program Calculus for differential dynamic logicDifferentialEquationCalculus
- Differential Equation Calculus for differential dynamic logicUnifyUSCalculus
- Unification-based uniform substitution calculus underlying the other calculi[edu.cmu.cs.ls.keymaerax.btactics.UnifyUSCalculus.ForwardTactic ForwardTactic]
- Forward tactic framework for conducting proofs from premises to conclusionsedu.cmu.cs.ls.keymaerax.lemma
- Lemma mechanismLemma
- Lemmas are Provables stored under a name, e.g., in files.LemmaDB
- Lemma database stored in files or database etc.edu.cmu.cs.ls.keymaerax.tools.qe
- Real arithmetic back-end solversMathematicaQETool
- Mathematica interface for real arithmetic.Z3QETool
- Z3 interface for real arithmetic.edu.cmu.cs.ls.keymaerax.tools.ext
- Extended back-ends for noncritical ODE solving, counterexamples, algebra, simplifiers, etc.Mathematica
- Mathematica interface for ODE solving, algebra, simplification, invariant generation, etc.Z3
- Z3 interface for real arithmetic including simplifiers.Entry Points
Additional entry points and usage points for KeYmaera X API:
edu.cmu.cs.ls.keymaerax.launcher.KeYmaeraX
- Command-line launcher for KeYmaera X supports command-line argument-help
to obtain usage informationedu.cmu.cs.ls.keymaerax.btactics.AxIndex
- Axiom indexing data structures with keys and recursors for canonical proof strategies.edu.cmu.cs.ls.keymaerax.btactics.DerivationInfo
- Meta-information on all derivation steps (axioms, derived axioms, proof rules, tactics) with user-interface info.edu.cmu.cs.ls.keymaerax.bellerophon.UIIndex
- Index determining which canonical reasoning steps to display on the KeYmaera X User Interface.edu.cmu.cs.ls.keymaerax.btactics.Ax
- Registry for derived axioms and axiomatic proof rules that are proved from the core.References
Full references on KeYmaera X are provided at http://keymaeraX.org/. The main references are the following:
1. André Platzer. A complete uniform substitution calculus for differential dynamic logic. Journal of Automated Reasoning, 59(2), pp. 219-265, 2017.
2. Nathan Fulton, Stefan Mitsch, Jan-David Quesel, Marcus Völp and André Platzer. KeYmaera X: An axiomatic tactical theorem prover for hybrid systems. In Amy P. Felty and Aart Middeldorp, editors, International Conference on Automated Deduction, CADE'15, Berlin, Germany, Proceedings, volume 9195 of LNCS, pp. 527-538. Springer, 2015.
3. André Platzer. Logical Foundations of Cyber-Physical Systems. Springer, 2018. Videos