Introducció a la Lògica (IL)

L'objectiu d'aquesta assignatura és proporcionar a l'estudiant una base sòlida de coneixements teòrics i pràctics de lògica per informàtics, i, al mateix temps, contribuir a la seva formació global en raonament formal (sobre conjunts, relacions, funcions, estructures d'ordre, recursió, comptatge), i tècniques de demostració (contrarrecíproc, contraexemples, inducció, reducció a l'absurd).

Coneixements

1. El concepte de què és una lògica, en termes de sintaxi (què és una fórmula F), i semàntica (què és una interpretació I, i quan una I satisfà una F).
   
2. La definició (sintaxi i semàntica) de dues lògiques: la proposicional i la de primer ordre.
3. Els conceptes de tautologia/validesa, contradicció, conseqüència i equivalència lògiques (de forma independent de la lògica concreta), com s'utilitzen per a formalitzar problemes pràctics a l'informàtica, i com es redueixen al problema de satisfactibilitat.
4. Els mètodes de deducció per a determinar aquestes propietats de major relevància a la informàtica: Davis-Putnam, i resolució; la seva correcció i completesa respecte de la definició de la lògica.
   
5. El poder expressiu de les dues lògiques, i entendre en quin sentit la lògica proposicional és una restricció de l'altra; compromís entre poder expressiu i bones propietats computacionals: primeres nocions intuïtives de complexitat i decidibilitat.
   
6. Algunes de les -cada cop més abundants- aplicacions a la informàtica dels mètodes deductius: fonaments de la programació lògica (Prolog), bases de dades deductives, circuits, problemes de planificació, etc.
   

Habilitats

1. Entendre, escriure i manipular ágilment fórmules en les dues lògiques, amb especial émfasi a les aplicacions a l'informàtica.
2. Saber demostrar formalment propietats senzilles sobre fórmules, conjunts, relacions, funcions, etc, mitjançant tècniques de demostració com ara el contrarrecíproc, contraexemeple, inducció, o reducció l'absurd.
   
3. Ser capaç d'aplicar a ma resolució i Davis-Putnam sobre exemples pràctics abordables, i saber utilitzar la resolució com a mecanisme de còmput (càlcul de respostes).
   
4. Saber expressar alguns problemes pràctics NP-complets (sudokus, horaris, problemes de grafs, circuits) com a problemes de satisfacció de lògica proposicional, i resoldre-ls amb un SAT solver.
   
5. Saber expressar problemes senzills utilitzant el llenguatge Prolog, i entendre les extensions "extra-lògiques" del Prolog (l'aritmética predefinida, l'operador de tall i la negació, l'entrada/sortida).
   

Competències

A les sessions de classe (en total cinc hores setmanals) s'intercalaran teoria i problemes de manera flexible segons les necessitats del temari a cada moment. No convé fixar de manera rígida quantes i quines hores setmanals seran de problemes. No hi ha classes de laboratori.

La metodologia docent es basa en els següents principis:

1. Es planteja la classe com un inici de l'estudi i el treball que l'estudiant ha de continuar i aprofundir pel seu compte.

2. Es proporciona el màxim de materials de qualitat (apunts, exercicis resolts, exercicis per fer, referències bibliogràfiques).

3. S'aprofiten al màxim les classes per a fomentar la motivació de l'estudiant (amb exemples, debats, comentaris, etc.) i es transmet l'enfocament i les intuïcions darrere les definicions, propietats i tècniques tractades.

Al voltant de la setmana 7 del quadrimestre es farà un parcial d'uns 90 minuts de duració, sobre els dos temes de lògica proposicional, amb un pes del 40% de la nota total.

L'examen final, a celebrar a l'epoca de exàmens, tindrà dues parts: recuperació dels dos temes de lògica proposicional (40% de la nota final) i els temes de lògica de primer ordre i programació lògica (60%). Tot estudiant pot decidir lliurement si es presenta o no a la part de recuperació, i se li comptarà la nota màxima entre la nota d'aquesta part i el parcial, és a dir, inclús si té una nota molt alta, no corre el risc de perdre-la.

Els exàmens constaran de preguntes de comprensió dels conceptes, de demostració de propietats, d'aplicació de les tècniques de deducció, i de resolució de problemes Prolog.

Qualsevol intent de frau realitzat durant el curs comportarà l'aplicació de la normativa acadèmica general de la UPC i l'inici d'un procés disciplinari.

• 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ó a la programació i a la programació recursiva.