03_subconjuntos y conjunto potencia
DESCRIPTION
123456TRANSCRIPT
SUBCONJUNTOS y
CONJUNTO POTENCIA COMP 2501: Estructuras Computacionales Discretas I
Dra. Madeline Ortiz Rodríguez
3 de septiembre de 2013
1
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.
2
El prefijo “sub”
• ¿Cómo se define el prefijo “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?
3
Subconjunto
• 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.
4
Subconjunto
• Todo aquel conjunto que se puede construir
seleccionando 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 o ningún elemento.
5
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.
6
¿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 un subconjunto 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.
7
¿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?
8
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
9
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é?
10
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 se multiplica por sí mismo 4 veces
• 2 4 = 2 x 2 x 2 x 2
• 2 4 = 16
• Entonces el conjunto B tendrá 16 subconjuntos.
11
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 subconjuntos de dos elementos
• Hay seis subconjuntos: { 2, 3 }, { 2, 7 }, { 2, 9 }, { 3, 7 }, { 3, 9 }, { 7, 9 }
• CUARTO: identificamos los subconjuntos de tres elementos
• Hay cuatro subconjuntos: { 2, 3, 7 }, { 2, 3, 9 }, { 2, 7, 9 }, { 3, 7, 9 }
• QUINTO: identificamos el subconjunto de cuatro elementos, todos
los elementos de B.
• Hay un subconjunto de cuatro elementos: { 2, 3, 7, 9 }
12
Total de subconjuntos de B
• Si contamos todos los subconjuntos o sumamos cuántos
hay de cero elementos, un elemento, dos elementos, tres
elementos y cuatro elementos:
• Encontramos que B tendrá 16 subconjuntos, tal y como nos indica
la fórmula. Veamos otra vez el proceso:
• Si B = {2, 3, 7, 9}
• entonces | B | = 4
• y | P (B) | = 2 4
= 16
13
Para encontrar los subconjuntos
• Esto es sencillo cuando tenemos pocos elementos, pero
puede llegar a ser complejo si tuviéramos muchos
elementos.
• Una alternativa es utilizar el Triángulo de Pascal.
14
El Triángulo de Pascal
• Esta construcción sencilla nos permite identificar cuántos
subconjuntos habrán por número de elementos.
• Compara la cuarta línea, con los valores 1, 4, 6, 4, 1 al
total de subconjuntos de B en las diapositiva 11 y12.
15
Imagen obtenida de: http://en.wikipedia.org/wiki/Triangle_of_Pascal
Entendiendo el Triángulo de Pascal
La primera línea se conoce como la línea 0, para un conjunto
de 0 elementos. Esto es, el conjunto nulo o vacío sólo tiene
un subconjunto, él mismo. Esto es 20 es igual a 1.**
16
Línea 0
** Ver diapositiva 24-26.
Entendiendo el Triángulo de Pascal
La segunda línea se conoce como la línea 1, para un conjunto
de un elemento. Esto es, el conjunto con un elemento tiene dos
subconjuntos, un conjunto vació y otro con un elemento. Si
sumas 1 + 1, en total tendrás 2, o sea dos subconjuntos (21).
17
Línea 1
Entendiendo el Triángulo de Pascal
La tercera línea se conoce como la línea 2, para un conjunto de dos elementos. Esto es, el conjunto con dos elementos tiene cuatro subconjuntos, uno vacío, dos con un elemento y otro con todos los elementos. Si sumas 1 + 2 + 1 tendrás 4, o sea cuatro subconjuntos (22).
18
Línea 2
Para crear el Triángulo de Pascal
Suma los dos elementos superiores para encontrar el de abajo, en forma triangular. En los extremos escribe un uno. Mira el ejemplo en la línea 3, para construir la línea 4.
19
Construyendo el Triángulo de Pascal
• Sigue le patrón presentado para construir las próximas
líneas del Triángulo de Pascal, hasta llegar a la línea 9.
• Suma los elementos de la novena línea. Deberás obtener
512.
• Este sistema te permitirá saber cuántos subconjuntos de
un 5 elementos tendrías, sin tener que identificarlos con
los elementos.
• Puede ayudarte a confirmar si tienes todos los
subconjuntos cuando te los solicitan.
20
Vídeos sobre el Triángulo de Pascal
• Los vídeos que aparecen a continuación te ayudarán a
entender y construir el Triángulo. Dos de sus usos
principales en matemáticas son:
• Expansión del Binomio en álgebra
• Combinaciones en estadísticas
• Determinar el número de subconjuntos (en nuestra clase)
• pascal triangle animation. (2007).
http://www.youtube.com/watch?v=Zo2JrPjijHc
• Binomial Expressions & Pascal's Triangle (Part 1). (2010).
http://www.youtube.com/watch?v=CmH3ogYAy4k&feature
=related
21
Otros ejercicios
• Ejercicio #1:
• Dado K = { 1, 2, 3, 5. 8 }
• Encuentra todos los subconjuntos de K.
• Confirma tu respuesta construyendo el Triángulo de Pascal hasta
la línea 5.
• Ejercicio #2:
• Dado T = { 0, 3, 6, 9, 12, 15, 18, 21 }
• Determina la cardinalidad del conjunto potencia (¿cuántos
subconjuntos tiene T?). Utiliza el Triángulo de Pascal para
confirmar tu respuesta.
22
¿Qué significa la potencia 0?
• Muchas veces confundimos el significado de la potencia 0
con la multiplicación por cero.
• Estamos conscientes de que:
• 20 ≠ 2 x 0
• pero aun así no estamos seguros si la solución debe ser
cero.
• La solución correcta de cualquier número elevado a la cero
es uno, incluyendo variables.
• 20 = 1
• (-5)0 = 1
• x0 = 1
23
Interpretación de la potencia cero
• Tal vez la manera más fácil de entender este concepto es
trabajar con la simplificación de potencias.
• Así si tenemos el cociente (división) de
• 25 / 23
• Sabemos que se cancelan los dos que se repiten al multiplicar o
siguiendo la regla de álgebra, se restan los exponente y la solución
debe ser 22 = 4.
24
Interpretación de la potencia cero
• Si la división fuera entre potencias iguales entonces,
podríamos tener:
• 72 / 72
• Al solucionar las potencias tenemos: 49/49 = 1
• Si restamos los exponentes, siguiendo la regla de división
de potencias, tendremos:
• 72-2 = 70
• Siendo el mismo ejercicio, las mismas potencias,
entonces podemos concluir que:
• 70 = 1.
25