26/02/2014

Conjuntos, relaciones y funciones Matemáticas Discretas para el Diseño Geométrico

Teoría de conjuntos Representación y manipulación de grupos

2

Matemáticas Discretas: Conjuntos, relaciones y funciones

1

26/02/2014

Motivación  Las nociones que estudiaremos constituyen fundamentos

matemáticos importantes.

3

Matemáticas Discretas: Conjuntos, relaciones y funciones http://www.ipuc-an.org/imagenes/7columnas.jpg

Aplicaciones de los conjuntos  Clustering  Complejidad computacional  Definiciones formales  Ej. grafos

 Manejo de grupos en general  ¡Tema básico! 4

Matemáticas Discretas: Conjuntos, relaciones y funciones

2

26/02/2014

Definición  Conjunto= grupo de elementos u objetos.  Formas de representación  Extensión  Enumeración de miembros  Intención  Descripción formal  Diagramas de Venn y Euler  Representación gráfica

5

Matemáticas Discretas: Conjuntos, relaciones y funciones

Formas de representación  Extensión– Enumeración de miembros  A={1,2,3} // E={ mateo, marcos, lucas, juan } // ¿…?

 Intención-- Descripción formal  A={x | 0 < x < 4} // { n3+ n2 | n  {1,2,3,4} }

 Diagramas de Venn y Euler-- Representación gráfica A

6

B

Matemáticas Discretas: Conjuntos, relaciones y funciones

3

26/02/2014

Consideraciones  Los elementos se encierran entre llaves y se escriben con

minúsculas.

 Los nombres de conjuntos se representan con mayúsculas.  A= {1,2}, B={c, d}.

 No importa el orden ni las repeticiones.  {a, b, c} = {b, a, c} = {b, b, a, c, c, c}.

 Podemos tener conjuntos dentro de conjuntos.

 Ej. C={ {1,2}, {3,4} }, E={{u,v} | u,v V}

7

Matemáticas Discretas: Conjuntos, relaciones y funciones

Pertenencia de elementos  Un elemento puede o no pertenecer a un conjunto*.  La pertenencia se indica con .  La no-pertenencia se indica con .  Ej. a  {a, b, c} // {3,4}  {{3,4},5} // A = {1, 2, 3} 

4 A

 *=(En el caso nítido o booleano; en conjuntos difusos, existen grados de

pertenencia.)

8

Matemáticas Discretas: Conjuntos, relaciones y funciones

4

26/02/2014

Conjuntos finitos e infinitos  Existen conjuntos finitos e infinitos.  La diferencia consiste en si es posible expresar su tamaño (cantidad

de elementos) con un número.  A = {1,3,5}  finito  B = {a, b, c…z}  finito  C = {1,2,3…}  infinito  D = {x | x es un número real}  infinito  Los conjuntos infinitos pueden ser contables o

incontables. 9

Matemáticas Discretas: Conjuntos, relaciones y funciones

Conjuntos infinitos  Conjuntos infinitos: su tamaño no puede expresarse con un

número.  Ejemplo: Los números naturales

 Conjuntos contables (numerables)  Los elementos pueden ponerse en correspondencia a los

números naturales.  Ej. números pares

 Un conjunto incontable es, por ejemplo, el de los números

reales.

10

Matemáticas Discretas: Conjuntos, relaciones y funciones

5

26/02/2014

Ejercicio  Menciona un ejemplo concreto de:  un conjunto finito.  un conjunto infinito.

11

Matemáticas Discretas: Conjuntos, relaciones y funciones

Conjunto vacío y universo de discurso  Conjunto vacío  Se representa como { } ó   || = 0  Observa que {} no es vacío.  Universo de discurso  Se representa como U.  Contiene todos los elementos.  “El todo”.

12

U B A

C

Matemáticas Discretas: Conjuntos, relaciones y funciones

6

26/02/2014

