Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/528
Title: Theorem Proving as Constraint Solving with Coherent Logic
Authors: Janičić, Predrag 
Narboux, Julien
Affiliations: Informatics and Computer Science 
Keywords: Automated theorem proving;Coherent logic;Constraint solving;Interactive theorem proving;SAT/SMT solving
Issue Date: 2022
Journal: Journal of Automated Reasoning
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.
URI: https://research.matf.bg.ac.rs/handle/123456789/528
ISSN: 01687433
DOI: 10.1007/s10817-022-09629-z
Appears in Collections:Research outputs

Show full item record

SCOPUSTM   
Citations

2
checked on Dec 20, 2024

Page view(s)

24
checked on Dec 24, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.