Estructuras Discretas

Teoría de Conjuntos

Definicion: llamaremos conjunto a una colección o agrupación de objetos, el cual se llamaran elementos.

Conjunto Universal (U): es el conjunto que contiene los elementos a seleccionar

Para visualizar mejor estas definiciones a continuación pondré un ejemplo.

Consideremos el conjunto formado por todos los números pares menores que 10 diciendo que el conjunto A= {2,4,6,8} y nuestro conjunto universal P, el conjunto formado por todos los números pares menores que 10.

Normalmente los conjuntos son identificados con las letras mayúsculas, mientras que los elementos se denotan con las minúsculas.

Los elementos del conjunto son encerrados en llaves o círculos, el cual es llamado diagrama de ven.

Existen dos formas de determinar un conjunto: por extensión y por comprensión.

a) Por extensión

A={2,4,6,8}; P={a,x,y,w}b) Por comprensión

A={XϵR/1} (x pertenece a todos los reales diferentes a 1)

Subconjuntos

Relación de inclusión:

Si A es el conjunto formado por las vacas y B es el conjunto Formado por los mamíferos entonces tenemos que todo elemento de A es también elemento de B.

P={vacas}

M={mamiferos} decimos que P ì M

Teorema: la relación de inclusión entre conjuntos es.

Reflexiva: AìA, para todo conjunto A

Antisimetrica: AìB ù BìA ϷA=B

Transitiva: AìB ù BìC Ϸ AìC

Definicion: diremos que un conjunto A esta incluido propiamente en un conjunto B o que A es subconjunto propio de B si y solo si AìB y A ¹ B

Ejemplo:

A={x,y,z} y B={t,u,v,x,y,w,z} entonces A es subconjunto propio de B

Conjunto Vacio

Definicion: es aquel conjunto que no tiene elementos

Dado el conjunto A, el Conjunto vacio Fₐ es el conjunto:

Fₐ={xîA/x ¹ x} el Fₐ no tiene elementos ya que todo xîA satisface x=x a demás por definición se tiene que vacio es subconjunto de todo conjunto A.

Conjunto Potencia

Definicion: es el conjunto formado por todos los subconjuntos que es posible formar de un conjunto dado

Ejemplo:

Si A={x,y,z} entonces Ᾱ(A)= {{n}, {x}, {y}, {z}, {x,y}, {x,z}, {y,z}, {x,y,z}}

-La principal característica de este conjunto es que es un conjunto de conjuntos, es decir, sus elementos son conjuntos.

-Dado un conjunto A podemos conocer el numero de elementos de Ᾱ(A), ya que si A tiene n elementos, entonces Ᾱ(A) tiene 2n elementos.

Igualdad de Conjuntos

Dos conjuntos son iguales si tienen los mismos elementos.

Ejemplo:

A={1,3,7,9,a,b} B={b,a,9,3,1,7}

Entonces: A=B pues son los mismos elementos aunque estén en diferente orden.

Unión e Intersección de Conjuntos

Sean A y B dos conjuntos. Se define la unión de A y B como el conjunto:

A U B = { xÎ U / xÎ A Ú xÎ B}

Es decir, son todos los elementos que están en A o están en B.

Ejemplo: Si A = {1,3,5,6,7,8} y B = {0,1,-14,5,8,7,10} entonces,

A U B = {0,1,3,5,6,7,8,10,-14}

Propiedades de la Unión de Conjuntos

Sean A y B dos conjuntos, luego se cumplen las siguientes propiedades:

     i. A U A = A

     ii. A U U = U

    iii. A U f = A

    iv. AUB = BUA

Sean A y B dos conjuntos. La intersección de A con B se define como el conjunto:

A I B = { xÎ U / xÎ A Ù xÎ B}

Es decir, los elementos que están en A y también están en B.

Ejemplo: Sea A = {a,b,c,d,e} y B = {a,c,e,h,i,j,k} luego, la intersección de los conjuntos A y B es el siguiente conjunto A I B ={a,c,e}

Propiedades de la Intersección de Conjuntos

Sean A y B conjuntos, luego se cumple:

      i. A I A = A , " A

      ii. A I U = A , donde U es el conjunto universal

      iii. A I f = f

      iv. A I B = B I A

Diferencia y Complemento

Si A y B son conjuntos, entonces se

define la diferencia entre A y B como

el siguiente conjunto:

A - B = { xÎ U / xÎ A Ù xÏ B}. Es decir,

son todos los elementos que están en A

pero que no están en B.

Ejemplo: Consideremos los conjuntos

A = {1,2,3,5,7,9,11,12} y B = {0,1,2,-

4,5,7,9,6,8,10,18}

Luego A-B = {3,11,12} mientras que B-