Tamaño (cardinalidad)  Número de elementos que contiene un conjunto finito.  Los elementos pueden ser atómicos o compuestos (otros conjuntos).

 Se denota |A| para un conjunto A.  Ej.  A = {a, b, c, d} / |A|=4  C = {a, b, a, c, d} / |A|=4  D={{a, b}, {c, d}} / |D|=2

 B={1,2,{3,4}} … ¿|B|?

13

Matemáticas Discretas: Conjuntos, relaciones y funciones

Operaciones binarias con conjuntos  Unión (A  B)  Enumeración de todos los elementos de A y

B.  Intersección (A  B)  Elementos que están tanto en A como en B.

 Diferencia (A – B)  Elementos de A que no están en B.

 Diferencia simétrica (A  B)  Elementos no compartidos entre A y B. 14

Matemáticas Discretas: Conjuntos, relaciones y funciones

7

26/02/2014

Ejemplos con operaciones  A = {a, b, c}, B = {b, c, d}  A  B = {a, b, c, d}  A  B = {b, c}  A – B = {a}  A  B = {a, d}

15

Matemáticas Discretas: Conjuntos, relaciones y funciones

Otras operaciones con conjuntos  Complemento (Ac)  Diferencia entre el universo U y el conjunto.

 Producto cartesiano (A  B)  Conjunto de pares ordenados de forma (a,b), tal que a pertenece

a A y b pertenece a B.  Error común: no representar al producto cartesiano como un conjunto.  Nota que esta operación no es conmutativa. 16

Matemáticas Discretas: Conjuntos, relaciones y funciones

8

26/02/2014

Ejemplos  U = {a,b,c,d,e,f,g}  A = {a,b,c}, B={f,g}

¿Qué regla de conteo nos explica el tamaño del conjunto cartesiano?

 Ac = {d,e,f,g}  A  B = {(a,f), (b,f), (c,f), (a,g), (b,g), (c,g)}.  B  A = {(f,a), (f,b), (f,c), (g,a), (g,b), (g,c)}.  B  B = {(f,f), (f,g), (g,g), (g,f)}. Aplicación: en redes complejas, el producto cartesiano representa todas las posibles conexiones que existen para una red. 17

Matemáticas Discretas: Conjuntos, relaciones y funciones

Igualdad si y sólo si

 Dos conjuntos son iguales ssi tienen los mismos elementos.  Son idénticos (sin importar orden o repeticiones).

 Ejemplos    

(A={1,2,3,4}  B={1,2,3,4})  A=B. (A={1,2,3,4}  B={2,1,3,4})  A=B. (A={1,2,3,4}  B={2,1,3,5})  AB. (A={1,2,3,4}  B={0,1,2,3,4})  AB.

 Nota que cuando A=B, |A| = |B|. 18

Matemáticas Discretas: Conjuntos, relaciones y funciones

9

26/02/2014

Subconjuntos  Un conjunto A es subconjunto de un conjunto B si los elementos de A se

encuentran en B.

 Se denota con .  Todo conjunto es subconjunto de sí mismo.  Ejemplo:   

{1,2,3,4,5}  {1,2,3,4,5} {1,2,3}  {1,2,4} En un grafo (red), las conexiones son un subconjunto de todas las relaciones posibles entre pares de vértices; formalmente, E  V  V.

 Observa que |A|  |B|.

19

Matemáticas Discretas: Conjuntos, relaciones y funciones

Subconjuntos propios  Si la cantidad de elementos en A es estrictamente menor, entonces A

es un subconjunto propio de B.  Se denota con .

  siempre es subconjunto propio de cualquier conjunto.

 Ejemplos

 A={1,2,3} y B={1,2,3,4,5} // A  B  {a}  {a,b,c,d,e}  {a,x}  {a,b,c,d,e}

 Observa que |A| < |B|. 20

Matemáticas Discretas: Conjuntos, relaciones y funciones

10

26/02/2014

Conjunto potencia  Enumeración de todos los subconjuntos de un conjunto. Se denota

