The superposition calculus is a
calculus
Calculus is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithmetic operations.
Originally called infinitesimal calculus or "the ...
for
reasoning
Reason is the capacity of consciously applying logic by drawing valid conclusions from new or existing information, with the aim of seeking the truth. It is associated with such characteristically human activities as philosophy, religion, scien ...
in
equational logic. It was developed in the early 1990s and combines concepts from
first-order resolution
In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation-complete theorem-proving technique for sentences in propositional logic and first-order logic. For propositional logic, systematically ...
with ordering-based equality handling as developed in the context of (unfailing)
Knuth–Bendix completion. It can be seen as a generalization of either resolution (to equational logic) or unfailing completion (to full
clausal logic). Like most
first-order calculi, superposition tries to show the ''unsatisfiability'' of a set of first-order
clauses
In language, a clause is a Constituent (linguistics), constituent or Phrase (grammar), phrase that comprises a semantic predicand (expressed or not) and a semantic Predicate (grammar), predicate. A typical clause consists of a subject (grammar), ...
, i.e. it performs proofs by
refutation. Superposition is
refutation complete—given unlimited resources and a ''fair'' derivation strategy, from any
unsatisfiable
In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...
clause set a contradiction will eventually be derived.
Many (state-of-the-art)
theorem provers for first-order logic are based on superposition (e.g. the
E equational theorem prover
E is a high-performance Automated theorem proving, theorem prover for full first-order logic with equality. It is based on the equational superposition calculus and uses a purely equational paradigm. It has been integrated into other theorem prover ...
), although only a few implement the pure calculus.
Implementations
*
E
*
SPASS
*
Vampire
A vampire is a mythical creature that subsists by feeding on the Vitalism, vital essence (generally in the form of blood) of the living. In European folklore, vampires are undead, undead humanoid creatures that often visited loved ones and c ...
*
Waldmeisterbr>
(official web page)
References
*
Rewrite-Based Equational Theorem Proving with Selection and Simplification', Leo Bachmair and
Harald Ganzinger,
Journal of Logic and Computation
A journal, from the Old French ''journal'' (meaning "daily"), may refer to:
*Bullet journal, a method of personal organization
*Diary, a record of personal secretive thoughts and as open book to personal therapy or used to feel connected to onesel ...
3(4), 1994.
* ''Paramodulation-Based Theorem Proving'', Robert Nieuwenhuis and Alberto Rubio,
Handbook of Automated Reasoning
The ''Handbook of Automated Reasoning'' (, 2128 pages) is a collection of survey articles on the field of automated reasoning. Published in June 2001 by MIT Press, it is edited by John Alan Robinson and Andrei Voronkov. Volume 1 describes methods ...
I(7),
Elsevier
Elsevier ( ) is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its products include journals such as ''The Lancet'', ''Cell (journal), Cell'', the ScienceDirect collection of electronic journals, ...
Science and
MIT Press
The MIT Press is the university press of the Massachusetts Institute of Technology (MIT), a private research university in Cambridge, Massachusetts. The MIT Press publishes a number of academic journals and has been a pioneer in the Open Ac ...
, 2001.
Mathematical logic
Logical calculi
{{mathlogic-stub