Matemáticas discretas Schaum Lipschutz & Lipson 3ed PDF

Preview

Summary

www.FreeLibros.me www.FreeLibros.me MATEMÁTICAS DISCRETAS www.FreeLibros.me www.FreeLibros.me MATEMÁTICAS DISCRETAS Tercera edición Seymour Lipschutz, Ph. D. Temple University Marc Lars Lipson, Ph. D. University of Virginia Revisión técnica María de Lourdes Quezada Batalla Departamento de Ciencias B...

Description

www.FreeLibros.me

www.FreeLibros.me

MATEMÁTICAS DISCRETAS

www.FreeLibros.me

www.FreeLibros.me

MATEMÁTICAS DISCRETAS Tercera edición

Seymour Lipschutz, Ph. D. Temple University

Marc Lars Lipson, Ph. D. University of Virginia

Revisión técnica María de Lourdes Quezada Batalla Departamento de Ciencias Básicas Instituto Tecnológico y de Estudios Superiores de Monterrey Campus Estado de México

MÉXICO • BOGOTÁ • BUENOS AIRES • CARACAS • GUATEMALA LISBOA • MADRID • NUEVA YORK • SAN JUAN • SANTIAGO AUCKLAND • LONDRES • MILÁN • MONTREAL • NUEVA DELHI SAN FRANCISCO • SINGAPUR • SAN LUIS • SIDNEY • TORONTO

www.FreeLibros.me

Director Higher Education: Miguel Ángel Toledo Castellanos Director editorial: Ricardo A. del Bosque Alayón Coordinadora editorial: Marcela I. Rocha Martínez Editor sponsor: Pablo E. Roig Vázquez Supervisor de producción: Zeferino García García Traducción: Hugo Villagómez Velázquez

MATEMÁTICAS DISCRETAS Tercera edición Prohibida la reproducción total o parcial de esta obra, por cualquier medio, sin la autorización escrita del editor.

DERECHOS RESERVADOS © 2009, respecto a la primera edición en español por McGRAW-HILL/INTERAMERICANA EDITORES, S.A. de C.V. A Subsidiary of The McGraw-Hill Companies, Inc. Edificio Punta Santa Fe Prolongación Paseo de la Reforma 1015, Torre A Piso 17, Colonia Desarrollo Santa Fe Delegación Álvaro Obregón C.P. 01376, México, D. F. Miembro de la Cámara Nacional de la Industria Editorial Mexicana, Reg. Núm. 736 ISBN 13: 978-970-10-7236-3 Copyright © 2007, 1997, 1976 de la edición en inglés Discrete Mathematics, by Seymour Lipschutz and Marc Lipson, published by The McGraw-Hill Companies, Inc. All rights reserved

0123456789

08765432109

Impreso en México

Printed in Mexico

www.FreeLibros.me

ACERCA DE LOS AUTORES

SEYMOUR LIPSCHUTZ da clases en la Facultad de Matemáticas de la Universidad Temple y antes enseñó en el Instituto Politécnico de Brooklin. Se doctoró en 1960 en el Instituto Courant de Ciencias Matemáticas de la Universidad de Nueva York. Es uno de los más prolíficos autores de la serie Schaum’s Outlines, y también es autor de Probability; Finite Mathematics, 2a. edición; Linear Algebra, 3a. edición; 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. También es coautor de Linear Algebra, 3a. edición y 2000 Solved Problems in Discrete Mathematics con Seymour Lipschutz.

V

www.FreeLibros.me

www.FreeLibros.me

PRÓLOGO

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. SEYMOUR LIPSCHUTZ MARC LARS LIPSON

VII

www.FreeLibros.me

www.FreeLibros.me

CONTENIDO

CAPÍTULO 1

CAPÍTULO 2

CAPÍTULO 3

Teoría de conjuntos

1

1.1 Introducción 1.2 Conjuntos, elementos y subconjuntos 1.3 Diagramas de Venn 1.4 Operaciones con conjuntos 1.5 Álgebra de conjuntos, dualidad 1.6 Conjuntos finitos y principio de conteo 1.7 Clases de conjuntos, conjuntos potencia y particiones 1.8 Inducción matemática Problemas resueltos Problemas suplementarios

