Problemas de decisión y recursividad en sistemas lógicos formales

Problemas de decisión y recursividad en sistemas lógicos formales

En la teoría de la recursión se dice que un problema de decisión es recursivamente resoluble si existe un procedimiento mecánico para resolverlo. Dentro del contexto de las lógicas formales, el problema de decisión consiste simplemente en determinar si una fórmula bien formada cualquiera del...

Descripción completa

Detalles Bibliográficos
Autores principales: Martínez, Iveth, Piza, Eduardo
Formato: Online
Idioma:spa
Publicado: Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2017
Acceso en línea:https://revistas.ucr.ac.cr/index.php/matematica/article/view/22338
id RMTA22338
record_format ojs
spelling RMTA223382022-01-31T15:46:48Z Decision problems and recursiveness in formal logic systems Problemas de decisión y recursividad en sistemas lógicos formales Martínez, Iveth Piza, Eduardo decision problems formal logic first-order logic Entscheidungs problem partial propositional logics semi-Thue production systems problemas de decisión lógicas formales lógicas de primer orden lógicas proposicionales parciales Entscheidungsproblem sistemas productivos semi-Thue The recursion theory states that a decision problem is recursively solvable if there is a mechanical process to solve it. Within the context of formal logic, the decision problem consist to determine whether any wellformed formula of the system is a theorem or not. This paper first discusses, among other things, the famous problem of decision of the canonical first-order logic F0 (also called Entscheidungsproblem) from a modern perspective. Then we study the decision problem of the partial propositional logics. It exploits the development achieved by recursion theory and semi-Thue production systems after the work of Post and Kleene in the 40’s and Davis in the early 70’s, among others, to explain a solution to these decision problems. En la teoría de la recursión se dice que un problema de decisión es recursivamente resoluble si existe un procedimiento mecánico para resolverlo. Dentro del contexto de las lógicas formales, el problema de decisión consiste simplemente en determinar si una fórmula bien formada cualquiera del sistema es, o no es, un teorema. En este trabajo se analizan, entre otros asuntos, primeramente el famoso problema de decisión de la lógica canónica de primer orden F0 (también llamado Entscheidungsproblem) desde una perspectiva moderna. Luego se estudian los problemas de decisión de las lógicas proposicionales parciales. Se aprovecha el desarrollo alcanzado por la teoría de la recursión y de los sistemas productivos semi-Thue, luego de los trabajos de Post y Kleene en los años 40’s y de Davis en la década de los 70’s, entre otros, para explicar una solución a estos problemas de decisión. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2017-04-19 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/22338 10.15517/rmta.v23i1.22338 Revista de Matemática: Teoría y Aplicaciones; Vol. 23 No. 1 (2016): Revista de Matemática: Teoría y Aplicaciones; 11-39 Revista de Matemática: Teoría y Aplicaciones; Vol. 23 Núm. 1 (2016): Revista de Matemática: Teoría y Aplicaciones; 11-39 Revista de Matemática; Vol. 23 N.º 1 (2016): Revista de Matemática: Teoría y Aplicaciones; 11-39 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/22338/22494 Derechos de autor 2016 Revista de Matemática: Teoría y Aplicaciones
institution Universidad de Costa Rica
collection Revista de Matemática: Teoría y Aplicaciones
language spa
format Online
author Martínez, Iveth
Piza, Eduardo
spellingShingle Martínez, Iveth
Piza, Eduardo
Problemas de decisión y recursividad en sistemas lógicos formales
author_facet Martínez, Iveth
Piza, Eduardo
author_sort Martínez, Iveth
description En la teoría de la recursión se dice que un problema de decisión es recursivamente resoluble si existe un procedimiento mecánico para resolverlo. Dentro del contexto de las lógicas formales, el problema de decisión consiste simplemente en determinar si una fórmula bien formada cualquiera del sistema es, o no es, un teorema. En este trabajo se analizan, entre otros asuntos, primeramente el famoso problema de decisión de la lógica canónica de primer orden F0 (también llamado Entscheidungsproblem) desde una perspectiva moderna. Luego se estudian los problemas de decisión de las lógicas proposicionales parciales. Se aprovecha el desarrollo alcanzado por la teoría de la recursión y de los sistemas productivos semi-Thue, luego de los trabajos de Post y Kleene en los años 40’s y de Davis en la década de los 70’s, entre otros, para explicar una solución a estos problemas de decisión.
title Problemas de decisión y recursividad en sistemas lógicos formales
title_short Problemas de decisión y recursividad en sistemas lógicos formales
title_full Problemas de decisión y recursividad en sistemas lógicos formales
title_fullStr Problemas de decisión y recursividad en sistemas lógicos formales
title_full_unstemmed Problemas de decisión y recursividad en sistemas lógicos formales
title_sort problemas de decisión y recursividad en sistemas lógicos formales
title_alt Decision problems and recursiveness in formal logic systems
publisher Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate 2017
url https://revistas.ucr.ac.cr/index.php/matematica/article/view/22338
work_keys_str_mv AT martineziveth decisionproblemsandrecursivenessinformallogicsystems
AT pizaeduardo decisionproblemsandrecursivenessinformallogicsystems
AT martineziveth problemasdedecisionyrecursividadensistemaslogicosformales
AT pizaeduardo problemasdedecisionyrecursividadensistemaslogicosformales
_version_ 1811744093094543360

Ejemplares similares