Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T05:47:52.852Z Has data issue: false hasContentIssue false
  • English
  • Français

Abductive Reasoning in Intuitionistic Propositional Logic via Theorem Synthesis

Published online by Cambridge University Press:  28 June 2022

PAUL TARAU Open the ORCID record for PAUL TARAU [Opens in a new window]
PAUL TARAU*
Affiliation:
University of North Texas, Denton, TX 76203, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

With help of a compact Prolog-based theorem prover for Intuitionistic Propositional Logic, we synthesize minimal assumptions under which a given formula formula becomes a theorem. After applying our synthesis algorithm to cover basic abductive reasoning mechanisms, we synthesize conjunctions of literals that mimic rows of truth tables in classical or intermediate logics and we abduce conditional hypotheses that turn the theorems of classical or intermediate logics into theorems in intuitionistic logic. One step further, we generalize our abductive reasoning mechanism to synthesize more expressive sequent premises using a minimal set of canonical formulas, to which arbitrary formulas in the calculus can be reduced while preserving their provability. Organized as a self-contained literate Prolog program, the paper supports interactive exploration of its content and ensures full replicability of our results.

Keywords

abductive reasoning in intuitionistic logictheorem synthesislogic programming and automated reasoningtheorem provers for intuitionistic propositional logicimplementing sequent calculi in Prolog
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 22 , Issue 5: 38th International Conference on Logic Programming Special Issue II , September 2022 , pp. 693 - 707
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

We thank the anonymous reviewers of ICLP’2022 for their constructive comments and suggestions.

References

Denecker, M. and Kakas, A. 2002. Abduction in logic programming. In Computational Logic: Logic Programming and Beyond. Springer, 402–436.Google Scholar
Dyckhoff, R. 1992. Contraction-free sequent calculi for intuitionistic logic. Journal of Symbolic Logic 57, 3, 795–807.CrossRefGoogle Scholar
Dyckhoff, R. 2016. Intuitionistic decision procedures since Gentzen. In Advances in Proof Theory, R. Kahle, T. Strahm and T. Studer, Eds. Springer International Publishing, Cham, 245–267.Google Scholar
Eshghi, K. and Kowalski, R. A. 1989. Abduction compared with negation by failure. In Logic Programming, Proceedings of the Sixth International Conference, Lisbon, Portugal, 19–23 June 1989, G. Levi and M. Martelli, Eds. MIT Press, 234–254.Google Scholar
Gabbay, D. and Olivetti, N. 2002. Goal-oriented deductions. In Handbook of Philosophical Logic. Springer, 199–285.Google Scholar
Gabbay, D. M. 2000. Goal directed mechanisms: Proofs, interpolation and abduction procedures. In Proceedings of the Seventh Workshop on Automated Reasoning, Bridging the Gap between Theory and Practice, King’s College London, UK, 20–21 July 2000, H. J. Ohlbach, U. Endriss, O. Rodrigues and S. Schlobach, Eds. CEUR Workshop Proceedings, vol. 32. CEUR-WS.org.CrossRefGoogle Scholar
Hudelmaier, J. 1988. A PROLOG Program for Intuitionistic Logic. SNS-Bericht-. Universität Tübingen.Google Scholar
Lifschitz, V., Pearce, D. and Valverde, A. 2001. Strongly equivalent logic programs. ACM Transactions on Computational Logic 2, 4, 526–541.CrossRefGoogle Scholar
Mints, G. 1992. Complexity of subclasses of the intuitionistic propositional calculus. BIT 32, 1, 64–69.CrossRefGoogle Scholar
Pearce, D. 1996. A new logical characterisation of stable models and answer sets. In NMELP. Lecture Notes in Computer Science, vol. 1216. Springer, 57–70.Google Scholar
Pearce, D. 1997. A new logical characterisation of stable models and answer sets. In Selected Papers from the Non-Monotonic Extensions of Logic Programming. NMELP’96. Springer-Verlag, Berlin, Heidelberg, 57–70.Google Scholar
Pearce, D., de Guzmán, I. P. and Valverde, A. 2000. Tableau calculus for equilibrium entailment. In Automated Reasoning with Analytic Tableaux and Related Methods, International Conference, TABLEAUX 2000, St Andrews, Scotland, UK, 3–7 July 2000, Proceedings, R. Dyckhoff, Ed. Lecture Notes in Computer Science, vol. 1847. Springer, 352–367.Google Scholar
Tarau, P. 2019. A combinatorial testing framework for intuitionistic propositional theorem provers. In Practical Aspects of Declarative Languages - 21th International Symposium, PADL 2019, Lisbon, Portugal, 14–15 January 2019, Proceedings, J. J. Alferes and M. Johansson, Eds. Lecture Notes in Computer Science, vol. 11372. Springer, 115–132.Google Scholar
Tarau, P. 2020. Synthesis of modality definitions and a theorem prover for epistemic intuitionistic logic. In Logic-Based Program Synthesis and Transformation - 30th International Symposium, LOPSTR 2020, Bologna, Italy, 7–9 September 2020, Proceedings, M. Fernández, Ed. Lecture Notes in Computer Science, vol. 12561. Springer, 329–344.Google Scholar
Tarau, P. and de Paiva, V. 2020. Deriving theorems in implicational linear logic, declaratively. In Proceedings, 36th International Conference on Logic Programming (Technical Communications), F. Ricca, A. Russo, S. Greco, N. Leone, A. Artikis, G. Friedrich, P. Fodor, A. Kimmig, F. A. Lisi, M. Maratea, A. Mileo and F. Riguzzi, Eds. EPTCS, vol. 325, 110–123.Google Scholar