1 1 3 4 7 8 10 12 12 18

Relaciones

23

2.1 Introducción 2.2 Producto de conjuntos 2.3 Relaciones 2.4 Representación gráfica de las relaciones 2.5 Composición de relaciones 2.6 Tipos de relaciones 2.7 Propiedades de cerradura 2.8 Relaciones de equivalencia 2.9 Relaciones de orden parcial 2.10 Relaciones n-arias Problemas resueltos Problemas suplementarios

23 23 24 25 27 28 30 31 33 33 34 40

Funciones y algoritmos

43

3.1 3.2 3.3 3.4 3.5 3.6

43 43 46 47 50 52

Introducción Funciones Funciones uno a uno, sobre e invertibles Funciones matemáticas, funciones exponencial y logarítmica Sucesiones, clases indexadas de conjuntos Funciones definidas en forma recursiva

IX

www.FreeLibros.me

X CONTENIDO

CAPÍTULO 4

CAPÍTULO 5

CAPÍTULO 6

3.7 Cardinalidad 3.8 Algoritmos y funciones 3.9 Complejidad de los algoritmos Problemas resueltos Problemas suplementarios

55 56 57 60 66

Lógica y cálculo de proposiciones

70

4.1 Introducción 4.2 Proposiciones y declaraciones compuestas 4.3 Operaciones lógicas básicas 4.4 Proposiciones y tablas de verdad 4.5 Tautologías y contradicciones 4.6 Equivalencia lógica 4.7 Álgebra de proposiciones 4.8 Proposiciones condicionales y bicondicionales 4.9 Argumentos 4.10 Funciones proposicionales, cuantificadores 4.11 Negación de proposiciones cuantificadas Problemas resueltos Problemas suplementarios

70 70 71 72 74 74 75 75 76 77 79 82 86

Técnicas de conteo

88

5.1 Introducción 5.2 Principios básicos de conteo 5.3 Funciones matemáticas 5.4 Permutaciones 5.5 Combinaciones 5.6 El principio del palomar 5.7 El principio de inclusión-exclusión 5.8 Diagramas de árbol Problemas resueltos Problemas suplementarios

88 88 89 91 93 94 95 95 96 103

Técnicas de conteo avanzadas, recurrencia 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9

Introducción Combinaciones con repeticiones Particiones ordenadas y no ordenadas Otra aplicación del principio de inclusión-exclusión Otra aplicación del principio del palomar Relaciones recursivas, o de recurrencia Relaciones recursivas, o de recurrencia, lineales con coeficientes constantes Solución de relaciones de recurrencia lineales homogéneas de segundo orden Solución de relaciones de recurrencia lineales homogéneas generales

www.FreeLibros.me

107 107 107 108 108 110 111 113 114 116

CONTENIDO XI

Problemas resueltos Problemas suplementarios

CAPÍTULO 7

Probabilidad 7.1 Introducción 7.2 Espacio muestral y eventos 7.3 Espacios de probabilidad finitos 7.4 Probabilidad condicional 7.5 Eventos independientes 7.6 Ensayos independientes repetidos, distribución binomial 7.7 Variables aleatorias 7.8 Desigualdad de Chebyshev, ley de los grandes números Problemas resueltos Problemas suplementarios

CAPÍTULO 8

Teoría de grafos 8.1 Introducción, estructura de datos 8.2 Grafos y multigrafos 8.3 Subgrafos, grafos isomorfos y homeomorfos 8.4 Caminos y conectividad 8.5 Recorridos y grafos eulerianos, los puentes de Königsberg 8.6 Grafos etiquetados y ponderados 8.7 Grafos completos, regulares y bipartidos 8.8 Árboles 8.9 Grafos planos 8.10 Coloreados de grafos 8.11 Representación de grafos en la memoria de la computadora 8.12 Algoritmos de gráficas 8.13 El problema del agente viajero Problemas resueltos Problemas suplementarios

