Matemática discreta / Malva Alberto de Toso ... [et al.].

CONTENIDO
Capítulo 1. Lógica Proposicional
1 .1 Introducción 13
1.2 El lenguaje 14
1.3 Sintaxis 16
1.4 Semántica 18
1.4.1 Informalmente 19
1.4.2 Interpretaciones 27
1.4.3 Modelos. Fórmulas satisfacibles. Fórmulas tautológicas 31
1.4.4 La implicación y la consecuencia lógicas 37
1.4.5 La equivalencia lógica 40
1.4.6 Síntesis semántica 43
1.4.7 Conectivos adecuados 45
1.5 Convenciones para simplificar la notación 46
1.6 Redes de conmutación 48
1.7 Predicados, Relaciones y Cuantificadores. Primer acercamiento a la LPO 53
1.7.1 El dominio de las variables 55
1.7.2 ¿Cómo se obtienen proposiciones? 55
1.7.3 Negación de expresiones relacionales cuantificadas 59
1.7.4 Expresiones que contienen más de un cuantificador 59
1.7.5 Formas implícitas de los cuantificadores 62
1.7.6 Los dominios finitos. Interpretaciones para cuantificadores 62
1.8 Las expresiones relacionales en los algoritmos 63
1.8.1 Algoritmo 63
1.8.2 Variables e instrucciones 64
1.8.3 Operaciones entrada/salida 66
1.8.4 Operadores aritméticos 69
1.8.5 Operadores lógicos 70
1.8.6 Operadores relacionales 71
1.8.7 Estructuras de control 73
1.9 Reglas de inferencia de la LPC 86
1.9.1 Modus Ponens 88
1.9.2 Modus Tollens 88
1.9.3 Silogismo hipotético 89
1.9.4 Silogismo disyuntivo 90
1.9.5 Dilema constructivo 90
1.9.6 Regla de contradicción 91
1.9.7 Dilema destructivo 91
1.9.8 Prueba formal 91
1.10.1 Método directo 98
1.10.2 Método por contraposición 99
1.10.3 Método por reducción al absurdo 101
Capítulo 2. Teoría del Conteo
2.1 Introducción 111
2.2 Reglas de la suma y el producto 112
2.2.1 Generalización de la regla de la suma 113
2.2.2 Generalización de la regla del producto 114
2.3 Cadenas de símbolos. Alfabetos 120
2.4 Permutaciones 130
2.4.1 La Función Factorial 133
2.5 Permutaciones con repetición 134
2.6 Combinaciones 136
2.8 Permutaciones generalizadas 139
2.9 Coeficientes binomiales 144
2.9.1 Una aplicación del Teorema Binomial 146
2.9.2 El Triángulo de Tartaglia 147
2.9.3 Cálculos usuales con los números combinatorios 150
2.9.4 Propiedades de los números combinatorios 152
2.10 Combinaciones con repetición 154
2.11.1 Burbujas 161
2.11.2 Selección 163
2.11.3 Inserción 164
Capítulo 3. Teoría de Números e Inducción
3.1 Introducción 173
3.2 El anillo de los enteros 174
3.3 Divisibilidad y divisores 176
3.4 El máximo común divisor y el mínimo común múltiplo 186
3.5 Primos relativos. Teorema fundamental de la aritmética 199
3.6 Relaciones binarias en los enteros. La congruencia entera 202
3.7 Ecuaciones lineales en congruencias 208
3.8 Inducción 212
3.9 La inducción en los algoritmos 222
Capítulo 4. Relaciones de Recurrencia
4.1 Introducción 237
4.2 Sucesiones 237
4.3 Relaciones de recurrencia 238
4.3.1 Relaciones de recurrencia lineales homogéneas con coeficientes constantes 245
4.3.2 Relaciones de recurrencia lineales no homogéneas con coeficientes constantes 249
4.4 Generación de números (pseudo) aleatorios 258
4.4.1 Método de los cuadrados centrales de Von Neumann 259
4.4.2 Método congruencial lineal 261
4.5.1 Funciones recursivas 265
4.5.2 Los números de Fibonacci y el algoritmo de Euclides 271
4.5.3 La razón divina: "El número de oro" 275
Capítulo 5. Estructuras Algebraicas Finitas
5.1 Introducción 283
5.2 Leyes de composición interna 284
5.3 Propiedades de una ley de composición interna 288
5.4 Estructuras algebraicas 293
5.5 Grupos 295
5.6 Grupos finitos 300
5.7 Homomorfismos de grupos 302
5.8 Subgrupos 310
5.9 Congruencias 314
5.10 Anillos 321
5.11 Anillos finitos 324
5.12 Algebras de Boole: definiciones y ejemplos 328
5.13 Propiedades y simplificaciones 335
5.14 Subálgebras booleanas y morfismos 340
5.15 Algebras de Boole finitas 342
5.16 Funciones y expresiones booleanas 343
5.17.1 ¿Qué es un código? 356
5.17.2 La métrica de Hamming 360
5.17.3 Códigos de grupos 362
5.17.4 Decodificación y corrección de errores 367
5.17.5 Síndromes y líderes para decodificar 370
Capítulo 6. Digrafos y Grafos
6.1 Introducción 381
6.2 Primeros problemas y ejemplos 381
6.3 Digrafos 389
6.4 Subdigrafos y digrafos parciales 395
6.5 Relaciones binarias y digrafos 397
6.6 Matrices y digrafos 401
6.6.1 Matriz de adyacencia 401
6.6.2 Suma y Producto de digrafos 402
6.7 Grafos 409
6.7.1 Nueva terminología 409
6.7.2 Grafos y matrices 413
6.7.3 Grafos Especiales 417
6.8 Arboles 425
6.9 Arboles con raíz y definiciones recursivas 432
6.9.1 Los árboles como estructuras ordenadas 434
6.9.2 Arboles binarios 437
6.9.3 Recorrido de árboles binarios 439
6.9.4 Los árboles como estructuras etiquetadas 441
6.10 Arboles de refutación de una fórmula de la LPC 446
Capítulo 7. Autómatas Finitos
7.1 Introducción 473
7.2 Máquinas de estados finitos 473
7.2.1 Definiciones, representaciones y ejemplos 477
7.2.2 La máquina reconocedora de sucesiones 481
7.2.3 El sumador binario 482
7.3 Autómatas finitos 486
7.4 Máquinas de estados finitos equivalentes 490
Capítulo 8. Lógica de Primer Orden
8.1 Introducción 501
8.2 Sintaxis 502
8.2.1 Lenguajes de Primer Orden 502
8.2.2 Términos 504
8.2.3 Fórmulas 506
8.2.4 Cuantificadores Existencial y Universal 508
8.2.5 Variables libres y ligadas 509
8.2.6 Sustituciones 513
8.3 Semántica 516
8.3.1 Interpretaciones de fórmulas en lenguajes de primer orden 516
8.3.2 Conceptos semánticos básicos. Satisfacibilidad. Validez. Consecuencia y Equivalencia lógicas 521
8.3.3 Restricciones de los cuantificadores Existencial y Universal a colecciones de grupos y objetos 531
Respuestas y Sugerencias 541
Bibliografía 601