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