Palabras clave
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
Cómo citar
Resumen
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.
Citas
Church, A. (1936) “A note on the Entscheidungsproblem”, The Journal of Symbolic Logic 1(1): 40–41.
Church, A. (1956) Introduction to Mathematical Logic, Vol. 1. Princeton University Press, Princeton NJ.
Davis, M. (1958) Computability and Unsolvability. Dover Publications, New York.
Davis, M.; Weyuker, E. (1983) Computability, Complexity, and Languages. Academic Press, Boston.
Dekker, J.C.E. (1976) Equivalencia Recursiva. Editorial CAEM, San José.
Hennie, F. (1977) Introduction to Computability. Addison-Wesley, Boston MA.
Hopcroft, J.; Ullman, J. (1979) Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading MA.
Kfoury, A.J.; Moll, R.N.; Arbib, M.A. (1982) A Programming Approach to Computability. Springer-Verlag, New York.
Linial, S.; Post, E. (1949) “Recursive unsolvability of the deductibility, Tarsky’s completeness and independence of axioms problems of the propositional calculus”, Bulletin of the American Mathematical Society 55: 50.
Piza, E. (2001) Aritmética Recursiva y Algunas de sus Aplicaciones, Editorial CIMPA, San José.
Rogers, H. (1967) Theory of Recursive Function and Effective Computability. McGraw-Hill, New York.
Soare, R. (1980) Recursive Enumerate Sets and Degrees: a Study of Computable Functions and Computable Generated Sets. Springer-Verlag, Berlin.
Turing, A. (1936) “On computable numbers, with an application to the “Entscheidungsproblem”, Proceedings of the London Mathematical Society 42(2) 230–265.