Teoria dos Conjuntos

Vista previa del material en texto

09/06/2011
1
Georg Cantor
Matemático 
Alemán creador de 
la teoría de 
conjuntos
John Venn
Matemático y 
filósofo británico 
creador de los 
diagramas de Venn
August De Morgan
Matemático ingles 
creador de leyes 
que llevan su 
nombre dentro del 
álgebra de la lógica
Un conjunto es una colección bien definida de objetos
llamados elementos o miembros del conjunto.
 Para que una colección de objetos se considere
como un conjunto no debe haber ambigüedad ni
subjetividad.
CONJUNTOS NO SON CONJUNTOS
La colección de pizarrones 
azules
El grupo de los mejores 
maestros de computación
El grupo de alemanes entre 20 y 
30 años
El grupo de alumnas más 
guapas de la Facultad de 
Ciencias de la Computación
 Los conjuntos se indican por medio de letras
mayúsculas y los elementos con letras minúsculas,
números o combinación de ambos, estos elementos se
colocan entre llaves { }, además el orden no es
importante.
B = {n, r, i, m , d}
Pertenencia:
Se dice que un elemento x pertenece a un conjunto C si
se verifica que el elemento se encuentra en el conjunto.
x C x C
Notación abstracta: 
A = {x | P(x) } 
Se lee “A es el conjunto de las x, tal que cumple la 
condición P(x)”
09/06/2011
2
Ejemplo
 El conjunto B tiene como elementos a las letras de 
la palabra “mandarina”:
› B={m, a, n, d, a, r, i, n, a} = {m, a, n, d, r, i}= {n, r, a, i, m, 
d}
 En un conjunto se pueden eliminar los elementos 
repetidos y el orden no es importante.
 N={1,2,3,..} = Conjunto de los números naturales
 Z+=Conjunto de los números enteros no negativos= 
{0,1,2,3,…}
 Q= Conjunto de los números racionales = { | a,b 
Z; b ≠0}
b
a
Si todos los elementos de A también son elementos de
B, se dice que A es subconjunto de B o que A está
contenido en B, y se denota como:
A B
Igualdad de conjuntos: Se dice que dos conjuntos A y B
son iguales si tienen los mismos elementos, es decir:
A B B A
A= {x|x Z; 10≤ x ≤ 100}
B={2,3,5,11,12,15,21,30,45,82}
C={12,15,45}
• C B A B
• C A A C
• B A B C
1) Todo conjunto A es un subconjunto de si mismo
A A
2) El conjunto vacio ( ) es subconjunto de todos los
conjuntos y en particular de él mismo:
A
U
3) Todos los conjuntos son subconjuntos del conjunto
universo (U):
A U
U
U U 
Si A es un conjunto entonces al conjunto de todos los
subconjuntos de A se le llama conjunto potencia de A y
se indica como P(A).
E
je
m
p
lo Sea el conjunto A= {a,b,c}
entonces el conjunto potencia de A es:
P(A) = { ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
El número de subconjuntos del conjunto A está dado
por:
|P(A)|=2n
donde n es el número de elementos del conjunto A
09/06/2011
3
Son representaciones gráficas para mostrar la relación
entre los elementos de los conjuntos. Por lo general
cada conjunto se representa por medio de un circulo,
óvalo o rectángulo.
A C B
U
Algunas afirmaciones de este diagrama son:
A U C U B U
B C C B U C
A C B A U B
 Determine los elementos de:
› A, B, C, U
› ¿B A?, ¿B C?, ¿A C?, ¿A U?
› |A|, |B|, |C|, |U|
La unión del conjunto A y el conjunto B es el conjunto
que contiene a todos los elementos del conjunto A y
del conjunto B:
A B = {x | x A ó x B}
A
U
La unión cumple las siguientes leyes
A B
A B
Ley conmutativa A B = B A
Ley de 
idempotencia A A = A
Unión con el 
universo A U = U
Sean los conjuntos:
A = {1,2,3,6,7,8}
B= {x | x N ; x ≤ 12; x es par}
N es el conjunto de los números naturales
N = {1,2,3,4,5,…}
Entonces
A B = {1,2,3,4,6,7,8,10,12}
A B
U
A=B
U
A=B
U
A U
09/06/2011
4
La intersección del conjunto A y el conjunto B es el
conjunto que contiene a todos los elementos que son
comunes a los conjuntos A y B:
A B = {x | x A ; x B}
U
La intersección cumple lo siguiente:
Si A y B son 
disjuntos A B = 
Si A = B A B = A A = A
Intersección con el 
universo A U = A
A = Intersección con el vacío
Sean los conjuntos:
A = {1,2,3,6,7,8}
B= {x | x Z+ ; x ≤ 12; x es par}
Z + es el conjunto de los números enteros positivos
Z + = {0,1,2,3,4,5,…}
Entonces
A B = {2,6,8}
A B
U U
A=B
U
A U
A A = AA B = A U = A
Dados tres conjuntos cualquiera A,B y C, se puede ver
que se cumple la siguiente ley distributiva en la que
intervienen la unión y la intersección de conjuntos:
A (B C) = (A B) (A C)
A (B C) = (A B) (A C) 
B C
A
A
CB
El complemento de un conjunto A, que se denota como
A‟, es el conjunto que contiene a todos los elementos del
conjunto universo que no pertenecen al conjunto A:
A‟ = {x | x U; x A}
A‟ A
U
Propiedades del complemento
a) ( A‟ )‟ = A
b) A A‟= U
c) A A‟ = 
d) U‟ = 
e) ‟ = U
09/06/2011
5
 Sean los conjuntos
 U = {x | x Z}
 A= {1,3,5,8}
 A‟= {x | x Z ; x {1,3,5,8}}
