Click here to load reader

Matematicas discretas schawm 3ed

  • View
    270

  • Download
    15

Embed Size (px)

DESCRIPTION

 

Text of Matematicas discretas schawm 3ed

  • MATEMTICASDISCRETAS

    00_Preliminares_Lipschutz.indd I00_Preliminares_Lipschutz.indd I 11/25/08 3:00:28 PM11/25/08 3:00:28 PM

  • 00_Preliminares_Lipschutz.indd II00_Preliminares_Lipschutz.indd II 11/25/08 3:00:31 PM11/25/08 3:00:31 PM

  • MXICO BOGOT BUENOS AIRES CARACAS GUATEMALALISBOA MADRID NUEVA YORK SAN JUAN SANTIAGO

    AUCKLAND LONDRES MILN MONTREAL NUEVA DELHISAN FRANCISCO SINGAPUR SAN LUIS SIDNEY TORONTO

    MATEMTICASDISCRETAS

    Seymour Lipschutz, Ph. D.Temple University

    Marc Lars Lipson, Ph. D.University of Virginia

    Revisin tcnicaMara de Lourdes Quezada Batalla

    Departamento de Ciencias BsicasInstituto Tecnolgico y de Estudios Superiores de Monterrey

    Campus Estado de Mxico

    Tercera edicin

    00_Preliminares_Lipschutz.indd III00_Preliminares_Lipschutz.indd III 11/25/08 3:00:31 PM11/25/08 3:00:31 PM

  • Director Higher Education: Miguel ngel Toledo CastellanosDirector editorial: Ricardo A. del Bosque AlaynCoordinadora editorial: Marcela I. Rocha MartnezEditor sponsor: Pablo E. Roig VzquezSupervisor de produccin: Zeferino Garca Garca

    Traduccin: Hugo Villagmez Velzquez

    MATEMTICAS DISCRETASTercera edicin

    Prohibida la reproduccin total o parcial de esta obra, por cualquier medio, sin la autorizacin escrita del editor.

    DERECHOS RESERVADOS 2009, respecto a la primera edicin en espaol porMcGRAW-HILL/INTERAMERICANA EDITORES, S.A. de C.V.A Subsidiary of The McGraw-Hill Companies, Inc. Edifi cio Punta Santa Fe Prolongacin Paseo de la Reforma 1015, Torre A Piso 17, Colonia Desarrollo Santa Fe Delegacin lvaro Obregn C.P. 01376, Mxico, D. F. Miembro de la Cmara Nacional de la Industria Editorial Mexicana, Reg. Nm. 736

    ISBN 13: 978-970-10-7236-3

    Copyright 2007, 1997, 1976 de la edicin en ingls Discrete Mathematics, by Seymour Lipschutz and MarcLipson, published by The McGraw-Hill Companies, Inc.All rights reserved

    0123456789 08765432109

    Impreso en Mxico Printed in Mexico

    00_Preliminares_Lipschutz.indd IV00_Preliminares_Lipschutz.indd IV 11/25/08 3:00:31 PM11/25/08 3:00:31 PM

  • SEYMOUR LIPSCHUTZ da clases en la Facultad de Matemticas de la Universidad Temple y antes ense en el Instituto Politcnico de Brooklin. Se doctor en 1960 en el Instituto Courant de Ciencias Matemticas de la Universidad de Nueva York. Es uno de los ms prolficos autores de la serie Schaums Outlines, y tambin es autor de Probability; Finite Mathematics, 2a. edicin; Linear Algebra, 3a. edicin; Beginning Linear Algebra; Set Theory; y Essential Computer Mathematics.

    MARC LARS LIPSON da clases en la Universidad de Virginia y antes ense en la Facultad de la Universidad de Georgia. Se doctor en finanzas en 1994 en la Universidad de Michigan. Tambin es coautor de Linear Algebra, 3a. edicin y 2000 Solved Problems in Discrete Mathematics con Seymour Lipschutz.

    ACERCA DE LOS AUTORES

    V

    00_Preliminares_Lipschutz.indd V00_Preliminares_Lipschutz.indd V 11/25/08 3:00:32 PM11/25/08 3:00:32 PM

  • 00_Preliminares_Lipschutz.indd VI00_Preliminares_Lipschutz.indd VI 11/25/08 3:00:32 PM11/25/08 3:00:32 PM

  • VII

    Las matemticas discretas, el estudio de los sistemas finitos, han adquirido cada vez ms importancia en la medida en que ha avanzado la era de las computadoras. Bsicamente, la computadora digital es una estructura finita, y muchas de sus propiedades pueden comprenderse e interpretarse en el marco de referencia de los sistemas matemticos finitos. Este libro, al presentar el material esencial, cumple los requisitos de un curso formal de matemticas discretas, o como complemento de cualquier texto actual.

    Los tres primeros captulos cubren el material normal sobre conjuntos, relaciones y funciones y algoritmos. Luego, siguen captulos sobre lgica, conteo y probabilidad. A continuacin hay tres captulos sobre teora de grficas,grficas dirigidas y rboles binarios. Por ltimo, hay captulos individuales sobre propiedades de los enteros, lenguajes, mquinas, conjuntos ordenados y retculas, y lgebra booleana, as como apndices sobre vectores y matrices, ysistemas algebraicos. El captulo sobre funciones y algoritmos incluye un anlisis de cardinalidad y conjuntos nume-rables, y complejidad. Los captulos sobre teora de grficas incluyen anlisis sobre planaridad, recorribilidad (traver-sability), rutas mnimas y los algoritmos de Warshall y Huffman. Se recalca que los captulos han sido escritos de modo que sea posible modificar su orden sin dificultad ni prdida de continuidad.

    Cada captulo empieza con un planteamiento claro de las definiciones, principios y teoremas pertinentes, con mate-rial ilustrativo y de otros materiales descriptivos. Despus, se plantean conjuntos de problemas resueltos y complemen-tarios. Los problemas resueltos sirven para ilustrar y ampliar el material, y tambin incluye demostraciones de teoremas. Los problemas complementarios proporcionan una revisin completa del material del captulo. Se ha incluido ms material, el cual puede cubrirse en la mayor parte de los primeros cursos. Lo anterior se ha hecho con la intencin de que el libro sea ms flexible, a fin de ofrecer un libro de referencia ms til, y para estimular un mayor inters en los temas presentados.

    SEYMOUR LIPSCHUTZMARC LARS LIPSON

    PRLOGO

    00_Preliminares_Lipschutz.indd VII00_Preliminares_Lipschutz.indd VII 11/25/08 3:00:33 PM11/25/08 3:00:33 PM

  • 00_Preliminares_Lipschutz.indd VIII00_Preliminares_Lipschutz.indd VIII 11/25/08 3:00:33 PM11/25/08 3:00:33 PM

  • IX

    CONTENIDO

    CAPTULO 1 Teora de conjuntos 1 1.1 Introduccin 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 Induccin matemtica 12 Problemas resueltos 12 Problemas suplementarios 18

    CAPTULO 2 Relaciones 23 2.1 Introduccin 23 2.2 Producto de conjuntos 23 2.3 Relaciones 24 2.4 Representacin grfica de las relaciones 25 2.5 Composicin 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

    CAPTULO 3 Funciones y algoritmos 43 3.1 Introduccin 43 3.2 Funciones 43 3.3 Funciones uno a uno, sobre e invertibles 46 3.4 Funciones matemticas, funciones exponencial y logartmica 47 3.5 Sucesiones, clases indexadas de conjuntos 50 3.6 Funciones definidas en forma recursiva 52

    00_Preliminares_Lipschutz.indd IX00_Preliminares_Lipschutz.indd IX 11/25/08 3:00:33 PM11/25/08 3:00:33 PM

  • X CONTENIDO

    3.7 Cardinalidad 55 3.8 Algoritmos y funciones 56 3.9 Complejidad de los algoritmos 57 Problemas resueltos 60 Problemas suplementarios 66

    CAPTULO 4 Lgica y clculo de proposiciones 70 4.1 Introduccin 70 4.2 Proposiciones y declaraciones compuestas 70 4.3 Operaciones lgicas bsicas 71 4.4 Proposiciones y tablas de verdad 72 4.5 Tautologas y contradicciones 74 4.6 Equivalencia lgica 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 Negacin de proposiciones cuantificadas 79 Problemas resueltos 82 Problemas suplementarios 86

    CAPTULO 5 Tcnicas de conteo 88 5.1 Introduccin 88 5.2 Principios bsicos de conteo 88 5.3 Funciones matemticas 89 5.4 Permutaciones 91 5.5 Combinaciones 93 5.6 El principio del palomar 94 5.7 El principio de inclusin-exclusin 95 5.8 Diagramas de rbol 95 Problemas resueltos 96 Problemas suplementarios 103

    CAPTULO 6 Tcnicas de conteo avanzadas, recurrencia 107 6.1 Introduccin 107 6.2 Combinaciones con repeticiones 107 6.3 Particiones ordenadas y no ordenadas 108 6.4 Otra aplicacin del principio de inclusin-exclusin 108 6.5 Otra aplicacin 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 Solucin de relaciones de recurrencia lineales homogneas de segundo orden 114 6.9 Solucin de relaciones de recurrencia lineales homogneas generales 116

    00_Preliminares_Lipschutz.indd X00_Preliminares_Lipschutz.indd X 11/25/08 3:00:34 PM11/25/08 3:00:34 PM

  • Problemas resueltos 118 Problemas suplementarios 121

    CAPTULO 7 Probabilidad 123 7.1 Introduccin 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, distribucin binomial 130 7.7 Variables aleatorias 132 7.8 Desigualdad de Chebyshev, ley de los grandes nmeros 135 Problemas resueltos 136 Problemas suplementarios 149

    CAPTULO 8 Teora de grafos 154 8.1 Introduccin, 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 Knigsberg 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 Representacin de grafos en la memoria de la computadora 171 8.12 Algoritmos de grficas 173 8.13 El problema del agente viajero 176 Problemas resueltos 178 Problemas suplementarios 191

    CAPTULO 9 Grafos dirigidos 201 9.1 Introduccin 201 9.2 Grafos dirigidos 201 9.3 Definiciones bsicas 202 9.4 rboles con raz 204 9.5 Representacin secuencial de grafos dirigidos 206 9.6 Algoritmo de Warshall, caminos ms cortos 209 9.7 Representacin ligada de grafos dirigidos 211 9.8 Algoritmos de grafos: bsquedas en profundidad y en anchura 213 9.9 Grafos d

Search related