Skip to content

Departamento de Matematica

Sections
Personal tools
You are here: Home » Académico » Programas de las materias dictadas por el Departamento » Lógica y Computabilidad

Lógica y Computabilidad

Lógica: Sistemas formales. Cálculo proposicional y cálculo de predicados de primer orden. Sintaxis y semántica. Unicidad de escritura. Valuaciones y tablas de verdad. Consecuencia semántica y satisfacibilidad. Árboles de refutación. Teoremas de completud y compacidad.

Computabilidad: Algoritmos y funciones computables. Un lenguaje de programación básico para la definición de funciones computables. El Halting Problem. Funciones recursivas primitivas y funciones recursivas. Programas universales. El programa Step Counter. Tesis de Church. Teorema de la recursión. Conjuntos recursivos y recursivamente enumerables. Teorema de Rice.


BIBLIOGRAFÍA BÁSICA:

  • Davis, M. D. and Weyuker, E.J., Computability, Complexity and Languages. Fundamentals of theoretical computer science, Academic Press, 1983.

  • Fitting, M., First order logic and automated theorem proving, Springer-Verlag, 1990

  • Hennie, F., Introduction to computability, Addison-Wesley, 1977.

  • Smullyan, R. First order logic, Springer-Verlag, 1968

  • Notas de clase.

CORRELATIVAS Álgebra I y Estructura de datos (Comp.)/ Cálculo Avanzado (Lic. Prof.)


Created by secre
Last modified 2008-03-07 01:41 PM
 

Powered by Plone