491
www.elsolucionario.net www.elsolucionario.net

ɷMatematicas discretas (schaum) seymour lipschutz

  • Upload
    quiasma

  • View
    507

  • Download
    55

Embed Size (px)

DESCRIPTION

ɷMatematicas discretas (schaum) seymour lipschutz

Citation preview

  • ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • MATEMTICASDISCRETAS

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

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

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

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 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

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 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

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 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

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

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

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 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

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

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

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 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

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 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

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 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 dirigidos libres de ciclos, ordenacin topolgica 216 9.10 Algoritmo de poda para el camino ms corto 218 Problemas resueltos 221 Problemas suplementarios 228

    CONTENIDO XI

    00_Preliminares_Lipschutz.indd XI00_Preliminares_Lipschutz.indd XI 11/25/08 3:00:34 PM11/25/08 3:00:34 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • XII CONTENIDO

    CAPTULO 10 rboles binarios 235 10.1 Introduccin 235 10.2 rboles binarios 235 10.3 rboles binarios completos y extendidos 237 10.4 Representacin de rboles binarios en la memoria 239 10.5 Recorrido de rboles binarios 240 10.6 rboles binarios de bsqueda 242 10.7 Colas prioritarias, montculos 244 10.8 Longitudes de caminos, algoritmo de Huffman 248 10.9 rboles generales (con raz ordenados), repaso 251 Problemas resueltos 252 Problemas suplementarios 259

    CAPTULO 11 Propiedades de los enteros 264 11.1 Introduccin 264 11.2 Orden y desigualdades, valor absoluto 265 11.3 Induccin matemtica 266 11.4 Algoritmo de la divisin 267 11.5 Divisibilidad, primos 269 11.6 Mximo comn divisor, algoritmo euclidiano 270 11.7 Teorema fundamental de la aritmtica 273 11.8 Relacin de congruencia 274 11.9 Ecuaciones de congruencia 278 Problemas resueltos 283 Problemas suplementarios 299

    CAPTULO 12 Lenguajes, autmatas, gramticas 303 12.1 Introduccin 303 12.2 Alfabeto, palabras, semigrupo libre 303 12.3 Lenguajes 304 12.4 Expresiones regulares, lenguajes regulares 305 12.5 Autmatas de estado finito 306 12.6 Gramticas 310 Problemas resueltos 314 Problemas suplementarios 319

    CAPTULO 13 Mquinas de estados finitos y mquinas de Turing 323 13.1 Introduccin 323 13.2 Mquinas de estados finitos 323 13.3 Nmeros de Gdel 326 13.4 Mquinas de Turing 326 13.5 Funciones computables 330 Problemas resueltos 331 Problemas suplementarios 334

    00_Preliminares_Lipschutz.indd XII00_Preliminares_Lipschutz.indd XII 11/25/08 3:00:35 PM11/25/08 3:00:35 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • CAPTULO 14 Conjuntos ordenados y retculos 337 14.1 Introduccin 337 14.2 Conjuntos ordenados 337 14.3 Diagramas de Hasse de conjuntos parcialmente ordenados 340 14.4 Enumeracin consistente 342 14.5 Supremo e nfimo 342 14.6 Conjuntos ordenados (semejantes) isomorfos 344 14.7 Conjuntos bien ordenados 344 14.8 Retculos 346 14.9 Retculos acotados 348 14.10 Retculos distributivos 349 14.11 Complementos, retculos complementados 350 Problemas resueltos 351 Problemas suplementarios 360

    CAPTULO 15 lgebra booleana 368 15.1 Introduccin 368 15.2 Definiciones bsicas 368 15.3 Dualidad 369 15.4 Teoremas bsicos 370 15.5 lgebras booleanas como retculos 370 15.6 Teorema de representacin 371 15.7 Representacin de conjuntos en forma de suma de productos 371 15.8 Representacin de lgebras booleanas en forma de suma de productos 372 15.9 Expresiones booleanas minimales, implicantes primos 375 15.10 Compuertas y circuitos lgicos 377 15.11 Tablas de verdad, funciones booleanas 381 15.12 Mapas de Karnaugh 383 Problemas resueltos 389 Problemas suplementarios 403

    APNDICE A Vectores y matrices 409 A.1 Introduccin 409 A.2 Vectores 409 A.3 Matrices 410 A.4 Adicin de matrices y multiplicacin por un escalar 411 A.5 Multiplicacin 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, eliminacin gaussiana (opcional) 418 A.11 Matrices booleanas (cero-uno) 422 Problemas resueltos 423 Problemas suplementarios 429

    CONTENIDO XIII

    00_Preliminares_Lipschutz.indd XIII00_Preliminares_Lipschutz.indd XIII 11/25/08 3:00:35 PM11/25/08 3:00:35 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • XIV CONTENIDO

    APNDICE B Sistemas algebraicos 432 B.1 Introduccin 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

    00_Preliminares_Lipschutz.indd XIV00_Preliminares_Lipschutz.indd XIV 11/25/08 3:00:35 PM11/25/08 3:00:35 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 1.1 INTRODUCCINEl concepto de conjunto aparece en todas las matemticas. Por ello es que conviene iniciar este captulo con la notacin y la terminologa bsicas de la teora de conjuntos, las cuales se utilizan en todo el texto; el captulo termina con la definicin formal, y ejemplos, de la induccin matemtica.

    1.2 CONJUNTOS, ELEMENTOS Y SUBCONJUNTOS

    Un conjunto es una coleccin bien definida de objetos, que se denominan elementos o miembros del conjunto. Las letras maysculas A, B, X, Y, . . . , denotan conjuntos y las minsculas a, b, x, y, . . . , denotan elementos de conjuntos. Algunos sinnimos de conjunto son clase, coleccin 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 smbolo para indicar es un elementos de y significa no es un elemento de.

    Especificacin de conjuntosHay 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 elemen-tos 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 con-junto 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 tambin 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 Teora deconjuntos

    1

    CAPTULO

    01_Cap. 1_Lipschutz.indd 101_Cap. 1_Lipschutz.indd 1 11/25/08 3:07:08 PM11/25/08 3:07:08 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 2 CAPTULO 1 TEORA 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 sealar 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 estn en desorden.Incluso si es posible enumerar los elementos de un conjunto, hacerlo tal vez no sea prctico. Es por esto que los elementos de

    un conjunto se enumeran slo si son pocos; en caso contrario, un conjunto se describe con la indicacin de la propiedad que carac-teriza a sus elementos.

    SubconjuntosSuponga que todo elemento de un conjunto A tambin 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. Tambin se dice que A est contenido en B o que B contiene a A. Esta relacin se escribe

    A B o B ADos 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 slo si A B y B ASi 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, tambin son miembros de A y B. Pero B A, puesto que algunos ele-mentos de B, por ejemplo, 2 y 5, no pertenecen a A. En forma semejante, A B.Propiedad 1: En matemticas es una prctica comn cruzar un smbolo con una lnea vertical | o una diagonal / para indicar el significado opuesto o negativo del smbolo.

    Propiedad 2: La declaracin 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 subcon-junto 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 tambin 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

    Smbolos especiales

    En el texto aparecen muy a menudo algunos conjuntos, para los que se usan smbolos especiales. Algunos de estos smbolos son:

    N = conjunto de nmeros naturales o enteros positivos: 1, 2, 3, . . .Z = conjunto de todos los enteros: . . . , 2, 1, 0, 1, 2, . . .Q = conjunto de nmeros racionalesR = conjunto de nmeros realesC = conjunto de nmeros complejos

    Observe que N Z Q R C.

    01_Cap. 1_Lipschutz.indd 201_Cap. 1_Lipschutz.indd 2 11/25/08 3:07:09 PM11/25/08 3:07:09 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • Conjunto universo y conjunto vacoTodos los conjuntos que se estudian en cualquier aplicacin de la teora 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 vaco o conjunto nulo y se denota por[

    Slo hay un conjunto vaco. Es decir, si S y T son vacos, entonces S = T, ya que tienen exactamente los mismos ele-mentos, a saber, ninguno.

    El conjunto vaco [ tambin 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 disjuntosDos conjuntos A y B son ajenos o disjuntos, si no tienen elementos en comn. 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 comn, 5 y 6. Observe que si A y B son ajenos, entonces ninguno es un subconjunto del otro (a menos que uno sea el conjunto vaco).

    1.3 DIAGRAMAS DE VENN

    Un diagrama de Venn es un grfico donde los conjuntos se representan con regiones encerradas en un plano. Aqu el conjunto universo U es el interior de un rectngulo y los otros conjuntos se representan por crculos dentro del rectn-gulo. Si A B, entonces el crculo que representa a A est dentro del crculo que representa a B, como se muestra en la figura 1-1a). Si A y B son ajenos, entonces el crculo que representa a A est separado del crculo que representa a B, como se muestra en la figura 1-1b).

    1.3 DIAGRAMAS DE VENN 3

    Figura 1-1

    b) A y B son ajenos c)

    U

    B A

    U

    B A

    U

    BA

    a) A B

    01_Cap. 1_Lipschutz.indd 301_Cap. 1_Lipschutz.indd 3 11/25/08 3:07:10 PM11/25/08 3:07:10 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 4 CAPTULO 1 TEORA DE CONJUNTOS

    No obstante, si A y B son dos conjuntos arbitrarios, es posible que algunos elementos estn en A pero no en B, que otros estn en B pero no en A, que algunos estn tanto en A como en B, y que otros no estn ni en A ni en B; por tanto, en general A y B se representan como en la figura 1-1c).

    Argumentos y diagramas de Venn

    Muchas declaraciones verbales son, en esencia, sobre conjuntos y, en consecuencia, se les puede describir mediante diagramas de Venn; por tanto, stos sirven para determinar si un argumento es vlido o no.

    EJEMPLO 1.3 Demuestre que el siguiente argumento (una adaptacin de un libro de lgica de Lewis Carroll, autor de Alicia en el pas de las maravillas) es vlido:

    S1: Todos mis objetos de estao son cazos.S2: Encuentro muy tiles todos tus regalos.S3: Ninguno de mis cazos es til.S3: Tus regalos no son de estao.

    Las declaraciones S1, S2 y S3, arriba de la lnea horizontal, son los supuestos o las hiptesis y la declaracin S, abajo de la lnea horizontal, es la conclusin. El argumento es vlido si la conclusin S se obtiene en forma lgica a partir de las hiptesis S1, S2y S3.

    Si S1 son todos los objetos de estao que contiene el conjunto de los cazos, entonces S3, el conjunto de los cazos, y el conjunto de los objetos tiles son ajenos. Adems, por S2, el conjunto de tus regalos es un subconjunto del conjunto de los objetos tiles. En consecuencia, es posible dibujar el diagrama de Venn que se muestra en la figura 1-2.

    Resulta evidente que la conclusin es vlida por el diagrama de Venn, porque el conjunto tus regalos es ajeno al conjunto de los objetos de estao.

    1.4 OPERACIONES CON CONJUNTOS

    En esta seccin se presentan varias operaciones con conjuntos, como son las operaciones bsicas de unin, interseccin y complemento.

    Unin e interseccin

    La unin de dos conjuntos A y B, que se denota por A B, es el conjunto de todos los elementos que pertenecen a A o a B; es decir,

    A B = {x | x A o x B}Aqu o se usa en el sentido incluyente de y/o. La figura 1-3a) es un diagrama de Venn en el que A B est som-breada.

    La interseccin de dos conjuntos A y B, que se denota por A B , es el conjunto de los elementos que pertenecen tanto a A como a B; es decir,

    A B = {x | x A y x B}La figura 1-3b) es un diagrama de Venn en el que A B est sombreada.

    objetos de estao

    cazos

    tus regalos

    objetos tiles

    Figura 1-2

    01_Cap. 1_Lipschutz.indd 401_Cap. 1_Lipschutz.indd 4 11/25/08 3:07:10 PM11/25/08 3:07:10 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • Recuerde que los conjuntos A y B son disjuntos o ajenos si no tienen elementos en comn o, al aplicar la definicin de interseccin, si A B = M, el conjunto vaco. Suponga que

    S = A B y A B = [Entonces S se denomina unin disjunta, o ajena, de A y B.

    EJEMPLO 1.4

    a) Sean A = {1, 2, 3, 4}, B = {3, 4, 5, 6, 7}, C = {2, 3, 8, 9}. Entonces A B = {1, 2, 3, 4, 5, 6, 7}, A C = {1, 2, 3, 4, 8, 9}, B C = {2, 3, 4, 5, 6, 7, 8, 9}, A B = {3, 4}, A C = {2, 3}, B C = {3}.b) Sean U el conjunto de estudiantes en una universidad, M el conjunto de estudiantes varones y F el conjunto de estudiantes

    mujeres. U es la unin disjunta de M y F; es decir,U = M F y M F = [

    Esto se debe a que cualquier estudiante en U est en M o en F, y resulta evidente que ningn estudiante pertenece tanto a M como a F; es decir, M y F son disjuntos.Es necesario observar las siguientes propiedades de la unin y la interseccin.

    Propiedad 1: Todo elemento x en A B pertenece tanto a A como a B; as, x pertenece a A y x pertenece a B. Entonces, A B es un subconjunto de A y de B; a saber,

    A B A y A B BPropiedad 2: Un elemento x pertenece a la unin A B si x pertenece a A o x pertenece a B; as, cualquier elemento en A pertenece a A B, y cualquier elemento en B pertenece a A B. Es decir,

    A A B y B A BEl planteamiento formal de los resultados anteriores es:

    Teorema 1.3: Para dos conjuntos A y B arbitrarios, se tiene: i) A B A A B y ii) A B B A B.

    La operacin de inclusin de conjuntos se relaciona estrechamente con las operaciones de unin e interseccin, como se muestra en el siguiente teorema.

    Teorema 1.4: Las siguientes expresiones son equivalentes: A B, A B = A, A B = B.Este teorema se demuestra en el problema 1.8. Otras condiciones equivalentes tambin se proporcionan en el pro-

    blema 1.31.

    1.4 OPERACIONES CON CONJUNTOS 5

    a) A B est sombreada b) A B est sombreada

    A B A B

    Figura 1-3

    01_Cap. 1_Lipschutz.indd 501_Cap. 1_Lipschutz.indd 5 11/25/08 3:07:11 PM11/25/08 3:07:11 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 6 CAPTULO 1 TEORA DE CONJUNTOS

    Complementos, diferencias y diferencias simtricas

    Recuerde que todos los conjuntos a considerar en un momento particular son subconjuntos de un conjunto universo fijo U. El complemento absoluto o, simplemente, el complemento de un conjunto A, denotado por AC, es el conjunto de elementos que pertenecen a U, pero que no pertenecen a A. Es decir,

    AC = {x | x U, x A}En algunos textos el complemento de A se denota por A o A. La figura 1-4a) es un diagrama de Venn en el que AC est sombreado.

    El complemento relativo de un conjunto B respecto de un conjunto A o, simplemente, la diferencia de A y B, deno-tada por A\B, es el conjunto de elementos que pertenecen a A pero que no pertenecen a B; es decir,

    A\B = {x | x A, x B}El conjunto A\B se lee A menos B. En muchos textos la expresin A\B aparece como A B o como A B. La figura 1-4b) es un diagrama de Venn en el que A\B est sombreada.

    La diferencia simtrica de los conjuntos A y B, denotada por A B, consta de los elementos que pertenecen a A o a B pero no a ambos. Es decir,

    A B = (A B)\(A B) o A B = (A\B) (B\A)La figura 1-4c) es un diagrama de Venn en el que A B est sombreada.EJEMPLO 1.5 Suponga que U = N = {1, 2, 3, . . .} es el conjunto universo. Sean

    A = {1, 2, 3, 4}, B = {3, 4, 5, 6, 7}, C = {2, 3, 8, 9,}, E = {2, 4, 6, . . .}(Aqu E es el conjunto de enteros pares.) Entonces:

    AC = {5, 6, 7, . . .}, BC = {1, 2, 8, 9, 10, . . .}, EC = {1, 3, 5, 7, . . .}Es decir, EC es el conjunto de enteros positivos impares. Tambin:

    A\B = {1, 2}, A\C = {1, 4}, B\C = {4, 5, 6, 7}, A\E = {1, 3},B\A = {5, 6, 7}, C\A = {8, 9}, C\B = {2, 8, 9}, E\A = {6, 8, 10, 12, . . .}.

    Adems:

    A B = (A\B) (B\A) = {1, 2, 5, 6, 7}, B C = {2, 4, 5, 6, 7, 8, 9},A C = (A\C) (B\C) = {1, 4, 8, 9}, A E = {1, 3, 6, 8, 10, . . .}.

    Productos fundamentales

    Considere n conjuntos distintos A1, A2, . . . , An. Un producto fundamental de los conjuntos es un conjunto de la formaA1 A2 . . . An donde Ai = A o Ai = AC

    a) Ac est sombreado b) A\B est sombreada c) A B est sombreada

    Figura 1.4

    01_Cap. 1_Lipschutz.indd 601_Cap. 1_Lipschutz.indd 6 11/25/08 3:07:11 PM11/25/08 3:07:11 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • Observe lo siguiente:

    i) Hay m = 2n de estos productos fundamentales. ii) Cualesquiera dos productos fundamentales arbitrarios son ajenos. iii) El conjunto universo U es la unin de todos los productos fundamentales.

    As, U es la unin disjunta de los productos fundamentales (problema 1.60). Abajo se ilustra una descripcin geomtrica de estos conjuntos.

    EJEMPLO 1.6 La figura 1-5a) es el diagrama de Venn de tres conjuntos A, B, C. A continuacin se enumeran los m = 23 = 8 productos fundamentales de los conjuntos A, B y C:

    P1 = A B C, P3 = A BC C, P5 = AC B C, P7 = AC BC C,P2 = A B CC, P4 = A BC CC, P6 = AC B CC, P8 = AC BC CC.

    Los ocho productos corresponden precisamente a las ocho regiones disjuntas en el diagrama de Venn de los conjuntos A, B, C como se indica con la identificacin de las regiones en la figura 1-5b).

    1.5 LGEBRA DE CONJUNTOS, DUALIDAD 7

    Figura 1-5

    A B

    C

    A B

    C

    P1

    P2

    P3P7

    P5

    P6P4

    P8

    a) b)

    1.5 LGEBRA DE CONJUNTOS, DUALIDADLos conjuntos bajo las operaciones de unin, interseccin y complemento satisfacen varias leyes (identidades) que se presentan en la tabla 1-1. El planteamiento formal es:

    Teorema 1.5: Los conjuntos cumplen las leyes de la tabla 1-1.

    Tabla 1-1 Leyes del lgebra de conjuntosLeyes idempotentes: (1a) A A = A (1b) A A = ALeyes asociativas: (2a) (A B) C = A (B C) (2b) (A B) C = A (B C)Leyes conmutativas: (3a) A B = B A (3b) A B = B ALeyes distributivas: (4a) A (B C) = (A B) (A C) (4b) A (B C) = (A B) (A C)

    Leyes de identidad:(5a) A M = A (5b) A U = A(6a) A U = U (6b) A M = M

    Leyes de involucin: (7a) (AC)C = A

    Leyes de complementos:(8a) A AC = U (8b) A AC = M(9a) UC = M (9b) MC = U

    Leyes de De Morgan: (10a) (A B)C = AC BC (10b) (A B)C = AC BC

    01_Cap. 1_Lipschutz.indd 701_Cap. 1_Lipschutz.indd 7 11/25/08 3:07:17 PM11/25/08 3:07:17 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 8 CAPTULO 1 TEORA DE CONJUNTOS

    Observacin: Cada ley en la tabla 1-1 se deduce a partir de una ley lgica equivalente. Considere, por ejemplo, la demostracin de la ley de De Morgan (10a):

    (A B)C {x | x / (A o B)} {x | x / A y x / B} = AC BCAqu se usa la ley lgica equivalente (de De Morgan):

    (p q) = p qdonde significa no, significa o y significa y. (Algunas veces se usan diagramas de Venn para ilustrar las leyes de la tabla 1-1, como en el problema 1.17.)

    Dualidad

    Las identidades en la tabla 1-1 estn dispuestas por pares, por ejemplo (2a) y (2b). A continuacin se abordar el prin-cipio que est detrs de esta disposicin. Suponga que E es una ecuacin de lgebra de conjuntos. El dual E* de E es la ecuacin que se obtiene al sustituir cada aparicin de , , U y M en E por , , M y U, respectivamente. Por ejemplo, el dual de

    (U A) (B A) = A es (M A) (B A) = AObserve que los pares de leyes en la tabla 1-1 son duales entre s. Se trata de un hecho del lgebra de conjuntos que se denomina principio de dualidad: si cualquier ecuacin E es una identidad, entonces su dual E* tambin es una identi-dad.

    1.6 CONJUNTOS FINITOS Y PRINCIPIO DE CONTEO

    Los conjuntos son finitos o infinitos. Se dice que un conjunto S es finito si S es vaco o contiene exactamente m ele-mentos, donde m es un entero positivo; en caso contrario, S es infinito.

    EJEMPLO 1.7

    a) El conjunto A de las letras del alfabeto espaol y el conjunto D de los das de la semana son conjuntos finitos. En especfico, A tiene 29 elementos y D tiene 7 elementos.

    b) Sea E el conjunto de enteros positivos pares, y sea I el intervalo unitario; es decir,

    E = {2, 4, 6, . . .} e I = [0, 1] = {x | 0 x 1} As, tanto E como I son infinitos.

    Un conjunto S es numerable si S es finito o si es posible disponer los elementos de S como una sucesin, en cuyo caso se dice que S es infinito numerable; en caso contrario, se dice que S es no numerable. El conjunto E anterior de enteros positivos pares es infinito numerable, mientras es posible demostrar que el intervalo unitario I = [0, 1] es no numerable.

    Conteo de elementos en conjuntos finitosLa notacin n(S) o | S | denota el nmero de elementos en un conjunto S. (En algunos textos se usa #(S) o card(S) en lugar de n(S).) As, n(A) = 26, donde A es el conjunto de letras del alfabeto espaol, y n(D) = 7, donde D es el con-junto de das de la semana. Tambin, n(M) = 0, ya que el conjunto vaco no tiene elementos.

    El siguiente lema es vlido.

    Lema 1.6: Suponga que A y B son conjuntos finitos ajenos. Entonces A B es finito yn(A B) = n(A) + n(B)

    Este lema se replantea como:

    Lema 1.6: Suponga que S es la unin disjunta de los conjuntos finitos A y B. Entonces S es finito y n(S) = n(A) + n(B)

    01_Cap. 1_Lipschutz.indd 801_Cap. 1_Lipschutz.indd 8 11/25/08 3:07:19 PM11/25/08 3:07:19 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • Demostracin. Al contar los elementos de A B, primero se cuentan los que estn en A. De stos hay n(A). Los nicos elementos por contar de A B son los que estn en B pero no en A. Pero como A y B son ajenos, ningn elemento de B est en A, de modo que hay n(B) elementos que estn en B pero no en A. En consecuencia, n(A B) = n(A) + n(B).

    Para dos conjuntos arbitrarios A y B, el conjunto A es la unin disjunta de A\B y A B. As, el lema 1.6 proporcio-na el siguiente resultado til.

    Corolario 1.7: Sean A y B conjuntos finitos. Entoncesn(A\B) = n(A) n(A B)

    Por ejemplo, suponga que en un curso de arte A hay 25 estudiantes, de los cuales 10 llevan un curso B de biologa. Entonces el nmero de estudiantes en el curso A que no estn en el curso B es:

    n(A\B) = n(A) n(A B) = 25 10 = 15Dado cualquier conjunto A, recuerde que el conjunto universo U es la unin disjunta de A y AC. En consecuencia,

    el lema 1.6 tambin proporciona el siguiente resultado.

    Corolario 1.8: Sea A un subconjunto de un conjunto universo U. Entonces

    n(AC) = n(U) n(A)Por ejemplo, suponga que en un curso U con 30 estudiantes hay 18 estudiantes de tiempo completo. Entonces en el curso U hay 30 18 = 12 estudiantes de tiempo parcial.

    Principio de inclusin-exclusin

    Hay una frmula para n(A B) aun cuando A y B no son disjuntos, la cual se denomina principio de inclusin-exclu-sin. A saber:

    Teorema (principio de inclusin-exclusin) 1.9: Suponga que A y B son conjuntos finitos. Entonces A B y A B son finitos y

    n(A B) = n(A) + n(B) n(A B)Es decir, el nmero de elementos en A o en B (o en ambos) se encuentra, primero, al sumar n(A) y n(B) (inclusin) y luego al restar n(A B) (exclusin), ya que sus elementos se contaron dos veces.

    Este resultado se aplica con el fin de obtener una frmula semejante para tres conjuntos:Corolario 1.10: Suponga que A, B y C son conjuntos finitos. Entonces A B C es finito y

    n(A B C) = n(A) + n(B) + n(C) n(A B) n(A C) n(B C) + n(A B C)Para generalizar an ms este resultado a cualquier nmero de conjuntos finitos se aplica la induccin matemtica (seccin 1.8).

    EJEMPLO 1.8 Suponga que una lista A contiene los 30 estudiantes de un curso de matemticas, y otra lista B contiene los 35 estudiantes de un curso de ingls, y que en ambas listas hay 20 nombres. Encuentre el nmero de estudiantes a) slo en la lista A (es decir slo toman clase de matemticas), b) slo en la lista B (es decir, slo toman clase de ingls), c) en la lista A o en la lista B (o en ambas), d ) exactamente en una lista (es decir, slo estudian matemticas o slo estudian ingls).a) La lista A contiene 30 nombres, 20 de ellos estn en la lista B; as, 30 20 = 10 nombres estn slo en la lista A.b) De manera semejante, 35 20 = 15 nombres estn slo en la lista B.c) Se busca n(A B). Por el principio de inclusin-exclusin,

    n(A B) = n(A) + n(B) n(A B) = 30 + 35 20 = 45. En otras palabras, se combinan las dos listas y luego se eliminan los 20 nombres que aparecen dos veces.

    d ) Por los incisos a) y b), 10 + 15 = 25 nombres estn slo en una lista; es decir, n(A B) = 25.

    1.6 CONJUNTOS FINITOS Y PRINCIPIO DE CONTEO 9

    01_Cap. 1_Lipschutz.indd 901_Cap. 1_Lipschutz.indd 9 11/25/08 3:07:20 PM11/25/08 3:07:20 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 10 CAPTULO 1 TEORA DE CONJUNTOS

    1.7 CLASES DE CONJUNTOS, CONJUNTOS POTENCIAY PARTICIONES

    Dado un conjunto S, quiz considere conveniente decir algo sobre algunos de sus subconjuntos. Entonces S sera un conjunto de conjuntos. Sin embargo, siempre que ocurra una situacin as y para evitar confusin, se hablar de una clase de conjuntos o una coleccin de conjuntos, en lugar de un conjunto de conjuntos. Si se quiere considerar algunos de los conjuntos en una clase de conjuntos dada, entonces se habla de una subclase o subcoleccin.

    EJEMPLO 1.9 Suponga que S = {1, 2, 3, 4}.

    a) Sea A la clase de subconjuntos de S que contiene exactamente tres elementos de S. EntoncesA = [{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}]

    Es decir, los elementos de A son los conjuntos {1, 2, 3}, {1, 2, 4}, {1, 3, 4} y {2, 3, 4}.b) Sea B la clase de subconjuntos de S, donde cada uno contiene al 2 y a otros dos elementos de S. Entonces

    B = [{1, 2, 3}, {1, 2, 4}, {2, 3, 4}] Los elementos de B son los conjuntos {1, 2, 3}, {1, 2, 4} y {2, 3, 4}. As, B es una subclase de A, ya que cada elemento de B

    tambin es un elemento de A. (Para evitar confusiones, algunas veces los conjuntos de una clase se escriben entre corchetes, en lugar de hacerlo entre llaves.)

    Conjuntos potenciaPara un conjunto S dado, es posible hablar de la clase de todos los subconjuntos de S. Esta clase se denomina conjun-to potencia de S y se denota P(S). Si S es finito, entonces tambin P(S) lo es. De hecho, el nmero de elementos en P(S) es igual a 2 elevado a la potencia n(S). Es decir,

    n(P (S)) = 2n(S)(Debido a lo anterior, el conjunto potencia de S algunas veces se denota por 2S.)

    EJEMPLO 1.10 Suponga que S = {1, 2, 3}. EntoncesP(S) = [M, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, S]

    Observe que el conjunto vaco M pertenece a P(S), ya que M es un subconjunto de S. En forma semejante, S pertenece a P(S). Como era de esperar, con base en la observacin anterior, P(S) tiene 23 = 8 elementos.

    Particiones

    Sea S un conjunto no vaco. Una particin de S es una subdivisin de S en subconjuntos no vacos que no se traslapan. Con ms precisin, una particin de S es una coleccin {Ai} de subconjuntos no vacos de S tal que:

    i) Cada a en S pertenece a uno de los Ai. ii) Los conjuntos {Ai} son mutuamente ajenos; es decir, si

    Aj = Ak entonces Aj Ak = MEn una particin los subconjuntos se denominan celdas. La figura 1-6 es un diagrama de Venn de una particin del

    conjunto rectangular S en cinco celdas, A1, A2, A3, A4, A5.

    01_Cap. 1_Lipschutz.indd 1001_Cap. 1_Lipschutz.indd 10 11/25/08 3:07:24 PM11/25/08 3:07:24 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • EJEMPLO 1.11 Considere las siguientes colecciones de subconjuntos de S = {1, 2, . . . , 8, 9}:

    i) [{1, 3, 5}, {2, 6}, {4, 8, 9}] ii) [{1, 3, 5}, {2, 4, 6, 8}, {5, 7, 9}] iii) [{1, 3, 5}, {2, 4, 6, 8}, {7, 9}]

    Entonces i) no es una particin de S puesto que 7 est en S y no pertenece a ninguno de los subconjuntos. Adems, ii) no es una particin de S puesto que {1, 3, 5} y {5, 7, 9} no son ajenos. Por otra parte, iii) es una particin de S.

    Operaciones generalizadas con conjuntosLas operaciones de unin e interseccin de conjuntos ya se definieron para dos conjuntos. Estas operaciones se extien-den a cualquier nmero de conjuntos, finitos o infinitos, como sigue.

    Primero considere un nmero finito de conjuntos; por ejemplo, A1, A2, . . . , Am. La unin y la interseccin de estos conjuntos se denotan y definen, respectivamente, por A1 A2 . . . Am =mi=1 Ai = {x | x Ai para algn Ai} A1 A2 . . . Am =mi=1 Ai = {x | x Ai para todo Ai}Es decir, la unin consta de los elementos que pertenecen, por lo menos, a uno de los conjuntos, y la interseccin consta de los elementos que pertenecen a todos los conjuntos.

    Ahora, sea A cualquier coleccin de conjuntos. La unin y la interseccin de los conjuntos en la coleccin A se denotan y definen, respectivamente, por

    (A|A A ) = {x | x Ai para algn Ai A }

    (A|A A ) = {x | x Ai para todo Ai A }

    Es decir, la unin consta de los elementos que pertenecen por lo menos a uno de los conjuntos en la coleccin A, y la interseccin consta de los elementos que pertenecen a cada uno de los conjuntos en la coleccin A.

    EJEMPLO 1.12 Considere los conjuntos

    A1 = {1, 2, 3, . . .} = N, A2 = {2, 3, 4, . . .}, A3 = {3, 4, 5, . . .}, An = {n, n + 1, n + 2, . . .}.

    Entonces la unin y la interseccin de los conjuntos son:

    (Ak | k N) = N y

    (Ak | k N) = MLas leyes de De Morgan tambin se cumplen para las operaciones generalizadas con los conjuntos anteriores. Es decir:Teorema 1.11: Sea A una coleccin de conjuntos. Entonces:

    i) [ (A |A A )]C = (AC |A A ) ii) [ (A |A A )]C = (AC |A A )

    1.7 CLASES DE CONJUNTOS, CONJUNTOS POTENCIA Y PARTICIONES 11

    A1

    A4

    A2

    A5

    A3

    Figura 1-6

    01_Cap. 1_Lipschutz.indd 1101_Cap. 1_Lipschutz.indd 11 11/25/08 3:07:26 PM11/25/08 3:07:26 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 12 CAPTULO 1 TEORA DE CONJUNTOS

    1.8 INDUCCIN MATEMTICAA continuacin se presenta una propiedad esencial del conjunto N = {1, 2, 3, . . .} de enteros positivos: Principio de induccin matemtica I: Sea P una proposicin definida acerca de los enteros positivos N; es decir, P(n) es verdadera o falsa para cualquier n N. Suponga que P tiene las dos propiedades siguientes:

    i) P(1) es verdadera. ii) P(k + 1) es verdadera siempre que P(k) es verdadera.

    Entonces P es verdadera para todo entero positivo n N.Aqu no se demostrar este principio. De hecho, este principio suele aparecer como uno de los axiomas cuando N

    se desarrolla a partir de axiomas.

    EJEMPLO 1.13 Sea P la proposicin de que la suma de los n primeros nmeros impares es igual a n2; es decir,

    P(n) : 1 + 3 + 5 + + (2n 1) = n2

    (El k-simo nmero impar es 2k 1, y el siguiente nmero impar es 2k + 1.) Observe que P(n) es verdadera para n = 1; a saber,

    P(1) = 12

    Si se considera que P(k) es verdadera, y se suma 2k + 1 a ambos miembros de P(k), se obtiene

    1 + 3 + 5 + + (2k 1) + (2k + 1) k2 + (2k + 1) = (k + 1)2

    que es P(k + 1). En otras palabras, P(k + 1) es verdadera siempre que P(k) es verdadera. Por el principio de induccin matemtica, P es verdadera para todo n.

    Hay una forma del principio de induccin matemtica que es ms conveniente utilizar algunas veces. Aunque parece diferente, en realidad es equivalente al principio de induccin anterior.

    Principio de induccin matemtica II: Sea P una proposicin definida sobre los enteros positivos N tal que: i) P(1) es verdadera. ii) P(k) es verdadera siempre que P( j ) sea verdadera para todo 1 j < k.

    Entonces P es verdadera para todo entero positivo n N.Observacin: Algunas veces es necesario demostrar que una proposicin P es verdadera para el conjunto de enteros

    {a, a + 1, a + 2, a + 3, . . .}donde a es cualquier entero, incluso cero. En este caso se reemplaza 1 por a en cualquiera de los principios de induccin matemtica anteriores.

    PROBLEMAS RESUELTOS

    CONJUNTOS Y SUBCONJUNTOS

    1.1 Cules de los siguientes conjuntos son iguales {x, y, z}, {z, y, z, x}, {y, x, y, z}, {y, z, x, y}?Todos son iguales. El orden y la repeticin de los elementos no modifican un conjunto.

    1.2 Enumere los elementos de cada conjunto donde N = {1, 2, 3, . . .}.a) A = {x N | 3 < x < 9}b) B = {x N | x es par, x < 11}

    01_Cap. 1_Lipschutz.indd 1201_Cap. 1_Lipschutz.indd 12 11/25/08 3:07:32 PM11/25/08 3:07:32 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • c) C = {x N | 4 + x = 3}a) A consta de los enteros positivos entre 3 y 9; por tanto, A = {4, 5, 6, 7, 8}.b) B consta de los enteros positivos pares menores que 11; por tanto, B = {2, 4, 6, 8, 10}.c) Ningn entero positivo satisface 4 + x = 3; por tanto, C = M, el conjunto vaco.

    1.3 Sea A = {2, 3, 4, 5}a) Demuestre que A no es un subconjunto de B = {x N | x es par}.b) Demuestre que A es un subconjunto propio de C = {1, 2, 3, . . . , 8, 9}.a) Es necesario demostrar que por lo menos un elemento en A no pertenece a B. Luego, 3 A y, puesto que B consta de

    los nmeros pares, 3 A; por tanto, A no es un subconjunto de B.b) Cada elemento de A pertenece a C, por lo que A C. Por otra parte, 1 C pero 1 A. As, A = C. En consecuencia,

    A es un subconjunto propio de C.

    OPERACIONES CON CONJUNTOS

    1.4 Sea U = {1, 2, . . . , 9} el conjunto universo, y seaA = {1, 2, 3, 4, 5}, C = {5, 6, 7, 8, 9}, E = {2, 4, 6, 8},B = {4, 5, 6, 7}, D = {1, 3, 5, 7, 9}, F = {1, 5, 9}.

    Encuentre: a) A B y A B; b) A C y A C; c) D F y D F.Recuerde que la unin X Y consta de los elementos que estn en X o en Y (o en ambos), y que la interseccin X Y consta de los elementos que estn tanto en X como en Y.

    a) A B = {1, 2, 3, 4, 5, 6, 7} y A B = {4, 5}b) A C = {1, 2, 3, 4, 5, 6, 7, 8, 9} = U y A C = {5}c) D F = {1, 3, 5, 7, 9} = D y D F = {1, 5, 9} = F

    Observe que F D, de modo que por el teorema 1.4 debe tenerse D F = D y D F = F.

    1.5 Considere los conjuntos en el problema 1.4. Encuentre:a) AC, BC, DC, EC; b) A\B, B\A, D\E; c) A B, C D, E F.Recuerde que:1) Los complementos X C constan de los elementos en U que no pertenecen a X.2) La diferencia X \Y consta de los elementos en X que no pertenecen a Y.3) La diferencia simtrica X Y consta de los elementos que estn en X o en Y pero no en ambos.En consecuencia:

    a) AC = {6, 7, 8, 9}; BC = {1, 2, 3, 8, 9}; DC = {2, 4, 6, 8} = E; EC = {1, 3, 5, 7, 9} = D.b) A\B = {1, 2, 3}; B\A = {6, 7}; D\E = {1, 3, 5, 7, 9} = D; F\D =M .c) A B = {1, 2, 3, 6, 7}; C D = {1, 3, 6, 8}; E F = {2, 4, 6, 8, 1, 5, 9} = E F .

    1.6 Demuestre que puede cumplirse: a) A B = A C sin que B = C; b) A B = A C sin que B = C.a) Sea A = {1, 2}, B = {2, 3}, C = {2, 4}. Entonces A B = {2} y A C = {2}; pero B = C.b) Sea A = {1, 2}, B = {1, 3}, C = {2, 3}. Entonces A B = {1, 2, 3} y A C = {1, 2, 3}; pero B = C.

    1.7 Demuestre: B\A = B AC. As, la operacin de la diferencia en conjuntos se escribe en trminos de las opera-ciones de interseccin y complemento.

    B\A = {x | x B, x / A} = {x | x B, x AC} = B AC.

    PROBLEMAS RESUELTOS 13

    01_Cap. 1_Lipschutz.indd 1301_Cap. 1_Lipschutz.indd 13 11/25/08 3:07:33 PM11/25/08 3:07:33 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 14 CAPTULO 1 TEORA DE CONJUNTOS

    1.8 Demuestre el teorema 1.4. Las siguientes expresiones son equivalentes: A B, A B = A, A B = B.Suponga que A B y sea x A. Entonces x B, por tanto x A B y A A B. Por el teorema 1.3, (A B) A; en consecuencia, A B = A. Por otra parte, suponga A B = A y sea x A. Entonces x (A B), por tanto, x A y x B. En consecuencia, A B. Ambos resultados muestran que A B es equivalente a A B = A.Suponga de nuevo que A B. Sea x (A B). Entonces x A o x B. Si x A, entonces x B, porque A B. En cualquier caso, x B. Por consiguiente, A B B. Por el teorema 1.3, B A B. En consecuencia, A B = B. Ahora suponga que A B = B y que x A. Entonces x A B por la definicin de unin de conjuntos. As, x B = A B. Por consiguiente, A B. Ambos resultados muestran que A B es equivalente a A B = B.Por tanto, A B, A B = A y A B = B son equivalentes.

    DIAGRAMAS DE VENN, LGEBRA DE CONJUNTOS Y DUALIDAD

    1.9 Ilustre la ley de De Morgan (A B)C = AC BC mediante diagramas de Venn.En un diagrama de Venn de los conjuntos A a B se sombrea la regin fuera de A B. Esto se muestra en la figura 1-7a); por tanto, la regin sombreada representa (A B)C. Luego, en un diagrama de Venn de A y B se sombrea la regin fuera de A con lneas diagonales en un sentido (////) y luego se sombrea la regin fuera de B con lneas diagonales en otro sentido (\\\\). Esto se muestra en la figura 1-7b); por tanto, la regin sombreada como cuadrcula (regin donde estn presentes ambos tipos de lneas diagonales) representa AC BC. Tanto (A B)C como AC BC estn representadas por la misma regin; as, el diagrama de Venn indica (A B)C = AC BC. (Cabe sealar que un diagrama de Venn no constituye una demostracin formal, aunque indica relaciones entre conjuntos.)

    1.10 Demuestre la ley distributiva: A (B C) = (A B) (A C).A (B C)= {x | x A, x (B C)}

    = {x | x A, x B o x A, x C} = (A B) (A C)Aqu se usa la ley lgica anloga p (q r) (p q) (p r) donde denota y y denota o.

    1.11 Escriba el dual de: a) (U A) (B A) = A; b) (A U) (M AC) = M.En cada ecuacin de conjuntos se intercambian y , as como U y M:a) (M A) (B A) = A; b) (A M) (U AC) = U.

    1.12 Demuestre: (A B)\(A B) = (A\B) (B\A). (As, cualquiera puede usarse para definir B A.)Al usar X \Y) = X Y C y las leyes en la tabla 1.1, junto con la ley de De Morgan, se obtiene

    (A B)\(A B)= (A B) (A B)C = (A B) )AC BC)= (A AC) (A BC) (B AC) (B BC)=M (A BC) (B AC) M= (A BC) (B AC) = (A\B) (B\A)

    Figura 1-7

    a)

    A B A B

    b)

    01_Cap. 1_Lipschutz.indd 1401_Cap. 1_Lipschutz.indd 14 11/25/08 3:07:36 PM11/25/08 3:07:36 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 1.13 Determine la validez del siguiente argumento:

    S1: Todos mis amigos son msicos.S2: Juan es mi amigo.S3: Ninguno de mis vecinos es msico.S3: Juan no es mi vecino.

    Las premisas S1 y S3 conducen al diagrama de Venn en la figura 1-8a). Por S2 Juan pertenece al conjunto de amigos que es ajeno del conjunto de vecinos. Por tanto, S es una conclusin vlida y as el argumento es vlido.

    PROBLEMAS RESUELTOS 15

    CONJUNTOS FINITOS Y PRINCIPIO DEL CONTEO

    1.14 En una universidad cada estudiante de humanidades debe acreditar un curso A de matemticas y un curso B de ciencias. En una muestra de 140 estudiantes de segundo ao se observ lo siguiente: 60 acreditaron A, 45 acreditaron B, 20 acreditaron tanto A como B.Use un diagrama de Venn para determinar el nmero de estudiantes que acreditaron:

    a) Por lo menos uno de A y B; b) exactamente uno de A o B; c) ni A ni B.Al escribir los datos anteriores en notacin de conjuntos se obtiene:

    n(A) = 60, n(B) = 45, n(A B) = 20, n(U) = 140Se dibuja un diagrama de Venn de los conjuntos A y B como en la figura 1-1c). Luego, como en la figura 1-8b), se asignan nmeros a las cuatro regiones:

    20 acreditaron tanto A como B, de modo que n(A B) = 20.60 20 = 40 acreditaron A pero no B, por lo que n(A\B) = 40.45 20 = 25 acreditaron B pero no A, por lo que n(B\A) = 25.140 20 40 25 = 55 no acreditaron A ni B.

    Por el diagrama de Venn:

    a) 20 + 40 + 25 = 85 acreditaron A o B.Ahora, por el principio de inclusin-exclusin:n(A B) = n(A) + n(B) n(A B) = 60 + 45 20 = 85

    b) 40 + 25 = 65 acreditaron exactamente uno de los cursos. Es decir, n(A B) = 65.c) 55 no acreditaron ninguno de los cursos; es decir, n(AC BC) = n[(A B)C] = 140 85 = 55.

    1.15 En una encuesta aplicada a 120 personas se encontr que:

    65 leen Newsweek, 20 leen tanto Newsweek como Time,45 leen Time, 25 leen tanto Newsweek como Fortune,42 leen Fortune, 15 leen tanto Time como Fortune. 8 leen las tres publicaciones.

    msicos

    a) b)

    A B

    40 20 2555

    amigos vecinos

    Figura 1-8

    01_Cap. 1_Lipschutz.indd 1501_Cap. 1_Lipschutz.indd 15 11/25/08 3:07:36 PM11/25/08 3:07:36 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 16 CAPTULO 1 TEORA DE CONJUNTOS

    a) Encuentre el nmero de personas que leen por lo menos una de las tres publicaciones.b) En cada una de las ocho regiones del diagrama de Venn de la figura 1-9a) se escribe el nmero correcto de

    personas, donde N, T y F denotan el conjunto de personas que leen Newsweek, Time y Fortune, respecti-vamente.

    c) Encuentre el nmero de personas que leen exactamente una publicacin.

    a) Se quiere encontrar n(N T F). Por el corolario 1.10 (principio de inclusin-exclusin),n( N T F ) = n( N ) + n(T ) + n( F ) n( N T ) n( N F ) n( T F ) + n( N T F )

    = 65 + 45 + 42 20 25 15 + 8 = 100 b) El diagrama de Venn de la figura 1-9b) se obtiene como sigue:

    8 leen las tres publicaciones,

    20 8 = 12 leen Newsweek y Time pero no las tres publicaciones,25 8 = 17 leen Newsweek y Fortune pero no las tres publicaciones,15 8 = 7 leen Time y Fortune pero no las tres publicaciones,65 12 8 17 = 28 slo leen Newsweek,45 12 8 7 = 18 slo leen Time,42 17 8 7 = 10 slo leen Fortune,120 100 = 20 no leen ninguna publicacin.

    c) 28 + 18 + 10 = 56 leen exactamente una publicacin.

    1.16 Demuestre el teorema 1.9. Suponemos que A y B son conjuntos finitos. Entonces A B y A B son finitos yn(A B) = n(A) + n(B) n(A B)

    Si A y B son finitos, entonces resulta evidente que A B y A B son finitos.Suponemos que primero se cuentan los elementos en A y despus los elementos en B.

    Entonces cualquier elemento en A B se contara dos veces, una en A y otra en B. As,n(A B) = n(A) + n(B) n(A B)

    a)

    N T

    F

    b)

    N T

    F10

    20

    18828

    12

    17 7

    Figura 1-9

    01_Cap. 1_Lipschutz.indd 1601_Cap. 1_Lipschutz.indd 16 11/25/08 3:07:37 PM11/25/08 3:07:37 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • CLASES DE CONJUNTOS

    1.17 Sea A = [{1, 2, 3}, {4, 5}, {6, 7, 8}]. a) Enumere los elementos de A; b) encuentre n(A).a) A tiene tres elementos; los conjuntos {1, 2, 3}, {4, 5} y {6, 7, 8}.b) n(A) = 3.

    1.18 Determine el conjunto potencia P(A) de A = {a, b, c, d}.Los elementos de P(A) son los subconjuntos de A. As,

    P(A) = [A, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d},{c, d}, {a}, {b}, {c}, {d}, ]

    Como era de esperar, P(A) tiene 24 = 16 elementos.

    1.19 Sea S = {a, b, c, d, e, f, g}. Determine cules de las siguientes particiones son de S:a) P1 = [{a, c, e}, {b}, {d, g}], c) P3 = [{a, b, e, g}, {c}, {d, f }],b) P2 = [{a, e, g}, {c, d}, {b, e, f }], d) P4 = [{a, b, c, d, e, f , g}].

    a) P1 no es una particin de S, puesto que f S no pertenece a ninguna de las celdas.b) P2 no es una particin de S, puesto que e S pertenece a dos de las celdas.c) P3 es una particin de S, puesto que cada elemento en S pertenece exactamente a una celda.d) P4 es una particin de S en una celda, S mismo.

    1.20 Encuentre todas las particiones de S = {a, b, c, d }.Primero observe que cada particin de S contiene 1, 2, 3 o 4 celdas distintas. Las particiones son como sigue:

    1) [{a, b, c, d}]2) [{a}, {b, c, d}], [{b}, {a, c, d}], [{c}, {a, b, d}], [{d}, {a, b, c}], [{a, b}, {c, d}], [{a, c}, {b, d}], [{a, d}, {b, c}]3) [{a}, {b}, {c, d}], [{a}, {c}, {b, d}], [{a}, {d}, {b, c}], [{b}, {c}, {a, d}], [{b}, {d}, {a, c}], [{c}, {d}, {a, b}]4) [{a}, {b}, {c}, {d}]Hay 15 particiones distintas de S.

    1.21 Sea N = {1, 2, 3, . . .} y, para cada n N. Sea An = {n, 2n, 3n, . . .}. Encuentre:a) A3 A5; b) A4 A5; c) iQAi donde Q = {2, 3, 5, 7, 11, . . . ,} es el conjunto de nmeros primos.a) Los nmeros que son mltiplos tanto de 3 como de 5 son mltiplos de 15; por tanto, A3 A5 = A15.b) Los elementos comunes a A4 y A6 son los mltiplos de 12; por tanto, A4 A6 = A12.c) Todo entero positivo excepto 1 es mltiplo de por lo menos un nmero primo; por tanto,

    iQAi = {2, 3, 4, . . .} = N\{1}

    1.22 Sea {Ai | i I } una clase indexada de conjuntos y sea i0 I. Demuestre

    iIAi Ai0

    iIAi.

    Sea x iI Ai, entonces x Ai para todo i I. En particular, x Ai0. Por tanto, il Ai Ai0. Ahora sea y Ai0. Puesto que i0 I, y il Ai. Entonces Ai0 il Ai.

    PROBLEMAS RESUELTOS 17

    01_Cap. 1_Lipschutz.indd 1701_Cap. 1_Lipschutz.indd 17 11/25/08 3:07:38 PM11/25/08 3:07:38 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 18 CAPTULO 1 TEORA DE CONJUNTOS

    1.23 Demuestre (ley de De Morgan): Para cualquier clase indexada {Ai | i I }, se tiene (

    i Ai)C =i ACi .

    Al usar las definiciones de unin e interseccin de clases indexadas de conjuntos:(

    iAi)C = {x | x /

    iAi} = {x | x / Ai para toda i}

    = {x | x ACi para toda i} =

    iACi

    INDUCCIN MATEMTICA

    1.24 Demuestre la proposicin P(n) de que la suma de los primeros n enteros positivos es igual a 12n(n + 1), es decir P(n) = 1 + 2 + 3 + + n = 12n(n + 1)La proposicin se cumple para n = 1, ya que:

    P(1) : 1 = 12 (1)(1 + 1) Si se acepta que P(k) es verdadera, y se suma k + 1 a ambos miembros de P(k) se obtiene

    1 + 2 + 3 + + k + (k + 1)= 12k(k + 1) + (k + 1)= 12 [k(k + 1) + 2(k + 1)]= 12 [(k + 1)(k + 2)]

    que es P(k + 1). Es decir, P(k + 1) es verdadera siempre que P(k) es verdadera. Por el principio de induccin, P(n) es verdadera para toda n.

    1.25 Demuestre la siguiente proposicin (para n 0): P(n) : 1 + 2 + 22 + 23 + + 2n = 2n+1 1P(0) es verdadera porque 1 = 21 1. Si se acepta que P(k) es verdadera, y se suma 2k+1 a ambos miembros de P(k) se obtiene

    1 + 2 + 22 + 23 + + 2k + 2k+1 = 2k+1 1 + 2k+1 = 2(2k+1) 1 = 2k+2 1que es P(k + 1). Es decir, P(k + 1) es verdadera siempre que P(k) es verdadera. Por el principio de induccin, P(n) es verdadera para toda n.

    PROBLEMAS SUPLEMENTARIOS

    CONJUNTOS Y SUBCONJUNTOS

    1.26 Cules de los siguientes conjuntos son iguales? A = {x | x2 4x + 3 = 0}, C = {x | x N, x < 3}, E = {1, 2}, G = {3, 1},

    B = {x | x2 3x + 2 = 0}, D = {x | x N, x es impar, x < 5}, F = {1, 2, 1}, H = {1, 1, 3}.

    1.27 Enumere los elementos de los siguientes conjuntos si el conjunto universo es U = {a, b, c, . . . , y, z}Adems, identifique cules de los conjuntos, en caso de haber algunos, son iguales. A = {x | x es una vocal}, C = {x| x precede a f en el alfabeto}, B = {x | x es una letra de la palabra little}, D = {x | x es una letra de la palabra title}.

    1.28 Sea A = {1, 2, . . . , 8, 9}, B = {2, 4, 6, 8}, C = {1, 3, 5, 7, 9}, D = {3, 4, 5}, E = {3, 5}.Cules de esos conjuntos pueden ser iguales a X bajo cada una de las siguientes condiciones?a) X y B son ajenos. c) X A pero X C.b) X D pero X B. d ) X C pero X A.

    01_Cap. 1_Lipschutz.indd 1801_Cap. 1_Lipschutz.indd 18 11/25/08 3:07:41 PM11/25/08 3:07:41 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • OPERACIONES CON CONJUNTOS

    1.29 Dados el conjunto universo U = {1, 2, 3, . . . , 8, 9} y los conjuntos A = {1, 2, 5, 6}, B = {2, 5, 7}, C = {1, 3, 5, 7, 9}. Encuentre:

    a) A B y A C c) AC y C C e) A B y A Cb) A B y B C d ) A\B y A\C f ) (A C )\B y (B C )\A

    1.30 Sean A y B conjuntos arbitrarios. Demuestre lo siguiente:a) A es la unin disjunta de A\B y A B.b) A B es la unin disjunta de A\B, A B y B\A.

    1.31 Demuestre lo siguiente:

    a) A B si y slo si A BC = M c) A B si y slo si BC ACb) A B si y slo si AC B = U d ) A B si y slo si A\B = M(Compare los resultados con el teorema 1.4.)

    1.32 Demuestre las leyes de absorcin: a) A (A B) = A; b) A (A B) = A.

    1.33 La frmula A\B = A BC define la operacin diferencia en trminos de las operaciones interseccin y complemento. Encuentre una frmula que defina la unin A B en trminos de las operaciones interseccin y complemento.

    DIAGRAMAS DE VENN

    1.34 En el diagrama de Venn de la figura 1-5a) se muestran los conjuntos A, B y C. Sombree los siguientes conjuntos:a) A\(B C); b) AC (B C); c) AC (C\B).

    1.35 Use el diagrama de Venn de la figura 1-5b) para escribir cada conjunto como la unin (disjunta) de productos fundamenta-les:

    a) A (B C); b) AC (B C); c) A (B\C).

    1.36 Considere las siguientes premisas:

    S1: Todos los diccionarios son tiles.S2: Mara slo tiene novelas rosas.S3: Ninguna novela rosa es til.

    Use un diagrama de Venn para determinar la validez de cada una de las siguientes conclusiones:a) Las novelas rosas no son diccionarios.b) Mara no tiene ningn diccionario.c) Todos los libros tiles son diccionarios.

    LGEBRA DE CONJUNTOS Y DUALIDAD1.37 Escriba el dual de cada ecuacin:

    a) A = (BC A) (A B)b) (A B) (AC B) (A BC) (AC BC) = U

    1.38 Use las leyes en la tabla 1-1 para demostrar cada identidad de conjuntos:a) (A B) (A BC) = Ab) A B = (A BC) (AC B) (A B)

    PROBLEMAS SUPLEMENTARIOS 19

    01_Cap. 1_Lipschutz.indd 1901_Cap. 1_Lipschutz.indd 19 11/25/08 3:07:49 PM11/25/08 3:07:49 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 20 CAPTULO 1 TEORA DE CONJUNTOS

    CONJUNTOS FINITOS Y PRINCIPIO DEL CONTEO

    1.39 Determine cules de los siguientes conjuntos son finitos:a) Rectas paralelas al eje x. c) Enteros mltiplos de 5.b) Letras del alfabeto espaol. d ) Animales vivientes sobre la Tierra.

    1.40 Use el teorema 1.9 para demostrar el corolario 1.10: Suponga que A, B y C son conjuntos finitos. Entonces A B C es finito y

    n(A B C) = n(A) + n(B) + n(C) n(A B) n(A C) n(B C) + n(A B C)

    1.41 Se aplic una encuesta acerca de 25 automviles nuevos vendidos en una agencia para ver qu opciones de equipo: aire acondicionado (A), radio (R) y ventanillas elctricas (W), ya estaban instaladas. Se encontr lo siguiente: 15 tenan aire acondicionado (A), 5 tenan A y P, 12 tenan radio (R), 9 tenan A y R, 3 tenan las tres opciones. 11 tenan ventanillas elctricas (W), 4 tenan R y W,Encuentre el nmero de automviles que tenan: a) slo W; b) slo A; c) slo R; d ) R y W pero no A; e) A y R pero no W; f ) slo una de las opciones; g) por lo menos una opcin; h) ninguna de las opciones.

    CLASES DE CONJUNTOS

    1.42 Encuentre el conjunto potencia P(A) de A = {1, 2, 3, 4, 5}.

    1.43 Dado A = [{a, b}, {c}, {d, e, f }].a) Enumere los elementos de A. b) Encuentre n(A). c) Encuentre el conjunto potencia de A.

    1.44 Suponga que A es finito y que n(A) = m. Demuestre que el conjunto potencia P(A) tiene 2m elementos.

    PARTICIONES

    1.45 Sea S = {1, 2, . . . , 8, 9}. Determine si cada una de las siguientes expresiones es o no una particin de S:a) [{1, 3, 6}, {2, 8}, {5, 7, 9}] c) [{2, 4, 5, 8}, {1, 9}, {3, 6, 7}]b) [{1, 5, 7}, {2, 4, 8, 9}, {3, 5, 6}] d) [{1, 2, 7}, {3, 5}, {4, 6, 8, 9}, {3, 5}]

    1.46 Sea S = {1, 2, 3, 4, 5, 6}. Determine si cada una de las siguientes expresiones es o no una particin de S:a) P1 = [{1, 2, 3}, {1, 4, 5, 6}] c) P3 = [{1, 3, 5}, {2, 4}, {6}]b) P2 = [{1, 2}, {3, 5, 6}] d ) P4 = [{1, 3, 5}, {2, 4, 6, 7}]

    1.47 Determine si cada una de las siguientes expresiones es o no una particin del conjunto N de enteros positivos:a) [{n | n > 5}, {n | n < 5}]; b) [{n | n > 6}, {1, 3, 5}, {2, 4}];c) [{n | n2 > 11}, {n | n2 < 11}].

    1.48 Sean [A1, A2, . . . , Am] y [B1, B2, . . . , Bn] particiones de un conjunto S. Demuestre que la siguiente coleccin de conjuntos tambin es una particin (denominada particin que se cruza) de S:

    P = [Ai Bj |i = 1, . . . , m, j = 1, . . . , n]\MSe observa que se elimin el conjunto vaco M.

    1.49 Sea S = {1, 2, 3, . . . , 8, 9}. Encontrar la particin que se cruza P de las siguientes particiones de S:P1 = [{1, 3, 5, 7, 9}, {2, 4, 6, 8}] y P2 = [{1, 2, 3, 4}, {5, 7}, {6, 8, 9}]

    01_Cap. 1_Lipschutz.indd 2001_Cap. 1_Lipschutz.indd 20 11/25/08 3:07:52 PM11/25/08 3:07:52 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • INDUCCIN1.50 Demuestre: 2 + 4 + 6 + + 2n = n(n + 1)1.51 Demuestre: 1 + 4 + 7 + + 3n 2 = n(3n1)21.52 Demuestre: 12 + 22 + 32 + + n2 = n(n+1)(2n+1)61.53 Demuestre: 113 + 135 + 157 + + 1(2n1)(2n+1) = n2n+11.54 Demuestre: 115 + 159 + 1913 + + 1(4n3)(4n+1) = n4n+11.55 Demuestre: 7n 2n es divisible entre 5 para toda n N1.56 Demuestre: n3 4n + 6 es divisible entre 3 para toda n N1.57 Use la identidad 1 + 2 + 3 + + n = n(n + 1)/2 para demostrar que: 13 + 23 + 33 + + n3 = (1 + 2 + 3 + + n)2

    PROBLEMAS DIVERSOS

    1.58 Suponga que N = {1, 2, 3, . . .} es el conjunto universo, y queA = {n | n 6}, B = {n | 4 n 9}, C = {1, 3, 5, 7, 9}, D = {2, 3, 5, 7, 8}.

    Encuentre: a) A B; b) B C; c) A (B D); d) (A B) (A D).

    1.59 Demuestre las siguientes propiedades de la diferencia simtrica:

    a) (A B) C = A (B C) (Ley asociativa).b) A B = B A (Ley conmutativa).c) Si A B = A C, entonces B = C (Ley de cancelacin).d ) A (B C) = (A B) (A C) (Ley distributiva).

    1.60 Considere m conjuntos no vacos diferentes A1, A2, . . . , Am en un conjunto universo U. Demuestre lo siguiente:a) Hay 2m productos fundamentales de los m conjuntos.b) Dos productos fundamentales cualesquiera son ajenos.c) U es la unin de todos los productos fundamentales.

    PROBLEMAS DIVERSOS 21

    Respuestas a los problemas suplementarios

    1.26 B = C = E = F, A = D = G = H.1.27 A = {a, e, i, o, u}, B = D = {l, i, t, e},

    C = {a, b, c, d, e}.1.28 a) C y E; b) D y E; c) A, B y D; d ) ninguno.1.29 a) A B = {2, 5}, A C = {1, 5};

    b) A B = {1, 2, 5, 6, 7}, B C = {1, 2, 3, 5, 7, 9};c) AC = {3, 4, 7, 8, 9}, CC = {2, 4, 6, 8};d) A\B = {1, 6}, A\C = {2, 6};e) A B = {1, 6, 7}, A C = {2, 3, 6, 7, 9};f )(A C)\B = {1, 3, 6, 9}, (B C)\A = {3, 9}.

    1.33 A B = (AC BC)C.

    1.34 Vea la figura 1-10.

    1.35 a) (A B C) (A B CC) (A BC C)b) (ACBCC) (ACBC) (ACBCC)c) (A B C) (A B CC) (A BC C)

    (AC B CC) (A BC CC)1.36 Las tres premisas producen el diagrama de Venn en la

    figura 1-11a). a) y b) son vlidas, pero c) no es vlida.1.37 a) A = (BC A) (A B)

    b) (AB) (AC B) (ABC) (AC BC) =M1.39 a) Infinito; b) finito; c) infinito; d ) finito.

    01_Cap. 1_Lipschutz.indd 2101_Cap. 1_Lipschutz.indd 21 11/25/08 3:07:54 PM11/25/08 3:07:54 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 22 CAPTULO 1 TEORA DE CONJUNTOS

    1.41 Use los datos para sustituir lo que corresponda en la figura 1-11b). Entonces:a) 5; b) 4; c) 2; d ) 1; e) 6; f ) 11; g) 23; h) 2.

    1.42 P(A) tiene 25 = 32 elementos como sigue:[M, {1}, {2}, {3}, {4}, {5}, {1, 2}, {1, 3}, {1, 4}, {1,5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}, {1, 2,3}, {1, 2, 4}, {1, 2, 5}, {2, 3, 4}, {2, 3, 5}, {3, 4, 5},{1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 4, 5}, {1, 2, 3, 4},{1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}, A]

    1.43 a) Tres elementos: [a, b], (c), y {d, e, f }. b) 3. c) P(A) tiene 23 = 8 elementos como sigue:P(A) = {A, [{a, b}, {c}], [{a, b}, {d, e, f }],

    [{c}, {d, e, f }], [{a, b}], [{c}], [{d, e, f }],M}

    1.44 Sea X un elemento en P(A). Para cada a A se tiene que a X o a A. Puesto que n(A) = m, hay 2m conjuntos distintos X. Es decir, |P(A)| = 2m.

    1.45 a) No, b) no, c) s, d ) s.1.46 a) No, b) no, c) s, d ) no.1.47 a) No, b) no, c) s.1.49 [{1, 3}, {2, 4}, {5, 7}, {9}, {6, 8}]1.55 Sugerencia: 7k+1 2k+1 = 7k+1 7(2k) + 7(2k) 2k+1

    = 7(7k 2k) + (7 2)2k1.58 a) {1, 2, 3, 7, 8, 9}; b) {1, 3, 4, 6, 8}; c)

    y d ) {2, 3, 4, 6}.

    a) b) c)

    A B

    C

    A B

    C

    A B

    C

    libros tiles

    diccionarios

    novelas rosas

    libros de Mara

    a) b)

    W

    A R

    4

    6

    32 1

    2

    25

    Figura 1-10

    Figura 1-11

    01_Cap. 1_Lipschutz.indd 2201_Cap. 1_Lipschutz.indd 22 11/25/08 3:07:59 PM11/25/08 3:07:59 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 2.1 INTRODUCCINPuesto que el lector ya tiene familiaridad con muchas relaciones como menor que, es paralela a, es un subcon-junto de, etc., percibe que estas relaciones consideran la existencia o inexistencia de cierta conexin entre pares de objetos que se consideran en un orden definido. Formalmente, una relacin se define en trminos de estos pares orde-nados.

    Un par ordenado de elementos a y b, donde a es el primer elemento y b es el segundo, se denota por (a, b). En particular,

    (a, b) = (c, d)si y slo si a = c y b = d. As, (a, b) = (b, a), a menos que a = b. Esto contrasta con los conjuntos donde el orden de los elementos es irrelevante; por ejemplo, {3, 5} = {5, 3}.

    2.2 PRODUCTO DE CONJUNTOS

    Considere dos conjuntos arbitrarios A y B. El conjunto de todos los pares ordenados (a, b), donde a A y b B se denomina producto, o producto cartesiano, de A y B. Una notacin abreviada para indicar este producto es A B, que se lee A cruz B. Por definicin,

    A B = {(a, b)} | a A y b B}A menudo, en vez de A A se escribe A2.

    EJEMPLO 2.1 R denota el conjunto de nmeros reales, as que R2 = R R es el conjunto de pares ordenados de nmeros reales. El lector ya conoce la representacin geomtrica de R2 como puntos en el plano que se muestra en la figura 2-1. Aqu cada punto P representa un par ordenado (a, b) de nmeros reales y viceversa; la recta vertical que pasa por P corta al eje x en a, yla recta horizontal que pasa por P corta al eje y en b. R2 a menudo se denomina plano cartesiano.

    EJEMPLO 2.2 Sean A = {1, 2} y B = {a, b, c}. Entonces

    A B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}B A = {(a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2)}

    Tambin, A A = {(1, 1), (1, 2), (2, 1), (2, 2)}.

    23

    2 RelacionesCAPTULO

    02_Cap. 2_Lipschutz.indd 2302_Cap. 2_Lipschutz.indd 23 11/25/08 3:10:53 PM11/25/08 3:10:53 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 24 CAPTULO 2 RELACIONES

    Hay dos cosas que vale la pena observar en los ejemplos presentados. En primer lugar, A B = B A. El produc-to cartesiano tiene que ver con pares ordenados, de modo que, naturalmente, el orden en que se consideran los conjun-tos es importante. En segundo lugar, si n(S) se usa para indicar el nmero de elementos que hay en un conjunto S, se tiene:

    n(A B) = 6 = 2(3) = n(A)n(B)De hecho, para conjuntos A y B finitos arbitrarios se tiene n(A B) = n(A)n(B). Lo anterior es una consecuencia de la observacin de que, para un par ordenado (a, b) en A B, para a hay n(A) posibilidades, y para cada una de stas hay n(B) posibilidades para b.

    La idea de producto de conjuntos se extiende a cualquier nmero finito de conjuntos. Para conjuntos cualesquiera A1, A2, . . . , An, el conjunto de todas las n-adas ordenadas (a1, a2, . . . , an), donde a1 A1, a2 A2, . . . , an An se deno-mina producto de los conjuntos A1, . . . , An y se denota por

    A1 A2 An on

    i=1A1

    As como en lugar de A A se escribe A2, tambin en lugar de A A A, donde hay n factores iguales a A, se escribe An. Por ejemplo, R3 = R R R denota el espacio tridimensional usual.

    2.3 RELACIONES

    Aqu conviene iniciar con una definicin.

    Definicin 2.1: Sean A y B conjuntos. Una relacin binaria, o simplemente una relacin de A a B, es un subconjunto de A B.

    Suponga que R es una relacin de A a B. Entonces R es un conjunto de pares ordenados donde el primer elemento proviene de A y el segundo proviene de B. Es decir, para cada par a A y b B, es verdadera exactamente una de las siguientes proposiciones:

    i) (a, b) R; entonces se dice a est relacionado con b, lo que se escribe aRb. ii) (a, b) R; entonces se dice a no est relacionado con b, lo que se escribe aRb.Si R es una relacin del conjunto A en s mismo; es decir, si R es un subconjunto de A2 = A A, entonces se dice que R es una relacin sobre A.

    El dominio de una relacin R es el conjunto de todos los primeros elementos de los pares ordenados que pertenecen a R, y el rango es el conjunto de los segundos elementos.

    Aunque las relaciones n-arias, que implican n-adas ordenadas, se presentan en la seccin 2.10, el trmino relacin significar entonces relacin binaria, a menos que se indique o implique otra cosa.

    Figura 2-1

    2P

    1

    b

    a03 2 1 1 2 3

    32

    1

    3

    02_Cap. 2_Lipschutz.indd 2402_Cap. 2_Lipschutz.indd 24 11/25/08 3:10:54 PM11/25/08 3:10:54 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • EJEMPLO 2.3

    a) Sean A = (1, 2, 3) y B = {x, y, z}, y sea R = {(1, y), (1, z), (3, y)}. Entonces R es una relacin de A a B, puesto que R es un subconjunto de A B. Con respecto a esta relacin,

    1Ry, 1Rz, 3Ry, pero 1Rx, 2Rx, 2Ry, 2Rz, 3Rx, 3Rz

    El dominio de R es {1, 3} y el rango es {y, z}.b) La inclusin de conjuntos es una relacin sobre cualquier coleccin de conjuntos, ya que, dado cualquier par de conjuntos A

    y B, se tiene A B o A B.c) Una relacin conocida sobre el conjunto Z de enteros es m divide a n. Una notacin comn para indicar esto consiste en

    escribir m | n cuando m divide a n. As, 6 | 30 pero 7 | 25.d ) Considere el conjunto de L lneas rectas en el plano. La perpendicularidad, que se escribe es una relacin sobre L. Es decir,

    dado cualquier par de lneas rectas a y b, se cumple a b o a b. En forma semejante, la relacin es paralela a, que se escribe , es una relacin sobre L, ya que se cumple a b o a b.

    e) Sea A cualquier conjunto. Una relacin importante sobre A es la de igualdad,

    {(a, a) | a A}

    que suele denotarse por =. Esta relacin tambin se denomina relacin identidad o diagonal sobre A y del mismo modo se denotar por A, o simplemente por .

    f ) Sea A cualquier conjunto. Entonces A A y M son subconjuntos de A A y son relaciones sobre A denominadas relacin universal y relacin vaca, respectivamente.

    Relacin inversa

    Sea R cualquier relacin de un conjunto A a un conjunto B. La inversa de R, denotada por R1, es la relacin de B a A que consta de los pares ordenados que, cuando se invierten, pertenecen a R; es decir,

    R1 = {(b, a) | (a, b) R}Por ejemplo, sean A = {1, 2, 3} y B = {x, y, z}. As, la inversa de

    R = {(1, y), (1, z), (3, y)} es R1 = {(y, 1), (z, 1), (y, 3)}Resulta evidente que si R es cualquier relacin, entonces (R1)1 = R. Tambin, el dominio y el rango de R1 son iguales, respectivamente, al rango y al dominio de R. Adems, si R es una relacin sobre A, entonces R1 tambin es una relacin sobre A.

    2.4 REPRESENTACIN GRFICA DE LAS RELACIONESHay varias formas de representar las relaciones.

    Relaciones sobre R

    Sea S una relacin sobre el conjunto R de nmeros reales; es decir, S es un subconjunto de R2 = R R. A menudo, S consta de todos los pares ordenados de nmeros reales que satisfacen alguna ecuacin dada E(x, y) = 0 (como x2 + y2 = 25).

    Puesto que R2 puede representarse mediante el conjunto de puntos en el plano, S se representa recalcando los pun-tos en el plano que pertenecen a S. La representacin grfica de la relacin algunas veces se denomina grfica de la relacin. Por ejemplo, la grfica de la relacin x2 + y2 = 25 es una circunferencia centrada en el origen con radio igual a 5. Vea la figura 2-2a).

    2.4 REPRESENTACIN GRFICA DE LAS RELACIONES 25

    02_Cap. 2_Lipschutz.indd 2502_Cap. 2_Lipschutz.indd 25 11/25/08 3:10:55 PM11/25/08 3:10:55 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 26 CAPTULO 2 RELACIONES

    Grficas dirigidas y relaciones sobre conjuntosHay una forma importante de representar una relacin R sobre un conjunto finito. Primero se escriben los elementos del conjunto, y luego se traza una flecha desde cada elemento x hasta cada elemento y, siempre que x est relacionado con y. Este diagrama se denomina grfica dirigida de la relacin. La figura 2-2b), por ejemplo, muestra la grfica dirigida de la siguiente relacin R sobre el conjunto A = {1, 2, 3, 4}:

    R = {(1, 2), (2, 2), (2, 4), (3, 2), (3, 4), (4, 1), (4, 3)}Observe que hay una flecha que va de 2 a s mismo, ya que 2 est relacionado con 2 bajo R.

    Estas grficas dirigidas se estudiarn en detalle como un tema por separado en el captulo 8. Aqu se mencionan para tener una panormica ms completa.

    Representaciones de relaciones sobre conjuntos finitosSuponga que A y B son conjuntos finitos. Hay dos formas de representar una relacin R de A a B. i) Se forma un arreglo rectangular (matriz) cuyos renglones se identifican mediante los elementos de A y cuyas

    columnas se identifican mediante los elementos de B. En cada posicin del arreglo se escribe 1 o 0 segn a A est o no relacionado con b B. Este arreglo se denomina matriz de la relacin.

    ii) Los elementos de A y de B se escriben en dos valos ajenos y luego se traza una flecha de a A a b B siempre que a est relacionado con b. Esta representacin se denomina diagrama sagital de la relacin.

    En la figura 2-3 se muestra, en las dos formas mencionadas, la relacin R en el ejemplo 2.3a).

    Figura 2-2

    Figura 2-3

    i) ii)

    a) b)

    y

    x

    x2 + y2 = 25

    5 0 5

    5

    5

    1 2

    3 4

    02_Cap. 2_Lipschutz.indd 2602_Cap. 2_Lipschutz.indd 26 11/25/08 3:10:56 PM11/25/08 3:10:56 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 2.5 COMPOSICIN DE RELACIONESSean A, B y C conjuntos, R una relacin de A a B y S una relacin de B a C. Es decir, R es un subconjunto de A B y S es un subconjunto de B C. Entonces R y S originan una relacin de A a C denotada por R S y definida por:

    a(R S)c si para alguna b B se tiene aRb y bSc.Es decir,

    R S = {(a, c) | existe b B para la cual (a, b) R y (b, c) S}La relacin R S se denomina composicin de R y S; algunas veces se denota simplemente por RS.

    Suponga que R es una relacin sobre un conjunto A; es decir, R es una relacin de un conjunto A en s mismo. Entonces R R, la composicin de R consigo mismo, siempre est definida. Tambin, R R algunas veces se denota por R2. En forma semejante, R3 = R2 R = R R R, y as sucesivamente. Por tanto, Rn est definida para todo n positivo.

    Advertencia: Muchos textos denotan la composicin de las relaciones R y S con S R, en lugar de R S. Esto se hace as a fin de coincidir con el hbito de usar g f para denotar la composicin de f y g, donde f y g son funciones. As, el lector quiz deba ajustarse a esta notacin cuando utilice este texto como complemento de otro texto. Sin embargo, cuando una relacin R se compone consigo misma, entonces el significado de R R es inequvoco.

    EJEMPLO 2.4 Sea A = {1, 2, 3, 4}, B = {a, b, c, d }, C = {x, y, z} y seaR = {(1, a), (2, d), (3, a), (3, b), (3, d )} y S = {(b, x), (b, z), (c, y), (d, z)}

    Considere los diagramas sagitales de R y S como en la figura 2-4. Observe que hay una flecha de 2 a d seguida por una flecha de d a z. Estas dos flechas pueden considerarse como una ruta que conecta (o une) el elemento 2 A con el elemento z C. As,

    2(R S)z puesto que 2Rd y dSzEn forma semejante hay una ruta de 3 a x y una ruta de 3 a z. Entonces

    3(R S)x y 3(R S)zNingn otro elemento de A est unido con un elemento de C. En consecuencia,

    R S = {(2, z), (3, x), (3, z)}El primer teorema que se presenta establece que la composicin de relaciones es asociativa.

    Teorema 2.1: Sean A, B, C y D conjuntos. Suponga que R es una relacin de A a B, S es una relacin de B a C y T es una relacin de C a D. Entonces

    (R S) T = R (S T )La demostracin de este teorema se proporciona en el problema 2.8.

    2.5 COMPOSICIN DE RELACIONES 27

    Figura 2-4

    1

    2

    3

    4

    b

    a

    c

    d

    x

    y

    z

    R S

    02_Cap. 2_Lipschutz.indd 2702_Cap. 2_Lipschutz.indd 27 11/25/08 3:10:57 PM11/25/08 3:10:57 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 28 CAPTULO 2 RELACIONES

    Composicin de relaciones y matrices

    Hay otra forma para encontrar R S. Sean MR y MS que denotan, respectivamente, las representaciones matriciales de las relaciones R y S. Entonces

    MR =

    a b c d

    1234

    1 0 0 00 0 0 11 1 0 10 0 0 0

    y MS =

    x y z

    a

    b

    c

    d

    0 0 01 0 10 1 00 0 1

    Al multiplicar MR y MS se obtiene la matriz

    x y z

    M = MRMS =1234

    0 0 00 0 11 0 20 0 0

    Los elementos diferentes de cero en esta matriz indican cules elementos estn relacionados por R S. As, M = MRMS y MRS tienen los mismos elementos distintos de cero.

    2.6 TIPOS DE RELACIONES

    En esta seccin se analizan varios tipos de relaciones importantes definidas sobre un conjunto A.

    Relaciones reflexivas

    Una relacin R sobre un conjunto es reflexiva si aRa para toda a A; es decir, si (a, a) R para toda a A. Por tanto, R no es reflexiva si existe a A tal que (a, a) R.

    EJEMPLO 2.5 Considere las cinco relaciones siguientes sobre el conjunto A = {1, 2, 3, 4}:R1 = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}R2 = {(1, 1)(1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}R3 = {(1, 3), (2, 1)}R4 =M, la relacin vacaR5 = A A, la relacin universal

    Determine cules de las relaciones son reflexivas.Puesto que A contiene los cuatro elementos 1, 2, 3 y 4, una relacin sobre A es reflexiva si contiene los cuatro pares (1, 1),

    (2, 2), (3, 3) y (4, 4). As, slo R2 y la relacin universal R5 = A A son reflexivas. Observe que R1, R3 y R4 no son reflexivasporque, por ejemplo, (2, 2) no pertenece a ninguna de ellas.

    EJEMPLO 2.6 Considere las cinco relaciones siguientes:

    1) Relacin (menor que o igual a) sobre el conjunto Z de enteros.2) Inclusin de conjuntos sobre una coleccin C de conjuntos.3) Relacin (es perpendicular a) sobre el conjunto L de lneas rectas en el plano.4) Relacin (es paralela a) sobre el conjunto L de lneas rectas en el plano.5) Relacin | de divisibilidad sobre el conjunto N de enteros positivos. (Recuerde que x | y si existe z tal que xz = y.)Determine cules de las relaciones son reflexivas.

    02_Cap. 2_Lipschutz.indd 2802_Cap. 2_Lipschutz.indd 28 11/25/08 3:10:58 PM11/25/08 3:10:58 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • La relacin 3) no es reflexiva porque ninguna lnea recta es perpendicular a s misma. Tambin la relacin 4) no es reflexiva porque ninguna lnea recta es paralela a s misma. Las otras relaciones son reflexivas; es decir, x x para toda x Z, A A para cualquier conjunto A C, y n | n para todo entero positivo n N.

    Relaciones simtricas y antisimtricas

    Una relacin R sobre un conjunto A es simtrica si siempre que aRb entonces bRa; es decir, siempre que (a, b) R entonces (b, a) R. Por tanto, R no es simtrica si existen a, b A, tales que (a, b) R pero (b, a) R.

    EJEMPLO 2.7

    a) Determine cules de las relaciones en el ejemplo 2.5 son simtricas. R1 no es simtrica porque (1, 2) R1 pero (2, 1) R1. R3 no es simtrica porque (1, 3) R3 pero (3, 1) R3. Las otras relacio-

    nes son simtricas.

    b) Determine cules de las relaciones en el ejemplo 2.6 son simtricas. La relacin es simtrica porque si la lnea recta a es perpendicular a la lnea recta b, entonces b es perpendicular a a. Tambin,

    es simtrica porque si la lnea recta a es paralela a la lnea recta b, entonces b es paralela a la lnea recta a. Las otras relaciones no son simtricas. Por ejemplo:

    3 4 pero 4 3; {1, 2} {1, 2, 3} pero {1, 2, 3} {1, 2} y 2 | 6 pero 6 | 2.Una relacin R sobre un conjunto A es antisimtrica siempre que aRb y bRa entonces a = b; es decir, si a = b y aRb, entonces bRa. Por tanto, R no es antisimtrica si existen elementos distintos a y b en A tales que aRb y bRa.

    EJEMPLO 2.8

    a) Determine cules de las relaciones en el ejemplo 2.5 son antisimtricas. R2 no es antisimtrica porque (1, 2) y (2, 1) pertenecen a R2, pero 1 = 2. En forma semejante, la relacin universal R3 no es

    antisimtrica. Todas las otras relaciones son antisimtricas.

    b) Determine cules de las relaciones en el ejemplo 2.6 son antisimtricas. La relacin es antisimtrica porque siempre que a b y b a entonces a = b. La inclusin de conjuntos es antisimtrica

    siempre que A B y B A entonces A = B. Tambin, la divisibilidad sobre N es antisimtrica porque siempre que m | n y n | m, entonces m = n. (Observe que la divisibilidad sobre Z no es antisimtrica porque 3 | 3 y 3 | 3 pero 3 = 3.) Las relaciones y no son antisimtricas.

    Observacin: Las propiedades de ser simtrica y ser antisimtrica no son negaciones entre s. Por ejemplo, la relacin R = {(1, 3), (3, 1), (2, 3)} no es simtrica ni antisimtrica. Por otra parte, la relacin R = {(1, 1), (2, 2)} es tanto sim-trica como antisimtrica.

    Relaciones transitivas

    Una relacin R sobre un conjunto A es transitiva si siempre que aRb y bRc entonces aRc; es decir, siempre que(a, b), (b, c) R entonces (a, c) R. Por tanto, R no es transitiva si existe a, b, c R tal que (a, b), (b, c) R pero(a, c) R.

    2.6 TIPOS DE RELACIONES 29

    02_Cap. 2_Lipschutz.indd 2902_Cap. 2_Lipschutz.indd 29 11/25/08 3:10:59 PM11/25/08 3:10:59 PM

    ww

    w.e

    lsol

    ucio

    nario

    .net

    www.elsolucionario.net

  • 30 CAPTULO 2 RELACIONES

    EJEMPLO 2.9

    a) Determine cules de las relaciones en el ejemplo 2.5 son transitivas. La relacin R3 no es transitiva porque (2, 1), (1, 3) R3 pero (2, 3) R3. Todas las otras relaciones son transitivas.b) Determine cules de las relaciones en el ejemplo 2.6 son transitivas. Las relaciones , y | son transitivas, aunque ciertamente no lo es. Tambin, puesto que ninguna lnea recta es paralela a s

    misma, se tiene que a b y b a, pero a a. Por tanto, no es transitiva. (Se observa que la relacin es paralela o igual a es una relacin transitiva sobre el conjunto L de lneas rectas en el plano.)

    La propiedad de transitividad tambin se expresa en trminos de la composicin de relaciones. Para una relacin R sobre A se defi-ni R2 = R R y, de manera ms general, Rn = Rn1 R. Entonces se tiene el siguiente resultado:

    Teorema 2.2: Una relacin R es transitiva si y slo si para toda n 1, se tiene Rn R.

    2.7 PROPIEDADES DE CERRADURA

    Considere un conjunto dado A y la coleccin de todas las relaciones sobre A. Sea P una propiedad de tales relaciones, como ser simtrica o transitiva. Una relacin con la propiedad P se denomina P-relacin. La P-cerradura de una rela-cin arbitraria R sobre