CAPÍTULO 9

Grafos dirigidos 9.1 Introducción 9.2 Grafos dirigidos 9.3 Definiciones básicas 9.4 Árboles con raíz 9.5 Representación secuencial de grafos dirigidos 9.6 Algoritmo de Warshall, caminos más cortos 9.7 Representación ligada de grafos dirigidos 9.8 Algoritmos de grafos: búsquedas en profundidad y en anchura 9.9 Grafos dirigidos libres de ciclos, ordenación topológica 9.10 Algoritmo de poda para el camino más corto Problemas resueltos Problemas suplementarios

www.FreeLibros.me

118 121

123 123 123 126 127 129 130 132 135 136 149

154 154 156 158 159 160 162 162 164 166 168 171 173 176 178 191

201 201 201 202 204 206 209 211 213 216 218 221 228

XII CONTENIDO

CAPÍTULO 10

Árboles binarios 10.1 Introducción 10.2 Árboles binarios 10.3 Árboles binarios completos y extendidos 10.4 Representación de árboles binarios en la memoria 10.5 Recorrido de árboles binarios 10.6 Árboles binarios de búsqueda 10.7 Colas prioritarias, montículos 10.8 Longitudes de caminos, algoritmo de Huffman 10.9 Árboles generales (con raíz ordenados), repaso Problemas resueltos Problemas suplementarios

CAPÍTULO 11

Propiedades de los enteros 11.1 Introducción 11.2 Orden y desigualdades, valor absoluto 11.3 Inducción matemática 11.4 Algoritmo de la división 11.5 Divisibilidad, primos 11.6 Máximo común divisor, algoritmo euclidiano 11.7 Teorema fundamental de la aritmética 11.8 Relación de congruencia 11.9 Ecuaciones de congruencia Problemas resueltos Problemas suplementarios

CAPÍTULO 12

Lenguajes, autómatas, gramáticas 12.1 Introducción 12.2 Alfabeto, palabras, semigrupo libre 12.3 Lenguajes 12.4 Expresiones regulares, lenguajes regulares 12.5 Autómatas de estado finito 12.6 Gramáticas Problemas resueltos Problemas suplementarios

CAPÍTULO 13

Máquinas de estados finitos y máquinas de Turing 13.1 Introducción 13.2 Máquinas de estados finitos 13.3 Números de Gödel 13.4 Máquinas de Turing 13.5 Funciones computables Problemas resueltos Problemas suplementarios

www.FreeLibros.me

235 235 235 237 239 240 242 244 248 251 252 259

264 264 265 266 267 269 270 273 274 278 283 299

303 303 303 304 305 306 310 314 319

323 323 323 326 326 330 331 334

CONTENIDO XIII

CAPÍTULO 14

Conjuntos ordenados y retículos 14.1 Introducción 14.2 Conjuntos ordenados 14.3 Diagramas de Hasse de conjuntos parcialmente ordenados 14.4 Enumeración consistente 14.5 Supremo e ínfimo 14.6 Conjuntos ordenados (semejantes) isomorfos 14.7 Conjuntos bien ordenados 14.8 Retículos 14.9 Retículos acotados 14.10 Retículos distributivos 14.11 Complementos, retículos complementados Problemas resueltos Problemas suplementarios

CAPÍTULO 15

Álgebra booleana 15.1 15.2 15.3 15.4 15.5 15.6 15.7 15.8

Introducción Definiciones básicas Dualidad Teoremas básicos Álgebras booleanas como retículos Teorema de representación Representación de conjuntos en forma de suma de productos Representación de álgebras booleanas en forma de suma de productos 15.9 Expresiones booleanas minimales, implicantes primos 15.10 Compuertas y circuitos lógicos 15.11 Tablas de verdad, funciones booleanas 15.12 Mapas de Karnaugh Problemas resueltos Problemas suplementarios

APÉNDICE A

Vectores y matrices A.1 A.2 A.3 A.4 A.5 A.6 A.7 A.8 A.9 A.10

