apuntes de älgebra y matemática discreta

1. Apuntes de Matemtica Discreta a 1. Conjuntos y SubconjuntosFrancisco Jos Gonzlez Gutirrez e a e Cdiz, Octubre de 2004 a

2. Universidad de Cdiz aDepartamento de Matemticas aii

3. Leccin 1 oConjuntos y Subconjuntos Contenido 1.1Generalidades . . . . . . . . . . . . . . . . . . . 1.1.1 Conjuntos y Elementos . . . . . . . . . . . . 1.1.2 Determinacin por Extensin . . . . . . . . . o o 1.1.3 Determinacin por Comprensin . . . . . . . o o 1.1.4 Conjunto Universal . . . . . . . . . . . . . . . 1.1.5 Conjunto Vac . . . . . . . . . . . . . . . . . o 1.1.6 Axioma de Extensin . . . . . . . . . . . . . o 1.2 Inclusin de conjuntos . . . . . . . . . . . . . o 1.2.1 Subconjuntos . . . . . . . . . . . . . . . . . . 1.2.2 Inclusin Estricta . . . . . . . . . . . . . . . . o 1.2.3 Proposicin . . . . . . . . . . . . . . . . . . . o 1.2.4 Proposicin . . . . . . . . . . . . . . . . . . . o 1.2.5 Caracterizacin de la Igualdad . . . . . . . . o 1.2.6 Corolario . . . . . . . . . . . . . . . . . . . . 1.2.7 Transitividad de la Inclusin . . . . . . . . . o 1.3 Diagramas de Venn . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . 2 . . . . . . . . . . . 2 . . . . . . . . . . . 2 . . . . . . . . . . . 3 . . . . . . . . . . . 5 . . . . . . . . . . . 5 . . . . . . . . . . . 5 . . . . . . . . . . 7 . . . . . . . . . . . 7 . . . . . . . . . . . 8 . . . . . . . . . . . 9 . . . . . . . . . . . 9 . . . . . . . . . . . 11 . . . . . . . . . . . 12 . . . . . . . . . . . 12 . . . . . . . . . . 13Un conjunto es la reunin en un todo de objetos de nuestra ino tuicin o de nuestro pensar, bien determinados y diferenciables o los unos de los otros. Georg Cantor (1845-1918)El concepto de conjunto es de fundamental importancia en las matemticas modernas. La mayor de los a a matemticos creen que es posible expresar todas las matemticas en el lenguaje de la teor de conjuntos. a a a Nuestro inters en los conjuntos se debe tanto al papel que representan en las matemticas como a su e a utilidad en la modelizacin e investigacin de problemas en la informtica. o o a Los conjuntos fueron estudiados formalmente por primera vez por Georg Cantor1 . Despus de que la e teor de conjuntos se estableciera como un rea bien definida de las matemticas, aparecieron cona a a tradicciones o paradojas en la misma. Para eliminar tales paradojas, se desarrollaron aproximaciones ms sofisticadas que las que hizo Cantor. Un tratamiento introductorio de la teor de conjuntos se a a ocupa, generalmente, de la teor elemental, la cual es bastante similar al trabajo original de Cantor. a Utilizaremos esta aproximacin ms simple y desarrollaremos una teor de conjuntos de la cual es posible o a a 1 Georg Cantor. Matemtico alemn de origen ruso (San Petesburgo 1845-Halle 1918). Despus de estudiar en Alemania, a a e fue profesor de la universidad de Halle (1879). Escribi numerosas memorias, pero es especialmente conocido por ser el o creador de la Teor de los conjuntos. a1

4. Universidad de Cdiz aDepartamento de Matemticas aderivar contradicciones. Parece extrao el proponerse tal cosa deliberadamente, pero las contradicciones n no son un problema si, como es nuestro caso, el universo del discurso se define convenientemente. An u ms, la existencia de las paradojas en la teor elemental no afecta a la validez de nuestros resultados ya a a que los teoremas que presentaremos pueden demostrarse mediante sistemas alternativos en los que las paradojas no ocurren.1.1GeneralidadesDefinimos los conceptos fundamentales del tema como conjunto, elemento, determinacin de un conjunto o por extensin, por comprensin y estudiamos la igualdad de dos conjuntos. o o1.1.1Conjuntos y ElementosIntuitivamente, un conjunto es cualquier coleccin de objetos que pueda tratarse como una entidad. o A cada objeto de la coleccin lo llamaremos elemento o miembro del conjunto. o A los conjuntos los designaremos con letras maysculas y a sus elementos con letras minsculas. La u u armacin el elemento a pertenece al conjunto A se escribe o aA y la negacin de este hecho, (a A), se escribe o aA / La definicin de un conjunto no debe ser ambigua en el sentido de que pueda decidirse cuando un objeto o particular pertenece, o no, a un conjunto.1.1.2Determinacin por Extensin o oUn conjunto est denido por extensin cuando se especican todos los elementos que forman el a o mismo. Ejemplo 1.1Los siguientes conjuntos estn definidos por extensin. a o(a) El conjunto de las vocales del alfabeto. A = {a, e, i, o, u} (b) El conjunto formado por los nmeros enteros pares no negativos y menores que diez. u B = {0, 2, 4, 6, 8}Obsrvese que los elementos del conjunto estn separados por comas y encerrados entre llaves. e a Ejemplo 1.2Definir por extensin los siguientes conjuntos. o(a) El conjunto de los enteros no negativos menores que cinco. (b) El conjunto de las letras de mi nombre. 2

5. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a e(c) El conjunto cuyo unico elemento es el primer Presidente de Gobierno de la democracia. (d) El conjunto de los nmeros primos entre 10 y 20. u (e) El conjunto de los mltiplos de 12 que son menores que 65. u Solucin o (a) A = {0, 1, 2, 3, 4} (b) B = {p, a, c, o} (c) C = {Adolfo Surez} a (d) D = {11, 13, 17, 19} (e) E = {12, 24, 36, 48, 60}Ejemplo 1.3Definir, por extensin, los conjuntos siguientes: o(a) A = {x : x Z 3 < x < 12} (b) B = {x : x es un nmero de un d u gito} (c) B = {x : x = 2 x = 5} Solucin o (a) A = {4, 5, 6, 7, 8, 9, 10, 11} (b) B = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} (c) C = {2, 5}Nota 1.1 Los elementos de un conjunto infinito no pueden especificarse de una forma expl cita; consecuentemente, necesitaremos una forma alternativa de describir tales conjuntos impl citamente.1.1.3Determinacin por Comprensin o oSe dice que un conjunto est denido por comprensin cuando se especica una propiedad que caraca o teriza a todos los elementos del mismo. Esta propiedad o especificacin impl o cita, se hace a menudo mediante un predicado con una variable libre. El conjunto estar determinado por aquellos elementos del universo que hacen del predicado una a proposicin verdadera. De aqu que si p(x) es un predicado con una variable libre, el conjunto o A = {x : p(x)} denota al conjunto A tal que a A si, y slo si p(a) es verdad. o Ejemplo 1.4Definir por comprensin los siguientes conjuntos: o 3

6. Universidad de Cdiz aDepartamento de Matemticas a(a) El conjunto de los enteros mayores que diez. (b) El conjunto de los enteros pares. (c) El conjunto {1, 2, 3, 4, 5} Solucin o (a) A = {x : x Z x > 10} (b) B = {x : x Z y Z x = 2y} (c) C = {x : x Z 1Ejemplo 1.5x5}Definir por extensin el siguiente conjunto dado por comprensin. o o A = x R : x2 3x + 2 = 0Solucin o Dado que las soluciones de la ecuacin son 1 y 2, podemos escribir o A = {1, 2}Nota 1.2Muchas veces se utilizan significados algo menos formales para describir conjuntos.Por ejemplo, el conjunto de los nmeros enteros mayores que diez, suele escribirse: u A = {x Z : x > 10} y el conjunto de los enteros pares, B = {x : x = 2y, y Z} A veces tanto en conjuntos finitos demasiado grandes como en conjuntos infinitos, se utiliza la elipsis matemtica para caracterizar a los elementos de un conjunto. Por ejemplo, el conjunto de los nmeros a u enteros del 1 al 100, C = {1, 2, 3, . . . , 100} o el conjunto de los enteros pares no negativos, D = {0, 2, 4, 6, . . .} Algunos conjuntos aparecern muy frecuentemente a lo largo del curso y se usan s a mbolos especiales para designarlos. Z: Conjunto de los nmeros enteros. u N = Z+ : Conjunto de los nmeros naturales o enteros positivos. u Z+ : Conjunto de los enteros no negativos. 0 Q: Conjunto de los nmeros racionales. u R: Conjunto de los nmeros reales. u C: Conjunto de los nmeros complejos. u 4

7. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a eIncluso si podemos especificar todos los elementos de un conjunto puede que no sea prctico hacerlo. a Por ejemplo, no definir amos por extensin el conjunto de los estudiantes de la Universidad de Cdiz que o a estudien Informtica, aunque tericamente es posible definirlo. a o As pues, describiremos un conjunto mediante un listado exhaustivo de sus elementos slo si contiene unos o pocos elementos, en caso contrario describiremos un conjunto mediante una propiedad que caracterice a los mismos.1.1.4Conjunto UniversalEn cualquier aplicacin de la teor de conjuntos, los elementos de todos los conjuntos en consideracin o a o pertenecen a un gran conjunto jo llamado conjunto universal. Lo notaremos por U . Ejemplo 1.6 Para cada uno de los conjuntos siguientes, elegir un conjunto universal y un predicado apropiados para definirlo. (a) El conjunto de los enteros entre 0 y 100. (b) El conjunto de los enteros positivos impares. (c) El conjunto de los mltiplos de 10. u Solucin o (a) A = {x : x Z x > 0 x < 100} A = {x Z : 0 < x < 100} o (b) B = {x : y Z+ , x = 2y 1} B = {x : x = 2y 1, y Z+ } o (c) C = {x : y Z, x = 10y} C = {x : x = 10y, y Z} o1.1.5Conjunto Vac oAl conjunto unico que no contiene elementos, lo llamaremos conjunto vac Lo notaremos con el o. s mbolo que proviene del alfabeto noruego.1.1.6Axioma de Extensin oDos conjuntos A y B son iguales si, y slo si tienen los mismos elementos. Es decir, cada elemento o del conjunto A es un elemento de B y cada elemento de B es un elemento de A. Su expresin formal en notacin lgica es: o o o A = B x [(x A = x B) (x B = x A)] o bien, A = B x (x A x B) Nota 1.3 El axioma de extensin asegura que si dos conjuntos tienen los mismos elementos, ambos o son iguales, independientemente de como estn definidos. e 5

8. Universidad de Cdiz aDepartamento de Matemticas aComo todo conjunto tiene los mismos elementos que l mismo, se sigue que si un conjunto est definido e a por extensin, el orden el que los elementos guren en l es intrascendente. As pues, los conjuntos o e {a, b, c}, {b, c, a} y {c, b, a} son iguales. Tambin se sigue del axioma de extensin que la aparicin de un elemento ms de una vez en un conjunto, e o o a es igualmente intrascendente. Por ejemplo, los conjuntos {a, b}, {a, b, b} y {a, a, a, b} son iguales ya que todo elemento de cualquiera de ellos est en los dems, por tanto, son especificaciones diferentes del a a mismo conjunto. Ejemplo 1.7 iguales.Determinar, en el conjunto de los nmeros enteros, cules de los siguientes conjuntos son u aA = x : x es par y x2 es impar B = {x : y, y Z x = 2y} C = {1, 2, 3} D = {0, 2, 2, 3, 3, 4, 4, . . .} E = {2x : x Z} F = {3, 3, 2, 1, 2} G = x : x3 6x2 7x 6 = 0 Solucin o Sea x cualquier nmero entero, entonces ux es par = x = 2y, y Z = x2 = 4y 2 , y Z = x2 = 2(2y 2 ), 2y 2 Z = x2 es par Por lo tanto, la proposicin x(x es par x2 es impar) es falsa o dicho de otra forma no hay o ningn nmero par cuyo cuadrado sera impar y, por lo tanto, A no tiene elementos es decir es el u u conjunto vac o. x B y : y Z x = 2y x es par, luego B = {x Z : x es par} x C x = 1 x = 2 x = 3 E = {0, 2, 2, 4, 4, 6, 6, . . .} = {x Z : x es par} x F x = 1 x = 2 x = 3 x G x3 6x2 7x 6 = 0 Pero no existe ningn nmero entero que satisfaga la ecuacin anterior, por lo tanto, G es el u u o conjunto vac o. De todo lo anterior, se sigue que A=G B=E C=F El conjunto D no es igual a ninguno de los otros. 6