= {x | x Z ; x ≠1; x ≠3; x ≠ 5; x ≠ 8}}
1) La negación de la intersección de dos o más
conjuntos es equivalente a la unión de los conjuntos
negados separadamente.
(A B)‟= (A‟ B‟)
2) La negación de la unión de dos o más conjuntos es
igual a la intersección de los conjuntos negados por
separado.
(A B)‟= (A‟ B‟)
Sean los conjuntos:
U = {1,2,3,4,5,6,7,8,9,10}
A = {1,3,6,7,9,10}
B = {1,2,3,7,9,10}
Por una parte tenemos Y por otra parte tenemos
A B = {1,2,3,6,7,9,10}
(A B)’ = {4,5,8} 
A’ = {2,4,5,8}
B’ = {4,5,6,8}
A’ B’ = {4,5,8}
1 3
7 9 
10
26
4
5
8
U
A B
La diferencia entre dos conjuntos A y B es el conjunto
que contiene a todos los elementos del conjunto A que
no se encuentran en B:
A - B = {x | x A y x B} ={x|x A} {x| x B} =A B’
A - B 
A B
Ejemplo: Sean los conjuntos:
A= {1,2,3,4,7,9,10}
B= {3,4,5,6,7,8}
A - B= {1,2,9,10}
B - A= {5,6,8}
09/06/2011
6
 Determine:
› A, B, C, U
› A B, A C, B C‟, (A B‟) C , (B C)‟ C
 Determina el conjunto que representa la 
parte sombreada
La diferencia simétrica entre los conjuntos A y B es el
conjunto que contiene a todos los elementos que se
encuentran en A B pero que no están en A B:
A B = {x | (x A y x B) o (x B y x A)}= (A B) – (A B)
Ejemplo: Sean los conjuntos:
A= {1,2,3,4,7,9,10}
B= {3,4,5,6,7,8}
A - B= {1,2,9,10}
B - A= {5,6,8}
A B = {1,2,5,6,8,9,10}
A B 
09/06/2011
7
Sean los conjuntos:
U={x | x Z}
A={1,2,5,7,10,12}
B = {x | x Z ; 3 < x < 15 ; x es primo}
C={3,5,9,10,12,13,14}
D={2,4,8,10,11}
Aplicando las definiciones correspondientes obtener:
a) (A B)’
b) (C D’) B’
c) C’ – (D A)
d) [(A B’) – C] D’
 Para cada inciso obtenga el diagrama de Venn
