1. Lògica de proposicions.
1.1. Proposicions. Connectors lògics. Taules de veritat associades.
1.2. Fórmules del càlcul proposicional.
1.3. Formalització de proposicions.
1.4. Tautologies i contradiccions. Implicacions i equivalències en el càlcul de proposicions.
2. Lògica de predicats.
2.1. Definicions bàsiques: conjunt, element, pertinença, inclusió, funció, operacions amb conjunts, producte cartesià entre conjunts.
2.2. Predicats. Quantificadors: universal i existencial.
2.3. Fórmules del càlcul de predicats.
2.4. Formalització de proposicions en el càlcul de predicats.
2.5. El predicat igualtat. Formalització de proposicions utilitzant el predicat igualtat.
2.6. Fórmules vàlides, invàlides, satisfactibles i insatisfactibles. Implicacions i equivalències en el càlcul de predicats.
3. Inferència lògica.
3.1. Inferència lògica. La demostració directa. La demostració per reducció a l’absurd. Regles d’inferència.
3.2. Formes conjuntives i disjuntives d’una fórmula.
3.3. Forma normal de Skolem.
3.4. La demostració automàtica: el mètode de resolució lineal.
3.5. Contraexemples. Cerca de contraexemples.
3.6. El mètode de demostració per inducció.
4. Conjunts i combinatòria.
4.1. Producte cartesià entre conjunts.
4.2. Relacions binàries. Relacions d'equivalència i relacions d'ordre.
4.3. El cardinal d’un conjunt.
4.4. Variacions i permutacions amb i sense repetició.
4.5. Combinacions amb i sense repetició.
4.6. Els coeficients binomials: significat i algunes propietats.
4.7. Principi d'inclusió-exclusió. Desarranjaments.
5. Introducció als grafs.
5.1. Conceptes bàsics sobre grafs i propietats.
5.2. Tipus especials de grafs.
5.3. Isomorfisme de grafs.
5.4. Subestructures de grafs.
5.5. Seqüència de graus d'un graf.
5.6. Connexió i components.
5.7. Grafs plans.
5.8. Coloració d'un graf.
5.9. Emmagatzematge d'un graf en memòria. Matriu d’adjacència, llista d’adjacències.
6. Recorreguts i camins mínims.
6.1. Recorregut d'un graf. Recorregut en profunditat. Recorregut en amplada.
6.2. Camins mínims. Algorisme de Dijkstra. Algorisme de Bellman-Ford.
7. Arbres generadors.
7.1. Conceptes generals.
7.2. Arbres dirigits amb arrel.
7.3. Arbres generadors minimals. Algorisme de Kruskal. Algorisme de Prim.
8. Grafs eulerians i hamiltonians.
8.1. Caracterització dels camins i dels circuits eulerians. Algorisme de Hierholzer.
8.2. Problema del carter xinès. Algorisme d'Edmonds.
8.3. Caracterització dels camins i dels circuits hamiltonians. Algorisme de Roberts i Flores.
Exercicis: Els exercicis només es podran lliurar una vegada i no es podran recuperar.
Pràctiques: Assistència (5%), pràctica final (10%)
Per a les activitats recuperables s'ha de tenir en compte que quan la nota de recuperació d'una part sigui superior a l'anterior, es prendrà aquesta com a nota definitiva de la part. En cas contrari, es prendrà com a nota definitiva la mitjana de les notes dels dos exàmens de la part.
Criteris específics de la nota «No Presentat»:
L'alumne se'l considerarà No Presentat si no es presenta a cap de les següents activitats: Examen Lògica, Examen Combinatòria i Grafs.
Avaluació única:
L'avaluació única consistirà en:
• Examen final, 85% de la nota (40% Lògica, 45% Grafs i Combinatòria)
• Examen de pràctiques, 15% de la nota.
L'examen final serà recuperable en la data fixada en el calendari d’exàmens.
Requisits mínims per aprovar:
Per considerar superada l’assignatura, caldrà obtenir una qualificació global mínima de 5.0. Ara bé, es necessitarà un mínim de 3 en la nota de l'examen de Lògica i un mínim de 3 en la nota de l'examen de Combinatòria i Grafs per poder aprovar l'assignatura. En cas que alguna d'aquestes dues notes sigui inferior a 3 la nota màxima de l'assignatura serà de 4.5