como P(A) para un conjunto A.

 Ejemplos:  A = {1,2,3}, B={a,b,c,d}  P(A)={,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}.  P(B)={,{a},{b},{c},{d},{a,b},{a,c},{a,d},{b,c},{b,d},

{c,d},{a,b,c},{b,c,d},{a,b,d},{a,c,d}{a,b,c,d}}.  Observa que |P(X) |=2n, donde n=|X|. 21

¿Cómo explicas esta cantidad a través de conteo?

Matemáticas Discretas: Conjuntos, relaciones y funciones

Diagramas de Venn  Utilizados para representar conjuntos

Intersección

22

Contención (subconjunto propio)

Conjuntos disjuntos

Matemáticas Discretas: Conjuntos, relaciones y funciones

11

26/02/2014

Venn: contención NR  A

Código nuevo reusable

Código agregado

23

Matemáticas Discretas: Conjuntos, relaciones y funciones

Venn: intersección Estudian

Trabajan

Estudian y trabajan 24

Matemáticas Discretas: Conjuntos, relaciones y funciones

ET

12

26/02/2014

Venn: conjuntos disjuntos PL= Estudiantes de posgrado

25

Estudiantes de licenciatura

Matemáticas Discretas: Conjuntos, relaciones y funciones

Algunos ejemplos más…

26

Matemáticas Discretas: Conjuntos, relaciones y funciones

13

26/02/2014

Algunos ejemplos más… AB

A

B

AC

BC

C

27

ABC

Matemáticas Discretas: Conjuntos, relaciones y funciones

U A 12

B 6

C

D 1

10

7

3

F

9 14

2

E 16

15

11

8 4

G 5

28

13

MATDIS / Posgrado / FIME / UANL

14

26/02/2014

 F  (B - A)

 D  E = {1, 7, 9}

 AC

 (D  E)  (A  B)

 E - D = {9}

 16  (D  E)

 ED=

 (A  B)’ = {5, 13, 15}

 (C  E)  B

 B – A = {2, 4, 8, 11}

 (D - E)  (A  B )

 (A  B)  (A - B) = A

 C – G = {3, 10}

 2  U’

 G–F=

 [U – (A  B)] = G  {13,

 (F – C)  B  A – B = {3, 10, 12, 14}

15}  D  E = {1, 9}  A – (A  B) = C  {12, 14}

¿Falso o verdadero? (F oV) 29

MATDIS / Posgrado / FIME / UANL

Ejercicios  Considera como universo un lote de autos de una planta.  Existen los siguientes conjuntos en el universo:  A1 = Autos que tienen el defecto 1.  A2 = Autos que tienen el defecto 2.  A3 = Autos que tienen el defecto 3.

30

Matemáticas Discretas: Conjuntos, relaciones y funciones

15

26/02/2014

Ejercicios (Continúa)  Crea un diagrama de Venn que represente el caso.  Representa gráficamente lo siguiente e interprétalo (en

español) :  A1  A2  A1  A2

 A1  A2  A3  A1  A2  A3

31

Matemáticas Discretas: Conjuntos, relaciones y funciones

Ejercicios (continúa)  Representa (gráfica y formalmente) lo siguiente:  Los autos que tienen el defecto 1 pero no el 2.  (Pueden o no tener el defecto 3.)  Los autos que tienen los defectos 2 y 3.  Los autos que tienen el defecto 2 y, además, el 1 ó el 3.  Los autos que tienen el defecto 3 pero no tienen ni el 1 ni el 2.

 ¿Qué representa el resto del universo?

32

Matemáticas Discretas: Conjuntos, relaciones y funciones

16

26/02/2014

Leyes  Conmutativa  Unión e intersección  A  B = B  A, A  B = B  A

 Distributiva  Unión e intersección  A  (B  C)= (A  B)  (A  C) / A  (B  C)= (A  B)  (A  C)

 De de Morgan  Complemento  (A  B)C = AC  BC, (A  B)C = AC  BC

 Doble complemento  (AC)C = A 33

Matemáticas Discretas: Conjuntos, relaciones y funciones

Ejemplo con De Morgan

(Ac) c = Lo que NO es Ac

