TY - BOOK AU - Scheinerman,Edward R. TI - Matemáticas discretas / SN - 9706860711 PY - 2001/// CY - México : PB - Thomson, KW - MATEMATICAS DISCRETAS KW - PROBABILIDAD KW - TEORIA DE NUMEROS KW - FUNCIONES MATEMATICAS KW - GRUPOS KW - ISOMORFISMO DE GRUPO KW - TEOREMA DE FERMAT KW - CRIPTOGRAFIA KW - GRAFICAS KW - ARBOLES KW - GRAFICA DE EULER N1 - 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 ER -