Search

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.

We describe a syntactical proof-reconstruction approach to verify derivations generated by Metis prover to theorems in classical propositional logic -- To verify such derivations, we formalize in type theory each inference rule of the Metis reasoning -- We developed a tool jointly with two Agda libraries to translate Metis derivations to Agda proof-terms -- These developments allowed us to type-check with Agda, Metis derivations step-by-step

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

El artículo revisa los límites teóricos que unen y separan la lógica de Aristóteles de la lógica aristotélica y la lógica de primer orden. Considera las razones para sostener la actualidad de la lógica de Aristóteles y se pregunta por la unidad de la disciplina, destacando la importancia de la noción de ciencia en la definición de lógica The article deals with the theoretical limits which unify Aristotle's logic with Aristotelian logic and First Order Logic, and it realizes their differences too. It examines the reasons to maintain the presence and actuality of Aristotle's logic and discovers the importance of the notion of science in defining the nature of logic

Beth's method of semantic tableaux has been utilized in first order logic to obtain some results. From a metalogical point of view, a known result can be proved: completeness of first order logic. Can we extend this method to second order logic? What about completeness? Given a second order formal language, for every formula a prenex form can be defined so that some of them have a first order formula as its matrix, then the mentioned method could be applied to study several classes of formulae, particularly ∑¦, ∏¦and Zykov's inverses. In order to do that some modifications of such method must be introduced, so that we take known rules for first order semantic trees, by applying them, modifying the treatment of "∃" and defining specific rules for some second order formulae, then we can achieve some results relative to such classes similar to that obtained by means of abstract model theory. On the other hand, a restricted completeness (to certain class of sentences) could be settled. Ministerio Español de Educación y Cultura PB96-1301-C05-0