U={x | x Z}
A={1,2,5,7,10,12}
B = {x | x Z ; 3 < x < 15 ; x es primo}={5,7,11,13}
C={3,5,9,10,12,13,14}
D={2,4,8,10,11}
U
 (A B)’= {x | x Z; x {5,7} }
› A B= {5,7}
 (C D’) B’
› D’={x | x Z; x {2,4,8,10,11}}
› C D’ = {x | x Z; x {2,4,8,11}}
› B’= {x | x Z; x {5,7,11,13}}
› (C D’) B’ = {2,4,5,7,8,13}
› A B = (A - B) (B - A)= (A B) – (A B)
U={x | x Z}
A={1,2,5,7,10,12}
B = {x | x Z ; 3 < x < 15 ; x es primo}={5,7,11,13}
C={3,5,9,10,12,13,14}
D={2,4,8,10,11}
 C’ – (D A)
› C’ = {x | x Z; x {3,5,9,10,12,13,14}}
› D A = {1,4,5,7,8,11,12}
› C’ – (D A) = {x | x Z; x 
{1,3,4,5,7,8,9,10,11,12,13,14}}
U={x | x Z}
A={1,2,5,7,10,12}
B = {x | x Z ; 3 < x < 15 ; x es primo}={5,7,11,13}
C={3,5,9,10,12,13,14}
D={2,4,8,10,11}
09/06/2011
8
 [(A B’) – C] D’
› A B’ = {x | x Z; x {11,13} }
› (A B’) – C = {x | x Z; x {3,5,9,10,11,12,13,14}
› [(A B’) – C] D’={2,3,4,5,8,9,12,13,14}
› B’= {x | x Z; x {5,7,11,13}}
› D’={x | x Z; x {2,4,8,10,11}}
U={x | x Z}
A={1,2,5,7,10,12}
B = {x | x Z ; 3 < x < 15 ; x es primo}={5,7,11,13}
C={3,5,9,10,12,13,14}
D={2,4,8,10,11}
 Construye el diagrama de Venn que cumple con 
las siguientes condiciones :
› C (A – B)
› (A B) (F – E)
› D (E – F)
› G (E F)
› A B ≠ 
› E F ≠
› (E F) U
 Un grupo de jóvenes fue entrevistado acerca de sus preferencias por 
ciertos medios de transporte (bicicleta, motocicleta y automóvil). 
Los datos de la encuesta fueron los que aparecen en el diagrama de 
Venn:
› ¿Cuál fue el número de personas entrevistadas? 
› ¿A cuántos le gustaba la bicicleta solamente? 
› ¿A cuántos le gustaba el automóvil solamente? 
› ¿A cuántosle gustaban las tres cosas? 
› ¿A cuántos le gustaba la bicicleta y el automóvil pero no la motocicleta? 
1. Doble negación a) (A‟)‟ = A
2. Ley conmutativa a) A B = B A
b) A B = B A
3. Ley asociativa a) A (B C) = (A B) C
b) A (B C) = (A B) C
4. Ley distributiva a) A (B C) = (A B) (A C)
b) A (B C) = (A B) (A C)
5. Ley de 
idempotencia
a) A A = A
b) A A = A
c) U U = U
d) U U = U
e) = 
f) = 
09/06/2011
9
6. Ley de Morgan a) (A B)‟ = A‟ B‟
b) (A B)‟ = A‟ B‟
7. Equivalencia a) A (A‟ B) = A B
8. Ley inversa a) A A‟ =
b) A A‟ = U
9. Propiedades del 
complemento
a) U‟ = 
b) ‟ = U
10. Ley de identidad a) A = A
b) A U = A
11. Ley aniquilación a) A U = U
b) A = 
12. Ley absorción a) A (A B) = A (A B) = A
 Demostrar que :