A = {0,-4,6,8,10,18}

 Sean A y B dos conjuntos. La diferencia simétrica

entre A y B es el conjunto.

AD B = (A-B) U (B-A) = { xÎ U / xÎ A Ú xÎ B}

En el ejemplo anterior se tiene que AD B = {-4,0,3,6,10,11,12,18}

Propiedades de la Diferencia de Conjuntos

Sean A,B,C tres conjuntos, luego se cumple que:

i. (AUB) - C = (A - C) U (B - C)

ii. (A I B) - C = (A - C) I (B - C)

iii. (AD B) - C = (A - C) D (B - C)

iv. A I ( B - C) = (A I B) - (A I C)

v. (B - C) I A = (B I A) - (C I A)

Sea B un conjunto. Se define el Complemento de B como el conjunto.

C(B) = {xÎ U/ xÏ B}. Es decir, el complemento de B son los elementos que le

faltan a B para llegar a ser igual a U.

Así podemos decir xÎ C(B) Û xÏ B.

Ejemplo: Si U = {1,2,3,4,5,6,7,8,9,10} y B = {1,3,5,7}

entonces C(B) = {2,4,6,8,9,10}

Teorema: Sean A y B dos conjuntos luego:

a. A - B = AI C(B)

b. C(C(A)) = A

c. AUC(A) = U

d. AI C(A) = f

e. C(U) = f

f. C(f ) = U

g. AÌ B Û C(B) Ì C(A)

a. A U A = A A = A

Leyes de Idempotenciab. A

Leyes Asociativas

A U (BUC) = (AUB) U C A I (BIC) = (AIB) I C

Leyes Conmutativas

a. A U B = B U Ab. A I B = B I A

Leyes Distributivasa. A U (B I C) = (A U B) I (A U C)

I (B U C) = (A I B) U (A I C)b. A

Leyes de Identidad

a. A U f = A I f = fb. A

Leyes de Dominación

a. A U U = U U: conjunto universal

b. A I U = A

Leyes de Complementación

a. A U C(A) = Ub. A I C(A) = f f f) = Uc. C (C(A)) = Ad. C (U) =e. C (

Leyes de De Morgan a. C(A U B) = C(A) I C (B) I B) = C(A) U C (B)

b. C(A

Algebra de Conjuntos

Así como en las proposiciones existen las leyes del álgebra de proposicional, en la teoría de conjuntos tenemos las leyes del álgebra de conjuntos que veremos a continuación.

Producto Cartesiano

Sean A y B dos conjuntos. Se define el conjunto producto o producto cartesiano de A y B como el conjunto Ax B = { (a,b) / aÎ B Ù bÎ B}

Ejemplo: Si A = {a,b} y B = {1,5,8}

entonces Ax B = {(a,1), (a,5), (a,8), (b,1), (b,5), (b,8)}

mientras que BxA = {(1,a), (1,b), (5,a), (5,b), (8,a),(8,b)}

Nótese que Ax B ¹ Bx A

Operaciones Generalizadas

Consideremos un conjunto de índices I={1, 2, 3, & , n} y una familia de conjuntos {A1,

A2, & , An}, donde cada Ai con iÎ I, representa un conjunto.

Al conjunto {A1, A2, & , An} lo llamaremos Familia Indizada de conjuntos; y lo

denotaremos {Ai}iÎ I.

Ejemplo

Sea la familia indizada {Ai}iÎ I, donde I={1, 2, 3, 4} y  determinar por extensión cada

miembro de la familia.

Solución

La familia de conjuntos dadas en el ejemplo anterior es finita.Sin embargo, podemos

también considerar familiar infinitas. Por ejemplo, consideremos el conjunto , donde n

es un número natural cualquiera; luego la familia es una familia infinita, cuyo conjunto

de índice es el conjunto de los números naturales . Algunos de los miembros de la

familia son:

Ahora definamos la unión e intersección de una familia indizada de conjuntos:

Definición

Sea {Ai}iÎ I una familia indizada de conjuntos, se define:

i. La unión de esta familia como el conjunto

ii. La intersección de esta familia como el conjunto

Partición

Sea X un conjunto y {Ai}iÎ I una familia de subconjuntos de X. Se dice que {Ai}iÎ I es una

partición de X, si y sólo si:

iii. Cada Ai es una celda o bloque de la partición, es decir, una partición es una

familia {Ai}iÎ I donde cada conjunto de la familia es no-vacío, la intersección

entre dos miembros de la familia es vacía y la unión de todos los miembros da

X.

iv. Ejemplo

v. Si X={a, b, c, d, e, f, g} y A1={a, b}, A2{e, c, g}, A3={d, f} , entonces {A1, A2,

A3} es una partición de X.

Juan Alvarez

C.I: 26085548