Las matemáticas discretas, el estudio de los sistemas finitos, han adquirido cada vez más importancia en la medida en que ha avanzado la era de las computadoras. Básicamente, la computadora digital es una estructura finita, y muchas de sus propiedades pueden comprenderse e interpretarse en el marco de referencia de los sistemas matemáticos finitos. Este libro, al presentar el material esencial, cumple los requisitos de un curso formal de matemáticas discretas, o como complemento de cualquier texto actual.
Los tres primeros capítulos cubren el material normal sobre conjuntos, relaciones y funciones y algoritmos. Luego, siguen capítulos sobre lógica, conteo y probabilidad. A continuación hay tres capítulos sobre teoría de gráficas, gráficas dirigidas y árboles binarios. Por último, hay capítulos individuales sobre propiedades de los enteros, lenguajes, máquinas, conjuntos ordenados y retículas, y álgebra booleana, así como apéndices sobre vectores y matrices, y sistemas algebraicos. El capítulo sobre funciones y algoritmos incluye un análisis de cardinalidad y conjuntos numerables, y complejidad. Los capítulos sobre teoría de gráficas incluyen análisis sobre planaridad, recorribilidad (traversability), rutas mínimas y los algoritmos de Warshall y Huffman. Se recalca que los capítulos han sido escritos de modo que sea posible modificar su orden sin dificultad ni pérdida de continuidad.
Cada capítulo empieza con un planteamiento claro de las definiciones, principios y teoremas pertinentes, con material ilustrativo y de otros materiales descriptivos. Después, se plantean conjuntos de problemas resueltos y complementarios. Los problemas resueltos sirven para ilustrar y ampliar el material, y también incluye demostraciones de teoremas. Los problemas complementarios proporcionan una revisión completa del material del capítulo. Se ha incluido más material, el cual puede cubrirse en la mayor parte de los primeros cursos. Lo anterior se ha hecho con la intención de que el libro sea más flexible, a fin de ofrecer un libro de referencia más útil, y para estimular un mayor interés en los temas presentados.
Contenido:
CAPÍTULO 1 Teoría de conjuntos 1
1.1 Introducción 1
1.2 Conjuntos, elementos y subconjuntos 1
1.3 Diagramas de Venn 3
1.4 Operaciones con conjuntos 4
1.5 Álgebra de conjuntos, dualidad 7
1.6 Conjuntos finitos y principio de conteo 8
1.7 Clases de conjuntos, conjuntos potencia y particiones 10
1.8 Inducción matemática 12
Problemasresueltos 12
Problemassuplementarios 18
CAPÍTULO 2 Relaciones 23
2.1 Introducción 23
2.2 Producto de conjuntos 23
2.3 Relaciones 24
2.4 Representación gráfica de las relaciones 25
2.5 Composición de relaciones 27
2.6 Tipos de relaciones 28
2.7 Propiedades de cerradura 30
2.8 Relaciones de equivalencia 31
2.9 Relaciones de orden parcial 33
2.10 Relaciones n-arias 33
Problemas resueltos 34
Problemas suplementarios 40
CAPÍTULO 3 Funciones y algoritmos 43
3.1 Introducción 43
3.2 Funciones 43
3.3 Funciones uno a uno, sobre e invertibles 46
3.4 Funciones matemáticas, funciones exponencial y logarítmica 47
3.5 Sucesiones, clases indexadas de conjuntos 50
3.6 Funciones definidas en forma recursiva 52
3.7 Cardinalidad 55
3.8 Algoritmos y funciones 56
3.9 Complejidad de los algoritmos 57
Problemas resueltos 60
Problemas suplementarios 66
CAPÍTULO 4 Lógica y cálculo de proposiciones 70
4.1 Introducción 70
4.2 Proposiciones y declaraciones compuestas 70
4.3 Operaciones lógicas básicas 71
4.4 Proposiciones y tablas de verdad 72
4.5 Tautologías y contradicciones 74
4.6 Equivalencia lógica 74
4.7 Álgebra de proposiciones 75
4.8 Proposiciones condicionales y bicondicionales 75
4.9 Argumentos 76
4.10 Funciones proposicionales, cuantificadores 77
4.11 Negación de proposiciones cuantificadas 79
Problemas resueltos 82
Problemas suplementarios 86
CAPÍTULO 5 Técnicas de conteo 88
5.1 Introducción 88
5.2 Principios básicos de conteo 88
5.3 Funciones matemáticas 89
5.4 Permutaciones 91
5.5 Combinaciones 93
5.6 El principio del palomar 94
5.7 El principio de inclusión-exclusión 95
5.8 Diagramas de árbol 95
Problemas resueltos 96
Problemas suplementarios 103
CAPÍTULO 6 Técnicas de conteo avanzadas, recurrencia 107
6.1 Introducción 107
6.2 Combinaciones con repeticiones 107
6.3 Particiones ordenadas y no ordenadas 108
6.4 Otra aplicación del principio de inclusión-exclusión 108
6.5 Otra aplicación del principio del palomar 110
6.6 Relaciones recursivas, o de recurrencia 111
6.7 Relaciones recursivas, o de recurrencia, lineales con coeficientes constantes 113
6.8 Solución de relaciones de recurrencia lineales homogéneas de segundo orden 114
6.9 Solución de relaciones de recurrencia lineales homogéneas generales 116
Problemas resueltos 118
Problemas suplementarios 121
CAPÍTULO 7 Probabilidad 123
7.1 Introducción 123
7.2 Espacio muestral y eventos 123
7.3 Espacios de probabilidad finitos 126
7.4 Probabilidad condicional 127
7.5 Eventos independientes 129
7.6 Ensayos independientes repetidos, distribución binomial 130
7.7 Variables aleatorias 132
7.8 Desigualdad de Chebyshev, ley de los grandes números 135
Problemas resueltos 136
Problemas suplementarios 149
CAPÍTULO 8 Teoría de grafos 154
8.1 Introducción, estructura de datos 154
8.2 Grafos y multigrafos 156
8.3 Subgrafos, grafos isomorfos y homeomorfos 158
8.4 Caminos y conectividad 159
8.5 Recorridos y grafos eulerianos, los puentes de Königsberg 160
8.6 Grafos etiquetados y ponderados 162
8.7 Grafos completos, regulares y bipartidos 162
8.8 Árboles 164
8.9 Grafos planos 166
8.10 Coloreados de grafos 168
8.11 Representación de grafos en la memoria de la computadora 171
8.12 Algoritmos de gráficas 173
8.13 El problema del agente viajero 176
Problemas resueltos 178
Problemas suplementarios 191
CAPÍTULO 9 Grafos dirigidos 201
9.1 Introducción 201
9.2 Grafos dirigidos 201
9.3 Definiciones básicas 202
9.4 Árboles con raíz 204
9.5 Representación secuencial de grafos dirigidos 206
9.6 Algoritmo de Warshall, caminos más cortos 209
9.7 Representación ligada de grafos dirigidos 211
9.8 Algoritmos de grafos: búsquedas en profundidad y en anchura 213
9.9 Grafos dirigidos libres de ciclos, ordenación topológica 216
9.10 Algoritmo de poda para el camino más corto 218
Problemas resueltos 221
Problemas suplementarios 228
CAPÍTULO 10 Árboles binarios 235
10.1 Introducción 235
10.2 Árboles binarios 235
10.3 Árboles binarios completos y extendidos 237
10.4 Representación de árboles binarios en la memoria 239
10.5 Recorrido de árboles binarios 240
10.6 Árboles binarios de búsqueda 242
10.7 Colas prioritarias, montículos 244
10.8 Longitudes de caminos, algoritmo de Huffman 248
10.9 Árboles generales (con raíz ordenados), repaso 251
Problemas resueltos 252
Problemas suplementarios 259
CAPÍTULO 11 Propiedades de los enteros 264
11.1 Introducción 264
11.2 Orden y desigualdades, valor absoluto 265
11.3 Inducción matemática 266
11.4 Algoritmo de la división 267
11.5 Divisibilidad, primos 269
11.6 Máximo común divisor, algoritmo euclidiano 270
11.7 Teorema fundamental de la aritmética 273
11.8 Relación de congruencia 274
11.9 Ecuaciones de congruencia 278
Problemas resueltos 283
Problemas suplementarios 299
CAPÍTULO 12 Lenguajes, autómatas, gramáticas 303
12.1 Introducción 303
12.2 Alfabeto, palabras, semigrupo libre 303
12.3 Lenguajes 304
12.4 Expresiones regulares, lenguajes regulares 305
12.5 Autómatas de estado finito 306
12.6 Gramáticas 310
Problemas resueltos 314
Problemas suplementarios 319
CAPÍTULO 13 Máquinas de estados finitos y máquinas de Turing 323
13.1 Introducción 323
13.2 Máquinas de estados finitos 323
13.3 Números de Gödel 326
13.4 Máquinas de Turing 326
13.5 Funciones computables 330
Problemas resueltos 331
Problemas suplementarios 334
CAPÍTULO 14 Conjuntos ordenados y retículos 337
14.1 Introducción 337
14.2 Conjuntos ordenados 337
14.3 Diagramas de Hasse de conjuntos parcialmente ordenados 340
14.4 Enumeración consistente 342
14.5 Supremo e ínfimo 342
14.6 Conjuntos ordenados (semejantes) isomorfos 344
14.7 Conjuntos bien ordenados 344
14.8 Retículos 346
14.9 Retículos acotados 348
14.10 Retículos distributivos 349
14.11 Complementos, retículos complementados 350
Problemas resueltos 351
Problemas suplementarios 360
CAPÍTULO 15 Álgebra booleana 368
15.1 Introducción 368
15.2 Definiciones básicas 368
15.3 Dualidad 369
15.4 Teoremas básicos 370
15.5 Álgebras booleanas como retículos 370
15.6 Teorema de representación 371
15.7 Representación de conjuntos en forma de suma de productos 371
15.8 Representación de álgebras booleanas en forma de suma de productos 372
15.9 Expresiones booleanas minimales, implicantes primos 375
15.10 Compuertas y circuitos lógicos 377
15.11 Tablas de verdad, funciones booleanas 381
15.12 Mapas de Karnaugh 383
Problemas resueltos 389
Problemas suplementarios 403
APÉNDICE A Vectores y matrices 409
A.1 Introducción 409
A.2 Vectores 409
A.3 Matrices 410
A.4 Adición de matrices y multiplicación por un escalar 411
A.5 Multiplicación de matrices 412
A.6 Traspuesta 414
A.7 Matrices cuadradas 414
A.8 Matrices invertibles (no singulares), inversas 415
A.9 Determinantes 416
A.10 Operaciones elementales en los renglones, eliminación gaussiana (opcional) 418
A.11 Matrices booleanas (cero-uno) 422
Problemas resueltos 423
Problemas suplementarios 429
APÉNDICE B Sistemas algebraicos 432
B.1 Introducción 432
B.2 Operaciones 432
B.3 Semigrupos 435
B.4 Grupos 438
B.5 Subgrupos, subgrupos normales y homomorfismos 440
B.6 Anillos, dominios de integridad y campos 443
B.7 Polinomios sobre un campo 446
Problemas resueltos 450
Problemas suplementarios 461
ÍNDICE 467
DATOS TÉCNICOS:
Formato: .PDF
Compresión: .RAR
Hospedaje: DF, PL, MG
Peso: 5.23 MB
Idioma: Español
Contraseña: www.freelibros.org
No hay comentarios.:
Publicar un comentario