34 Matemáticas Discretas: Conjuntos, relaciones y funciones

17

26/02/2014

Algunos conjuntos ya definidos

35

Conjunto

Significado

Z

Enteros

N

Naturales (no negativos)

Z+

Positivos

Q

Racionales

Q+

Racionales positivos

Q*

Racionales distintos de cero

R

Reales

R+

Reales positivos

R*

Reales distintos de cero

C

Complejos

C*

Complejos distintos de cero

Matemáticas Discretas: Conjuntos, relaciones y funciones

Ejercicio  Proporciona ejemplos para:  AN  AZ  AR  e N  eC

 ¿Qué diferencia existe entre N y Z+? Exprésalo con notación

de conjuntos. 36

Matemáticas Discretas: Conjuntos, relaciones y funciones

18

26/02/2014

Aplicación práctica: índices de similitud  El Índice de Jaccard J(A,B) mide la similitud entre dos

conjuntos A y B. Divide el tamaño de la intersección entre el tamaño de la unión.

J ( A, B) 

| A B | | A B |

Mini-ejercicio 1. Proporciona un ejemplo del índice Jaccard. Incluye un diagrama de Venn. 2. ¿Qué pasa si A=B? 3. ¿Qué pasa si A B=? 37

Matemáticas Discretas: Conjuntos, relaciones y funciones

Más ejercicios  Construye tres conjuntos (finitos)  Representa uno por intención  Construye el diagrama de Venn correspondiente (de preferencia

que los conjuntos no sean disjuntos)

 Calcula lo siguiente:  Unión, Intersección, Diferencia, Cardinalidades  Conjunto potencia (al menos de uno)  Complemento  Producto cartesiano 38

Matemáticas Discretas: Conjuntos, relaciones y funciones

19

26/02/2014

Hasta aquí…  ¿Qué es un conjunto?  ¿Cuáles son sus formas de representación?  ¿Qué operaciones se pueden realizar con un conjunto?  ¿Qué es un subconjunto?

39

Matemáticas Discretas: Conjuntos, relaciones y funciones

Resumen  Conjunto = colección de elementos donde el orden y

repeticiones son irrelevantes.

 Representaciones: extensión, intención o diagramas de Venn.  Subconjunto= porción de un conjunto (propio) o conjunto

completo (igualdad).

 Operaciones unarias: tamaño, complemento, conjunto potencia.  Operaciones binarias: unión, intersección, diferencia, producto

cartesiano.

40

Matemáticas Discretas: Conjuntos, relaciones y funciones

20

26/02/2014

Ejercicio para dominio del tema  Programa (en el lenguaje de tu elección) las siguientes

operaciones con conjuntos:  Intersección  Unión

 Diferencia  Producto cartesiano

 Investiga y establece la conexión entre teoría de conjuntos y

álgebra relacional. Puntos extra

41

Matemáticas Discretas: Conjuntos, relaciones y funciones

Caso de estudio: conjuntos difusos  Generalización: cualquier elemento del universo de discurso

tiene un grado de pertenencia a un conjunto dado.  En el caso convencional o nítido (el que acabamos de ver), el

grado g(e)A de pertenencia de un elemento e en un conjunto A es binario. Es decir, g(e)A {0,1}.  Para conjuntos difusos, se permiten valores intermedios, i.e.

g(e)A [0,1]. 42

Matemáticas Discretas: Conjuntos, relaciones y funciones

21

26/02/2014

Caso de estudio: conjuntos difusos  Realiza los ejercicios

planteados por el profesor.

 ¿Qué ventajas tiene la lógica

difusa sobre la lógica booleana?

 En resumen, ¿qué diferencias

encuentras entre los conjuntos nítidos y los conjuntos difusos?

43

 ¿Qué ventajas tiene un

conjunto nítido sobre un conjunto difuso?

 ¿Qué desventajas tiene un

conjunto nítido sobre uno difuso?

 ¿Encuentras alguna aplicación

práctica para este concepto?

Matemáticas Discretas: Conjuntos, relaciones y funciones

