Conjuntos
Conjuntos
Conjuntos
Contenido
1 Conjuntos 2
1.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Conjuntos y subconjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Conjunto universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Conjunto finito y conjunto infinito . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Cardinalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.4 Subconjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.5 Conjunto Vaco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Operaciones de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Complemento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Complemento relativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.3 Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.4 Interseccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.5 Exclusion mutua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.6 Diferencia simetrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.7 Generalizacion de las operaciones de conjuntos . . . . . . . . . . . . . . . . . . . . 9
1.3.8 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Leyes de la teora de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.1 Proposiciones equivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.2 Leyes de la teora de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.3 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Diagramas de Venn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5.1 Diagrama de Venn numerando regiones . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5.2 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6 Producto Cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6.1 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7 Conjunto Potencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.7.1 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1
1 Conjuntos
Material multimedia recomendado:
https://www.youtube.com/watch?v=Hek8Y3FlAm0
https://www.youtube.com/watch?v=aPxx9 sqAL8
https://www.youtube.com/watch?v=ybSYaefNC4w
https://www.youtube.com/watch?v=HDYy88AzjXg
1.1 Introduccion
La matematica discreta, tambien llamada matematica finita, comprende el estudio de las estructuras
matematicas fundamentalmente discretas en el sentido de no soportar o requerir la nocion de con-
tinuidad. Estas son necesarias para hacer ciencia de la computacion en una forma
Esta seccion contiene los temas referentes a Teora de Conjuntos. Los conjuntos son las estructuras
mas simples pero no triviales de las matematicas. Otros objetos y propiedades de las matematicas se
definen en base a ellos. En un principio fueron usados para estudiar la nocion de infinito. Tambien son
utiles en problemas de conteo y teora de probabilidad.
Ejemplo 1
xA si x es un elemento de A ;
y
/A indica que y no pertenece a A
Para denotar un conjunto se utiliza un par de llaves {} alrededor de los elementos del conjunto. Se
puede determinar un conjunto listando sus elementos entre llaves como:
Este conjunto tambien se puede determinar mediante una propiedad que indica como deben ser los
elementos (determinacion intencional). Entonces A tambien se puede escribir como:
A = {x|x es un entero, 1 x 5}
2
1.2.1 Conjunto universal
Cuando se trata un problema particular, hay un universo o conjunto universal , formulado o impli-
cado, del cual se seleccionan los elementos para formar los conjuntos. Tambien es llamado espacio de
muestra S (principalmente en probabilidad)
Ejemplo 1
Ejemplo 2
Para el universo U = {1, 2, 3, 4, 5}, considerese un conjunto A = {1, 2}. Si B = {x|x2 U } los
elementos de B son 1,2. Como A y B tiene los mismo elementos se consideran que son el mismo
conjunto.
Definicion 1
Para el universo U se dice que los conjuntos A y B (tomados de U ) son iguales y se escribe A = B
si A y B contienen los mismos elementos
De esta definicion se deduce que ni el orden ni la repeticion tiene importancia para un conjunto, de
modo que
{1, 2, 3} = {3, 1, 2} = {2, 2, 1, 3} = {1, 2, 1, 3, 1}
Ejemplo 1
1.2.3 Cardinalidad
Dado un conjunto finito A
|A| denota el numero de elementos en A y se denomina cardinalidad o tamano de A
Ejemplo 1
3
1.2.4 Subconjunto
Definicion 1
C D si y solo si x[x C x D]
Teorema. Sea A, B, C U .
a) Si A B y B C, entonces A C.
b) Si A B y B C, entonces A C.
c) Si A B y B C, entonces A C.
d) Si A B y B C, entonces A C.
Para los conjuntos A, B del universo U puede suceder que A no sea subconjunto de B. Esto se
expresa por A 6 B y tiene lugar cuando hay algun elemento x A tal que x
/ B.
Ejemplo 1
Figura 1: A es subconjunto de B
Ejemplo 2
Sea U = {1, 2, 3, 4, 5} con A = {1, 2, 3}, B = {3, 4}, C = {1, 2, 3, 4}. Entonces se cumplen las
siguientes relaciones de subconjuntos:
a) A C
b) A C
c) B C
d) A A
e) B * A (es decir, B no es subconjunto de A)
f) A 6 A
Ejemplo 3
4
Edad de las personas en anos de acuerdo a las siguientes categoras:
1. Tercera edad. A = {x 65, x N+ }
2. Votante. B = {x 18, x N+ }
3. Servicio Militar. C = {x 18 y x < 45, x N+ }
A B; C B; A 6 C
Definicion 1
El conjunto nulo o vaco es aquel que NO contiene elementos y se denota por o {}.
1.2.6 Ejercicios
1. Cuales de los siguientes conjuntos son iguales?
a) {1, 2, 3} c) {3, 1, 2, 3}
b) {3, 2, 1, 3} d) {1, 2, 2, 3}
Solucion:
a), b), c) y d)
Ni el orden ni la repeticion tiene importancia para un conjunto.
2. Sea A = {1, {1}, 2}. Cuales de las siguientes proposiciones son verdaderas?
a) 1 A e) {2} A
b) {1} A f) {2} A
c) {1} A g) {{2}} A
d) {{1}} A h) {{2}} A
Solucion:
a), b), c), d)y f) son verdaderas
e) el conjunto {2} no esta en A
g) y h) el conjunto que tiene como elemento al conjunto {2} no es subconjunto ni subconjunto
propio de A
3. Sea A = {1, 2, {2}}. Cuales de las proposiciones del ejercicio anterior son verdaderas?
Solucion:
a), c), e), f), g) y h)
a) d) {}
b) e) {}
c) f) {}
5
Solucion:
c), d), e) y f) son verdaderas
1.3.1 Complemento
Se dice que un conjunto es el complemento de otro conjunto A, si contiene todos los elementos del
conjunto universal U que NO pertenecen a A, y se denota Ac (Figura 2). Tambien puede escribirse
como A
Figura 2: Del conjunto U = {figuras geometricas} donde A = {cuadrados}, Ac = {todos los que NO son
cuadrados}
Ejemplo 1
1. A = {anverso}
2. B = {reverso}
A = B c ; B = Ac
Ejemplo 2
a) Ac = {x < 65, x N + };
b) B c = {x < 18, x N + };
c) C c = {x < 18 o x 45, x N + }
6
1.3.2 Complemento relativo
Para A, B U , el complemento relativo de A en B, denotado por B A, esta dado por {x|x B, x
/ A}
Ejemplo 1
a) B A = {6, 7} d) C A = C
b) A B = {1, 2} e) A A =
c) A C = A f) U A = {6, 7, 8, 9, 10} = Ac
1.3.3 Union
La union de dos conjuntos A B es el conjunto que incluye a todos los elementos que pertenecen solo a
A, solo a B, o a ambos A y B (Ver Figura 3).
A B = {x|x A o x B}
Ejemplo 1
A = {
,
a
}
R
B = {F, , }
C = {
, }
a) A B = {
,
a
,
R F, , } d) B A = {
,
a
,
R F, , }
b) A C = {
,
a
,
R
, } e) C A = {
,
a
,
R
, }
c) B C = {F, , , , } f) C B = {F, , , , }
7
g) A B C = {
,
a
,
R F, , ,
, } i) (A B) C = {
,
a
,
R F, , ,
, }
h) A (B C) = {
,
a
,
R F, , ,
, }
1.3.4 Interseccion
La interseccion de dos conjuntos A y B es el conjunto que incluye a aquellos elementos que pertenecen a
ambos conjuntos, A y B. Es decir, son SOLO aquellos elementos que se encuentran en A y B, como se
muestra en la Figura 4.
A B = {x|x A y x B}
Ejemplo 1
B = {F, ,
a }
C = {
,
a , }
a) A B = {
a } d) B A = {
a } g) A B C = {
a }
b) A C = {
a } e) C A = {
a } h) (A B) C = {
a }
c) B C = {,
a } f) C B = {,
a } i) A (B C) = {
a }
AB =
8
Figura 5: Los Conjuntos disjuntos NO tienen elementos en comun
Esto implica que si un elemento esta en A, entonces no esta en B y si un elemento esta en B, entonces
no esta en A.
NOTA. Los conjuntos y elementos no ocurren.
Ejemplo 1
Escoger una carta de una baraja espanola: O-oros, B-bastos, E-espadas, C-copas, Z-sota, C-caballo,
R-rey. Las cartas escogidas se dividen en tres grupos
Figuras: A = {OZ, OC, OR, BZ, BC, BR, EZ, EC, ER, CZ, CC, CR}
Oros: B = {O1, O2, O3, O4, O5, O6, O7, OZ, OC, OR}
Ases C = {O1, B1, E1, C1}
A 4 B = {x|x A x B, pero x
/ A B}
Definicion 1
Denotese por I un conjunto de ndices. Si para para cada ndice i I hay un conjunto Ai U ,
entonces S
Ti = {x|x Ai para al menos una i I} y
iI A
iI Ai = {x|x Ai para todo i I}
9
T
ObserveseSque x
/ iI Ai si x / Ai para todo ndice i I. Si x
/ Ai para al menos un ndice i I,
entonces x / iI Ai .
Si el conjunto de ndices I es el conjunto Z + , se puede escribir:
S S
TiZ + Ai = A1 A2 ... = T i=1 Ai
iZ + Ai = A1 A2 ... = i=1 Ai
Ejemplo 1
1.3.8 Ejercicios
1. Sean los conjuntos
U = {0, ..., 40}
A = {2, 3, 5, 6, 14, 28, 32}
B = {0, 1, 3, 5, 16, 17, 21, 28, 30, 31, 32, 33}
C = {1, 2, 4, 5, 8, 9, 10, 16, 18, 24, 28}
Encuentre:
a) A B
b) B C
c) A (B C)
d) B c C
Solucion:
a) A B = {3, 5, 28, 32}
b) B C = {0, 1, 2, 3, 4, 5, 8, 9, 10, 16, 17, 18, 21, 24, 28, 30, 31, 32, 33}
c) A (B C) =
Primero se resuelve (B C) = {1, 5, 16, 28}
para hacer la union con el conjunto A: A (B C) = {1, 2, 3, 5, 6, 14, 16, 28, 32}
d) B c C =
Primero se obtiene el complemento de B:
B c = {2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 19, 20, 22, 23, 24, 25,
26, 27, 29, 34, 35, 36, 37, 38, 39, 40}
B c C = {2, 4, 8, 9, 10, 18, 24}
2. Dados los tres colores primarios R, G, y B, Enumere el conjunto universal de una imagen de 3
pixeles, si cada pixel solo puede tomar un color cada vez
Solucion:U = {RRR, RRG, RRB, RGR, RGG, RGB, RBR, RBG, RBB, GRR, GRG, GRB,
GGR, GGG, GGB, GBR, GBG, GBB, BRR, BRG, BRB, BGR, BGG, BGB, BBR, BBG, BBB}
3. Con U = {1, 2, 3, ..., 9, 10}, A = {1, 2, 3, 4, 5}, B = {3, 4, 5, 6, 7}, C = {7, 8, 9}, encuentre:
10
a) AB e) A 4 B
b) AB
f) A C
c) BC
d) AC g) A 4 C
Solucion:
a) A B = {3, 4, 5}
b) A B = {1, 2, 3, 4, 5, 6, 7}
c) B C = {7}
d) AC =
e) A 4 B = {1, 2, 6, 7} (Recuerda que son los elementos que NO tienen en comun.)
f) A C = {1, 2, 3, 4, 5, 7, 8, 9}
g) A 4 C = {1, 2, 3, 4, 5, 7, 8, 9}
4. Para U = {1, 2, 3, ..., 9, 10}, A = {1, 2, 3, 4, 5}, B = {3, 4, 5, 6, 7}, y C = {7, 8, 9}, calcule los
complementos de A, B y C.
Solucion:
a) Ac = {6, 7, 8, 9, 10}
b) B c = {1, 2, 8, 9, 10}
c) C c = {1, 2, 3, 4, 5, 6, 10}
a) (A B) C d) C D g) (B C) D
b) A (B C) e) (A B) C h) B (C D)
c) C D f) A (B C) i) (A B) (C D)
Solucion:
a) {1, 2, 3, 5} d) U {2} g)
b) A e) {4, 8} h) {2, 4, 8}
c) U {2} f) {1, 2, 3, 4, 5, 8} i) {1, 3, 4, 5, 8}
c) A B = A
d) B c Ac
11
1.4.2 Leyes de la teora de conjuntos
Para conjuntos cualesquiera A, B y C de un universo U :
2. AB =AB De Morgan
AB =AB
3. AB =BA Conmutativas
AB =BA
4. A (B C) = (A B) C Asociativas
A (B C) = (A B) C
5. A (B C) = (A B) (A C) Distributiva
A (B C) = (A B) (A C)
6. AA=A Idempotente
AA=A
7. A=A Identidad
AU =A
8. AA=U Inversas
AA=
9. AU =U Dominacion
A=
10. A (A B) = A Absorcion
A (A B) = A
Notese que las leyes 2 a 10 se representan por pares. Estos pares se llaman duales. Una proposicion
se puede obtener a partir de la otra intercambiando en todos los casos en los que se presente por , y
viceversa, y donde aparezca U por , y viceversa.
Sea s un teorema que trata de conjuntos e incluye solo operaciones con conjuntos y ,
entonces el dual de s, denotado por sd tambien es un teorema de la teora de conjuntos.
Para cada par de las leyes del 2 al 10 solo se necesita demostrar una de las preposiciones y
reducir a este principio para obtener la otra preposicion del par.
Ejemplo 1
Sea e un teorema que trata de conjuntos, el dual ed de e es el teorema que se obtiene de sustituir
cada aparicion de , , , U en e por , , U, , respectivamente.
e: Leyes de idempotencia:
1a) A A = A 1b) A A = A
12
1.4.3 Ejercicios
1. Demostrar las propiedades de dominacion:
a) X =
b) X U = U
Solucion:
a)
X = (X ) identidad
= (X ) (X X c ) inversa
= X ( X c ) distributiva
= X Xc identidad
= inversa
b)
X U = (X U ) U identidad
= (X U ) (X X c ) inversa
= X (U X c ) distributiva
= X Xc identidad
= U inversa
2. Simplifique la expresion (A B) C B
Solucion: Aplicando las leyes de la teora de conjuntos
= (A B) C B De Morgan
= ((A B) C) B doble complemento
= (A B) (C B) asociativa
= (A B) (B C) conmutativa de interseccion
= [(A B) B] C asociativa de la interseccion
= BC absorcion
Ejemplo 1
13
En las Figuras 8 y 9 se usan diagramas de Venn para mostrar una de las leyes de De Morgan:
AB =AB
(a) A B (b) A B
En la Figura 10:
La region 3 es A B C (vease Figura 11d).
14
(a) A (b) A B (c) C (d) A B C
Figura 11: Region 3. Podemos realizar el diagrama de Venn por partes para facilitar el proceso
Figura 12: A B
Figura 13: A B
15
Figura 14: A B C
1.5.2 Ejercicios
1. Represente con un diagrama de Venn (A B) C
Solucion:
El conjunto A consta de las regiones 1, 3, 4, 6,
16
Si se toma la union de C con A B, se concluye con las regiones 1, 4, 6, 7, 8.
2. En una clase de 50 alumnos de primero de universidad, 30 estudian C++, 25 Java, y 10 los dos
lenguajes. Cuantos alumnos estudian un solo lenguaje de programacion?
Solucion:
Sea U la clase de 50 alumnos, A el subconjunto de los que estudian C++ y B el de los
que estudian Java. Primero necesitamos saber cuantos estan estudiando algun lenguaje,
por lo que necesitamos la cardinalidad de |A B| para restar a aquellos que estudian dos
(|A B|).
Si se suma |A| + |B| da un total de 55 alumnos, esto es debido a que |A| + |B| cuenta dos
veces a los alumnos de |A B|. Para evitar esta sobrecuenta se resta |A B| de |A| + |B|
y se obtiene la formula correcta.
|A B| = (|A| + |B|) (|A B|)
Los alumnos que estudian un solo lenguaje se muestran en rojo en la figura:
3. Dada una muestra de 100 chips logicos, sean A, B, C los subconjuntos que tiene los defectos
D1 , D2 , D3 , respectivamente. Con |A| = 23, |B| = 26, |C| = 30, |A B| = 7, |A C| = 8,
|B C| = 10, |A B C| = 3. Cuantos chips de la muestra son defectuosos?
17
Solucion:
Trabajando haca atras desde |A B C| = 3, se etiquetan las regiones como se muestra
a continuacion.
Definicion 1
A B = {(a, b) : a A, b B}
Note que hay una diferencia entre (a, 2) y (2, a), porque para (a, b), (c, d) A B, se tiene que (a, b) =
(c, d) si y solo si, a = c y b = d.
Definicion 2
NOTA. Una tupla es una lista ordenada de elementos cuyo tamano dependera del numero de
conjuntos involucrados en el producto cartesiano. Este concepto es explicado mas ampliamente en
el material de Relaciones y Funciones (se recomienda revisarlo).
Ejemplo 1
18
Sean A = {1, 2} y B = {x, y, z}, el producto cartesiano (Figura 15) es
A B = {(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)}
Ejemplo 2
Si A, B son finitos, por la regla del producto resulta que A B = |A| |B|. Aunque, en general, no es
cierto que A B = B A, se tendra que |A B| = |B A|. Ademas aunque A, B U , no es necesario
que A B U , de modo que U no es necesariamente cerrado para esta operacion.
1.6.1 Ejercicios
1. Sea U = {1, 2, 3, ..., 7}, A = {2, 3, 4}, B = {4, 5}. Determine
a) A B
b) B A
c) B 2 = B B
d) B 3 = B B B
Solucion:
a) A B = {(2, 4), (2, 5), (3, 4), (3, 5), (4, 4), (4, 5)}
b) B A = {(4, 2), (4, 3), (4, 4), (5, 2), (5, 3), (5, 4)}
c) B 2 = B B = {(4, 4), (4, 5), (5, 4), (5, 5)}
d) B 3 = B B B = {((4, 4), 4), ((4, 5), 4), ((5, 4), 4), ((5, 5), 4),
((4, 4), 5), ((4, 5), 5), ((5, 4), 5), ((5, 5), 5)}
19
Denotese por E1 la primera parte del experimento E y sea M1 = {1, 2, 3, 4, 5, 6} el espacio
muestral para E1 . As mismo sea M2 = {CA, CZ} el espacio muestral para E2 , la segunda
parte del experimento. Entonces, M = M1 M2 es el espacio muestral para E
M = M1 M2 = {(1, CA), (1, CZ), (2, CA), (2, CZ), (3, CA), (3, CZ),
(4, CA), (4, CZ), (5, CA), (5, CZ), (6, CA), (6, CZ)}
3. En el torneo de tenis de Wimbledon, las mujeres juegan a lo sumo 3 sets en un partido. Triunfa
quien gane primero 2 sets. Si N y E representan a las 2 jugadoras. Cuales son las maneras en que
puede ganarse el encuentro?
Solucion:
Si el espacio muestral de un set es A = {N, E} y considerando que:
El espacio muestral del segundo set es: A A = {(N, N ), (N, E), (E, N ), (E, E)}
En caso de que una jugadora gane dos veces, se termina el partido: (N, N ) o (E, E)
Para que se realice un tercer set solo se eliminan los pares donde una jugadora gana
dos veces: A A {(N, N ), (E, E)}
Finalmente el tercer set es:
|P ()| = 2n
Ejemplo 1
Sea A = {x, y, z}
El conjunto potencia de A es
P (A) = {{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}
1.7.1 Ejercicios
1. Sean los conjuntos = {}, A = {a}, B = {a, b}, C = {a, b, c} y D = {a, b, c, d}, determine para
cada uno:
a) El conjunto potencia
20
b) La cardinalidad del conjunto
c) La cardinalidad del conjunto potencia
Solucion:
Cardinalidad
Cardinalidad
Conjunto Conjunto Potencia del
del conjunto
Conjunto Potencia
= {} ||=0 P () = {} |P ()| = 1
A = {a} |A| = 1 P (A) = {, a} |P (A)| = 2
B = {a, b} |B| = 2 P (B) = {, {a}, {b}, {a, b}} |P (B)| = 4
P (C) = {, {a}, {b}, {c}, {a, b},
C = {a, b, c} |C| = 3 |P (C)| = 8
{a, c}, {b, c}, {a, b, c}}
P (D) = {, {a}, {b}, {c}, {d}, {a, b},
D = {a, b, c, d} |D| = 4 {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, |P (D)| = 16
{a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}}
21
Bibliografa
[1] Ralph P Grimaldi, Discrete and combinatorial mathematics, 5/e, Pearson Education India, 2006.
[2] Donald Johnson, John A Dossey, Albert D Otto, Lawrence E Spence, and Charles Vanden Eynden,
Discrete mathematics, 2d ed.(c), JSTOR, 1993.
22