Introducción a la Lógica (IL)

El objetivo de esta asignatura es proporcionar al estudiante una base sólida de conocimientos teóricos y prácticos de lógica para informáticos, y, al mismo tiempo, contribuir a su formación global en razonamiento formal (sobre conjuntos, relaciones, funciones, estructuras de orden, recursión, conteo), y técnicas de demostración (contrarrecíproco, contraejemplos, inducción, reducción al absurdo).

Conocimientos

1. El concepto de qué es una lógica, en términos de sintaxis (qué es una fórmula F), y semántica (qué es una interpretación I, y cuándo una I satisface una F).
   
   
2. La definición (sintaxis y semántica) de dos lógicas: la proposicional y la de primer orden.
   
3. Los conceptos de tautología/validez, contradicción, consecuencia y equivalencia lógica (de forma independiente de la lógica concreta), cómo se utilizan para formalizar problemas prácticos en informática, y cómo se reducen al problema de satisfactibilidad.
4. Los métodos de deducción para determinar estas propiedades de mayor relevancia para la informática: Davis-Putnam, y resolución; su corrección y completitud con respecto de la definición de la lógica.
   
5. El poder expresivo de las dos lógicas, y entender en qué sentido la lógica proposicional es una restricción de la otra; compromiso entre poder expresivo y buenas propiedades computacionales: primeras nociones intuitivas de complejidad y decidibilidad.
   
6. Algunas de las -cada vez más abundantes- aplicaciones a la informática de los métodos deductivos: fundamentos de la programación lógica (Prolog) bases de datos deductivas, circuitos, problemas de planificación, etc.
   

Habilidades

1. Entender, escribir y manipular ágilmente fórmulas en ambas lógicas, con especial énfasis en aplicaciones a la informática.
   
2. Saber demostrar formalmente propiedades sencillas sobre fórmulas, conjuntos, relaciones, funciones, etc, mediante técnicas de demostración como el contrarrecíproco, contraejemplos, inducción, o reducción al absurdo.
   
3. Ser capaz de aplicar a mano resolucion y Davis-Putnam sobre ejemplos practicos abordables, y saber utilizar la resolución como mecanismo de cómputo (cálculo de respuestas).
   
4. Saber expresar algunos problemas prácticos NP-completos (sudokus, horarios, problemas de grafos, circuitos) como problemas de satisfacción de lógica proposicional, y resolverlos con un SAT solver.
   
   
5. Saber expresar problemas sencillos utilizando el lenguaje Prolog, y entender las extensiones "extra-lógicas" de Prolog (la aritmética predefinida, el operador de corte y la negación, la entrada/salida).
   

Competencias

En las sesiones de clase (en total cinco horas semanales) se intercalarán teoría y problemas de manera flexible según las necesidades del temario en cada momento. No conviene fijar de manera rígida cuántas y qué horas semanales serán de problemas. No hay clases de laboratorio.

La metodología docente está basada en los siguientes principios:

1. Se plantea la clase como un inicio del estudio y el trabajo que el estudiante debe continuar y profundizar por su cuenta.

2. Se proporciona el máximo de materiales de calidad (apuntes, ejercicios resueltos, ejercicios por hacer, referencias bibliográficas).

3. Se aprovechan al máximo las clases para fomentar la motivación del estudiante (con ejemplos, debates, comentarios, etc.) y se transmite el enfoque y las intuiciones detrás de las definiciones, propiedades y técnicas tratadas.

Alrededor de la semana 7 del cuatrimestre se hará un examen parcial de unos 90 minutos de duración, sobre los dos temas de lógica proposicional, cuyo peso es del 40% de la nota total.

El examen final, a celebrar en la época de exámenes, tendrá dos partes: recuperación de los dos temas de lógica proposicional (40% de la nota final) y los temas de lógica de primer orden y programación lógica (60%). Todo estudiante puede decidir libremente si se presenta o no
a la parte de recuperación, y se le contará la nota máxima entre la nota del parcial y la nota de esta parte. Es decir, incluso si su nota
del parcial es muy alta, no cree el riesgo de perderla.

Los exámenes constarán de preguntas de comprensión de los conceptos, de demostración de propiedades, de aplicación de las técnicas de deducción, y de resolución de problemas en Prolog.

Cualquier intento de fraude realizado durante el curso comportará la aplicación de la normativa académica general de la UPC i el inicio de un proceso disciplinario.

• Uwe Schöning Logic for computer scientists, Birkhäuser, 1989.
• María Teresa Hortalá González, Javier Leach Albert, Mario Rodríguez Artalejo Matemática discreta y lógica matemática, Complutense, 2001.

Introducción a la programación y a la programación recursiva.