Relaciones y funciones Definición, propiedades, ejemplos

44

Matemáticas Discretas: Conjuntos, relaciones y funciones

22

26/02/2014

Contenidos  Relaciones  Definición  Propiedades

 Ejemplos

 Funciones  Definición  Propiedades  Ejemplos 45

Matemáticas Discretas: Conjuntos, relaciones y funciones

Relación  Subconjunto del producto cartesiano entre conjuntos.  R :A  B

46

Matemáticas Discretas: Conjuntos, relaciones y funciones

23

26/02/2014

Ejemplo 1  P = {países}  A = {a | 1929 < a < 2011}  Relación: País p que ganó el mundial

en el Año a  R={(España, 2010), (Italia, 2006),

(Brasil, 2002), (Francia, 1998), …}

47

Matemáticas Discretas: Conjuntos, relaciones y funciones

Ejemplo 2  A={1,2,3}  A x A: {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2),

(3,3)}  Relación: Menor que  Rmenor={ (x,y) | x < y }  Rmenor={(1,2), (1,3), (2,3)}

La relación puede ser del conjunto consigo mismo.

48

Matemáticas Discretas: Conjuntos, relaciones y funciones

24

26/02/2014

Ejemplo 3 (Jiménez p. 224)  A = {2, 4, 5, 6, 7, 11}  B = {b | b  Z; 1  b  10}  Relación: b es divisible entre a  R = {(2,2), (2,4), (2,6), (2,8), (2, 10), (4,4), (4,8), (5,5),

(5, 10), (6,6), (7,7)}

R: A -> B 49

Matemáticas Discretas: Conjuntos, relaciones y funciones

Ejercicio 1 (Brena p. 19)  Un juego infantil consiste

en proponer simultáneamente ya sea “piedra”, “papel” o “tijeras”.

 ¿Cuál es la relación

correspondiente para “gana sobre”?

 Se supone que tijera gana

sobre papel, piedra sobre tijera y papel sobre piedra.

50

Matemáticas Discretas: Conjuntos, relaciones y funciones

25

26/02/2014

Ejercicio 2  Plantea tres relaciones.  Define los conjuntos involucrados.  Define el producto cartesiano entre éstos.

 Define la relación en sí.

51

Matemáticas Discretas: Conjuntos, relaciones y funciones

Relaciones de diferentes órdenes  Comúnmente hablamos de relaciones binarias:  se tienen pares ordenados (i.e., dos elementos en la tupla)

 Pero también existen relaciones ternarias, cuaternarias y n-arias

en general…  Se tienen tuplas ordenadas.

En los hipergrafos podemos apreciar relaciones n-arias.

52

Matemáticas Discretas: Conjuntos, relaciones y funciones

26

26/02/2014

Relaciones de diferentes órdenes  Relaciones ternarias  Ejemplo: hipergrafos para redes de colaboración  A = {perez, gzz }, B={li, yong}, C={newman, smith}

 A x B x C = {(perez, li, newman), (perez, li, smith), …}

53

Matemáticas Discretas: Conjuntos, relaciones y funciones

Propiedades en relaciones  Reflexiva

 Contiene todos los pares de la forma (x, x) para x  A  Ejemplos: “es igual a”, “es igual o mayor que”

 Simétrica  Si contiene un par (x,y), también contiene (y,x)  Ejemplo: “hermano de”

 Transitiva  Si contiene los pares (x,y) y (y,z), entonces también contiene

(x,z)

 Ejemplo: “ancestro” 54

Matemáticas Discretas: Conjuntos, relaciones y funciones

27

26/02/2014

Ejercicio 3  Menciona si las relaciones presentadas son reflexivas,

simétricas y/o transitivas.  “Gana sobre” en el juego de piedra, papel o tijera.

 Las relaciones que planteaste en el Ejercicio 2.

 Plantea una relación:  Reflexiva  Simétrica  Transitiva 55

Matemáticas Discretas: Conjuntos, relaciones y funciones

