Matemáticas discretas

Portada Acerca del autor Agradecimientos Contenido Prólogo Parte I - Fundamentos CAPÍTULO 1 - Lógica y conjuntos 1.1 Introducción 1.2 Proposiciones y conectivos lógicos 1.3 Implicación y equivalencia lógica 1.4 Reglas de inferencia 1.5 Conjuntos 1.6 Predicados y cuantificadores 1.7 Operaciones con conjuntos 1.8 Resumen 1.9 Ejercicios CAPÍTULO 2 - Los enteros 2.1 Introducción 2.2 Axiomas de los números enteros 2.3 Orden en los enteros 2.4 Método de inducción matemática 2.5 El principio del buen orden 2.6 Resumen 2.7 Ejercicios CAPÍTULO 3 - Divisibilidad 3.1 Introducción 3.2 Divisibilidad 3.3 Aplicación: cambio de base 3.4 Números primos 3.5 Máximo común divisor 3.6 El teorema fundamental de la aritmética 3.7 Resumen 3.8 Ejercicios CAPÍTULO 4 - Funciones 4.1 Introducción 4.2 Producto cartesiano 4.3 Funciones 4.4 Funciones biyectivas 4.5 Composición de funciones 4.6 Conjuntos finitos 4.7 El principio de la pichonera 4.8 Conjuntos infinitos 4.9 Operaciones binarias 4.10 Resumen 4.11 Ejercicios CAPÍTULO 5 - Relaciones binarias 5.1 Introducción 5.2 Tipos de relaciones binarias 5.3 Relaciones de equivalencia 5.4 La matriz de una relación 5.6 Ejercicios Parte II - Métodos algebraicos CAPÍTULO 6 - Retículos y álgebras booleanas 6.1 Introducción 6.2 Relaciones de orden 6.3 Retículos 6.4 Álgebras booleanas 6.5 Orden en álgebras booleanas 6.6 Expresiones y funciones booleanas 6.7 Simplifi cación de expresiones booleanas 6.8 Aplicación: circuitos lógicos 6.9 Resumen 6.10 Ejercicios CAPÍTULO 7 - Computabilidad y complejidad computacional 7.1 Introducción 7.2 Funciones recursivas 7.3 Máquinas de Turing 7.4 Complejidad computacional 7.5 Problemas NP-completos 7.6 Resumen 7.7 Ejercicios CAPÍTULO 8 - Aritmética modular 8.1 Introducción 8.2 Congruencias 8.3 Aplicación: calendario perpetuo 8.4 El teorema chino del residuo 8.5 El teorema de Euler 8.6 El criptosistema RSA 8.7. Los enteros módulo m 8.8 Resumen 8.9 Ejercicios CAPÍTULO 9 - Grupos 9.1 Introducción 9.2 Semigrupos y monoides 9.3 Grupos 9.4 Propiedades de grupos 9.5 Subgrupos 9.6 Códigos de grupo 9.7 Homomorfi smos 9.8 Grupos cíclicos 9.9 El teorema de Lagrange 9.10 Resumen 9.11 Ejercicios CAPÍTULO 10 - Anillos, campos y poligonos 10.1 Introducción 10.2 Anillos 10.3 Campos 10.4 Polinomios 10.5 Divisibilidad 10.6 Máximo común divisor 10.7 Polinomios irreducibles 10.8 Construcción de campos finitos 10.9 Resumen 10.10 Ejercicios Parte III - Enumeración combinatoria CAPÍTULO 11 - Conteo 11.1 Introducción 11.2 Permutaciones y combinaciones 11.3 Teorema del binomio 11.4 Coeficientes multinomiales 11.5 Ecuaciones lineales diofantinas 11.6 Espacios finitos de probabilidad 11.7 Resumen 11.8 Ejercicios CAPÍTULO 12 - El principio de inclusión - exclusión 12.1 Introducción 12.2 El principio de inclusión-exclusión 12.3 Aplicaciones especiales 12.4 Extensión del principio 12.5 Resumen 12.6 Ejercicios CAPÍTULO 13 - Funciones generadoras 13.1 Introducción 13.2 Series de potencias formales 13.3 Funciones generadoras ordinarias 13.4 Particiones de enteros 13.5 Funciones generadoras exponenciales 13.6 Funciones generadoras de probabilidad 13.7 Resumen 13.8 Ejercicios CAPÍTULO 14 - Relaciones de recurrencia 14.1 Introducción 14.2 Recurrencias lineales de orden uno 14.3 Recurrencias lineales homogéneas de orden dos 14.4 Solución con funciones generadoras 14.5 Resumen 14.6 Ejercicios Parte IV - Teoría de grafos CAPÍTULO 15 - Grafos 15.1 Introducción 15.2 Grafos y subgrafos 15.3 Caminos y grafos conexos 15.4 Grafos isomorfos 15.5 Paseos eulerianos 15.6 Resumen 15.7 Ejercicios CAPÍTULO 16 - Árboles 16.1 Introducción 16.2 Propiedades de árboles 16.3 Árboles con raíz 16.4 Contando árboles 16.5 Árboles de búsqueda 16.6 Árbol de recubrimiento mínimo 16.7 Resumen 16.8 Ejercicios CAPÍTULO 17 - Grafos dirigidos 17.1 Introducción 17.2 Grafos dirigidos 17.3 Grafos orientados y torneos 17.4 Cerradura transitiva 17.5 El problema de la ruta más corta 17.6 Flujo máximo en una red 17.7 Resumen 17.8 Ejercicios CAPÍTULO 18 - Temas selectos de grafos 18.1 Introducción 18.2 Ciclos hamiltonianos 18.3 Emparejamientos 18.4 Grafos aplanables 18.5 Coloración de vértices 18.6 El problema de los cuatro colores 18.7 Resumen 18.8 Ejercicios Bibliografía Índice analítico