Aumentar letras   Inicio   Información   Contactar   Mapa
Català   English

Introducción a la Lógica (IL)

Créditos Dept. Tipo Requisitos
7.5 (6.0 ECTS) LSI-MA2
  • Obligatoria para la EI
  • Obligatoria para la ETIG
  • Obligatoria para la ETIS
    

Profesores

Responsable:  Enric Rodriguez Carbonell (erodri@lsi.upc.edu)
Robert Lukas Mario Nieuwenhuis (roberto@lsi.upc.edu)
Otros:Albert Oliveras Llunell (oliveras@lsi.upc.edu)
Anna De Mier Vinué (anna.de.mier@upc.edu)
Francisco Javier Larrosa Bondia (larrosa@lsi.upc.edu)
Maria Josefina Sierra Santibañez (jsierra@lsi.upc.edu)
Pilar Nivela Alos (nivela@lsi.upc.edu)

Objectivos Generales

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

Objectivos Específicos

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

(Información no introducida)

Contenidos

Horas estimadas de:

T P L Alt L Ext. Est O. Ext.
Teoria Problemas Laboratorio Otras actividades Laboratorio externo Estudio Otras horas fuera del horario fijado

1. Introducción y motivación
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 0 0 0 0 2,0 0 4,0
-Importancia de la lógica en la informática, ejemplos
-Lógica informática vs lógica matemática
-Qué es una lógica
-Objetivos de la asignatura


2. Definición de la Lógica Proposiciónal
T      P      L      Alt    L Ext. Est    O. Ext. Total 
12,0 0 0 0 0 12,0 0 24,0
-Sintaxis y semantica de la LP
-Satisfacción, tautología, consecuencia y equivalencia
-Todos estos problemas se pueden expresar como SAT
-Poder expresivo: qué cosas se pueden modelar
Ejercicios sobre: inducción, legibilidad única de formulas,
formalización de problemas, conteo (de formulas, interpretaciones, etc.),
problemas de consecuencia y equivalencia lógicas, intuición de coste
computacional polinómico vs. exponencial (tablas de verdad), coste
lineal de evaluar una fórmula, entre otros.
  • Laboratorio:
    Nota: no se hace distinción entre clases de teoría y de problemas.

3. Deducción en Lógica Proposicional
T      P      L      Alt    L Ext. Est    O. Ext. Total 
12,0 0 0 0 0 12,0 0 24,0
-Formas normales, literales y cláusulas.
-Algoritmo de Davis-Putnam-Logemann-Loveland (DPLL)
(a partir de tablas de verdad y árboles de decisión),
La pila explícita de Backtracking
-Cómo expresar problemas como SAT, y utilizar SAT-solvers
-Intuición de problemas NP y NP completos
-Sistemas deductivos: propiedades de corrección, completitud, y completitud refutacional.
-Resolución: clausura bajo resolución.
Ejercicios sobre formas normales, coste de las transformaciones,
relación con circuitos digitales, deducción por resolucion y DPLL,
y formulación de
problemas como SAT: (sudokus, vertex cover, confección de horarios,
hitting set)


4. Definición de la Lógica de Primer Orden
T      P      L      Alt    L Ext. Est    O. Ext. Total 
15,0 0 0 0 0 15,0 0 30,0
-Sintaxis y semántica de la LPO
-Fórmulas cerradas
-Poder expresivo y decidibilidad
-La LP como caso particular de la LPO
-Lógica de primer orden con igualdad, y teorías
Ejercicios sobre: legibilidad única de formulas,
formalización de problemas, conteo (de fórmulas, interpretaciones, etc.),
problemas de consecuencia y equivalencia lógicas,
modelos finitos e infinitos,etc.


5. Deducción en Lógica de Primer Orden
T      P      L      Alt    L Ext. Est    O. Ext. Total 
15,0 0 0 0 0 15,0 0 30,0
-Formas normales, literales y cláusulas.
-Paso a forma clausal, Skolemización
-Unificación, unificador simultáneo, las reglas de unificación:
terminación y corrección.
-Resolucion y factorización: corrección y completitud refutacional
-No-terminación: procedimientos de decision y de (co-)semi-decision
Ejercicios de formalización, paso a forma clausal, unificación,
resolución, y problemas sobre (semi-)decisión aplicados a los
programas y la compilación.

6. Programación Lógica
T      P      L      Alt    L Ext. Est    O. Ext. Total 
14,0 0 0 0 0 14,0 0 28,0
-Cálculo de respuestas: cómo encontrar los valores de X que hacen que F\models \exists X G?
-La estrategia SLD de resolución para cláusulas de Horn
-Completitud para el cálculo de respuestas
-La pila de backtracking: qué hace el operador de corte?
-Otros aspectos extra-lógicos: la negación, la aritmética predefinida, la entrada-salida.
Ejercicios de resolución con cálculo de respuestas, sobre la teoría y
el comportamiento de programas Prolog, y de confección de programas
Prolog.


Total por tipo T      P      L      Alt    L Ext. Est    O. Ext. Total 
70,0 0 0 0 0 70,0 0 140,0
Horas adicionales dedicadas a la evaluación 0
Total horas de trabajo para el estudiante 140,0

Metodología docente

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.

Método de evaluación

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.

Bibliografía básica

  • Schoening, Uwe Logic for Computer Scientists, Birkhauser, 1994.
  • Leach, javier, y hortalá, Teresa, y Rodriguez, Mario Matemática discreta y lógica matemática, Editorial Complutense, 2001.

Bibliografía complementaria

(Información no introducida)

Enlaces web

(Información no introducida)

Capacidades previas

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



 
logo FIB © Facultad de Informática de Barcelona - webmaster@fib.upc.edu - RSS RSS