Complejidad del esquema en lógicas basadas en proposiciones
Autores: Ramos, Jaime; Rasga, João; Sernadas, Cristina
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Complejidad del esquema en lógicas basadas en proposiciones
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Estructura
Derivaciones
Complejidad
Esquema
Metateoremas
Eliminación
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 33
Citaciones: Sin citaciones
La estructura esencial de las derivaciones se utiliza como una herramienta para medir la complejidad de las consecuencias de esquemas en lógicas basadas en proposiciones. Nuestras derivaciones de esquemas permiten el uso de lemas de esquemas y esto se refleja en la complejidad del esquema. En particular, el número de veces que se utiliza un lema de esquema en una derivación no es relevante. También abordamos la aplicación de metateoremas y comparamos la complejidad de una derivación de esquema después de eliminar el metateorema y antes de hacerlo. Como ilustraciones, consideramos una lógica modal proposicional presentada por un cálculo de Hilbert y una lógica proposicional intuicionista presentada por un cálculo de Gentzen. Para la primera, discutimos el uso del metateorema de deducción y su eliminación, y para la segunda, analizamos el corte y su eliminación. Además, aprovechamos el resultado para la eliminación del corte para la lógica intuicionista, para obtener un resultado similar para la lógica de Nelson a través de una traducción de lenguaje.
Descripción
La estructura esencial de las derivaciones se utiliza como una herramienta para medir la complejidad de las consecuencias de esquemas en lógicas basadas en proposiciones. Nuestras derivaciones de esquemas permiten el uso de lemas de esquemas y esto se refleja en la complejidad del esquema. En particular, el número de veces que se utiliza un lema de esquema en una derivación no es relevante. También abordamos la aplicación de metateoremas y comparamos la complejidad de una derivación de esquema después de eliminar el metateorema y antes de hacerlo. Como ilustraciones, consideramos una lógica modal proposicional presentada por un cálculo de Hilbert y una lógica proposicional intuicionista presentada por un cálculo de Gentzen. Para la primera, discutimos el uso del metateorema de deducción y su eliminación, y para la segunda, analizamos el corte y su eliminación. Además, aprovechamos el resultado para la eliminación del corte para la lógica intuicionista, para obtener un resultado similar para la lógica de Nelson a través de una traducción de lenguaje.