03_Subconjuntos Y Conjunto Potencia

1

SUBCONJUNTOS y
CONJUNTO POTENCIA
COMP 2501: Estructuras Computacionales Discretas I
Dra. Madeline Ortiz Rodríguez
3 de septiembre de 2013

2

Material de Estudio
• Libro de Koshy: páginas 71-72, 78-84.
• Vídeos sobre el Triángulo de Pascal.
• Colabora con tus compañeros de clase en la construcción

de soluciones de los ejercicios de práctica.

3

El prefijo “sub”
• ¿Cómo se define elprefijo “sub”?
• Entra al Diccionario de la Real Academia Española (RAE) y estudia
su definición (http://www.rae.es).
• ¿Cuándo dices subdirector, a qué te refieres?
• Entra al Diccionario de la RAE y estudia su definición.
• ¿Qué otras palabras conoces que comienzan por el

prefijo “sub”?
• Busca sus significados en el diccionario.

• Qué tal …
• Subcelular, subcomisión, subestación, subíndice?

4Subconjunto
• La definición de este término se ofrece para las

matemáticas, no importa que lo busques en el diccionario
de la RAE.
• Compara las definiciones de subconjunto, según las
ofrecen los siguientes recursos:
• RAE
• Diccionario matemático

• Libro de Koshy

• Escribe tu propia definición o escoge aquella que mejor

entiendas.

5

Subconjunto
• Todo aquel conjunto que se puede construirseleccionando elementos de un conjunto dado que está
bajo estudio.
• Por ejemplo, si estudiamos el conjunto V:
• V = { a, e, i, o, u }

• Podemos construir subconjuntos que:
• Tengan algunas de las vocales: { a, e }
• *Todas las vocales: { a, e, i, o, u }
• *Ninguna de las vocales, el conjunto nulo: { } = Ø
• *Observa que entre los subconjuntos se incluyen los

extremos: todos los elementos oningún elemento.

6

Subconjuntos
• Debemos comenzar por estudiar el conjunto dado:
• Digamos que A = { x | x < 10, x ∈ N }
• Entonces A = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
• Un subconjunto podría ser el de los números pares en A:
• P = { 2, 4, 6, 8 }
• Si P ≠ A, entonces P ⊆ A.
• P se conoce como subconjunto propio de A.

• Otro subconjunto podría ser el de los números impares:
• S = { 1, 3, 5, 7, 9}. S ⊆ A.
• Si consideráramos el conjunto T, en comparación con A:
• T = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
• Podemos decir que A = T. Además, T ⊆ A.

7

¿Cómo se relacionan A, P y T?
• En resumen, la notación de subconjuntos se establece de

la siguiente manera:
• Si P es un subconjunto de A y P ≠ A → P ⊆ A,
• P se conoce como un subconjunto de A que algunos de sus

elementos.
• Si T es unsubconjunto de A y T = A → T ⊆ A,
• T se conoce como un subconjunto de A que incluye los mismos

elementos.
• Ver libro de Koshy (2004), pág. 69.

8

¿Cuántos subconjuntos hay?
• ¿Será posible determinar cuántos subconjuntos se

pueden construir, dado un conjunto finito?
• ¿Existe alguna fórmula o algún método que me pueda

ayudar a encontrar la solución de manera lógica?

9

Conjunto Potencia: P (x)
•El conjunto potencia incluye todos los subconjuntos del

conjunto dado.
• Para encontrar su cardinalidad (el número total de
subconjuntos) se utiliza la siguiente fórmula:
• | P (x) | = 2 n

10

Conjunto Potencia: P (x)
• Así, si volvemos al ejemplo anterior, en donde:
• A = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
• La cardinalidad de A es: | A | = 9
• Entonces, el conjunto potencia de A es: | P (A) | =2

9

• Esto significa que del conjunto A podemos construir ______

subconjuntos.
• ¿Serán 18 subconjuntos?
• ¿Serán 512 subconjuntos?
• ¿Por qué?

11

Otro ejemplo
• Si B = {2, 3, 7, 9}
• ¿Cuántos subconjuntos tendrá B?
• PRIMERO se determina la cardinalidad de B:
| B | = 4.
• SEGUNDO se determina la cardinalidad del conjunto potencia:
| P (B) | = 2 4
• En total tendremos:
• 2

4

= 2 semultiplica por sí mismo 4 veces
• 24=2x2x2x2
• 2 4 = 16
• Entonces el conjunto B tendrá 16 subconjuntos.

12

Los subconjuntos de B = {2, 3, 7, 9}
• Seguiremos un patrón:
• PRIMERO: Comenzamos por el subconjunto vacío – sin elementos
• Hay un subconjunto: { }

• SEGUNDO: identificamos los subconjuntos de un elemento
• Hay cuatro subconjuntos: { 2 }, { 3 }, { 7 }, { 9 }

• TERCERO: identificamos los...