› [A-(A B)] [B-(A B)] (A B)=A B
[A-(A B)] [B-(A B)] (A B)=
([A (A B)‟ ] (A B)) [B-(A B)]= (def. diferencia, conmutativa y asociativa)
([A (A B)] [(A B)‟ (A B)]) [B-(A B)]= (distributiva)
([A (A B)] [U]) [B-(A B)]= (ley inversa)
([A (A B)]) [B-(A B)]= (identidad)
(A) [B-(A B)]= (absorción)
(A) [B (A B) „ ]= (def. diferencia)
(A) [B (A „ B „ )] = (De Morgan)
(A) [(B A „ ) (B B „)] = (distributiva)
(A) [(B A „ ) ( )] = (ley inversa)
(A) [(B A „ )] = (identidad)
(A B) (A A‟ )] = (distributiva)
(A B) (U)] = (ley inversa)
(A B) (identidad)
Usando las leyes de los conjuntos, demostrar que:
 (A‟ B‟ C) (A‟ B C) (A B‟ C) (A B C) (A B C‟) = 
C (A B)
 [(A‟ C) (B‟ B)] [(A C) (B‟ B)] (A B C‟)= C (A B)
Ley distributiva
 [(A‟ C) ( U )] [(A C) (U)] (A B C‟)= C (A B) Ley 
inversa
 (A‟ C) (A C) (A B C‟)= C (A B) Ley identidad
 (C ( A‟ A)) (A B C‟) = C (A B) Ley distributiva
 (C ( U )) (A B C‟) = C (A B) Ley inversa
 C (A B C‟) = C (A B) Ley identidad
 (C A) (C B) (C C‟) = C (A B) Ley distributiva
 (C A) (C B) U = C (A B) Ley inversa
 (C A) (C B) = C (A B) Ley identidad
 C (A B) = C (A B) Ley distributiva 
 Ejercicio 1 : Demuestra las igualdades
› (A-B)-C= A-(B C)
 Ejercicio 2: Simplifica la expresión
› [((A B) C )„ B‟ ]‟
 Ejercicio 3: Demuestra que
› (A‟ B) (A B C)‟ (C (B‟ A )) = U
09/06/2011
10
 Sean A y B dos conjuntos finitos, entonces:
|A B| = |A| + |B| - |A B|
 De 34 programas revisados en programación I, 23 
marcaron error en la compilación, 12 tuvieron fallas en 
lógica y 5 en lógica y compilación. ¿Cuántos programas 
tuvieron al menos un tipo de error?
 Así:
› |A B| = |A| + |B| - |A B|= 23 +12 -5 =30
 ¿Cuántos no tuvieron error? 
U
718 5
4
34
A B
 En el caso de tres conjuntos finitos A, B, y C, la 
expresión es:
 |A B C| = |A| + |B| + |C| - |A B| - |A C| - |B 
C| + |A B C|
 Para cuatro conjuntos es:
 |A B C D| = |A| + |B| + |C| +|D|- |A B| - |A 
C| - |A D| - |B C| - |B D| - |C D| + |A B C| 
+ |A B D| + |A C D|+ |B C D|- |A B 
C D| 
 El número de elementos que se suman o restan esta 
dado por (2n -1), n es el número de conjuntos. 
 Además, usamos el principio de inclusión exclusión que 
establece que se deben sumar las áreas que involucran 
un número impar de conjuntos y se restan las que 
relacionan un número par.
 En la biblioteca existen 103 libros de ciencias de la computación 
que tratan de los siguientes temas:
› Compiladores
› Estructuras de datos
› Redes
 Del total, 50 libros tienen información sobre compiladores, 54 
sobre estructuras de datos, 51 sobre redes, 30 sobre compiladores y 
estructuras de datos, 32 sobre compiladores y redes, 35 sobre 
estructuras de datos y redes, 19 sobre los tres temas. 
› ¿Cuántos libros contienen material exactamente sobre uno de los tres temas?
› ¿Cuántos no tienen material de redes?
› ¿Cuántos no tienen material sobre ninguno de los temas?
› ¿Cuántos libros contienen material de compiladores y redes pero no de 
estructuras de datos?
09/06/2011
11
 El número de libros que contiene material exclusivo de 
uno de los temas es 7 + 8 +3 =18
 Los libros que no tienen material de redes son: 26 + 7 
+11+8=25
 Los libros que no tienen material de 
ninguno de los tres temas son 26.
 Los libros que tienen información de 
redes y compiladores pero no de 
estructuras de datos son 13.