9. Matemtica Discreta aEjemplo 1.8Francisco Jos Gonzlez Gutirrez e a eDar una condicin necesaria y suficiente para que dos conjuntos sean distintos. oSolucin o Sean A y B dos conjuntos cualesquiera de un universal arbitrario U . Entonces, por el axioma de extensin o A = B x [(x A = x B) (x B = x A)] de aqu que por asociatividad (??), tengamos que A = B [x (x A = x B) x (x B = x A)] y si ahora negamos ambos miembros, tendremos (A = B) [x (x A = x B) x (x B = x A)] por lo tanto, [x (x A = x B) x (x B = x A)][x (x A = x B)] [x (x B = x A)]{De Morgan}[x : (x A = x B)] [x : (x B = x A)]{Regla General}[x : ((x A) (x B))] [x : ((x B) (x A))]{Implicacin} o[x : ((x A) (x B))] [x : ((x B) (x A))] {De Morgan}A=B[x : (x A x B)] [x : (x B x A)] / /{Doble Negacin} oAs pues, una condicin necesaria y suficiente para que dos conjuntos A y B sean distintos es que exista o un elemento en A que no est en B o que exista un elemento en B que no est en A. e e1.2 1.2.1Inclusin de conjuntos o SubconjuntosSean A y B dos conjuntos. Diremos que A est contenido en B o que es un subconjunto de B, y lo a notaremos por A B, si cada elemento de A es un elemento de B, es decir, A B x (x A = x B) Tambin puede decirse que B contiene a A, en cuyo caso escribiremos B A. e Ejemplo 1.9Probar que el conjunto A = x R : x2 3x + 2 = 0 es subconjunto del B = {1, 2, 3}Solucin o En efecto, sea a un elemento cualquiera de R, o sea, un nmero real arbitrario. Entonces, u a A a2 3a + 2 = 0 a = 2 a = 1 = a B o luego x (x A = x B) y segn la definicin anterior, A B. u o Ejemplo 1.10 Dar una condicin necesaria y suficiente para que un conjunto A no est contenido en o e otro conjunto B. Solucin o 7

10. Universidad de Cdiz aDepartamento de Matemticas a(A B) [x (x A = x B)]x : [ (x A = x B)]x : [ ((x A) (x B))]x : [(x A) (x B)]B Ax : (x A x B) /es decir, una condicin necesaria y suciente para que A no est contenido en B es que exista, al menos, o e un elemento en A que no est en B. e Ejemplo 1.11Es B = {1, 2, 3} un subconjunto de A = x R : x2 3x + 2 = 0 ?Solucin o No, ya que 3 B y, sin embargo, 32 3 3 + 2 = 2 = 0, luego 3 A, es decir, hemos encontrado un / elemento en B que no est en A, por tanto, B A. a1.2.2Inclusin Estricta oSi A B y adems B tiene un elemento que no est en A, diremos que A est estrictamente incluido a a a en B o que A es un subconjunto propio de B y lo notaremos por A B. A B A B [x : (x B x A)] / Ejemplo 1.12 tenido en otro.Dar una condicin necesaria y suficiente para que un conjunto est estrictamente cono eSolucin o Sean A y B dos conjuntos cualesquiera de un universal arbitrario U . Entonces, segn acabamos de ver u A B A B [x : (x B x A)] / de donde, teniendo en cuenta el resultado del ejemplo 1.8, se sigue que A B A B A = BNota 1.4 Los conjuntos tambin son objetos, luego pueden ser elementos de otros conjuntos, por e ejemplo, el conjunto A = {{a, b} , {a, c} , {b} , {c}} tiene cuatro elementos que son los conjuntos {a, b} , {a, c} , {b} y {c}. Si tuviramos una caja con tres e paquetes de caramelos, la considerar amos como una caja con paquetes antes que una caja con caramelos, por lo que se tratar de un conjunto (la caja) con tres elementos (los paquetes). a Anlogamente, si A es un conjunto, entonces {A} es un conjunto con un unico elemento, A, sin impora tarnos cuantos elementos tenga A. Un caso curioso ocurre con el conjunto vac . Una caja con un paquete vac de caramelos no es una o, o caja vac ya que contiene algo, un paquete. De la misma forma {} es un conjunto con un elemento a mientras que no contiene elementos, as que y {} son conjuntos distintos. Tendremos que {} e incluso {}, pero = {}. Ejemplo 1.13 Describir brevemente la diferencia entre los conjuntos {a} y {{a}} y entre los conjuntos , {} y {, {}}. 8

11. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a eSolucin o {a} es un conjunto cuyo unico elemento es el a. {{a}} es un conjunto cuyo unico elemento es el conjunto {a}. . Conjunto unico que no tiene elementos (definicin 1.1.5). o {}. Conjunto con un unico elemento que es el . {, {}}. Conjunto con dos elementos, el y el {}.1.2.3Proposicin oSea U el conjunto universal y A un conjunto cualquiera. Entonces A U . Demostracin o La demostracin es un ejemplo de demostracin trivial basada en la definicin de conjunto universal que o o o nos permite afirmar que la proposicin x, x U es una tautolog es decir es verdad siempre. o a, El conjunto A es un subconjunto de U si, y slo si la implicacin o o x A = x U es verdad para cada x de U . Pero x U es verdad para todos los x, luego la implicacin tambin es o e verdad independientemente de que x A sea verdadero o falso. Como x es un elemento arbitrario de U , se sigue que x (x A = x U ) es verdad y, por lo tanto, AU1.2.4Proposicin oSea A un conjunto cualquiera, entonces A. Demostracin o Esta demostracin es un ejemplo de demostracin vac ya que la definicin de conjunto vac nos permite o o a o o afirmar que la proposicin x : x es una contradiccin, es decir siempre es falsa. o o Pues bien, sea x un elemento arbitrario del universal. Como x es falsa para todos los elementos de U tendremos que la implicacin o x = x A es verdadera. De la arbitrariedad de x se sigue que x (x = x A) y, consecuentemente, AEjemplo 1.14Determinar los subconjuntos de un conjunto. 9

12. Universidad de Cdiz aDepartamento de Matemticas a(a) Veamos cuantos subconjuntos tiene el conjunto {a, b}. De la proposicin 1.2.4 se sigue que el conjunto vac es uno de ellos. Por otra parte, a A o o, y b B luego por la definicin de inclusin (1.2.1), {a}, {b} y {a, b} son subconjuntos de {a, b}. o o Consecuentemente, el conjunto propuesto tiene cuatro subconjuntos distintos: , {a} , {b} , y {a, b} Obsrvese que {a} {a, b} y a {a, b}, pero a e {a, b} /{a, b} y {a} {a, b}. Tambin {a, b}, pero / e(b) El conjunto {{a}} es un conjunto unitario ya que tiene un unico elemento, el conjunto {a}. Sus subconjuntos son el y el {{a}}. Ejemplo 1.15Determinar todos los subconjuntos de los siguientes conjuntos:(a) {1, 2, 3} (b) {1, {2, 3}} (c) {{1, {2, 3}}} (d) {} (e) {, {}} (f) {{1, 2} , {2, 1, 1} , {2, 1, 1, 2}} (g) {{, 2} , {2}} Solucin o Utilizaremos la definicin de subconjunto (1.2.1), o A B x (x A = x B) (a) {1, 2, 3} {1, 2, 3} (Proposicin 1.2.4). o 1 {1, 2, 3}, luego {1} {1, 2, 3}. 2 {1, 2, 3}, luego {2} {1, 2, 3}. 3 {1, 2, 3}, luego {3} {1, 2, 3}. 1 {1, 2, 3} y 2 {1, 2, 3}, luego {1, 2} {1, 2, 3}. 1 {1, 2, 3} y 3 {1, 2, 3}, luego {1, 3} {1, 2, 3}. 2 {1, 2, 3} y 3 {1, 2, 3}, luego {2, 3} {1, 2, 3}. 1 {1, 2, 3}, 2 {1, 2, 3} y 3 {1, 2, 3}, luego {1, 2, 3} {1, 2, 3}. por lo tanto, los subconjuntos de {1, 2, 3} son , {1} , {2} , {3} , {1, 2} , {1, 3} , {2, 3} y {1, 2, 3} (b) {1, {2, 3}}. Aqu tenemos que 1 y {2, 3} son los dos elementos que tiene este conjunto, luego razonando igual que en el apartado anterior, sus subconjuntos son: , {1} , {{2, 3}} y {1, {2, 3}} (c) {{1, {2, 3}}}. Este conjunto tiene un unico elemento que es {1, {2, 3}}, por lo tanto sus subconjuntos son: y {{1, {2, 3}}} 10

13. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a e(d) {}. Este conjunto tiene un elemento que es , por lo tanto tiene dos subconjuntos, (por 1.2.4) y {} (por 1.2.1) (e) {, {}}. Este conjunto tiene dos elementos, y {}, por lo tanto sus subconjuntos son (por 1.2.4) y {} , {{}} y {, {}} (por 1.2.1) (f) {{1, 2} , {2, 1, 1} , {2, 1, 1, 2}}. Obsrvese que e {1, 2} = {2, 1, 1} = {2, 1, 1, 2} luego el conjunto propuesto es {{1, 2}} y, por lo tanto, sus subconjuntos son y {{1, 2}} (g) {{, 2} , {2}}. Siguiendo un razonamiento idntico a los anteriores apartados, sus subconjuntos son e , {{, 2}} , {{2}} y {{, 2} , {2}}1.2.5Caracterizacin de la Igualdad oSean A y B dos conjuntos cualesquiera de un universal arbitrario U . Entonces A = B si, y slo si o A B y B A. Demostracin o Slo si. A = B = A B B A o En efecto, supongamos que A = B. Entonces por el axioma de extensin, cada elemento de o A es un elemento de B luego por definicin de subconjunto, A B. As pues, si A = B, o entonces A B. Utilizando los mismos argumentos, aunque intercambiando los papeles de A y B, tendremos que si A = B, entonces B A. De aqu que (A = B = A B) (A = B = B A) lo cual equivale a A = B = A B B A Si. A B B A = A = B En efecto, (A B) (B A) = [(x (x A = x B)] [(x (x B = x A)] consecuentemente, por el axioma de extensin o A=B Este teorema lo utilizaremos con mucha frecuencia para comprobar que dos conjuntos son iguales, es decir, para probar que A = B, probaremos que A B y B A. 11

14. Universidad de Cdiz a1.2.6Departamento de Matemticas aCorolarioDe la caracterizacin anterior se sigue que para cualquier conjunto A, se verica que A A. o1.2.7Transitividad de la Inclusin oSean A, B y C tres conjuntos cualesquiera de un universal arbitrario U . Si A B y B C, entonces A C. Demostracin o Sea x un elemento arbitrario del universal U . De A B, se sigue que x A = x B De B C, se sigue que x B = x C De la transitividad de la implicacin lgica se sigue que o o x A = x C y al ser x arbitrario, tendremos x (x A = x C) por lo tanto, ACEjemplo 1.16 Sean A, B y C tres conjuntos. Si A B y B C, es posible que A C?, es siempre verdad que A C?. Da ejemplos de tus afirmaciones. Solucin o En efecto, es posible. Por ejemplo, sean A = {a} B = {{a}} C = {{{a}} , {a}} entonces, A B, B C y A C. Ahora bien, esto no es verdad siempre. En efecto, sean A = {a} , B = {{a}} y C = {{{a}}} entonces, AB yBC y sin embargo, AC / Ejemplo 1.17Estudiar la relacin que existe entre los siguientes conjuntos: oA = {1, 2} B = {1, 3} C = x R : x2 4x + 3 = 0 D = x R : x2 3x + 2 = 0 E = {x Z+ : x < 3} F = {x Z+ : x es impar y x < 5} 12

15. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a eSolucin o A y B son distintos, ya que 2 A y 2 B y 3 B y 3 A. As pues, hemos encontrado un elemento en / / A que no est en B y un elemento en B que no est en A. Por tanto, por el resultado del ejemplo 1.8, a a A = B. Ahora observemos lo siguiente: Sea x un nmero real arbitrario. Entonces, u x C x2 4x + 3 = 0 x = 1 x = 3 x B o sea, C = B x D x2 3x + 2 = 0 x = 1 x = 2 x A es decir, A = D. Sea x un entero positivo cualquiera. Entonces, x E x < 3 x = 1 x = 2 x A por lo tanto, A = E. Sea x un entero positivo cualquiera. Entonces, x F x es impar x < 5 x = 1 x = 3 x B por lo tanto, F = B. Consecuentemente, A=B A=C A=D A=E A=FNota 1.52 2 2 2B=C B=D B=E B=F2 2 2C=D C=E C=F2 2D=E D=F2E=FCon el conjunto vac puede construirse una sucesin infinita de conjuntos distintos. o oEn la sucesin, o , {} , {{}} , {{{}}} , . . . el primer conjunto no tiene ningn elemento y cada uno de los restantes tiene, exactamente, un elemento u que es el conjunto que le precede en la sucesin. o En la sucesin, o , {} , {, {}} , {, {} , {, {}}} , {, {} , {, {}} , {, {} , {, {}}}} cada conjunto tiene como elementos todos los conjuntos que le preceden en la sucesin. As contando o , desde cero, el conjunto que ocupa el lugar k tiene k elementos.1.3Diagramas de VennUna representacin grfica para los conjuntos son los diagramas de Venn. El conjunto universal se o a representa por el interior de un rectngulo y todos los dems conjuntos se representan por regiones a a cerradas incluidos en el mismo. 13

16. Universidad de Cdiz aDepartamento de Matemticas a UUUA BBBAA(a) A B(b) A y B son disjuntos(c) A y B no son disjuntosDiagramas de Venn Si A es un subconjunto de B, A B, entonces la regin que representa a A, estar contenida en o a la que representa a B (apartado (a) de la gura). Si A y B no tienen elementos en comn (A y B son disjuntos), entonces la regin que representa u o a A estar separada completamente de la regin que representa a B (apartado (b) de la gura). a o Si A y B son dos conjuntos arbitrarios, entonces es posible que algunos elementos estn en A pero e no en B, algunos en B pero no en A, algunos en los dos, A y B, y algunos ni en A, ni en B (apartado (c) en la gura).14

17. Apuntes de Matemtica Discreta a 2. Operaciones con ConjuntosFrancisco Jos Gonzlez Gutirrez e a e Cdiz, Octubre de 2004 a

19. Leccin 2 oOperaciones con Conjuntos Contenido 2.1Deniciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .152.1.116Interseccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o162.1.3Diferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172.1.4Complementario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172.1.5 2.2Unin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o2.1.2Diferencia Simtrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e17Algebra de conjuntos. Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . .202.2.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20Leyes Conmutativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202.2.3Leyes Asociativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .212.2.4Leyes Distributivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .212.2.5Leyes de Identidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222.2.6Ley Involutiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .232.2.7Leyes del Complementario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .232.2.8 2.3Leyes Idempotentes2.2.2Leyes de De Morgan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24Conjunto de las Partes de un Conjunto . . . . . . . . . . . . . . . . . . . . .282.3.1 2.4Denicin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o29Producto cartesiano de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . .302.4.1n-tupla ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .302.4.2Igualdad de n-tuplas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .302.4.3Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .302.4.4Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32Introduciremos las operaciones con conjuntos que nos van a permitir obtener nuevos conjuntos, partiendo de conjuntos ya conocidos. A y B sern dos conjuntos cualesquiera de un universal arbitrario U . a2.1DenicionesDeniremos las principales operaciones entre conjuntos. 15

20. Universidad de Cdiz a2.1.1Departamento de Matemticas aUnin oLa unin de dos conjuntos A y B es el conjunto formado por todos los elementos que pertenecen a A o o a B. Se nota A B. A B = {x : x A x B} . La disyuncin, , se utiliza en el sentido inclusivo, es decir, signica y/o. o2.1.2Interseccin oLa interseccin de dos conjuntos A y B es el conjunto formado por todos los elementos que pertenecen o a A y a B. Se nota A B. A B = {x : x A x B} Si A y B no tienen elementos en comn, es decir, si A B = , entonces diremos que A y B son u conjuntos disjuntos. Ejemplo 2.1Sean A, B y C tres conjuntos.(a) Demostrar que si C A y C B, entonces C (A B), es decir, A B es el mayor conjunto que contiene a A y a B. (b) Demostrar que si C A y C B, entonces C (A B), es decir, A B es el conjunto ms a pequeo que contiene a A y a B. n Solucin o (a) Supongamos que C A y C B, entonces la proposicin o x (x C = x A) x (x C = x B) es verdad. Esta proposicin es equivalente a o x [(x C = x A) (x C = x B)] la cual, a su vez, equivale a x, [ x C = (x A x B)] de aqu que x, x C = x [(A B)] y, por lo tanto, C AB (b) Supongamos que C A y que C B, y sea x un elemento arbitrario de A B entonces, x (A B) xA xB{Denicin de unin} o o=xC xC{Por hiptesis} oxC{Idempotencia de }luego, x, (x A B = x C) de aqu que C (A B)16

21. Matemtica Discreta a2.1.3Francisco Jos Gonzlez Gutirrez e a eDiferenciaLa diferencia entre dos conjuntos A y B es el conjunto formado por todos los elementos que pertenecen a A y no pertenecen a B. Se nota por AB. AB = {x : x A x B} / El conjunto AB se lee A menos B y recibe tambin el nombre de complementario relativo del e conjunto B respecto del conjunto A.2.1.4ComplementarioEl complementario de un conjunto A es el conjunto formado por todos los elementos del conjunto universal que no pertenecen a A. Se nota Ac . Ac = {x : x U x A} / Obsrvese que el complementario de A es igual a la diferencia entre U y A, es decir, Ac = UA. e2.1.5Diferencia Simtrica eLa diferencia simtrica entre dos conjuntos A y B es el conjunto formado por todos los elementos que e pertenecen a A o a B pero no a ambos. Se nota por A B. AB = (AB) (BA)AB AABBABOperaciones con conjuntos 17BA

22. Universidad de Cdiz a Ejemplo 2.2Departamento de Matemticas aSean los conjuntosA = {n Z+ : n13}+B = {n Z : n es par y n20}C = {n Z+ : n es par}Hallar A B, A B, Ac , B c , AB, BA, AB, B C y BC.Solucin o 18

23. Matemtica Discreta aABFrancisco Jos Gonzlez Gutirrez e a e= {n Z+ : n13} {n Z+ : n es par y n20}= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} {2, 4, 6, 8, 10, 12, 14, 16, 18, 20} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 18, 20} AB= {n Z+ : n13} {n Z+ : n es par y n20}= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} {2, 4, 6, 8, 10, 12, 14, 16, 18, 20} = {2, 4, 6, 8, 10, 12} Ac= {n Z+ : n A} / = {n Z+ : n > 13}Bc= {n Z+ : n B} / = {n Z+ : (n B)} = {n Z+ : [n es par (n20)]}+= {n Z : (n es par) (n20)}= {n Z+ : (n es impar) (n > 20)} = {1, 3, 5, 7, 9, 11, . . .} {21, 22, 23, 24, . . .} = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 22, 23, 24, . . .} AB= {n Z+ : n A n B} / = {n Z+ : n A n B c } = {n Z+ : n13 n B c }= {1, 3, 5, 7, 9, 11, 13} BA = {n Z+ : n B n A} / = {n Z+ : n B n Ac } = {n Z+ : n es par y n20 y n > 13}= {n Z+ : n es par y 14n20}= {14, 16, 18, 20} AB=(AB) (BA)= {1, 3, 5, 7, 9, 11, 13} {14, 16, 18, 20} = {1, 3, 5, 7, 9, 11, 13, 14, 16, 18, 20} = {n Z+ : n es par y n20} {n Z+ : n es par}= {n Z+ : n es par y nBC20 y n es par}= {2, 4, 6, 8, 10, 12, 14, 16, 18, 20} BC= {n Z+ : n B y n C} / = {n Z+ : n es par y n20 y n es impar}= 19

24. Universidad de Cdiz a2.2Departamento de Matemticas aAlgebra de conjuntos. DualidadBajo las operaciones definidas en los apartados anteriores, los conjuntos satisfacen varias leyes o identidades. Observaremos que existe una dualidad entre las leyes que utilizan la interseccin y las que utilizan o la unin. o2.2.1Leyes IdempotentesDado cualquier conjunto A en un universal arbitrario U , se verica: 1. A A = A 2. A A = A Demostracin o En efecto, sea x un elemento arbitrario del universal U . Entonces, 1.x (A A) x A x A {Definicin de unin} o o xA{Idempotencia de }De la arbitrariedad de x se sigue que x [x (A A) x A] de aqu que AA=A 2. Anlogamente se prueba que A A = A. a2.2.2Leyes ConmutativasDados dos conjuntos A y B de un universal arbitrario U , se verica: 1. A B = B A 2. A B = B A Demostracin o En efecto, 1. Sea x cualquier elemento de U . Entonces, x (A B) xA xB{Definicin de unin} o ox B x A {Commutatividad de }x (B A){Denicin de unin} o oComo x es cualquiera de U , se sigue que x [x A B x B A] por lo tanto, AB =BA 2. De una forma similar se demuestra que A B = B A. 20

25. Matemtica Discreta a2.2.3Francisco Jos Gonzlez Gutirrez e a eLeyes AsociativasDados tres conjuntos A, B y C de un universal arbitrario, U , se verica: 1. A (B C) = (A B) C 2. A (B C) = (A B) C Demostracin o En efecto, sea x es un elemento arbitrario de U . Entonces, 1.x A (B C) x A [x (B C)]{Definicin de unin} o ox A (x B x C) {Definicin de unin} o o(x A x B) x C{Asociatividad de }(x A B) x C{Definicin de unin} o ox (A B) C{Definicin de unin} o oDe la arbitrariedad de x se sigue que x [x A (B C) x (A B) C] de aqu que A (B C) = (A B) C 2. Anlogamente se demuestra que a A (B C) = (A B) C2.2.4Leyes DistributivasDados tres conjuntos A, B y C de un conjunto universal arbitrario, U , se verica: 1. A (B C) = (A B) (A C) 2. A (B C) = (A B) (A C) Demostracin o En efecto, 1. En efecto, sea x cualquier elemento del conjunto universal U , entonces x A (B C) x A [x (B C)]{Definicin de unin} o ox A (x B x C){Definicin de interseccin} o o(x A x B) (x A x C) {Distributividad}x (A B) x (A C){Definicin de unin} o ox (A B) (A C){Definicin de interseccin} o oAl ser x cualquier elemento de U , se sigue que x [x A (B C) x (A B) (A C)] 21

26. Universidad de Cdiz aDepartamento de Matemticas aconsecuentemente, A (B C) = (A B) (A C) 2. De una forma similar se prueba que A (B C) = (A B) (A C)2.2.5Leyes de IdentidadDado un conjunto cualquiera de un universal arbitrario, U , se verica: 1. A = A 2. A U = U 3. A = 4. A U = A Demostracin o 1. A = A. En efecto, sea x es un elemento arbitrario de U . Entonces, x (A ) xA x{Denicin de unin} o oxA{x es falso siempre}luego, x [x (A ) x A] de aqu que A=A 2. A U = U . Sea x un elemento cualquiera de U . Entonces, x (A U ) xA xU xU{Denicin de unin} o o {x U es verdad siempre}luego, x [x (A U ) x U ] es decir, AU =U 3. A = . Si x es cualquiera de U , entonces x (A ) xA x{Denicin de unin} o ox{x es falso siempre}luego, A= 4. A U = A. Sea x un elemento arbitrario de U . Entonces, xAUxA xU{Definicin de interseccin} o oxA{x U es verdad siempre}luego, AU =A22

