Paper Info
Title
Theorem Proving as Constraint Solving with Coherent Logic.
Abstract
In contrast to common automated theorem proving approaches, in which the search space is a set of some formulae and what is sought is again a (goal) formula, we propose an approach based on searching for a proof (of a given length) as a whole. Namely, a proof of a formula in a fixed logical setting can be encoded as a sequence of natural numbers meeting some conditions and a suitable constraint solver can find such a sequence. The sequence can then be decoded giving a proof in the original theory language. This approach leads to several unique features, for instance, it can provide shortest proofs. In this paper, we focus on proofs in coherent logic, an expressive fragment of first-order logic, and on SAT and SMT solvers for solving sets of constraints, but the approach could be tried in other contexts as well. We implemented the proposed method and we present its features, perspectives and performances. One of the features of the implemented prover is that it can generate human understandable proofs in natural language and also machine-verifiable proofs for the interactive prover Coq.
Year
DOI
Venue
2022
10.1007/s10817-022-09629-z
Journal of Automated Reasoning
Keywords
DocType
Citations 
Automated theorem proving,Interactive theorem proving,Constraint solving,Coherent logic,SAT/SMT solving
Journal
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Predrag Janicic1738.22
Julien Narboux213012.49