Funciones  Una función es un tipo especial de relación.  Ningún par ordenado tiene el mismo primer componente.  i.e., para una entrada sólo existe una salida La mayoría de los textos considera adicionalmente que todas las entradas generan alguna salida. Nosotros consideraremos, en su lugar, la noción de función parcial.

56

Matemáticas Discretas: Conjuntos, relaciones y funciones

28

26/02/2014

Dominio y co-dominio  Para una función f : A  B

Dominio Co-dominio (rango) 57

Matemáticas Discretas: Conjuntos, relaciones y funciones

Funciones importantes para computación  Techo  “Redondear hacia arriba”.

 Piso  “Redondear hacia abajo”.

1.3  2 3.7  4 3.7  3 1.3  1

 Logaritmo base 2  Exponente al que fue

elevado una potencia de 2. 58

log 2 (8)  3

log 2 (1024)  10

log 2 (16)  4

Matemáticas Discretas: Conjuntos, relaciones y funciones

29

26/02/2014

Funciones importantes  log2(n) en calculadora =

log10 (n) log10 (2)

 Módulo  Residuo de una división

3 mod 5  3 5 mod 3  2 4 mod 2  0

59

Matemáticas Discretas: Conjuntos, relaciones y funciones

Propiedades en funciones  Inyectiva  Sobreyectiva  Biyectiva

60

Matemáticas Discretas: Conjuntos, relaciones y funciones

30

26/02/2014

Inyectiva  Relación de uno a uno.  Para cada elemento del dominio, hay un único elemento del

co-dominio.

61

Matemáticas Discretas: Conjuntos, relaciones y funciones

Sobreyectiva  Cada elemento del co-dominio aparece en un par ordenado.

x

62

Matemáticas Discretas: Conjuntos, relaciones y funciones

31

26/02/2014

Biyectiva  Inyectiva y sobreyectiva.

63

Matemáticas Discretas: Conjuntos, relaciones y funciones

Ejemplos

64

http://www.mathsisfun.com/sets/injective-surjective-bijective.html Matemáticas Discretas: Conjuntos, relaciones y funciones

32

26/02/2014

Parcial  No está definida para todos los elementos del dominio.

65

Matemáticas Discretas: Conjuntos, relaciones y funciones

Total  Está definida para todos los elementos del dominio.

66

Matemáticas Discretas: Conjuntos, relaciones y funciones

33

26/02/2014

Aplicaciones  Descripción formal de procesos.  Ej. autómatas celulares

 Análisis de algoritmos.  Descripción de su complejidad

67

Matemáticas Discretas: Conjuntos, relaciones y funciones

Hasta aquí  ¿Qué es una relación?  Menciona algunas de sus propiedades.

 ¿Qué es una función?  Menciona algunas de sus propiedades.

68

Matemáticas Discretas: Conjuntos, relaciones y funciones

34

26/02/2014

Resumen  Un conjunto es un grupo/colección de

elementos u objetos.

 Existen tres formas de representación:

extensión, intención y diagramas.

 Algunas operaciones que podemos realizar con

conjuntos: unión, intersección, complemento, diferencia, conjunto potencia, producto cartesiano.

 Un subconjunto es una porción de un

conjunto.

69

Matemáticas Discretas: Conjuntos, relaciones y funciones

Resumen  Una relación se define como un

subconjunto del producto cartesiano de conjuntos.

 Función: entrada = salida única  Tanto las funciones como las relaciones

poseen propiedades.

 Existen funciones importantes para la

computación.

70

Matemáticas Discretas: Conjuntos, relaciones y funciones

35

26/02/2014

Referencias  Brena, Ramón F. Autómatas y Lenguajes. E-book. 2003.  Grimaldi, Ralph P. Matemáticas Discreta y Combinatoria:

Una Introducción con Aplicaciones. Addison Wesley Longman, México, 1997.  Jiménez Murillo, José A. Matemáticas para la computación.

Alfaomega, México, 2009.

71

Matemáticas Discretas: Conjuntos, relaciones y funciones

36