27. Matemtica Discreta a2.2.6Francisco Jos Gonzlez Gutirrez e a eLey InvolutivaDado un conjunto cualquiera A de un universal U , se verica: (Ac )c = A Demostracin o Sea x cualquiera de U . Entonces, cx (Ac )x Ac /{Definicin de complementario} o c(x A ){Negacin} o(x A) /{Definicin de complementario} o(x A) {Negacin} oxA{Doble negacin} oluego, cx [x (Ac ) x A] es decir, c(Ac ) = A2.2.7Leyes del ComplementarioDado un conjunto cualquiera A de un universal arbitrario U , se verica: 1. A Ac = U 2. U c = 3. A Ac = 4. c = U Demostracin o 1. A Ac = U . En efecto, sea x cualquier elemento de U . Entonces, x (A Ac ) x A x Ac{Definicin de unin} o oxA xA /{Complementario}x A (x A) {Negacin} oxU{Tautolog a}luego, x [x (A Ac ) x U ] por lo tanto, A Ac = U 2. U c = . En efecto, U c = {x U : x U c } = {x U x U } = / 23

28. Universidad de Cdiz aDepartamento de Matemticas a3. A Ac = . En efecto, A Ac = {x U : x A x Ac } = {x U : x A x A} = / 4. c = U . En efecto, c = {x U : x c } = {x U : x } = {x U } = U /2.2.8Leyes de De MorganDados dos conjuntos A y B en un universal U , se verica: 1. (A B)c = Ac B c 2. (A B)c = Ac B c Demostracin o 1. (A B)c = Ac B c En efecto, sea x un elemento arbitrario del conjunto universal U . Entonces, x (A B)cx (A B) /{Definicin de complementario} o [x (A B)]{Negacin} o [(x A) (x B)] {Definicin de unin} o o(x A) (x B){De Morgan para }(x A) (x B) / /{Negacin} o(x Ac ) (x B c ){Definicin de complementario} occx (A B ){Definicin de interseccin} o oy al ser x un elemento arbitrario de U , se sigue que cx [x (A B) x (Ac B c )] luego, (A B)c = Ac B c 2. Anlogamente se prueba que a (A B)c = Ac B cEjemplo 2.3 Entonces,Sean A, B, C y D subconjuntos arbitrarios de un conjunto universal arbitrario, U .(a) AB A (b) Si A B y C D, entonces (A C) (B D) (c) Si A B y C D, entonces (A C) (B D) (d) A (A B) (e) A B A 24

29. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a e(f) Si A B, entonces A B = B (g) Si A B, entonces A B = A (h) A = A (i) A (BA) = (j) A (BA) = A B (k) A(B C) = (AB) (AC) (l) A(B C) = (AB) (AC) Solucin o (a) AB A En efecto, sea x un elemento arbitrario de U , xABxA xB /{Denicin de diferencia} o=xA{Simplificacin} oluego, x [x AB = x A] consecuentemente, AB A (b) Si A B y C D, entonces (A C) (B D) En efecto, supongamos que A B y C D y sea x un elemento arbitrario de U , entonces xACxA xC{Definicin de unin} o o=xB xD{Hiptesis} ox (B D){Definicin de unin} o oluego, x [x (A C) = x (B D)] por lo tanto, AC BD (c) Si A B y C D, entonces (A C) (B D) Se prueba de forma anloga a la anterior. a (d) A (A B) En efecto, si x es cualquiera de U , entonces xA=xA xB{Adicin} oxAB{Definicin de unin} o oluego, x [x A = x (A B)] de aqu que A (A B) 25

30. Universidad de Cdiz aDepartamento de Matemticas a(e) A B A En efecto, sea x un elemento cualquiera de A B. Entonces, xABxA xB{Definicin de interseccin} o o=xA{Simplificacin} oluego, x [x (A B) = x A] de donde se sigue AB A (f) Si A B, entonces A B = B En efecto, sea x cualquiera de U y supongamos que A B. x (A B) xA xB{Definicin de unin} o o=xB xB{Hiptesis} oxB{Idempotencia de }luego, x [x (A B) = x B] por lo tanto, AB B y por (d) B (A B) De la doble inclusin se sigue la igualdad que buscamos. o (g) Si A B, entonces A B = A Por el apartado (e), tenemos que AB A Veamos la inclusin contraria. o Supongamos que A B y sea x un elemento arbitrario de U , entonces xA=xA xB{Hiptesis} ox (A B){Definicin de interseccin} o oluego, x [x A = x (A B)] de aqu que A (A B) Tenemos, pues, que A (A B) y (A B) A por lo tanto, A=AB (h) A = A Sea x cualquiera de U . Entonces, xAxA x /{Denicin de diferencia} oxA{Por ser x verdad, siempre} /luego, A = {x : x A} = A 26

31. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a e(i) A (BA) = En efecto, A (BA)= A (B Ac ) {Diferencia de conjuntos} = A (Ac B) {Conmutatividad de la unin} o (A Ac ) B={Asociatividad de la interseccin} o= B{Leyes del complementario}= {Leyes de identidad}(j) A (BA) = A B En efecto, A (BA)= A (B Ac ){Diferencia de conjuntos}=(A B) (A Ac ) {Distributividad}=(A B) U{Leyes del complementario}= AB{Leyes de identidad}(k) A(B C) = (AB) (AC) A(B C)c{Diferencia de conjuntos}c{De Morgan}= A (B C) c= A (B C ) =(A A) (B c C c ) {Idempotencia de la interseccin} o=(A B c ) (A C c ) {Commutatividad y asociatividad}=(AB) (AC){Diferencia de conjuntos}(l) A(B C) = (AB) (AC) La demostracin es similar a la del apartado anterior. o Ejemplo 2.4Probar las identidades siguientes:(a) A (A B) = A (b) A (A B) = A (c) AB = A B c (d) A (Ac B) = A B (e) A (Ac B) = A B Solucin o (a) A (A B) = A Sea x un elemento cualquiera del universal U , entonces x A (A B) =x A x (A B) {Denicin de unin} o o xAluego x, x A (A B) = x A es decir, A (A B) A 27

32. Universidad de Cdiz aDepartamento de Matemticas aPor otro lado, siempre se verifica que A A X, X U en particular, A A (A B) De la doble inclusin se sigue el resultado, o A = A (A B) (b) A (A B) = A En efecto, A (A B)(A A) (A B) {Distributividad}== A (A B){Idempotencia de la interseccin} o= A{Apartado (a)}(c) AB = A B c En efecto, sea x cualquiera del conjunto universal U , entonces xABxA xB /xA xBx (A B c ){Definicin de diferencia} o c{Definicin de complementario} o {Definicin de interseccin} o oluego, x, x AB x (A B c ) por lo tanto, AB = A Bc (d) A (Ac B) = A B En efecto, A (Ac B)=(A Ac ) (A B) {Distributividad}= U (A B){Leyes del complementario}= AB{Leyes de identidad}(e) A (Ac B) = A B A (Ac B)=(A Ac ) (A B) {Distributividad}= (A B) = AB2.3{Leyes del complementario} {Leyes de identidad}Conjunto de las Partes de un ConjuntoDado un conjunto A, si nos referimos a algunos de sus subconjuntos estar amos considerando un conjunto de conjuntos. En tales casos hablaremos de una clase de conjuntos o coleccin de conjuntos en vez de o un conjunto de conjuntos. Si quisiramos considerar algunos de los conjuntos de una clase dada de e conjuntos, entonces hablaremos de una subclase o de una subcoleccin. o 28

33. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a eEjemplo 2.5 Sea A = {a, b, c, d, e} y sea A la clase de subconjuntos de A que contienen exactamente tres elementos de A. Entonces, A = {{a, b, c} , {a, b, d} , {a, b, e} , {a, c, d} , {a, c, e} , {a, d, e} , {b, c, d} , {b, c, e} , {c, d, e}} siendo los elementos de A los conjuntos: {a, b, c} , {a, b, d} , {a, b, e} , {a, c, d} , {a, c, e} , {a, d, e} , {b, c, d} , {b, c, e} y {c, d, e}2.3.1Denicin oDado un conjunto A, llamaremos conjunto de las partes de A a la clase o coleccin de todos los o subconjuntos de A y se nota por P(A). Obsrvese que de acuerdo con esta definicin, si X es un conjunto cualquiera de U , entonces e o X P(A) X A Ejemplo 2.6Sea A = {1, 2, 3}. Entonces, P(A) = {, {1} , {2} , {3} , {1, 2} , {1, 3} , {2, 3} , {1, 2, 3}}Nota 2.1 Si el conjunto A es finito y tiene n elementos, entonces P(A) tambin es un conjunto finito e y tiene 2n elementos. En efecto, sea X un elemento arbitrario de P(A). Para cada a A, hay dos opciones a X a X; o / como hay n elementos en A, habr a n veces 2 2 2 2 = 2n diferentes conjuntos X. Es decir, P(A) tiene 2n elementos. Veremos otra demostracin en una leccin posterior. o o Ejemplo 2.7Especificar el conjunto de las partes para cada uno de los conjuntos siguientes:(a) {a, b, c} (b) {{a, b} , {c}} (c) {{a, b} , {b, a} , {a, b, b}} Solucin o (a) {a, b, c} P ({a, b, c}) = {, {a} , {b} , {c} , {a, b} , {a, c} , {b, c} , {a, b, c}} (b) {{a, b} , {c}} P ({{a, b} , {c}}) = {, {{a, b}} , {{c}} {{a, b} , {c}}} (c) {{a, b} , {b, a} , {a, b, b}} P ({{a, b} , {b, a} , {a, b, b}}) = P ({a, b}) = {, {a, b} {{a, b}}}29

34. Universidad de Cdiz a2.4Departamento de Matemticas aProducto cartesiano de conjuntosEl concepto matemtico de relacin est basado en la nocin de relacin entre objetos. Algunas relaciones a o a o o describen comparaciones entre elementos de un conjunto: Una caja es ms pesada que otra, un hombre a es ms rico que otro, etc. Otras relaciones involucran elementos de conjuntos diferentes, tal como x a vive en y, donde x es una persona e y es una ciudad, x es propiedad de y donde x es un edicio e y es una empresa, x naci en el pa y en el ao z. o o s n Todos los ejemplos anteriores son de relaciones entre dos o tres objetos, sin embargo, en principio, podemos describir relaciones que abarquen n objetos, donde n es cualquier entero positivo. Cuando hagamos una armacin que relacione n objetos, ser necesario no solamente especicar los objetos en s o a mismos sino tambin una ordenacin de los mismos. Por ejemplo, la posicin relativa de 3 y 5 da lugar e o o unicamente a dos armaciones 5 < 3 y 3 < 5, siendo una de ellas falsa y la otra verdadera. Usaremos las n-tuplas ordenadas de elementos para especificar una sucesin finita de objetos no neceo sariamente distintos; la posicin relativa de los objetos en la sucesin nos dar la ordenacin necesaria o o a o de los mismos.2.4.1n-tupla ordenadaLlamaremos n-tupla ordenada a una sucesin de n objetos a1 , a2 , . . . , an dados en un cierto orden y o la notaremos por (a1 , a2 , . . . , an ). Obsrvese que es fundamental el orden en que escribamos los elementos de la n-tupla, as e (a1 , a2 , . . . , an ) = (a2 , a1 , . . . , an ) Si n = 2, una n-tupla ordenada se llama par ordenado y si n = 3, terna ordenada.2.4.2Igualdad de n-tuplasDiremos que dos n-tuplas ordenadas son iguales si, y slo si, sus i-simas componentes son iguales o e para todo i, 1 i n, es decir, (a1 , a2 , . . . , an ) = (b1 , b2 , . . . , bn ) ai = bi , i, 1inMuchas veces trataremos con colecciones de n-tuplas donde la componente i-sima de cada n-tupla es e un elemento de un conjunto Ai . Denimos el conjunto de todas las n-tuplas ordenadas.2.4.3Producto cartesianoDada una coleccin arbitraria de conjuntos A1 , A2 , . . . , An , llamaremos producto cartesiano de los o mismos y lo notaremos por A1 A2 An , al conjunto formado por todas las n-tuplas ordenadas, (a1 , a2 , . . . , an ), donde ai Ai , 1 i n, es decir, A1 A2 An = {(a1 , a2 , . . . , an ) : ai Ai 1 En el caso de dos conjuntos A y B, tendremos A B = {(a, b) : a A b B} y este producto se llama binario si A = B, o sea, A A = {(a, b) : a A b A} 30in}

35. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a ey suele notarse por A2 . Su extensin a n conjuntos se dene como o (nA A A = {(a1 , a2 , . . . , an ) : ai A, 1in}y lo notaremos por An . Nota 2.2 Obsrvese que A = . En efecto, si A no fuese vac entonces existir al menos, un e o, a, par (a, b) A de aqu que a A y b , lo cual es imposible. Ejemplo 2.8 Considerando el conjunto R de los nmeros reales, el producto cartesiano R2 = R R u es el conjunto de todos los pares ordenados de nmeros reales. u R R = R2 = {(x, y) : x, y R} Cada punto P representa un par ordenado (x, y) de nmeros reales y viceversa. A R2 se le llama u normalmente plano cartesiano. Ejemplo 2.9Sean A = {x R : 12} y B = {y R : 0xy1}. Hallar A B y B A.Solucin oA B = {(x, y) : 1x2 0y1}B A = {(y, x) : 0y1 1x2}3 3 2 2 BA1 1 AB 0 1 2 3 0 1 2 3Ejemplo 2.9 Cuando A y B son, como en este caso, conjuntos de nmeros reales, su producto cartesiano puede u representarse como un conjunto de puntos en el plano cartesiano. Ejemplo 2.10Sea 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), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)} 31

36. Universidad de Cdiz aDepartamento de Matemticas atambin, e A A = {(1, 1), (1, 2), (2, 1), (2, 2)} B B = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}Nota 2.3 En los ejemplos anteriores se observa que el producto cartesiano de dos conjuntos no es conmutativo. Es decir, en general, A B = B A Ejemplo 2.11 A2 . 3Sean A1 = {1, 2}, A2 = {a, b} y A3 = {x, y}. Calcular A1 A2 A3 , A2 A1 A3 ySolucin o A1 A2 A3 = {(1, a, x), (1, a, y), (1, b, x), (1, b, y), (2, a, x), (2, a, y), (2, b, x), (2, b, y)} A2 A1 A3 = {(a, 1, x), (a, 1, y), (a, 2, x), (a, 2, y), (b, 1, x), (b, 1, y), (b, 2, x), (b, 2, y)} A2 = A3 A3 = {(x, x), (x, y), (y, x), (y, y)} 32.4.4PropiedadesEl producto cartesiano es distributivo respecto de la unin y la interseccin de conjuntos, es decir, si o o A, B y C son tres conjuntos cualesquiera, se verica: (a) A (B C) = (A B) (A C) (b) A (B C) = (A B) (A C) (c) (A B) C = (A C) (B C) (d) (A B) C = (A C) (B C) Demostracin o (a) A (B C) = (A B) (A C) En efecto, sea (x, y) un elemento arbitrario de A (B C), entonces, (x, y) A (B C) x A y (B C){Def. producto cartesiano}x A (y B y C){Def. de unin} o(x A y B) (x A y C) {Dist. de respecto de }(x, y) (A B) (x, y) (A C){Def. producto cartesiano}(x, y) (A B) (A C){Definicin de unin} o oluego, (x, y) ((x, y) A (B C) (x, y) (A B) (A C)) es decir, A (B C) = (A B) (A C) Los apartados (b), (c) y (d) se demuestran de una forma similar. Ejemplo 2.12 siguientes:Si U = Z+ , A = {1, 2, 3, 4}, B = {2, 5} y C = {3, 4, 7}, determ nense los conjuntos(a) A B 32

37. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a e(b) B A (c) A (B C) (d) (A B) C (e) (A C) (B C) Solucin o (a) A B = {(a, b) : a A b B} luego, A B = {(1, 2), (1, 5), (2, 2), (2, 5), (3, 2), (3, 5), (4, 2), (4, 5)} (b) B A = {(b, a) : b B a A} luego, B A = {(2, 1), (2, 2), (2, 3), (2, 4), (5, 1), (5, 2), (5, 3), (5, 4)} (c) A (B C) = {1, 2, 3, 4, (2, 3), (2, 4), (2, 7), (5, 3), (5, 4), (5, 7)} (d) (A B) C= {(1, 3), (1, 4), (1, 7), (2, 3), (2, 4), (2, 7), (3, 3), (3, 4), (3, 7), (4, 3), (4, 4), (4, 7), (5, 3), (5, 4), (5, 7)}(e) (A C) (B C)= {(1, 3), (1, 4), (1, 7), (2, 3), (2, 4), (2, 7), (3, 3), (3, 4), (3, 7), (4, 3), (4, 4), (4, 7), (5, 3), (5, 4), (5, 7)}Ejemplo 2.13 Sean A = {a, b, c}, B = {b, c, d} y C = {a, d}. Encontrar A B C utilizando un diagrama en rbol. a Solucin o a d a d a d a d a d aEjemplo 2.13 33 d adcbdcbdcbcba d a d a d

38. Universidad de Cdiz aDepartamento de Matemticas aLa figura muestra el diagrama en rbol. Recorriendo cada una de las ramas obtenemos las distintas a ternas que integran el producto cartesiano de los tres conjuntos, es decir, ABC= {(a, b, a), (a, b, d), (a, c, a), (a, c, d), (a, d, a), (a, d, d), (b, b, a), (b, b, d), (b, c, a) (b, c, d), (b, d, a), (b, d, d), (c, b, a), (c, b, d), (c, c, a), (c, c, d), (c, d, a), (c, d, d)}Ejemplo 2.14Dados tres conjuntos arbitrarios A, B, C U , probar A (B C) = (A B) (A C)Solucin o A (B C) = (A B) (A C) En efecto, (a, b) A (B C) a A b (B C)a A (b B b C)(a A b B) (a A b C)(a, b) A B (a, b) A C(a, b) (A B) (A C)luego, (a, b) ((a, b) A (B C) (a, b) (A B) (A C)) es decir, A (B C) = (A B) (A C)Ejemplo 2.15 Hallar A BSe consideran los conjuntos A = {x Z : 3x8} y B = {x Z : 6 < x4}.Solucin o A = {x Z : 38} = {3, 4, 5, 6, 7, 8}xB = {x Z : 6 < x4} = {5, 4}luego, AB = {(3, 5), (4, 5), (5, 5), (6, 5), (7, 5), (8, 5), (3, 4), (4, 4), (5, 4), (6, 4), (7, 4), (8, 4)}Ejemplo 2.16Demostrar que (A1 B1 ) (A2 B2 ) = (A1 A2 ) (B1 B2 )Solucin o En efecto, sea (a, b) un elemento arbitrario de (A1 B1 ) (A2 B2 ). Entonces, (a, b) (A1 B1 ) (A2 B2 ) (a, b) (A1 B1 )) (a, b) (A2 B2 ){Def. de }(a A1 b B1 ) (a A2 b B2 ) {Def. de }(a A1 a A2 ) (b B1 b B2 ) {Asoc. y conm.}a (A1 A2 ) b (B1 B2 )(a, b) (A1 A2 ) (B1 B2 ) 34

39. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a eluego, (a, b) ((a, b) (A1 B1 ) (A2 B2 ) (a, b) (A1 A2 ) (B1 B2 )) es decir, (A1 B1 ) (A2 B2 ) = (A1 A2 ) (B1 B2 )Ejemplo 2.17Dados los conjuntos A = {a, b, c, d} , B = {1, 2, 3} y C = {, , }, hallar(a) A B C (b) A (B C) (c) A (B C) Solucin o (a) ABC= {(a, 1, ), (a, 1, ), (a, 1, ), (a, 2, ), (a, 2, ), (a, 2, ), (a, 3, ), (a, 3, ), (a, 3, ), (b, 1, ), (b, 1, ), (b, 1, ), (b, 2, ), (b, 2, ), (b, 2, ), (b, 3, ), (b, 3, ), (b, 3, ), (c, 1, ), (c, 1, ), (c, 1, ), (c, 2, ), (c, 2, ), (c, 2, ), (c, 3, ), (c, 3, ), (c, 3, ), (d, 1, ), (d, 1, ), (d, 1, ), (d, 2, ), (d, 2, ), (d, 2, ), (d, 3, ), (d, 3, ), (d, 3, )}(b) A (B C) = A = (c) A (B C) Segn hemos visto en la leccin, u o A (B C) = (A B) (A C) luego, A (B C)= {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c, 2), (c, 3), (d, 1), (d, 2), (d, 3) (a, ), (a, ), (a, ), (b, ), (b, ), (b, ), (c, ), (c, ), (c, ), (d, ), (d, ), (d, )}Ejemplo 2.18Para A, B, C U , probar que A (BC) = (A B)(A C).Solucin o En efecto, (a, b) A (BC) aA bBCa A (b B b C) /(a A b B) (a A b C) /(a, b) A B (a, b) (A C) /(a, b) (A B)(A C)luego, (a, b) ((a, b) A (BC) (a, b) (A B)(A C)) es decir, A (BC) = (A B)(A C)35

40. Apuntes de Matemtica Discreta a 3. Principios Bsicos de Conteo aFrancisco Jos Gonzlez Gutirrez e a e Cdiz, Octubre de 2004 a

42. Leccin 3 oPrincipios Bsicos de Conteo a Contenido 3.137Denicin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o373.1.2Recubrimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .383.1.3 3.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1.1Particin de un Conjunto oCardinal de un conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39 39Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .393.2.2 3.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.1Principio de Adicin oRegla de la Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40 41Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .413.3.2 3.4. . . . . . . . . . . . . . . . . . . . . . . . . . . .3.3.1Principio de Multiplicacin oRegla del Producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42Principio de Inclusin-Exclusin . . . . . . . . . . . . . . . . . . . . . . . . . o o453.4.1453.4.2Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .493.4.3 3.5Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Generalizacin del Principio de Inclusin-Exclusin . . . . . . . . . . . . . . . . o o o59Principio de Distribucin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o693.5.1Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .693.5.2Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70Desarrollamos en esta leccin los principios bsicos para contar elementos de un conjunto, el de Adicin, o a o el de Multiplicacin, el de Inclusin-Exclusin y finalizaremos con el de Distribucin. o o o o3.1 3.1.1Particin de un Conjunto o Denicin oDado un conjunto A, diremos que los subconjuntos de A, A1 , A2 , . . . , An , constituyen una particin o del mismo si se cumplen las siguientes condiciones: 1. Ai = ; i = 1, 2, . . . . . . , n 2. Ai Aj = ; i = j, i, j = 1, 2, . . . . . . n 3. A1 A2 An = A 37

43. Universidad de Cdiz a3.1.2Departamento de Matemticas aRecubrimientoSi los subconjuntos B1 , B2 , . . . . . . , Bn de un conjunto A cumplen las condiciones 1. y 3. de la denicin anterior, diremos que B1 , B2 , . . . . . . , Bn constituyen un recubrimiento de A. o Ejemplo 3.1AA2A3A1A4Particin del conjunto A. Ejemplo 3.1 o Los subconjuntos A1 , A2 , A3 y A4 constituyen una particin de A. o Ejemplo 3.2Si A = {a, b, c, d, e, f, g, h, i, j, k}, los conjuntosA1 = {a, b, c, d} A2 = {c, d, e, f, g} A3 = {g, h, i} A4 = {j, k} constituyen un recubrimiento del conjunto A. Solucin o En efecto, Ai = ; i = 1, 2, 3, 4 A1 A2 A3 A4 = {a, b, c, d} {c, d, e, f, g} {g, h, i} {j, k} = {a, b, c, d, e, f, g, h, i, j, k} = A 38

44. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a eSin embargo no es una particin ya que, por ejemplo, o A1 A2 = {a, b, c, d} {c, d, e, f } = {c, d} = 3.1.3Cardinal de un conjuntoSi A es un conjunto nito no vac designaremos por cardinal de A al nmero de elementos que tiene o, u A. Si A es el conjunto vac entonces su cardinal es cero. Lo notaremos |A|. o,3.2Principio de Adicin oEstudiamos el ms bsico y simple de los principios para contar elementos de un conjunto. a a3.2.1TeoremaSi A1 , A2 , . . . , An es una coleccin de conjuntos nitos no vac disjuntos dos a dos, entonces o os, |A1 A2 An | = |A1 | + |A2 | + + |An | Demostracin o Procederemos por induccin sobre el nmero de conjuntos n. o u Paso bsico. Veamos que el teorema es cierto para n = 2. a En efecto, sean A1 y A2 dos conjuntos finitos tales que A1 A2 = . Pues bien, si A1 = {a1 , a2 , . . . , aq } y A2 = {b1 , b2 , . . . , br } al ser disjuntos no tendrn elementos comunes, de aqu que a A1 A2 = {a1 , a2 , . . . , aq , b1 , b2 , . . . , br } luego, |A1 A2 | = q + r = |A1 | + |A2 | y el teorema es cierto para n = 2. Paso inductivo. Supongamos que el teorema es cierto para n = p, es decir, si A1 , A2 , . . . , Ap son una familia de conjuntos finitos y disjuntos dos a dos, entonces pp|Ai |Ai = i=1i=1Veamos que el teorema es cierto para n = p + 1. En efecto, sea A1 , A2 , . . . , Ap , Ap+1 una familia de conjuntos finitos y dos a dos disjuntos, entonces por la asociatividad de la unin de conjuntos, o p+1pAi = A1 A2 Ap Ap+1 = (A1 A2 Ap ) Ap+1 = i=1Ai i=139 Ap+1

45. Universidad de Cdiz aDepartamento de Matemticas asiendo, p Ap+1=(A1 A2 Ap ) Ap+1=Ai(A1 Ap+1 ) (A2 Ap+1 ) (Ap Ap+1 )i=1= = luego, pp+1AiAi= Ap+1i=1i=1pAi + |Ap+1 |{Paso bsico} a|Ai | + |Ap+1 |{Hiptesis de induccin} o o= i=1 p= i=1 p+1|Ai |= i=1Consecuentemente, por el primer principio de induccin, la propiedad es cierta para todo entero positivo o n y, |A1 A2 An | = |A1 | + |A2 | + + |An |Obsrvese que en este tipo de problemas, la palabra o aparece o se sobrentiende impl e citamente. En cualquier caso en el que tengamos una accin simple a realizar y que debe satisfacer una condicin u otra o o siendo las condiciones mutuamente excluyentes, utilizaremos normalmente el principio de adicin. Este o primer principio del conteo puede expresarse como sigue:3.2.2Regla de la SumaSi una primera tarea puede realizarse de m formas distintas, mientras que una segunda tarea puede realizarse de n formas distintas, y no es posible realizar ambas tareas de manera simultnea, entonces, a para llevar a cabo cualquiera de ellas pueden utilizarse cualquiera de m + n formas. Ejemplo 3.3 Se lanza al aire una moneda cuatro veces. De cuntas formas distintas pueden obtenerse a una, dos, tres o cuatro caras? Solucin o Sea Ai el conjunto formado por todos los resultados posibles en los que aparezcan, exactamente, i caras al lanzar cuatro veces la moneda. Entonces, A1 = {(c, x, x, x), (x, c, x, x), (x, x, c, x), (x, x, x, c)} A2 = {(c, c, x, x), (c, x, c, x), (c, x, x, c), (x, c, c, x), (x, c, x, c), (x, x, c, c)} A3 = {(c, c, c, x), (c, c, x, c), (c, x, c, c), (x, c, c, c)} A4 = {(c, c, c, c)} y el conjunto A1 A2 A3 A4 estar formado por todos los resultados en los que aparecen una, dos, a tres o cuatro caras, por tanto el nmero pedido es el cardinal de dicho conjunto. Al ser los Ai dos a dos u disjuntos, por el principio de adicin, tendremos que habr o a |A1 A2 A3 A4 | = |A1 | + |A2 | + |A3 | + |A4 | = 15 40

46. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a eformas distintas de obtener una, dos, tres o cuatro caras.3.3Principio de Multiplicacin oEste principio nos va a permitir resolver con ms comodidad situaciones que involucren procesos que a consistan en acciones sucesivas. Supongamos una accin que consista en una secuencia de pasos. Por ejemplo tirar un dado, luego otro o y a continuacin un tercero. Diremos que los pasos son independientes si el nmero de formas en que o u puede hacerse cada uno de ellos no depende del nmero de formas en que pueden realizarse cada uno de u los otros.3.3.1TeoremaSi A1 , A2 , . . . , An es una coleccin de conjuntos nitos no vac entonces o os, |A1 A2 An | = |A1 | |A2 | |An | Demostracin o Procederemos por induccin sobre el nmero de conjuntos, n. o u Paso bsico. Veamos si el teorema es cierto para n = 2. En efecto, sean A1 y A2 dos conjuntos finitos a no vac os, A1 = {a1 , a2 , . . . , aq } y A2 = {b1 , b2 , . . . , br } Por definicin de producto cartesiano, o A1 A2 = {(ai , bj ) : ai A1 y bj A2 } para cada uno de los ai , 1iq, tendremos los pares distintos, (ai , b1 ), (ai , b2 ), . . . , (ai , br )es decir, r pares o r elementos de A1 A2 . Haciendo lo mismo para cada uno de los ai Ai , 1 tendremos (a1 , b1 ), (a1 , b2 ), . . . , (a1 , br )iq,(a2 , b1 ), (a2 , b2 ), . . . , (a2 , br ) ........................... (aq , b1 ), (aq , b2 ), . . . , (aq , br ) o sea, un total de q r pares distintos en A1 A2 , luego |A1 A2 | = q r = |A1 | |A2 | por tanto, la proposicin es cierta para n = 2. o Paso inductivo. Supongamos que es cierta para n = p, es decir si A1 , A2 , . . . , Ap es una coleccin de o conjuntos finitos no vac os. Entonces, |A1 A2 Ap | = |A1 | |A2 | |Ap | Veamos si la proposicin es cierta para n = p + 1. En efecto, si A1 , A2 , . . . , Ap , Ap+1 es una coleccin de o o conjuntos finitos no vac entonces os, |A1 A2 Ap Ap+1 | = |(A1 A2 Ap ) Ap+1 |{Asociatividad de }= |A1 A2 Ap | |Ap+1 |{Paso bsico} a= |A1 | |A2 | |Ap | |Ap+1 |{Paso inductivo}41

47. Universidad de Cdiz aDepartamento de Matemticas aConsecuentemente, por el Principio de induccin matemtica, el teorema es cierto para todo entero o a positivo, n, es decir, |A1 A2 An | = |A1 | |A2 | |An |Ejemplo 3.4Cuntos resultados distintos son posibles al tirar tres dados diferentes? aSolucin o Sean A1 , A2 y A3 los conjuntos formados por los posibles resultados que podamos obtener al tirar cada uno de los tres dados, entonces |Ai | = 6, i = 1, 2, 3 y cada resultado es un elemento del producto cartesiano A1 A2 A3 , luego por el principio de multiplicacin, habr o a |A1 A2 A3 | = |A1 | |A2 | |A3 | = 6 6 6 = 216 resultados distintos. Obsrvese que al ser diferentes los dados, podemos etiquetarlos como primero, segundo y tercero y tratar e la tirada como una accin con tres pasos sucesivos, cada uno de las cuales tiene seis resultados posibles. o El nmero de posibilidades ser, por tanto, u a 6 6 6 = 216 Obsrvese tambin que si los dados no fueran diferentes, la respuesta ser distinta. Por ejemplo ser e e a a imposible distinguir entre el resultado 152 y el 251. Ejemplo 3.5 Un nmero de telfono consta de siete d u e gitos. Si la primera ha de ser un nmero entre u 2 y 9, ambos inclusive, la segunda y la tercera han de ser nmeros entre 1 y 9 ambos inclusive. Cuntos u a nmeros de telfono distintos pueden formarse con estas condiciones? u e Solucin o Sean los conjuntos, A1 = {2, 3, 4, 5, 6, 7, 8, 9} A2 = A3 = {1, 2, 3, 4, 5, 6, 7, 8, 9} A4 = A5 = A6 = A7 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} El nmero de telfonos con numeraciones distintas que pueden formarse son los del conjunto u e A1 A2 A3 A4 A5 A6 A7 Por el principio de multiplicacin, o |A1 A2 A7 | = |A1 | |A2 | |A3 | |A4 | |A5 | |A6 | |A7 | = =3.3.28 9 9 10 10 10 10 6.480.000Regla del ProductoSi un procedimiento puede descomponerse en las etapas primera y segunda, y si existen m resultados posibles de la primera etapa y si, para cada uno de estos resultados, existen n resultados posibles para la segunda etapa, entonces el procedimiento entero puede realizarse, en el orden dado, de mn formas. Ejemplo 3.6 entes:Se dispone de una baraja de 40 cartas de la cual extraemos cuatro de dos formas difer-42

48. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a e(a) Sin devolucin de cada carta extra o da. (b) Con devolucin de la carta en cada extraccin. o o Calcular el nmero de formas diferentes de obtener cuatro cartas en cada caso. u Solucin o Consideraremos el experimento como una accin con cuatro pasos independientes. o (a) Para el primer paso tenemos 40 opciones posibles y como la carta extra no se devuelve quedarn da a 39 opciones para el segundo paso y, por la misma razn, 38 y 37 opciones para el tercero y el cuarto, o respectivamente. As pues el experimento podr hacerse de a 40 39 38 37 = 2193360 formas distintas. (b) Cada carta extra se devuelve a la baraja. Por tanto, para cada una de las cuatro extracciones da dispondremos de las cuarenta. As pues, el nmero de formas diferentes de obtener las cuatro cartas u es 40 40 40 40 = 2560000Ejemplo 3.7 tirada.Se lanzan dos dados, uno azul y otro rojo, a continuacin se registra el resultado de cada o(a) En cuntos resultados la suma es 7 u 11? a (b) En cuntos resultados uno y slo uno de los dados muestra un 2? a o (c) En cuntos resultados ninguno de los dados muestra un 2? a Solucin o(a) Sean a y b los resultados de los dados azul y rojo, respectivamente. Entonces, a, b {1, 2, 3, 4, 5, 6} y el par (a, b) puede considerarse como un par ordenado. Pues bien, si A es el conjunto formado por todos los pares ordenados cuya suma sea 7 y B el formado por aquellos que suman 11, entonces, A = {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)} B = {(5, 6), (6, 5)} y el nmero de resultados en los cuales la suma es 7 u 11 ser igual al cardinal de A B. Al ser A u a y B disjuntos, por el principio de adicin, habr o a |A B| = |A| + |B| = 8 resultados que cumplan las condiciones requeridas. 43

