Matemática discreta con aplicaciones a las Ciencias de la Programación y de la Computación / Malva Alberto de Toso ... [y otros]

CONTENIDO
Capítulo 1. Lógica Proposicional
1.1 Introducción 17
1.2 Proposiciones 17
1.3 Tablas de verdad y conectivos lógicos 19
1.3.1 Negación 19
1.3.2 Conjunción 19
1.3.3 Disyunción 20
1.3.4 Implicación 21
1.3.5 Equivalencia o bicondicional 22
1.4 Generando nuevas proposiciones 23
1.5 Tautología, contradicción y contingencia 27
1.6 Implicaciones y equivalencias lógicas 29
1.6.1 Implicaciones asociadas 31
1.7 Las proposiciones duales 34
1.7.1 Conectivos adecuados 37
1.8 Redes de conmutación 38
1.9 Expresiones relacionales y cuantificadores 44
1.9.1 El dominio de las variables en las Funciones Proposicionales 46
1.9.2 ¿Cómo se obtienen proposiciones a partir de Funciones Proposicionales? 46
1.9.3 Negación de expresiones relacionales cuantificadas 51
1.9.4 Expresiones que contienen más de un cuantificador 52
1.9.5 Formas implícitas de los cuantificadores 55
1.9.6 Los dominios finitos. Interpretaciones para los cuantificadores 55
1.10 Lectura complementaria 56
1.10.1 Algoritmo 56
1.10.2 Variables e instrucciones 57
1.10.3 Operaciones entrada/salida 60
1.10.4 Operadores aritméticos 62
1.10.5 Operadores lógicos 64
1.10.6 Operadores relacionales 64
1.10.7 Reglas de precedencia 65
1.10.8 Los operadores div y mod en los algoritmos 65
1.10.9 Estructuras de control 67
1.11 Problemas complementarios 81
1.12 Ejercicios de opción múltiple 84
Capítulo 2. Teoría del Conteo
2.1 Introducción 87
2.2 Reglas de la suma y el producto 88
2.3 Cadenas de símbolos. Alfabetos 97
2.4 Permutaciones 106
2.5 Permutaciones con repetición 111
2.6 Combinaciones 112
2.7 Otros problemas resueltos 114
2.8 Permutaciones generalizadas 116
2.9 Coeficientes binomiales 121
2.9.1 Una aplicación del Teorema Binomial 123
2.9.2 El Triángulo de Tartaglia 124
2.9.3 Cálculos usuales con los números combinatorios 125
2.9.4 Propiedades de los números combinatorios 127
2.10 Combinaciones con repetición 129
2.11 Lectura complementaria 136
2.11.1 Burbujas 137
2.11.2 Selección 139
2.11.3 Inserción 140
2.12 Problemas complementarios 143
2.13 Ejercicios de opción múltiple 145
Capítulo 3. Teoría de Números e Inducción
3.1 Introducción 147
3.2 El anillo de los enteros 148
3.3 Divisibilidad y divisores 150
3.4 Relaciones binarias en los enteros 160
3.5 El máximo común divisor y el mínimo común múltiplo 162
3.6 Primos relativos. Teorema fundamental de la aritmética 170
3.7 Inducción 174
3.8 La inducción en los algoritmos 180
3.9 Lectura complementaria 187
3.10 Problemas complementarios 191
3.11 Ejercicios de opción múltiple 193
Capítulo 4. Relaciones de Recurrencia
4.1 Introducción 195
4.2 Sucesiones recursivas 195
4.3 Relaciones de recurrencia 199
4.3.1 Relaciones de recurrencia lineales homogéneas con coeficientes constantes 202
4.3.2 Relaciones de recurrencia lineales no homogéneas con coeficientes constantes 205
4.4 Generación de números aleatorios 214
4.4.1 Método de los cuadrados centrales de Von Neumann 215
4.4.2 Método congruencial lineal 216
4.5 Lecturas complementarias 220
4.5.1 Funciones recursivas 220
4.5.2 Los números de Fibonacci y el algoritmo de Euclides 226
4.6 Problemas complementarios 230
4.7 Ejercicios de opción múltiple 235
Capítulo 5. Estructuras Algebraicas Finitas
5.1 Introducción 237
5.2 Leyes de composición interna 238
5.3 Propiedades de una ley de composición interna 243
5.4 Estructuras algebraicas 247
5.5 Grupos 249
5.6 Grupos finitos 253
5.7 Homomorfismos de grupos 257
5.8 Subgrupos 263
5.9 Congruencias 267
5.10 Anillos 274
5.11 Anillos finitos 277
5.12 Álgebras de Boole: definiciones y ejemplos 280
5.13 Propiedades y simplificaciones 288
5.14 Subálgebras booleanas y morfismos 292
5.15 Álgebras de Boole finitas 294
5.16 Funciones y expresiones booleanas 295
5.17 Lectura complementaria 307
5.17.1 ¿Qué es un código? 307
5.17.2 La métrica de Hamming 311
5.17.3 Códigos de grupos 313
5.17.4 Decodificación y corrección de errores 318
5.18 Problemas complementarios 325
5.19 Ejercicios de opción múltiple 328
Capítulo 6. Digrafos y Grafos
6.1 Introducción 331
6.2 Primeros problemas y ejemplos 332
6.3 Dígrafos 340
6.4 Subdigrafos y digrafos parciales 346
6.5 Relaciones binarias y dígrafos 348
6.6 Matrices y dígrafos 352
6.6.1 Matriz de adyacencia 352
6.6.2 Suma y Producto de dígrafos 353
6.7 Grafos 360
6.7.1 Nueva terminología 360
6.7.2 Grafos y matrices 364
6.7.3 Grafos especiales 368
6.8 Árboles 377
6.9 Árboles con raíz y definiciones recursivas 384
6.9.1 Los árboles como estructuras ordenadas 386
6.9.2 Árboles binarios 389
6.9.3 Recorrido de árboles binarios 392
6.9.4 Los árboles como estructuras etiquetadas 394
6.10 Lectura complementaria 399
6.11 Problemas complementarios 403
6.12 Ejercicios de opción múltiple 407
Capítulo 7. Autómatas finitos
7.1 Introducción 409
7.2 Máquinas de estados finitos 409
7.2.1 Definiciones, representaciones y ejemplos 411
7.2.2 La máquina reconocedora de sucesiones 417
7.2.3 El sumador binario 419
7.3 Autómatas finitos 423
7.3.1 Representaciones 424
7.4 Máquinas de estados finitos equivalentes 426
7.5 Problemas complementarios 434
7.6 Ejercicios de opción múltiple 435
Respuestas y Sugerencias
Bibliografía