Introducción Vectores Matrices Adición de matrices y multiplicación por un escalar Multiplicación de matrices Traspuesta Matrices cuadradas Matrices invertibles (no singulares), inversas Determinantes Operaciones elementales en los renglones, eliminación gaussiana (opcional) A.11 Matrices booleanas (cero-uno) Problemas resueltos Problemas suplementarios

www.FreeLibros.me

337 337 337 340 342 342 344 344 346 348 349 350 351 360

368 368 368 369 370 370 371 371 372 375 377 381 383 389 403

409 409 409 410 411 412 414 414 415 416 418 422 423 429

XIV CONTENIDO

APÉNDICE B

Sistemas algebraicos B.1 Introducción B.2 Operaciones B.3 Semigrupos B.4 Grupos B.5 Subgrupos, subgrupos normales y homomorfismos B.6 Anillos, dominios de integridad y campos B.7 Polinomios sobre un campo Problemas resueltos Problemas suplementarios

ÍNDICE

432 432 432 435 438 440 443 446 450 461

467

www.FreeLibros.me

1

Teoría de conjuntos

CAPÍTULO

1.1

INTRODUCCIÓN

El concepto de conjunto aparece en todas las matemáticas. Por ello es que conviene iniciar este capítulo con la notación y la terminología básicas de la teoría de conjuntos, las cuales se utilizan en todo el texto; el capítulo termina con la definición formal, y ejemplos, de la inducción matemática.

1.2

CONJUNTOS, ELEMENTOS Y SUBCONJUNTOS

Un conjunto es una colección bien definida de objetos, que se denominan elementos o miembros del conjunto. Las letras mayúsculas A, B, X, Y, . . . , denotan conjuntos y las minúsculas a, b, x, y, . . . , denotan elementos de conjuntos. Algunos sinónimos de “conjunto” son “clase”, “colección” y “familia”. La pertenencia a un conjunto se denota: a ∈ S denota que a pertenece al conjunto S. a, b ∈ S denota que a y b pertenecen al conjunto S. Aquí ∈ es el símbolo para indicar “es un elementos de” y ∈ significa “no es un elemento de”.

Especificación de conjuntos Hay dos formas para especificar un conjunto particular. Una forma, de ser posible, consiste en enumerar sus elementos separados por comas y escritos entre llaves { }. La segunda es escribir las propiedades que caracterizan a los elementos del conjunto. Dos ejemplos de lo anterior son: A = {1, 3, 5, 7, 9}

y

B = {x | x es un entero par, x > 0}

Es decir, A consta de los elementos 1, 3, 5, 7, 9. El segundo conjunto se lee: B es el conjunto de x tal que x es un entero par y x es mayor que 0, denota el conjunto B, cuyos elementos son los enteros pares positivos. Observe que para denotar un miembro del conjunto se usa una letra, casi siempre x; la recta vertical | se lee “tal que” y la coma “y”. EJEMPLO 1.1 a) El conjunto A anterior también se escribe como A = {x | x es un entero positivo impar, x < 10}. b) Aunque no es posible listar todos los elementos del conjunto B anterior, a este conjunto se le especifica como B = {2, 4, 6, . . .} donde se supone que todo mundo lo entiende. Observe que 8 ∈ B, pero 3 ∈ B.

1

www.FreeLibros.me

2

CAPÍTULO 1 TEORÍA

DE CONJUNTOS

c) Sean E = {x | x2 − 3x + 2 = 0}, F = {2, 1} y G = {1, 2, 2, 1}. Entonces E = F = G. Aquí es preciso señalar que un conjunto no depende de la forma en que se muestren sus elementos. Un conjunto es el mismo aun si sus elementos se repiten o están en desorden. Incluso si es posible enumerar los elementos de un conjunto, hacerlo tal vez no sea práctico. Es por esto que los elementos de un conjunto se enumeran sólo si son pocos; en caso contrario, un conjunto se describe con la indicación de la propiedad que caracteriza a sus elementos.

Subconjuntos Suponga que todo elemento de un conjunto A también es un elemento de un conjunto B; es decir, si a ∈ A implica que a ∈ B. Entonces se dice que A es un subconjunto de B. También se dice que A está contenido en B o que B contiene a A. Esta relación se escribe A⊆B

