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, Silvina Meinero.

CONTENIDO
1 Lógica Proposicional
1.1 Introducción 15
1.2 Proposiciones 15
1.3 Tablas de verdad y conectivos lógicos 16
1.3.1 Negación 16
1.3.2 Conjunción 17
1.3.3 Disyunción 17
1.3.4 Implicación 18
1.3.5 Equivalencia o Bicondicional 19
1.4 Generando nuevas proposiciones 20
1.5 Tautología, contradicción y contingencia 23
1.6 Implicaciones y equivalencias lógicas 25
1.6.1 Implicaciones asociadas 27
1.7 Las proposiciones duales 29
1.7.1 Conectivos adecuados 32
1.8 Redes de conmutación 33
1.9 Expresiones Relacionales y Cuantificadores 38
1.9.1 El dominio de las variables en las Funciones Proposicionales 39
1.9.2 ¿Cómo se obtienen proposiciones a partir de Funciones Proposicionales? 39
1.9.3 Negación de expresiones relacionales cuantificadas 43
1.9.4 Expresiones que contienen más de un cuantificador 44
1.9.5 Formas implícitas de los cuantificadores 47
1.9.6 Los dominios finitos. Interpretaciones para los cuantificadores 47
1.10 Lectura complementaria: Las expresiones relacionales en los algoritmos 48
1.10.1 Algoritmo 48
1.10.2 Variables e instrucciones 49
1.10.3 Operaciones entrada/salida 51
1.10.4 Operadores aritméticos 53
1.10.5 Operadores lógicos 55
1.10.6 Operadores relacionales 55
1.10.7 Reglas de precedencia 56
1.10.8 Lo operadores div y mod en los algoritmos 56
1.10.9 Estructuras de control 57
1.11 Problemas complementarios 70
1.12 Ejercicios de opción múltiple 74
2 Combinatoria
2.1 Introducción 75
2.2 Reglas de la suma y el producto 76
2.3 Cadenas de símbolos. Alfabetos 83
2.4 Permutaciones 91
2.5 Permutaciones con repetición 95
2.6 Combinaciones 96
2.7 Otros problemas resueltos 97
2.8 Permutaciones generalizadas 98
2.9 Coeficientes binomiales 104
2.9.1 Una aplicación del Teorema Binomial 105
2.9.2 El Triángulo de Tartaglia 106
2.9.3 Cálculos usuales con los números combinatorios 107
2.9.4 Propiedades de los números combinatorios 108
2.10 Combinaciones con repetición 111
2.11 Lectura complementaria 116
2.11.1 Burbujas 117
2.11.2 Selección 118
2.11.3 Inserción 119
2.12 Problemas complementarios 122
2.13 Ejercicios de opción múltiple 123
3 Teoría de Números
3.1 Introducción 125
3.2 El anillo de los en enteros 125
3.3 Divisibilidad y divisores 126
3.4 Relaciones binarias en los enteros 132
3.5 El máximo común divisor y el mínimo común múltiplo 134
3.6 Primos relativos. Teorema fundamental de la arimética 140
3.7 Inducción 143
3.8 La inducción en los algoritmos 148
3.9 Lectura complementaria 152
3.10 Problemas complementarios 155
3.11 Ejercicios de opción múltiple 156
4 Relaciones de recurrencia y números aleatorios
4.1 Introducción 159
4.2 Sucesiones recursivas 159
4.3 Relaciones de recurrencia 162
4.3.1 Relaciones de recurrencia lineales homogéneas con coeficientes constantes 165
4.3.2 Relaciones de recurrencia lineales no homogéneas con coeficientes constantes 167
4.4 Generación de números aleatorios 173
4.4.1 Método de los cuadrados centrales de Von Neumann 174
4.4.2 Método congruencial lineal 175
4.5 Lecturas complementarias 178
4.5.1 Funciones recursivas 178
4.5.2 Los números de Fibonacci y el algoritmo de Euclides 184
4.6 Problemas complementarios 188
4.7 Ejercicios de opción múltiple 191
5 Estructuras Algebraicas Finitas
5.1 Introducción 193
5.2 Leyes de composición interna 194
5.3 Propiedades de una ley de composición interna 197
5.4 Estructuras algebraicas 201
5.5 Grupos y anillos finitos 209
5.6 Álgebras de Boole: definiciones y ejemplos 216
5.7 Propiedades y simplificaciones 222
5.8 Subálgebras booleanas y morfismos 226
5.9 Álgebras de Boole finitas 228
5.10 Funciones y expresiones booleanas 229
5.11 Lectura complementaria 239
5.12 Problemas complementarios 252
5.13 Ejercicios de opción múltiple 254
6 Digrafos y Grafos
6.1 Introducción 267
6.2 Primeros ejemplos 267
6.3 Dígrafos 274
6.4 Subdigrafos y digrafos parciales 279
6.5 Relaciones binarias y digrafos 281
6.6 Matrices y digrafos 282
6.6.1 Matriz de adyacencia 282
6.6.2 Suma y Producto de dígrafos 283
6.7 Grafos 287
6.7.1 Nueva terminología 287
6.7.2 Grafos y matrices 290
6.7.3 Grafos especiales 293
6.8 Árboles 300
6.9 Árboles con raíz y definiciones recursivas 306
6.9.1 Los árboles como estructuras ordenadas 309
6.9.2 Árboles binarios 311
6.9.3 Recorrido de árboles binarios 314
6.9.4 Los árboles como estructuras etiquetadas 316
6.9.5 Árboles trie 317
6.10 Problemas complementarios 322
6.11 Ejercicios de opción múltiple 325
7 Introducción a los autómatas finitos
7.1 Introducción 327
7.2 Máquinas de estados finitos 327
7.3 Definiciones, representaciones y ejemplos 328
7.3.1 Representaciones y ejemplos 329
7.3.2 La máquina reconocedora de sucesiones 334
7.3.3 El sumador binario 335
7.4 Autómatas finitos 338
7.4.1 Representaciones 339
7.5 Máquinas de estados finitos equivalentes 341
7.6 Problemas complementarios 347
7.7 Ejercicios de opción múltiple 348
Apéndice Relaciones y Funciones
A.1 Introducción 349
A.2 Productos cartesianos y relaciones 349
A.3 Propiedades de las relaciones binarias 354
A.4 Matrices y relaciones 360
A.4.1 Matrices y propiedades 361
A.5 Relaciones Funcionales o Funciones 362
A.5.1 Composición de funciones 365
A.5.2 Funciones usuales en lenguajes de programación 366
Respuestas y sugerencias 371
Bibliografía 407