 | |  | | | Conectados:
Actualmente hay 6 invitados, 1 miembro(s) conectado(s).
Es un usuario anónimo. Puede registrarse aquí | |  | |  |
|  |
 |
|
 |
| |
Patiperros del DCC
CC51I Seminario: Logica para Ciencia de la Computacion
10 UD
PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE
ESCUELA DE INGENIERIA
DEPARTAMENTO DE CIENCIA DE LA COMPUTACION
1 Requisitos
CC40A, CC41A
2 Programa
1. Sintaxis y semantica de la logica proposicional. Nocion de consecuencia
logica. Consistencia, satisfacibilidad de formulas, compacidad.
2. Demostraciones formales por resolucion en logica proposicional.
3. Introduccion a programacion en logica. Introduccion a PROLOG.
4. Un sistema de derivacion para la logica proposicional. Correccion y
completidad.
5. Introduccion a la computabilidad y a la complejidad computacional.
Problema de la parada de maquinas de Turing. NP-completidad de SAT.
6. Aplicaciones a bases de datos relacionales.
7. Sintaxis y semantica de la logica de predicados de primer orden.
Estructuras. Teorias.
8. Un sistema de derivacion formal para la logica de predicados de primer
orden. Correccion y completidad. Compacidad.
9. Ejemplos de otras logicas y reglas de deduccion. Abduccion, induccion,
no monotonia.
10. Teorias axiomatizables, recursivamente enumerables, decidibles,
completas. Teoremas de Kleene, Church-Turing, Goedel (incompletidad).
11. Introduccion a logica de segundo orden, aritmetica de segundo orden y
categoricidad (Teo. de Dedekind), esquemas de primer orden, modelos no
estandar para la aritmetica.
12. Complejidad computacional de teorias formalizadas (introduccion).
13. Logica con varias especies. Calculo de situaciones.
1
14. Formalizaciones del razonamiento con sentido comun (introduccion),
conexion con programacion en logica.
15. Especificaciones formales de tipos de datos y procedimientos.
Derivacion de programas a partir de especificaciones.
3 Bibliografia
o Schoning, U. "Logic for Computer Scientists", Birkhauser, 1989.
o Reeves & Clarke "Logic for Computer Science", Addison Wesley, 1990.
o Fitting, M. "First-Order Logic and Automated Theorem Proving", Springer,
1991.
Enderton, H. "A Mathematical Introduction to Logic", Academic
o Press, 1972.
o Barwise & Etchemendy "The Language of First-Order Logic", Chicago
University Press, 1992.
o Kowalsky, R. "Logic for Problem Solving", North-Holland, 1978.
o Gallier, J.H. "Logic for Computer Science", Harper & Row Publ., 1986.
o Bertossi, L. "Logica para Ciencia de Computacion", Libro en preparacion.
2
|
|
 |
|
 |
|
