Schema Complexity in Propositional-Based Logics

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Jaime Ramos, João Rasga, Cristina Sernadas
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	schematic complexity propositional-based schema calculus schema derivation schema metatheorems Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/19bd520978e34bb287db101bb426fa05
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:19bd520978e34bb287db101bb426fa05
record_format	dspace
spelling	oai:doaj.org-article:19bd520978e34bb287db101bb426fa052021-11-11T18:14:17ZSchema Complexity in Propositional-Based Logics10.3390/math92126712227-7390https://doaj.org/article/19bd520978e34bb287db101bb426fa052021-10-01T00:00:00Zhttps://www.mdpi.com/2227-7390/9/21/2671https://doaj.org/toc/2227-7390The 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.Jaime RamosJoão RasgaCristina SernadasMDPI AGarticleschematic complexitypropositional-based schema calculusschema derivationschema metatheoremsMathematicsQA1-939ENMathematics, Vol 9, Iss 2671, p 2671 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	schematic complexity propositional-based schema calculus schema derivation schema metatheorems Mathematics QA1-939
spellingShingle	schematic complexity propositional-based schema calculus schema derivation schema metatheorems Mathematics QA1-939 Jaime Ramos João Rasga Cristina Sernadas Schema Complexity in Propositional-Based Logics
description	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.
format	article
author	Jaime Ramos João Rasga Cristina Sernadas
author_facet	Jaime Ramos João Rasga Cristina Sernadas
author_sort	Jaime Ramos
title	Schema Complexity in Propositional-Based Logics
title_short	Schema Complexity in Propositional-Based Logics
title_full	Schema Complexity in Propositional-Based Logics
title_fullStr	Schema Complexity in Propositional-Based Logics
title_full_unstemmed	Schema Complexity in Propositional-Based Logics
title_sort	schema complexity in propositional-based logics
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/19bd520978e34bb287db101bb426fa05
work_keys_str_mv	AT jaimeramos schemacomplexityinpropositionalbasedlogics AT joaorasga schemacomplexityinpropositionalbasedlogics AT cristinasernadas schemacomplexityinpropositionalbasedlogics
_version_	1718431868365307904

Schema Complexity in Propositional-Based Logics

Ejemplares similares