Programa
Unidad I
Proposiciones y funciones proposicionales, constantes lógicas, negación, disyunción, conjunción, disyunción excluyente, condicional, implicación, bicondicional, equivalencia. Álgebra proposicional. Teorema de representación y completitud de juegos, las funciones de Scheffer y de Peirce. Descomposiciones canónicas, formas normales disyuntivas y conjuntivas. Circuitos y compuertas AND, OR, NOT, NAND, NOR, XOR. Cuantificación y predicados. Definición axiomática de un álgebra de Boole y realizaciones, isomorfismo con el
álgebra proposicional y de conjuntos. Propiedades básicas (acotación, asociatividad, involución, idempotencia, De Morgan, absorción). Relación de orden inducida en un álgebra de Boole, átomos, orden parcial, orden total
y buen orden, subálgebras de Boole. Representaciones de relaciones de orden: diagramas de Hasse. Elementos maximales, minimales, cotas, máximos, mínimos. Isomorfismos entre álgebras de Boole y preservación de elementos. Circuitos y juegos completos. Relaciones binarias en un conjunto, propiedades básicas y clausuras. Álgebra de relaciones y preservación de propiedades. Relaciones de equivalencia y partición en clases de equivalencia, conjunto cociente, autómatas. Representación gráfica de las relaciones y matriciales, relaciones entre propiedades y operaciones matriciales
Unidad II
El principio de inducción matemática, forma débil y fuerte. Equivalencia entre el buen orden y las dos formas del principio. Recurrencia y ecuaciones de recurrencia. Ecuaciones de recurrencia de primer orden con coeficientes variables, lineales o reducibles, existencia y unicidad de problemas de valor inicial. Ecuaciones de recurrencia de orden superior, lineales con coeficientes constantes, ecuaciones homogéneas e independencia lineal de soluciones, matriz de Casorati. La solución general de las ecuaciones completas. Sistemas de ecuaciones lineales de primer orden. Soluciones de equilibrio y nociones de comportamiento cualitativo y convergencia de soluciones, su relación con los coeficientes.Unidad III
Grafos, definiciones, vértices, aristas, orden, tamaño, adyacencia, lazos, aristas múltiples, arcos, caminos, recorridos, circuitos, ciclos, caminos simples, orden, tamaño, grado, sucesión gráfica, subgrafos, el ‘handshaking lemma’. Representaciones de un grafo: gráfica y matricial (adyacencia, incidencia). Métrica inducida y excentricidad, centro, periferia, radio, diámetro. Regularidad, complementos, grafos particulares: nulo, cadena, ciclo, completos, bipartitos, estrellas, ruedas, k-partitos, autocomplementarios, planares, árboles. Conexidad, componentes conexas. La relación de equivalencia isomorfismo, sus clases de equivalencia y la retención de invariantes. Operaciones. Independencia y cubrimiento. Árboles binarios. Árbol generador de longitud mínima con métricas ponderadas, algoritmos de Kruskal y de Prim. Grafos eulerianos, condiciones necesarias y suficientes. Grafos hamiltonianos, algunas condiciones suficientes (Dirac, Ore). Grafo arista. Coloración y planaridad. Grafos orientados, definiciones, conexidad, grafos orientados eulerianos y hamiltonianos. Conectividad, cortes, flujos y la minimización de longitudes ponderadas en grafos orientados y maximización de flujos en redes.