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.)