49. Universidad de Cdiz aDepartamento de Matemticas a(b) Sean A1 = {2} B1 = {1, 3, 4, 5, 6} y A2 = {1, 3, 4, 5, 6} B2 = {2} donde Ai y Bi , i = 1, 2, representan, respectivamente, los resultados de los dados azul y rojo. Entonces, todos los resultados en los cuales aparece un 2 en uno slo de los dados, son los elementos o del conjunto (A1 B1 ) (A2 B2 ) siendo A1 B1 y A2 B2 , disjuntos. Consecuentemente, por el principio de adicin y luego por el de multiplicacin tendremos que el o o nmero de resultados en los que uno slo de los dados muestra un 2 es u o |(A1 B1 ) (A2 B2 )| = |A1 B1 | + |A2 B2 | = |A1 | |A2 | + |B1 | |B2 | =1 5 + 1 5 = 10(c) Utilizando los mismos conjuntos que en el apartado anterior, los resultados en los que ninguno de los dos dados muestra un 2 son los elementos de A2 B1 . Por el principio de multiplicacin, habr o a |A2 B1 | = |A2 | |B1 | = 5 5 = 25 resultados que cumplen la condiciones pedidas. Ejemplo 3.8 Un viajante de comercio ha de visitar n ciudades sin pasar dos veces por ninguna de ellas. Cuntas rutas distintas puede tomar si el viaje ha de empezar y terminar en la ciudad A? a Solucin o El viajante elige cualquiera de las n 1 ciudades restantes para la primera visita, las opciones para la segunda ser n2 y n3 posibilidades para la siguiente. Seguimos as sucesivamente y por el principio an de multiplicacin, el nmero de rutas distintas ser o u a: (n 1)(n 2) 3 2 1 Obsrvese que al contar de esta forma, el orden en que se visitan las ciudades es importante, es decir una e ruta tal como ABCDEFA es distinta de la AFEDCBA. Si las rutas que se recorren en sentidos inversos las consideramos iguales, el nmero de posibilidades se reducir a: u a (n 1)(n 2) 3 2 1 2 es decir, la mitad de opciones. En el siguiente ejemplo, veremos una situacin en la cual se mezclan los principios de adicin y multiplio o cacin. o Ejemplo 3.9 El viajante de comercio del ejemplo anterior ha de visitar cinco ciudades A,B,C,D y E, teniendo su base en la ciudad A. Cuntas rutas distintas puede tomar si no puede visitar la ciudad E a hasta despus de haber visitado la B o la C? e Solucin o Como la ciudad E no puede ser visitada hasta despus de visitar B o C, la primera visita deber ser a B e a o a C o a D. 44

50. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a e Si la primera visita es a la ciudad B, entonces el viajante tiene tres opciones para la segunda, dos para la siguiente y una para la ultima, luego por el principio de multiplicacin hay o 321=6 rutas distintas teniendo a B como la primera ciudad visitada. Si la primera ciudad visitada es C, un razonamiento idntico al anterior ofrecer al viajante el e a mismo nmero de opciones, es decir, seis rutas distintas. u Si la primera ciudad visitada es la D, entonces hay dos opciones para la segunda (B y C), dos opciones para la siguiente y una para la ultima. Consecuentemente, el nmero de opciones distintas u es, en este caso, por el principio de multiplicacin o 221=4As pues, por el principio de adicin existen un total de o 6 + 6 + 4 = 16 rutas posibles que puede tomar el viajante.3.4Principio de Inclusin-Exclusin o oEl principio de adicin establec que si X es la unin de una coleccin de conjuntos A1 , A2 , . . . , An , o a o o disjuntos dos a dos, entonces |X| = |A1 | + |A2 | + + |An | . En muchas ocasiones, necesitaremos calcular el nmero de elementos de un conjunto X que es la unin u o de una coleccin de conjuntos A1 , A2 , . . . , An que no sean disjuntos. El principio de inclusin-exclusin o o o nos dice como hacerlo en funcin del nmero de elementos de los conjuntos A1 , A2 , . . . , An . o u En s ntesis, este principio nos dice que si sabemos contar elementos de intersecciones de conjuntos, entonces podremos determinar el tamao de la unin de dichos conjuntos. n o3.4.1TeoremaSean A y B dos subconjuntos de un conjunto universal arbitrario, U . Entonces, |A B| = |A| + |B| |A B| Demostracin o 45

51. Universidad de Cdiz aDepartamento de Matemticas a U AB ABABABBAPrincipio de Inclusin-Exclusin o o Intuitivamente, podemos justificar este teorema examinando la figura. Si sumamos el nmero de elemenu tos que hay en A y en B, entonces contamos los elementos de A B dos veces. As pues, para encontrar el |A B| deber amos sumar |A| a |B| y restar |A B|. Veamos una demostracin formal. o Sea x un elemento cualquiera de U . Entonces, x (A B) (x A) (x B).(3.1)Ahora bien, si un elemento x est en A, puede estar en A y no en B o en A y en B, es decir, a x A [(x A) (x B)] [(x A) (x B)] / o sea, x A [x (AB)] [x (A B)](3.2)A = (AB) (A B)(3.3)de aqu que Tambin, si un elemento x est en B, razonando exactamente igual, tendremos e a x B [x (BA)] [x (A B)](3.4)B = (BA) (A B)(3.5)luego Llevando los resultados (3.2) y (3.4) a (3.1), obtenemos x (A B) [x (AB)] [x (A B)] [x (BA)](3.6)es decir, si un elemento pertenece a A B, entonces puede estar en A y no en B o en B o en A y en B o en B y no en A. 46

52. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a eDe (3.6) se sigue directamente que A B = (AB) (A B) (BA) .(3.7)Adems, a (AB) (A B)=(A B c ) (A B)= A (B c B) = A = (AB) (BA)=(A B c ) (B Ac )= A B c B Ac = A Ac = (A B) (BA)=(A B) (B Ac )= A B Ac = A Ac B = es decir, los tres conjuntos son disjuntos dos a dos, por lo tanto (3.3), (3.5) y (3.7) son, respectivamente, descomposiciones de los conjuntos A, B y A B en unin de subconjuntos disjuntos, de aqu que por el o principio de adicin, o |A| = |AB| + |A B| = |AB| = |A| |A B| |B| = |BA| + |A B| = |BA| = |B| |A B| |A B| = |AB| + |A B| + |BA| y sustituyendo los dos primeros resultados en la tercera igualdad, |A B| = |A| |A B| + |B| |A B| + |A B| = |A| + |B| |A B|Ejemplo 3.10 De un grupo de programadores, 35 estn familiarizados con ordenadores del tipo A, 41 a con ordenadores del tipo B y 46 con algunos de los dos. Cuntos estn familiarizados con ambos? a a Solucin o Sea P el conjunto de todos los programadores y sean A y B los subconjuntos de P formados por los que estn familiarizados con los ordenadores de tipo A y tipo B, respectivamente. Los que lo estn con a a ambos son, por tanto, los del conjunto A B. Pues bien, segn los datos del enunciado, u |A| = 35 |B| = 41 |A B| = 46. Aplicando el principio de inclusin-exclusin, o o |A B| = |A| + |B| |A B| = |A B| = 35 + 41 46 = 30 Hay, por tanto, 30 programadores que estn familiarizados con ambos tipos de ordenadores. a Ejemplo 3.11 Los 100 alumnos de una facultad se han examinado de Matemtica Discreta y de Lgica a o Matemtica, obteniendo los siguientes resultados en los exmenes. a a 47

53. Universidad de Cdiz aDepartamento de Matemticas a20 alumnos no han aprobado ninguna de las dos asignaturas. Han aprobado las dos asignaturas un total de 25 personas. El nmero de alumnos que han aprobado Matemtica discreta es el doble de los que han aprobado u a el Lgica Matemtica. o a Cuntos alumnos aprobaron unicamente Matemtica discreta? a a Cuntos alumnos aprobaron unicamente Lgica Matemtica? a o a Solucin o Un diagrama de Venn que reeja la situacin planteada en el ejercicio es el de la gura, donde D y o L son los conjuntos cuyos elementos son los alumnos que han aprobado Matemtica Discreta y Lgica a o Matemtica, respectivamente. a UDLD LcDLDc LDc LcEjemplo 3.11 Los alumnos que han aprobado una de las dos asignaturas puede que no hayan aprobado la otra o que si la hayan aprobado, luego D = (D Lc ) (D L), L = (D L) (Dc L) y D L = (D Lc ) (D L) (Dc L) donde (D Lc ) (D L) = D Lc L = D = 48

54. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a ey (D L) (Dc L) = D Dc L = D = de aqu que por el Principio de Adicin, o |D| = |D Lc | + |D L| |D L| + |Dc L||L| =|D L| = |D Lc | + |D L| + |Dc L| . Por otra parte, si llamamos U al conjunto formado por los 100 alumnos, U = (D L) (D L)c donde, (D L) (D L)c = de aqu que nuevamente por el Principio de Adicin, o c|U | = |D L| + |(D L) | Pues bien, segn los datos aportados por el enunciado: u 20 alumnos no han aprobado ninguna de las dos asignaturas, es decir, c|(D L) | = 20. luego |D L| = 100 20 = 80. Han aprobado las dos asignaturas un total de 25 personas, o sea, |D L| = 25 El nmero de alumnos que han aprobado Matemtica discreta es el doble de los que han aprobado u a el Lgica Matemtica, es decir, o a |D| = 2 |L| . Datos que sustituidos en las ecuaciones anteriores, nos llevan a 2 |L| = |D Lc | + |L| = 8025 25 += |D Lc | +25|Dc L|+ |Dc L| .de aqu que |D Lc | = c|D L| =45 10luego hay 45 alumnos que han aprobado unicamente la Matemtica Discreta y 10 que aprobaron unicamente a el Lgica Matemtica. o a3.4.2TeoremaSean A, B y C tres subconjuntos de un conjunto universal arbitrario, U . Entonces, |A B C| = |A| + |B| + |C| |A B| |A C| |B C| + |A B C| Demostracin o 49

55. Universidad de Cdiz aDepartamento de Matemticas aApoyndonos en el teorema anterior y en la distributividad de la interseccin respecto a la unin de a o o conjuntos, |A B C| = |A (B C)| = |A| + |B C| |A (B C)| = |A| + |B| + |C| |B C| |(A B) (A C)| = |A| + |B| + |C| |B C| (|A B| + |A C| |(A B) (A C)|) = |A| + |B| + |C| |A B| |A C| |B C| + |A B C|Ejemplo 3.12 Cuntos nmeros existen entre 1 y 1000, ambos inclusive, que no sean ni cuadrados a u perfectos, ni cubos perfectos ni cuartas potencias? Solucin o Sea Z el conjunto de todos los enteros entre 1 y 1000 y sean A1 , A2 y A3 los subconjuntos de Z formados por los cuadrados perfectos, los cubos perfectos y las cuartas potencias, respectivamente. Entonces, A1=x : x = n2 , n ZA2=x : x = n3 , n ZA3=x : x = n4 , n ZPues bien, 312 = 961 < 1000 y 322 = 1024 > 1000, luego |A1 | = 31 103 = 1000, luego |A2 | = 10 54 = 625 y 64 = 1296, luego |A3 | = 5 Observemos ahora lo siguiente: A1 A2 = x : n Z+ ; x = n2 y x = n3 = x : n Z; x = n6 y al ser 36 = 729 < 1000 y 46 = 4096 > 1000, tendremos que |A1 A2 | = 3. Por otra parte, x A3 x = n4 , n Z = x = n22, n Z x A1es decir cada cuarta potencia es tambin un cuadrado, luego A3 A1 y, por tanto, A1 A3 = A3 y e |A1 A3 | = 5. Tambin, e A2 A3 = x : x = n3 y x = n4 , n Z+ = x : x = n12 , n Z+ luego el conjunto A2 A3 estar formado por todos los nmeros que son a un tiempo, cubos y cuartas a u potencias, es decir son de la forma n12 para algn entero n y al ser 212 = 4096 > 1000, tendremos que u |A2 A3 | = 1. Finalmente, x A2 A3 x = n12 = x = n62, n Z x A1luego las doceavas potencias son tambin cuadrados, es decir, A2 A3 A1 de aqu que e A1 A2 A3 = A2 A3 50

56. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a ey |A1 A2 A3 | = 1 Con todos estos datos, |A1 A2 A3 | = |A1 | + |A2 | + |A3 | |A1 A2 | |A1 A3 | |A2 A3 | + |A1 A2 A3 | =31 + 10 + 5 3 5 1 + 1=38Consecuentemente, el nmero de enteros entre 1 y 1000 que no son cuadrados, cubos o cuartas potencias u son 1000 38 = 962. Ejemplo 3.13Demostrar que |A B C| = |A(B C)| + |B(A C)| + |C(A B)| + |(A B)C| + |(A C)B| + |(B C)A| + |A B C|donde A, B y C estn incluidos en un universal arbitrario U . a Solucin o En efecto, sea x un elemento arbitrario de U . Entonces x (A B C) (x A) (x B) (x C) . Pues bien, si x est en A, entonces puede estar en A y no estar en B ni en C, o estar en A y en B pero a no estar en C o estar en A y en C pero no en B o estar en A, en B y en C (la situacin planteada puede o apreciarse con claridad en la figura), es decir, UAA(B C)(A C)B(A B)C ABCCBC(A B)(B C)AEjemplo 3.13 51B(A C)

57. Universidad de Cdiz a x A Departamento de Matemticas a[(x A) (x B) (x C)] / / [(x A) (x B) (x C)] / [(x A) (x B) (x C)] / [(x A) (x B) (x C)][(x A) (x B c ) (x C c )] [(x A) (x B) (x C c )] [(x A) (x B c ) (x C)] [(x A) (x B) (x C)][x (A B c C c )] [x (A B C c )] [x (A B c C)] [x (A B C)]de aqu que A = (A B c C c ) (A B C c ) (A B c C) (A B C) y razonando de forma anloga para los conjuntos B y C, tendremos a B = (Ac B C c ) (A B C c ) (Ac B C) (A B C) y C = (Ac B c C) (A B c C) (Ac B C) (A B C) . Si ahora unimos los tres, tendremos que ABC=(A B c C c ) (A B C c ) (A B c C) (A B C) (Ac B C c ) (Ac B C) (Ac B c C) . Adems, en cada pareja de conjuntos que tomemos, en uno de sus miembros aparece un conjunto y en a el otro su complementario, por lo tanto su interseccin es vac Por ejemplo, o a. (A B c C c ) (A B C c ) = A B c C c A B C c = A B c B C c = A C c = . Consecuentemente, la igualdad que obtuvimos anteriormente es una descomposicin de A B C en o unin de conjuntos disjuntos y aplicando el principio de adicin, tendremos que o o |A B C| = |A B c C c | + |A B C c |+ |A B c C| + |A B C|+ |Ac B C c | + |Ac B C| + |Ac B c C| y ahora bastar aplicar las leyes de De Morgan y la definicin de diferencia de conjuntos para obtener a o el resultado, |A B C| = |A(B C)| + |B(A C)| + |C(A B)| + |(A B)C| + |(A C)B| + |(B C)A| + |A B C|Ejemplo 3.14Una encuesta realizada entre 200 personas arroj el resultado siguiente: o40 leen Diario de Cdiz. a 42 leen El Mundo. 45 leen El Pa s. 13 leen Diario de Cdiz y El Mundo. a 20 leen El Mundo y El Pa s. 18 leen Diario de Cdiz y El Pa a s. 7 leen los tres peridicos. o 52

58. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a e(a) Cuntas personas no leen ninguno de los tres peridicos? a o (b) Cuntas personas leen unicamente el Diario de Cdiz? a a (c) Cuntas personas leen un slo peridico? a o o Solucin o Un diagrama de Venn de la situacin planteada se muestra en la figura. o UDD Mc PcD Mc PDc M c P cD M Pc DM PPMDc M c PDc M PDc M P cEjemplo 3.14 Sea U el conjunto formado por todas las personas encuestadas y sean D, M y P los conjuntos formados por las personas que leen Diario de Cdiz, El Mundo y El Pa respectivamente. Segn los datos del a s, u enunciado |D| = 40 |M | = 42 |P | = 45 |D M | = 13 |M P | = 20 |D P | = 18 |D M P | = 7 53

59. Universidad de Cdiz aDepartamento de Matemticas a(a) Veamos cuntas personas no leen ninguno de los tres peridicos. a o El conjunto D M P est formado por las personas que leen, al menos, uno de los tres peridicos, a o luego el conjunto de las personas que no leen ninguno de los tres peridicos ser su complementario o a c c (D M P ) y al ser D M P y (D M P ) disjuntos, por el principio de adicin, tendremos o cc|U | = |(D M P ) (D M P ) | = |D M P | + |(D M P ) | de aqu que c|(D M P ) | = |U | |D M P | . Por el principio de inclusin-exclusin para tres conjuntos, tendremos o o |D M P | = |D| + |M | + |P | |D M | |M P | |D P | + |D M P | =40 + 42 + 45 13 20 18 + 7=134 51=83por lo tanto, c|(D M P ) | = 200 83 = 117 (b) Calculemos ahora el nmero de personas que leen unicamente Diario de Cdiz. u a Las personas que leen unicamente Diario de Cdiz sern aquellas que lean Diario de Cdiz y no a a a lean El Mundo ni El Pa es decir las del conjunto D M c P c . Para calcular el nmero de s, u estas personas, y teniendo en cuenta los datos que proporciona el enunciado, habr que hacerlo en a funcin de |D|, |D M |, |D P | y |D M P |. o Pues bien, las personas que leen Diario de Cdiz puede que lean alguno de los otros dos peridicos a o c (D (M P )) o que no lean ninguno de los otros dos (D (M P ) ), es decir, cD = [D (M P )] [D (M P ) ] siendo esta descomposicin en unin de disjuntos. Aplicando el principio de adicin y, posterioro o o mente, el de inclusin-exclusin, o o c|D| = |D (M P )| + |D (M P ) | = |(D M ) (D P )| + |D M c P c | = |D M | + |D P | |D M P | + |D M c P c | de donde, |D M c P c | = |D| |D M | |D P | + |D M P | = 40 13 18 + 7 = 16 (c) Veamos ahora cuntas personas leen un slo peridico. a o o Las personas que leen unicamente un slo peridico sern aquellas que lean unicamente Diario de o o a Cdiz (ni El Mundo, ni El Pa o que unicamente lean El Mundo (ni Diario de Cdiz ni El Pa a s) a s) o que lean unicamente El Pa (ni Diario de Cdiz ni El Mundo), es decir las del conjunto s a (D M c P c ) (Dc M P c ) (Dc M c P ) y como estos tres conjuntos son disjuntos dos a dos, por el principio de adicin, tendremos o |(D M c P c ) (Dc M P c ) (Dc M c P )| = |D M c P c | + |Dc M P c | + |Dc M c P |(3.8)El primero de los sumandos lo hemos calculado en el apartado anterior. Si seguimos un camino anlogo para calcular los otros dos, tendremos: a |Dc M P c | = |M | |M P | |D M | + |D M P | = 42 20 13 + 7 = 16 54(3.9)

60. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a ey |Dc M c P | = |P | |M P | |D P | + |D M P | = 45 20 18 + 7 = 14.(3.10)Sustituyendo (3.9) y (3.10) junto con el resultado obtenido en el apartado anterior en (3.8) tendremos que el nmero de personas que leen unicamente un peridico es u o |(D M c P c ) (Dc M P c ) (Dc M c P )| = 16 + 16 + 14 = 46Ejemplo 3.15 Se ha comprado un lote de banderas monocolores, bicolores y tricolores. En todas ellas figura, al menos, el blanco, el rojo o el negro. Adems, en ocho de ellas no figura el blanco, en diez a no figura el rojo y en cuatro no gura el negro. Por otra parte, cinco banderas tienen, al menos, los colores rojo y blanco, siete el blanco y el negro y seis el rojo y el negro. Finalmente, cuatro tienen los tres colores. Averiguar: (a) Nmero total de banderas. u (b) Nmero de monocolores rojas. u Solucin o Sean B: Conjunto formado por las banderas en las que gura, al menos, el blanco. N : Conjunto formado por las banderas en las que gura, al menos, el negro. R: Conjunto formado por las banderas en las que gura, al menos, el rojo. (a) Nmero total de banderas. u Como en todas las banderas figura, al menos, uno de los tres colores, el nmero total de banderas u ser el cardinal del conjunto B R N . a Veamos que datos aporta el enunciado. En ocho de ellas no figura el blanco. Entonces, |B c | = 8 En diez de ellas no figura el rojo, es decir, |Rc | = 10 En cuatro de ellas no figura el negro, luego, |N c | = 4 Cinco tienen, al menos, los colores rojo y blanco. Pues bien, |B R| = 5 Siete tienen, al menos, los colores blanco y negro, o sea, |B N | = 7 55

61. Universidad de Cdiz aDepartamento de Matemticas aSeis tienen, al menos, los colores rojo y negro, es decir, |R N | = 6 Cuatro tienen los tres colores, es decir, |B R N | = 4. A la vista de estos datos parece que lo ms lgico es utilizar el principio de inclusin-exclusin a o o o para 3 conjuntos: |B N R| = |B| + |N | + |R| |B N | |B R| |N R| + |B N R| y utilizando el principio de adicin, o B Bc = B N R=|B| + |B c | = |B N R|=|B| = |B N R| |B c |N Nc = B N R=|N | + |N c | = |B N R| =|N | = |B N R| |N c |R Rc = B N R=|R| + |Rc | = |B N R||R| = |B N R| |Rc |=Si ahora sustituimos estos resultados en la igualdad anterior, 2 |B N R| = |B c | |N c | |Rc | |B N | |B R| |N R| + |B N R| de donde se sigue que el nmero total de banderas es u |B N R| = = =|B c | + |N c | + |Rc | + |B N | + |B R| + |N R| |B N R| 2 8 + 10 + 4 + 5 + 7 + 6 4 2 18BB(N R)(B N )R(B R)N BRNNRN(B R)(R N )BEjemplo 3.15 56R(B N )

62. Matemtica Discreta aFrancisco Jos Gonzlez Gutirrez e a e(b) Nmero de monocolores rojas. u El conjunto de banderas que tienen unicamente el color rojo es R(B N ) o B c N c R. Pues bien las banderas que tienen el color rojo, puede que tengan, adems, uno de los otros dos colores a o ninguno de los dos, es decir, cR = [R (B N )] [R (B N ) ] siendo sta una descomposicin de R en unin de subconjuntos disjuntos. Aplicando el principio e o o de adicin y el principio de inclusin-exclusin, o o o c|R| = |R (B N )| + |R (B N ) | = |(B R) (N R)| + |B c N c R| = |B R| + |N R| |B N R| + |B c N c R| si ahora sustituimos |R| por |B N R| |Rc | y despejamos, |B c N c R| = |B N R| |Rc | |N R| |B R| + |B N R| =18 10 6 5 + 4=1luego hay una sola bandera de color rojo. Ejemplo 3.16 En una muestra de 1000 individuos elegida para el estudio las preferencias gastronmicas o de una poblacin, se observa que sesenta comen pescado y carne pero no huevos, cuarenta comen pescado o y huevos pero no carne, treinta carne y huevos pero no pescado, cincuenta comen unicamente pescado, cuarenta slo carne y treinta comen unicamente, huevos. Todos comen al menos, una de las tres cosas. o (a) Cuntos comen las tres cosas? a (b) Cuntos comen pescado? a Solucin o Sean C, H y P los conjuntos formados por los individuos que comen, respectivamente, carne, huevos y pescado. (a) Los individuos que comen las tres cosas sern los del conjunto C H P es decir, tenemos que a calcular |C H P |. Descompondremos el conjunto C H P en unin de conjuntos disjuntos, para lo cual razonaremos o igual que en los ejercicios anteriores. En efecto, si un individuo come una de las tres cosas, puede que coma tambin las otras dos, una o ninguna. Por ejemplo, si come carne, puede que tambin e e coma huevos y pescado o huevos y no coma pescado o pescado y no coma huevos o que no coma huevos ni pescado. Esto en trminos de los conjuntos C, H y P quiere decir lo siguiente: eP(C H) (C H c ) (C H P ) (C H P c ) (C H c P ) (C H c P c )=(C H) (C c H)=H= =C(C H P ) (C H P c ) (C c H P ) (C c H P c )=(C P ) (C c P )=(C H P ) (C H c P ) (C c H P ) (C c H c P ) 57

apuntes de älgebra y matemática discreta

Documents