Schema Complexity in Propositional-Based Logics

Jaime Ramos, João Rasga and Cristina Sernadas
Additional contact information
Jaime Ramos: Instituto Superior Técnico, Universidade de Lisboa and Instituto de Telecomunicações, 1049-001 Lisboa, Portugal
João Rasga: Instituto Superior Técnico, Universidade de Lisboa and Instituto de Telecomunicações, 1049-001 Lisboa, Portugal
Cristina Sernadas: Instituto Superior Técnico, Universidade de Lisboa and Instituto de Telecomunicações, 1049-001 Lisboa, Portugal

Mathematics, 2021, vol. 9, issue 21, 1-22

Abstract: The essential structure of derivations is used as a tool for measuring the complexity of schema consequences in propositional-based logics. Our schema derivations allow the use of schema lemmas and this is reflected on the schema complexity. In particular, the number of times a schema lemma is used in a derivation is not relevant. We also address the application of metatheorems and compare the complexity of a schema derivation after eliminating the metatheorem and before doing so. As illustrations, we consider a propositional modal logic presented by a Hilbert calculus and an intuitionist propositional logic presented by a Gentzen calculus. For the former, we discuss the use of the metatheorem of deduction and its elimination, and for the latter, we analyze the cut and its elimination. Furthermore, we capitalize on the result for the cut elimination for intuitionistic logic, to obtain a similar result for Nelson’s logic via a language translation.

Keywords: schematic complexity; propositional-based schema calculus; schema derivation; schema metatheorems (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/21/2671/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/21/2671/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:21:p:2671-:d:661621

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().