A Modular Formalization of Superposition

Martin Desharnais 📧 and Balazs Toth 📧

October 24, 2024

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

Superposition is an efficient proof calculus for reasoning about first-order logic with equality that is implemented in many automatic theorem provers. It works by saturating the given set of clauses and is refutationally complete, meaning that if the set is inconsistent, the saturation will contain a contradiction. In this formalization, we restructured the completeness proof to cleanly separate the ground (i.e., variable-free) and nonground aspects. We relied on the IsaFoR library for first-order terms and on the Isabelle saturation framework. A paper describing this formalization was published at the 15th International Conference on Interactive Theorem Proving (ITP 2024).

License

BSD License

Topics

Related publications

  • Desharnais, M., Toth, B., Waldmann, U., Blanchette, J., & Tourret, S. (2024). A Modular Formalization of Superposition in Isabelle/HOL. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITP.2024.12

Session Superposition_Calculus

Depends on

Cite

× 
@article{Superposition_Calculus-AFP,
  author  = {Martin Desharnais and Balazs Toth},
  title   = {A Modular Formalization of Superposition},
  journal = {Archive of Formal Proofs},
  month   = {October},
  year    = {2024},
  note    = {\url{https://isa-afp.org/entries/Superposition_Calculus.html},
             Formal proof development},
  ISSN    = {2150-914x},
}
Download

Download

× Download latest