Matemáticas discretas /
Scheinerman, Edward R.
Matemáticas discretas / Edward R. Scheinerman. - México : Thomson, 2001 - 484 p.
CONTENIDO
Capítulo 1. Fundamentos 1
1 Definición 1
2 Teorema 7
Naturaleza de la categoría de verdadero 7
Si... entonces 9
Si Y sólo si 11
Y, o y no 12
Qué teoremas usar 13
Verdad vacua 13
3 Demostración 15
Demostración del teorema si, y sólo si 19
4 Contraejemplo 22
5 Álgebra booleana 25
Más operaciones 28
Capítulo 2 Colecciones 33
6 Listas 33
Conteo de listas de dos elementos 34
Listas más largas 36
7 Factorial 41
¡Mucho que hacer con 0! 42
Notación de producto 43
8 Conjuntos I: Introducción a los subconjuntos 46
Relaciones entre conjuntos 47
Conteo de subconjuntos 49
Conjunto potencia 50
9 Cuantificadores 52
Existe 52
Para todo (para toda) 53
Negación de enunciados cuantificados 54
Combinación de cuantificadores 55
10 Conjuntos II: Operaciones 58
Unión e intersección 58
Tamaño de una unión 60
Diferencia y diferencia simétrica 63
Producto cartesiano 67
Capítulo 3 Conteo y relaciones 72
11 Relaciones 72
Propiedades de las relaciones 75
12 Relaciones de equivalencia 78
Clases de equivalencia 82
13 Particiones 87
Conteo de clases y partes 90
14 Coeficientes binomiales 94
Cálculo de (n sobre k) 98
Triángulo de Pascal 100
Fórmula para calcular (n sobre k) 102
15 Conteo de multiconjuntos 108
Multiconjuntos 109
Fórmulas para (n sobre k) 110
16 Inclusión-exclusión 116
Cómo usar la inclusión-exclusión 119
Degradamientos 121
Una fórmula terrible 124
Capítulo 4 Más demostraciones 126
17 Contradicción 126
Demostración con contrapositiva 126
Reducción al absurdo 128
Cuestión de estilo 132
18 Contraejemplo con el elemento más pequeño 133
Buen ordenamiento 139
Y finalmente 146
19 Inducción 146
Inducción fuerte 149
Un ejemplo más complicado 151
Cuestión de estilo 157
Capítulo 5 Funciones 158
20 Funciones 158
Dominio e imagen 160
Figuras de funciones 161
Conteo de funciones 162
Funciones inversas 163
Conteo de funciones, otra vez 167
21 Principio del palomar 171
Teorema de Cantor 174
22 Composición 177
Función identidad 180
23 Permutaciones 183
Notación de ciclo 184
Cálculos con permutaciones 187
Transposiciones 188
24 Simetría 196
Simetrías de un cuadrado 196
Simetrías como permutaciones 198
Combinación de simetrías 198
Definición formal de simetría 200
25 Notación diversa 202
O mayúscula 202
Omega mayúscula y theta mayúscula 205
O minúscula 206
Piso y techo 207
Capítulo 6 Probabilidad 209
26 Espacio muestral 209
27 Eventos 213
Combinación de eventos 216
El problema del cumpleaños 218
28 Probabilidad condicional e independencia 221
Independencia 223
Los intentos independientes repetidos 226
Problema de Monty Hall 227
29 Variables aleatorias 231
Variables aleatorias como eventos 232
Variables aleatorias independientes 234
30 Esperanza matemática 236
Linealidad de la esperanza matemática 241
Producto de variables aleatorias 245
Valor esperado como medida de centralidad 248
Varianza 249
Capítulo 7 Teoría de los números 255
31 División 255
Div y mód 258
32 Máximo divisor común 260
Cálculo del mdc 261
Corrección 263
¿Qué tan rápido? 264
Un teorema importante 266
33 Aritmética modular 271
Un nuevo contexto para operaciones básicas 271
Adición y multiplicación modular 272
Sustracción modular 274
División modular 275
Nota sobre la notación 280
34 Teorema del residuo chino 283
Solución de una ecuación 283
Solución de dos ecuaciones 285
35 Factorización 288
Cantidad infinita de primos 290
Fórmula para determinar el máximo divisor común 291
Iracionalidad de raíz cuadrada de 2 292
Capítulo 8 Álgebra 299
36 Grupos 299
Operaciones 299
Propiedades de las operaciones 300
Grupos 302
37 Isomorfismo de grupo 310
¿Lo mismo? 310
Grupos cíclicos 312
38 Subgrupos 316
Teorema de LaGrange 319
39 Pequeño teorema de Fermat 325
Primera demostración 326
Segunda demostración 327
Tercera demostración 330
Teorema de Euler 331
Prueba de primalidad 332
40 Criptografía de clave pública I: Introducción 334
El problema: comunicación privada en público 334
Factorización 334
De palabras a números 335
Criptografía y ley 337
Criptografía de clave pública II: Método Rabin 337
Raíces cuadradas módulo n 338
Procedimientos de cifrado y descifrado 343
Criptografía de clave pública III: RSA 345
Funciones RSA de cifrado y descifrado 345
Seguridad 347
Capítulo 9 Gráficas 351
43 Fundamentos de la teoría de las gráficas 351
Iluminación de mapas 351
Tres servicios 353
Siete puentes 353
¿Qué es una gráfica? 354
Adyacencia 355
Cuestión de grado 357
Más notación y vocabulario 359
44 Subgráficas 362
Subgráficas inducida e incorporada 362
Camarillas y conjuntos independientes 365
Complementos 366
45 Conexión 369
Caminatas 369
Caminos 370
Desconexión 374
46 Árboles 377
Ciclos 377
Bosques y árboles 377
Propiedades de los árboles 378
Hojas 380
Árboles incorporados 382
47 Gráficas de Euler 385
Condiciones necesarias 386
Teoremas principales 387
Negocios inconclusos 389
48 Iluminación 391
Conceptos básicos 392
Gráficas bipartidas 394
Facilidad del dos-iluminable y dificultad del tres-iluminable 398
49 Gráficas planas 400
Curvas peligrosas 400
Incrustación 401
Fórmula de Euler 402
Gráficas no planas 405
Iluminación de gráficas planas 406
Capítulo 10 Conjuntos parcialmente ordenados 411
50 Fundamentos de conjuntos parcialmente ordenados 411
¿Qué es un poset? 411
Notación y lenguaje 414
51 Máximo y mínimo 417
52 Órdenes lineales 420
53 Extensiones lineales 423
Clasificación 427
Extensiones lineales de posets infinitos 429
54 Dimensión 431
Realizadores 431
Dimensión 434
Incrustación 436
55 Retículas 439
Encuentro y juntura 439
Retículas 442
Apéndices 447
A Muchas sugerencias y comentarios; algunas respuestas 447
B Glosario 469
C Fundamentos 476
Números 476
Operaciones 476
Ordenamiento 476
Sustitución 477
Indice 479
9706860711
MATEMATICAS DISCRETAS
PROBABILIDAD
TEORIA DE NUMEROS
FUNCIONES MATEMATICAS
GRUPOS
ISOMORFISMO DE GRUPO
TEOREMA DE FERMAT
CRIPTOGRAFIA
GRAFICAS
ARBOLES
GRAFICA DE EULER
519.1 SCH25
Matemáticas discretas / Edward R. Scheinerman. - México : Thomson, 2001 - 484 p.
CONTENIDO
Capítulo 1. Fundamentos 1
1 Definición 1
2 Teorema 7
Naturaleza de la categoría de verdadero 7
Si... entonces 9
Si Y sólo si 11
Y, o y no 12
Qué teoremas usar 13
Verdad vacua 13
3 Demostración 15
Demostración del teorema si, y sólo si 19
4 Contraejemplo 22
5 Álgebra booleana 25
Más operaciones 28
Capítulo 2 Colecciones 33
6 Listas 33
Conteo de listas de dos elementos 34
Listas más largas 36
7 Factorial 41
¡Mucho que hacer con 0! 42
Notación de producto 43
8 Conjuntos I: Introducción a los subconjuntos 46
Relaciones entre conjuntos 47
Conteo de subconjuntos 49
Conjunto potencia 50
9 Cuantificadores 52
Existe 52
Para todo (para toda) 53
Negación de enunciados cuantificados 54
Combinación de cuantificadores 55
10 Conjuntos II: Operaciones 58
Unión e intersección 58
Tamaño de una unión 60
Diferencia y diferencia simétrica 63
Producto cartesiano 67
Capítulo 3 Conteo y relaciones 72
11 Relaciones 72
Propiedades de las relaciones 75
12 Relaciones de equivalencia 78
Clases de equivalencia 82
13 Particiones 87
Conteo de clases y partes 90
14 Coeficientes binomiales 94
Cálculo de (n sobre k) 98
Triángulo de Pascal 100
Fórmula para calcular (n sobre k) 102
15 Conteo de multiconjuntos 108
Multiconjuntos 109
Fórmulas para (n sobre k) 110
16 Inclusión-exclusión 116
Cómo usar la inclusión-exclusión 119
Degradamientos 121
Una fórmula terrible 124
Capítulo 4 Más demostraciones 126
17 Contradicción 126
Demostración con contrapositiva 126
Reducción al absurdo 128
Cuestión de estilo 132
18 Contraejemplo con el elemento más pequeño 133
Buen ordenamiento 139
Y finalmente 146
19 Inducción 146
Inducción fuerte 149
Un ejemplo más complicado 151
Cuestión de estilo 157
Capítulo 5 Funciones 158
20 Funciones 158
Dominio e imagen 160
Figuras de funciones 161
Conteo de funciones 162
Funciones inversas 163
Conteo de funciones, otra vez 167
21 Principio del palomar 171
Teorema de Cantor 174
22 Composición 177
Función identidad 180
23 Permutaciones 183
Notación de ciclo 184
Cálculos con permutaciones 187
Transposiciones 188
24 Simetría 196
Simetrías de un cuadrado 196
Simetrías como permutaciones 198
Combinación de simetrías 198
Definición formal de simetría 200
25 Notación diversa 202
O mayúscula 202
Omega mayúscula y theta mayúscula 205
O minúscula 206
Piso y techo 207
Capítulo 6 Probabilidad 209
26 Espacio muestral 209
27 Eventos 213
Combinación de eventos 216
El problema del cumpleaños 218
28 Probabilidad condicional e independencia 221
Independencia 223
Los intentos independientes repetidos 226
Problema de Monty Hall 227
29 Variables aleatorias 231
Variables aleatorias como eventos 232
Variables aleatorias independientes 234
30 Esperanza matemática 236
Linealidad de la esperanza matemática 241
Producto de variables aleatorias 245
Valor esperado como medida de centralidad 248
Varianza 249
Capítulo 7 Teoría de los números 255
31 División 255
Div y mód 258
32 Máximo divisor común 260
Cálculo del mdc 261
Corrección 263
¿Qué tan rápido? 264
Un teorema importante 266
33 Aritmética modular 271
Un nuevo contexto para operaciones básicas 271
Adición y multiplicación modular 272
Sustracción modular 274
División modular 275
Nota sobre la notación 280
34 Teorema del residuo chino 283
Solución de una ecuación 283
Solución de dos ecuaciones 285
35 Factorización 288
Cantidad infinita de primos 290
Fórmula para determinar el máximo divisor común 291
Iracionalidad de raíz cuadrada de 2 292
Capítulo 8 Álgebra 299
36 Grupos 299
Operaciones 299
Propiedades de las operaciones 300
Grupos 302
37 Isomorfismo de grupo 310
¿Lo mismo? 310
Grupos cíclicos 312
38 Subgrupos 316
Teorema de LaGrange 319
39 Pequeño teorema de Fermat 325
Primera demostración 326
Segunda demostración 327
Tercera demostración 330
Teorema de Euler 331
Prueba de primalidad 332
40 Criptografía de clave pública I: Introducción 334
El problema: comunicación privada en público 334
Factorización 334
De palabras a números 335
Criptografía y ley 337
Criptografía de clave pública II: Método Rabin 337
Raíces cuadradas módulo n 338
Procedimientos de cifrado y descifrado 343
Criptografía de clave pública III: RSA 345
Funciones RSA de cifrado y descifrado 345
Seguridad 347
Capítulo 9 Gráficas 351
43 Fundamentos de la teoría de las gráficas 351
Iluminación de mapas 351
Tres servicios 353
Siete puentes 353
¿Qué es una gráfica? 354
Adyacencia 355
Cuestión de grado 357
Más notación y vocabulario 359
44 Subgráficas 362
Subgráficas inducida e incorporada 362
Camarillas y conjuntos independientes 365
Complementos 366
45 Conexión 369
Caminatas 369
Caminos 370
Desconexión 374
46 Árboles 377
Ciclos 377
Bosques y árboles 377
Propiedades de los árboles 378
Hojas 380
Árboles incorporados 382
47 Gráficas de Euler 385
Condiciones necesarias 386
Teoremas principales 387
Negocios inconclusos 389
48 Iluminación 391
Conceptos básicos 392
Gráficas bipartidas 394
Facilidad del dos-iluminable y dificultad del tres-iluminable 398
49 Gráficas planas 400
Curvas peligrosas 400
Incrustación 401
Fórmula de Euler 402
Gráficas no planas 405
Iluminación de gráficas planas 406
Capítulo 10 Conjuntos parcialmente ordenados 411
50 Fundamentos de conjuntos parcialmente ordenados 411
¿Qué es un poset? 411
Notación y lenguaje 414
51 Máximo y mínimo 417
52 Órdenes lineales 420
53 Extensiones lineales 423
Clasificación 427
Extensiones lineales de posets infinitos 429
54 Dimensión 431
Realizadores 431
Dimensión 434
Incrustación 436
55 Retículas 439
Encuentro y juntura 439
Retículas 442
Apéndices 447
A Muchas sugerencias y comentarios; algunas respuestas 447
B Glosario 469
C Fundamentos 476
Números 476
Operaciones 476
Ordenamiento 476
Sustitución 477
Indice 479
9706860711
MATEMATICAS DISCRETAS
PROBABILIDAD
TEORIA DE NUMEROS
FUNCIONES MATEMATICAS
GRUPOS
ISOMORFISMO DE GRUPO
TEOREMA DE FERMAT
CRIPTOGRAFIA
GRAFICAS
ARBOLES
GRAFICA DE EULER
519.1 SCH25