producto cartesiano relaciones binarias. producto cartesiano el producto cartesiano de dos conjuntos...

PRODUCTO CARTESIANORELACIONES BINARIAS

Producto Cartesiano

• El producto cartesiano de dos conjuntos A y B, denotado A × B, es el conjunto de todos los posibles pares ordenados cuyo primer componente es un elemento de A y el segundo componente es un elemento de B.

A × B = { (x,y) / x A ^ y B }

Producto Cartesiano

• Ejemplo: Si A = { a , b , c } y B = { 1 , 2 } AxB = { (a,1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2) }

Note que A tiene 3 elementos

B tiene 2 elementos A x B tiene 6 elementos.

Producto Cartesiano• Ejemplo: A = { corazón, trébol, coco, espada }

B = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }

A x B = { (corazón, 1), (corazón,2),…,(corazón,12), (trébol,1), (trébol,2), …,(trébol,12), …,(espada,12) }

Note que A tiene 4 elementos B tiene 12 elementos A x B tiene 48 elementos (todas las cartas del mazo)

Producto CartesianoRepresentación en forma de Tabla

• Ejemplo: A = { , } B = { , , }

Producto CartesianoRepresentación en forma de Diagrama

• Ejemplo: A = { , } B = { , , }

Producto Cartesiano

• Ejemplo: A = { , } B = { , , }

Gráfico cartesiano• Dados los conjuntos A = { 1 , 2 } y B = { 1 , 2 , 3 } el gráfico cartesiano de A x B es:

La primera componente de cada

elemento del producto cartesiano es la

abscisa

La segunda componente de cada

elemento del producto cartesiano es la

ordenada

Ejercicio : indicar el gráfico cartesiano de A x B donde

A = { x / x R –1 x 1 } B = R

Ejercicio : indicar el gráfico cartesiano de A x B donde

A = { x / x R 2 x < 5 }B = { x / x R 1 < x 3}

Relación entre elementos de conjuntos

• Hay casos en que no todos los pares ordenados de un producto cartesiano de dos conjuntos responden a una condición dada.

Relación entre elementos de conjuntos

• Se llama relación entre los conjuntos A y B a un subconjunto del producto cartesiano A x B.

• Este puede estar formado por un solo par ordenado, varios o todos los que forman parte de A x B.

Relaciones• Dado el siguiente diagrama que relaciona los

elementos de A con los de B

b está relacionado

con 1

3 es el correspondiente

de d

Conjuntos de salida y de llegada de un relación

• A es el conjunto de salida y B es el conjunto de llegada

Dominio de una relación

• Dom(R) = x / xA (x,y) R

Dom(R) = {b, c, d}

Imagen de una relación

• Im(R) = y / yB (x,y) R

Im(R) = {1, 3, 4}

Notación• Si R es una relación entre A y B , la expresión x R y

significa que (x,y) R , o sea, que x está relacionado con y por la relación R.

• Ej: b R 1 porque (b,1) R

Relación definida en un conjunto

• Cuando los conjuntos de partida y de llegada de una relación R son el mismo conjunto A, decimos que R es una relación definida en A, o, simplemente, una relación en A.

• Una relación R en A es entonces un subconjunto de A2 = A x A

Relación definida en un conjunto

• Ejemplo:

Sea H = { x / x es un ser humano} y R la relación “es madre de” – R es una relación en H. Por qué?– Como Ana es la madre de Luis, decimos que el par

(Ana,Luis) R.– Note que los pares que verifiquen R son un

subconjunto de H x H.

Propiedades de las relaciones definidas en un conjunto

• Si establecemos una relación entre los elementos de un mismo conjunto, existen cinco propiedades fundamentales que pueden cumplirse en esa relación

• Propiedad reflexiva

• Propiedad simétrica

• Propiedad asimétrica

• Propiedad antisimétrica

• Propiedad transitiva

Propiedad reflexiva

• La propiedad reflexiva dice que todos los elementos de un conjunto están relacionados con si mismo

R es reflexiva si para todo x A, el par (x,x) R

Propiedad simétrica• La propiedad simétrica dice que si un elemento está

relacionado con otro, éste segundo también está relacionado con el primero

R es simétrica si siempre que un par (x,y) R, el par (y,x) también pertenece a R

Propiedad Simétrica

• Ejemplo– Dado A = {3, 4, 2} decir si las siguientes relaciones

en A2 son simétricas

R = {(2, 3), (3, 4), (4, 3), (3, 2), (4, 4)}

S = {(3, 2), (4, 3), (2, 2), (3, 4)}

Propiedad asimétrica• Una relación es asimétrica si ningún par

ordenado de la relación cumple la propiedad simétrica.

Propiedad antisimétrica• Una relación es

antisimétrica cuando sólo cumplen la propiedad simétrica los pares de elementos iguales y no la cumplen los pares formados por distintos elementos.

Propiedad antisimétrica

• Ejemplo– Dado A = {2, 4, 6} decir si las siguientes relaciones

en A2 son antisimétricas

R = {(2, 2), (4, 4)}

S = {(2, 4)}

T ={(4, 6), (2, 2), (6, 4), (4, 2)}

Propiedad transitiva• La propiedad transitiva dice que si un elemento está

relacionado con otro y éste está a su vez relacionado con un tercero, el primer elemento está relacionado con el tercero.

R es transitiva si x , y ,z , (x,y) R (y,z) R (x,z) R

Propiedad transitiva

• Ejemplo– Dado A = {2, 4, 6, 3} decir si las siguientes

relaciones en A2 son transitivas

R = {(2, 2), (2, 3), (4, 6), (6, 2), (4, 2), (4, 3), (6, 3)}

S = {(2, 2), (4, 4), (4, 2), (2, 6), (6, 4), (6, 2)}

Ejercicio

• Dado A = {1, 2, 3} decir a que tipo pertenecen las siguientes relaciones

– R1 = {(1, 1), (2, 1), (2, 2), (3, 2), (2, 3), (3, 3)}.

– R2 = {(1, 1)}.

– R3 = {(1, 2)}.

– R4 = {(1, 1), (2, 3), (3, 2)}.

Ejercicio

• Sea A = {2, 3, 4, 5, 6}

R = {(x, y) / xA, yA, | x – y | es divisible por 3}

• Escribir por extensión a R.

Relación de equivalencia• Permite marcar características similares entre los

elementos de un conjunto

Ejemplo de Relación de Equivalencia

• Sea H el conjunto formado por todos los seres humanos.

R= {(x, y) / x,y H ^ "x es compatriota de y"}

– R es reflexiva puesto que toda persona es compatriota de si mismo.

– R es simétrica, puesto que "si x es compatriota de y, y es compatriota de x".

– R es transitiva, por que "si x es compatriota de y e y es compatriota de z, entonces x es compatriota de z".

Ejemplo de Relación de Equivalencia

• Sea H el conjunto formado por todos los seres humanos.

R= {(x, y) / x,y H ^ "x es compatriota de y"}

– Dado un elemento a de H, su clase de equivalencia estará formada por sus compatriotas.

– El conjunto cociente de H por R, H/R, es el conjunto formado por todas las clases de equivalencias.

– H/R es una partición de H.

Ejercicio

• ¿ Cuál de las siguientes relaciones en S son de equivalencia?

– R = {(a, b)/ a y b tienen la misma madre}, donde S = {a / a es cualquier persona}

– S es el conjunto de números enteros y R es la relación “x es congruente con y módulo 2”, es decir, que x e y tienen el mismo resto al ser divididos por 2.