o

B⊇A

Dos conjuntos son iguales si ambos tienen los mismos elementos o, equivalentemente, si cada uno está contenido en el otro. Es decir: A  B si y sólo si A ⊆ B y B ⊆ A Si A no es un subconjunto de B —porque al menos un elemento de A no pertenece a B— se escribe A ⊆ B. EJEMPLO 1.2

Considere los conjuntos: A  {1, 3, 4, 7, 8, 9},

B  {1, 2, 3, 4, 5},

C  {1, 3}.

Entonces C ⊆ A y C ⊆ B, ya que 1 y 3, los elementos de C, también son miembros de A y B. Pero B ⊆ A, puesto que algunos elementos de B, por ejemplo, 2 y 5, no pertenecen a A. En forma semejante, A ⊆ B.

Propiedad 1: En matemáticas es una práctica común cruzar un símbolo con una línea vertical “|” o una diagonal “/” para indicar el significado opuesto o negativo del símbolo. Propiedad 2: La declaración A ⊆ B no excluye la posibilidad de que A  B. De hecho, para todo conjunto A se tiene A ⊆ A, ya que todo elemento de A pertenece a A. No obstante, si A ⊆ B y A = B, entonces se dice que A es un subconjunto propio de B (lo que algunas veces se escribe A ⊂ B). Propiedad 3: Suponga que todo elemento de un conjunto A pertenece a un conjunto B y que todo elemento de B pertenece a un conjunto C. Entonces resulta evidente que todo elemento de A también pertenece a C. En otras palabras, si A ⊆ B y B ⊆ C, entonces A ⊆ C. Las propiedades anteriores llevan al siguiente teorema: Teorema 1.1: Sean A, B y C tres conjuntos cualesquiera. Entonces: i) A ⊆ A ii) Si A ⊆ B y B ⊆ A, entonces A = B iii) Si A ⊆ B y A ⊆ B, entonces A ⊆ B

Símbolos especiales En el texto aparecen muy a menudo algunos conjuntos, para los que se usan símbolos especiales. Algunos de estos símbolos son: N = conjunto de números naturales o enteros positivos: 1, 2, 3, . . . Z = conjunto de todos los enteros: . . . , −2, −1, 0, 1, 2, . . . Q = conjunto de números racionales R = conjunto de números reales C = conjunto de números complejos Observe que N ⊆ Z ⊆ Q ⊆ R ⊆ C.

www.FreeLibros.me

1.3 DIAGRAMAS

DE

VENN

3

Conjunto universo y conjunto vacío Todos los conjuntos que se estudian en cualquier aplicación de la teoría de conjuntos pertenecen a un gran conjunto fijo denominado universo, que se denota por U a menos que se establezca o implique otra cosa. Dados un conjunto universo U y una propiedad P, en U puede no haber elementos que tengan la propiedad P. Por ejemplo, el siguiente conjunto no tiene elementos: S = {x | x es un entero positivo, x2 = 3} Un conjunto que no tiene elementos se denomina conjunto vacío o conjunto nulo y se denota por [ Sólo hay un conjunto vacío. Es decir, si S y T son vacíos, entonces S = T, ya que tienen exactamente los mismos elementos, a saber, ninguno. El conjunto vacío [ también se considera como un subconjunto de cualquier otro conjunto. Así, el planteamiento formal de este sencillo resultado es: Teorema 1.2: Para cualquier conjunto A, se tiene [ ⊆ A ⊆ U.

Conjuntos ajenos o disjuntos Dos conjuntos A y B son ajenos o disjuntos, si no tienen elementos en común. Por ejemplo, suponga A  {1, 2}, B  {4, 5, 6} y

C  {5, 6, 7, 8}.

Entonces A y B son ajenos, y A y C son ajenos. Pero B y C no son ajenos porque B y C tienen elementos en común, 5 y 6. Observe que si A y B son ajenos, entonces ninguno es un subconjunto del otro (a menos que uno ...