Elementos de matemática discreta con aplicaciones a las Ciencias de la Computación / Malva Alberto de Toso, Ingrid Schwer de Inglese, Viviana del Carmen Cámara, Cristina Rogiano, Silvina Meinero.

CONTENIDO
1 Logica Proposicional
1.1 Proposiciones 15
1.2 Tablas de verdad y conectivos lógicos 16
1.2.1 Negación 16
1.2.2 Conjunción 16
1.2.3 Disyunción 17
1.2.4 Implicación 18
1.2.5 Equivalencia o Bicondicional 19
1.3 Generando nuevas proposiciones 20
1.4 Tautología, contradicción y contingencia 23
1.5 Implicaciones y equivalencias lógicas 24
1.5.1 Implicaciones asociadas 26
1.6 Las proposiciones duales 28
Conectivos adecuados 31
1.7 Redes de conmutación 32
1.8 Expresiones Relacionales y Cuantificadores 37
1.8.1 El dominio de las variables en las funciones proposicionales 38
1.8.2 ¿Cómo se obtienen proposiciones a partir de funciones proposicionales? 38
1.8.3 Negación de expresiones relacionales cuantificadas 42
1.8.4 Expresiones que contienen más de un cuantificador 43
1.9 Las expresiones relacionales en los algoritmos 47
1.9.1 Algoritmos 47
1.9.2 Variables e instrucciones 47
1.9.3 Operaciones entrada/salida 49
1.9.4 Operadores lógicos 52
1.9.5 Estructuras de control 53
1.10 Problemas complementarios 64
1.11 Ejercicios de opción múltiple 67
2 Combinatoria
2.1 Introducción 69
2.2 Reglas de la suma y el producto 69
2.3 Cadenas de símbolos. Alfabetos 77
2.4 Permutaciones 85
2.5 Permutaciones con repetición 90
2.6 Combinaciones 91
2.7 Otros problemas resueltos 92
2.8 Permutaciones generalizadas 93
2.9 Coeficientes binomiales 99
2.9.1 Una aplicación del Teorema Binomial 100
2.9.2 El Triángulo de Tartaglia 101
2.9.3 Cálculos usuales con los números combinatorios 102
2.9.4 Propiedades de los números combinatorios 103
2.10 Inducción 106
2.10.1 La inducción en los algoritmos 112
2.11 Lectura complementaria 116
2.11.1 Burbujas 117
2.11.2 Selección 118
2.11.3 Inserción 120
2.12 Problemas complementarios 122
2.13 Ejercicios de opción múltiple 124
3 Relaciones y Funciones
3.1 Introducción 125
3.2 Productos cartesianos y relaciones 125
3.3 Propiedades de las relaciones binarias 132
3.4 Matrices y relaciones 139
3.4.1 Composición de relaciones 140
3.4.2 Matrices y composición 141
3.5 Relaciones de recurrencia 146
3.6 Relaciones funcionales o funciones 156
3.6.1 Composición de funciones 158
3.6.2 Funciones usuales en lenguajes de programación 159
3.7 Lectura complementaria 164
3.8 Problemas complementarios 169
3.9 Ejercicios de opción múltiple 173
4 Estructuras Algebraicas Finitas
4.1 Introducción 175
4.2 Leyes de composición interna 175
4.3 Propiedades de una ley de composición interna 177
4.4 Estructuras algebraicas 181
4.5 Grupos 183
4.6 Grupos finitos 187
4.7 Homomorfismos de grupos (morfismos de grupos) 189
4.8 Subgrupos 195
4.9 Congruencias 198
4.10 Teoría de códigos 205
4.10.1 ¿Qué es un código? 205
4.10.2 La métrica de Hamming 208
4.10.3 Códigos de grupos 210
4.11 Decodificación y corrección de errores 215
4.11.1 Técnica de máxima verosimilitud 215
4.11.2 Líderes y coclases para decodificar 216
4.11.3 Síndromes y líderes para decodificar 217
Problemas complementarios 221
Ejercicios de opción múltiple 223
5 Algebras de Boole
5.1 Definiciones y ejemplos 225
5.2 Propiedades y simplificaciones 232
5.3 Subalgebras booleanas y morfismos 235
5.4 Algebras de Boole finitas 237
5.5 Funciones y expresiones booleanas 238
5.6 Problemas Complementarios 249
5.7 Ejercicios de opción múltiple 250
6 Digrafos y Grafos
6.1 Primeros problemas y ejemplos 253
6.1.1 Introducción 253
6.1.2 Ejemplos 254
6.2 Digrafos 261
6.3 Subdigrafos y digrafos parciales 265
6.4 Relaciones binarias y digrafos 268
6.5 Matrices y digrafos
6.5.1 Matriz de adyacencia 269
6.5.2 Suma y Producto de dígrafos 270
6.6 Grafos 274
6.6.1 Nueva terminología 274
6.6.2 Grafos y matrices 277
6.6.3 Grafos especiales 279
6.7 Arboles 286
6.8 Arboles con raíz Y definiciones recursivas 292
6.8.1 Los árboles como estructuras ordenadas 294
6.8.2 Arboles binarios 297
6.8.3 Recorrido de árboles binarios 298
6.8.4 Los árboles como estructuras etiquetadas 300
6.9 Problemas complementarios 305
6.10 Ejercicios de opción múltiple 309
7 Aplicaciones
7.1 Justificación 311
7.2 Relaciones de recurrencia y funciones generatrices 311
7.2.1 Relaciones de recurrencia no homogéneas - Método de coeficientes indeterminados 311
7.2.2 Aplicaciones 312
7.2.3 Funciones generatrices 314
7.2.4 El método de las funciones generatrices 316
7.3 Número de divisiones que requiere el algoritmo de Euclides 317
7.3.1 El algoritmo de Euclides 317
7.3.2 Los números de Fibonacci 318
7.3.3 El teorema de Gabriel Lamé 319
7.3.4 El peor caso 320
7.3.5 Teorema de Lamé 320
Respuestas y sugerencias 323
Bibliografía 355