Trabajo Práctico 5: Relaciones Matemática Discreta

1. a) Sea A  1,2,3 , B  2,3,4,7 y C  a, b, c . Halle A x A , B x C y (A  B) x C

b) Sean X e Y conjuntos. Si X tiene n elementos e Y tiene m elementos, ¿cuántos elementos tiene
Xx Y?
c) Si A es un conjunto de n elementos y B es un conjunto de m elementos, ¿cuántas relaciones se
podrían definir de A en B?

2. a) Si se considera el conjunto Z de los números enteros y la relación R  Z x Z dada por x R y si y sólo

y es múltiplo de x (es decir, existe k  Z tal que y = kx) ¿cuáles de los siguientes pares (x, y)
verifican (x, y)  R ?
i) (2, 9) ii) (11, -121) iii) (24, 28) iv) (-9, 0)

b) En el conjunto N de los números naturales se define la relación S como x S y si y sólo si x  y  2 .

Indicar cuatro pares (x, y) pertenecientes a S.

3. Para cada una de las relaciones de A en B que se dan a continuación, represéntela en un sistema de
coordenadas cartesianas, indique su dominio, su conjunto imagen y su conjunto gráfico (conjunto de
pares ordenados). Halle la relación inversa y represéntela en un sistema de coordenadas cartesianas,
indique su dominio y conjunto imagen.

A  1,2,3,4,5 B  4,5,6,7

a) xRy si y sólo si x < y

b) (x, y)  R si y sólo si 2x  y  6
c) d)

e)

4. Sea A  1,2,3,4,5,6. Grafique la relación R en A: R  (1,1),(1,3),(3,1),(5,4),(4,5),(6,6),(3,3)

a) mediante representación cartesiana
b) mediante diagrama de Venn
c) mediante matriz booleana.
Determine si R es reflexiva, simétrica, antisimétrica, transitiva. Justifique.

5. En el conjunto A  a, b, c, dse define la relación S  (a, b), (a, c), (b, b), ((b, d), (d, d), (c, a), (b, a) .
a) Represéntela S utilizando una matriz booleana. Indique dominio y conjunto imagen de la relación.
b) Determine si S es reflexiva, simétrica, antisimétrica, transitiva. Justificar.

1
Trabajo Práctico 5: Relaciones Matemática Discreta

6. Sea el conjunto A  1,2,3 . Dé en cada caso un ejemplo de una relación definida en A que sea:
a) reflexiva y transitiva pero no simétrica
b) simétrica y transitiva pero no reflexiva
c) simétrica y antisimétrica
d) reflexiva pero no simétrica ni tampoco antisimétrica
e) de equivalencia
f) de orden.

7. Para cada una de las siguientes relaciones analice si son o no relaciones de equivalencia y/o de orden en
A:
a) A  a, b, c, d; R  (a, a), (c, c), (b, b)(d, d) 
b) A  1,2,3,4 ; R la relación definida por la matriz booleana

c) A = Z (conjunto de números enteros); (x, y)  R si y sólo si x2 = y2

d) A = R (conjunto de números reales); x S y si y sólo si x  y  1
e) A = P(U) conjunto de partes de U, siendo U  1,2,3 ; x R y si y sólo si XY
f) A  1,2,3,4 ; T la relación definida por

g) A = Z; (x, y)  R si y sólo si x - y es múltiplo de tres.

h) A = N ; (x ; y)  R si y sólo si x  y

8. Sean R y S dos relaciones definidas en un conjunto A. Analice el valor de verdad de los siguientes
enunciados. Justifique.
a) Si R es reflexiva, entonces R -1 es reflexiva.
b) Si R es simétrica, entonces R -1 es simétrica.
c) Si R y S son transitivas, entonces R  S es transitiva.
d) Si R y S son simétricas, entonces R  S es simétrica.

9. a) Si R es una relación de equivalencia en A, ¿es también R -1 relación de equivalencia?

b) Si S es una relación de orden en A, ¿es también S -1 relación de orden en A? Justificar.

10. Sea A  1,2,3,4,5 y la relación de equivalencia en A,

R  (1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)
a) Represente en un diagrama de Venn.
b) Indique las clases de equivalencia de cada elemento de A. ¿Cuántas clases de equivalencia distintas
hay?
c) Indique la partición que queda determinada en A.

2
Trabajo Práctico 5: Relaciones Matemática Discreta

11. Sea A  1,2,4,5,9 y sea S la relación en A / S  (1,1);(2,2),(4,2),(2,9),(9,9)

a) Agregue a S la menor cantidad posible de pares ordenados para que resulte una relación de
equivalencia en A.
b) Para esta nueva relación obtenida en el ítem a), determine las clases de equivalencia y la partición
que queda inducida sobre A.

12. Sea A = {2, 3, 4, 5, 7, 10} y sea R la relación definida en A tal que

R = {(2 , 4) ; (3 ; 5) ; (5 , 7) ; (10 , 10) ; (3 , 3)}
a) Agregue a R la menor cantidad posible de pares ordenados para formar una relación S de modo tal
que S resulte una relación de equivalencia en A.
b) Para la relación S, determine las clases de equivalencia y la partición que queda inducida sobre A.

13. Si el diagrama indica la partición inducida en el conjunto A  0,1,2,4,5,6,7 por una relación de
equivalencia, determine el conjunto gráfico de dicha relación y represéntelo en un sistema de ejes
cartesianos.

14. Si en el conjunto de todas las proposiciones se define la relación p R q si y sólo si p es lógicamente

equivalente a q, ¿es ésta una relación de equivalencia?

15. Se define en el conjunto de números enteros la relación R dada por:

 x , y  : x R y si y sólo si x2  y2 es múltiplo de 5.
a) Probar que R es una relación de equivalencia en .
b) Decidir si las siguientes afirmaciones son verdaderas o falsas, justificando adecuadamente en cada
caso:
i. cl(5)  cl(2)  
ii. cl (15)  cl(  2)

16. Sea B= {a, b, c, d} y sea S la siguiente relación definida en B: S={(b,b),(b,c),(c,a),(b,d)}.

a) Complete S con la menor cantidad posible de pares ordenados para convertirla en una relación S´ de
manera tal que S` sea una relación de orden en B.
b) Represente S´ mediante un diagrama de Hasse. Indique elementos maximales y minimales.

17. Sea A = { 3, 5, 7, 9, 11}. Se define en A la siguiente relación R.

R = { (3; 3), (5; 5), (9; 11), (3; 5) ; (11; 11) ; (5 ; 7) ; (7 ; 7)}
a) Halle dominio e imagen de la relación.
b) Analice si R es una relación de orden y/o de equivalencia. Justificar.

3
Trabajo Práctico 5: Relaciones Matemática Discreta

c) Si R no es de orden, agregue a R la mínima cantidad de pares posibles para formar una relación S de
manera tal que S sea una relación de orden. Para esta nueva relación S, realice el diagrama de Hasse
y determine elementos maximales y minimales.

18. Sea A el conjunto formado por los divisores positivos de 12. Se define en A la relación R / x R y si y sólo si
y es múltiplo de x
a) Pruebe que R es una relación de orden en A
b) Realice el diagrama de Hasse correspondiente a R.
c) Indique elementos minimales y maximales.

19. Sea A  a, b, c. Se define en P(A) la relación de inclusión, es decir X S Y si y sólo si X  Y .
a) Pruebe que S es relación de orden en P(A).
b) Realice el diagrama de Hasse correspondiente a S.
c) Indique elementos minimales y maximales.

20. Sea (B, + , . , - , 0, 1) un álgebra de Boole. Se define en B la relación “  “ dada por

 x, y  B : ( x  y  x.y = x).
Demuestre que “  ” es una relación de orden en B.

21. Describa los pares ordenados de la relación de orden determinada por el diagrama de Hasse en el
conjunto A. Indicar si el orden es total o parcial.

a) A  1,2,3,4 b) A  1,2,3,4

c) A = {1, 2, 3, 4, 5, 6}

4
Trabajo Práctico 5: Relaciones Matemática Discreta

22. En el conjunto A  a1, a2 , a3 , a4  sean S y T las relaciones definidas por las matrices:

1 0 0 0 0 0 0 0
   
0 1 0 0 1 0 0 0
MS   MT  
1 0 0 0 0 1 1 1
   
1 0 0 0 0 0 0 1
Halle R  S  T y determine si es una relación de orden o de equivalencia. En caso que sea de
orden grafique su diagrama de Hasse y si es de equivalencia dar las clases.

Algunos ejercicios resueltos

Ejercicio 7, ítem g) Analizar si l siguiente relación es de orden y/o de equivalencia en A:

A = Z; (x, y)  R si y sólo si x - y es múltiplo de tres.

De acuerdo a la definición de la relación R, sabemos que un par (x ; y) pertenece a la relación si x - y = 3k, con
k  Z. Veamos que propiedades cumple la relación:

- R es reflexiva: el par (x ; x )  R dado que x - x = 0 res múltiplo de tres ( 0 = 3. 0, 0  Z)

- R es simétrica: si e par (x ; y)  R, entonces x - y = 3k, con k  Z. Luego, multiplicando ambos lados de la
igualdad por -1, se tiene que y - x = 3. (-k), -k  Z (dado que k es un entero).
- R es transitiva: supongamos que los pares (x ; y) , (y ; z) pertenecen a la relación R. Entonces tenemos que:

 x - y = 3.k1 , con k1  Z (pues (x ; y)  R)

 y - z = 3k2, con k2  Z (pues (y ; z)  R)

Sumando miembro a miembro, resulta que x - z = 3 (k1 + k2) . Llamando k = k1 + k2, tenemos que x - z = 3k, con
k  Z. Luego (x ; z)  R por lo que la relación dada es transitiva.

- R no es antisimétrica: basta un contraejemplo para demostrarlo. El par (3 ; -3)  R (pues 3 - (-3) = 6 es

múltiplo de tres) y el par (-3 ; 3)  R (dado que -3-3 = -6 es múltiplo de tres). Pero 3  -3.

Luego, la relación R es reflexiva, simétrica y transitiva. Se trata entonces de una relación de equivalencia.

Ejercicio 12: Sea A = {2, 3, 4, 5, 7, 10} y sea R la relación definida en A tal que
R = {(2 , 4) ; (3 ; 5) ; (5 , 7) ; (10 , 10) ; (3 , 3)}
a) Agregue a R la menor cantidad posible de pares ordenados para formar una relación S de modo tal
que S resulte una relación de equivalencia en A.
b) Para la relación S, determine las clases de equivalencia y la partición que queda inducida sobre A.

a) Para transformar la relación R en una relación S de modo tal que S resulte de equivalencia, tenemos que
asegurarnos que se verifiquen las siguientes propiedades:

 Reflexividad:  x  A : (x ; x )  S
Para que se cumpla esta propiedad, tenemos que agregar los pares (2 ; 2) , (4 ; 4), (5 ; 5) (7 ; 7).

5
Trabajo Práctico 5: Relaciones Matemática Discreta

 Simetría:  x , y  A : (x ; y)  S  (y; x)  S
Dado que el par (2, 4) pertenece a la relación R, para que se verifique la simetría tenemos que agregar
el par (4 ,2). Siguiendo un razonamiento análogo, tenemos que agregar los pares (5 , 3) y (7, 5).

 Transitividad:  x , y , z  A : (x ; y)  S  (y ; z)  S   ( x , z )  S 
Dado que (3, 5)  R , ( 5 , 7)  R para que se verifique la transitividad tendríamos que agregar el par
(3 , 7). Pero hay que tener cuidado, porque no tenemos que olvidar que la relación S que estamos
construyendo es simétrica por lo que también resulta necesario agregar el par (7, 3).

Si tenemos en cuenta que el par (5, 3)  S y el par (3, 7)  S, para que se verifique la transitividad
tendríamos que agregar el par (5, 7). No lo hacemos pues este par pertenece a la relación R. En este
caso, no es necesario agregar el par (7, 5) porque ya pertenece a la relación S.

Por último, dado que el par (7, 5)  S y el par (5, 3)  S, tendríamos que agregar el par (7, 3) (que lo
hicimos anteriormente)

En conclusión, la relación S resulta la siguiente:

S = {(2 , 4) ; (3 , 5) ; (5 , 7) ; (10 , 10) ; (3 , 3) ; (2 , 2) ; (4 , 4); (5 , 5); (7 , 7); (4, 2) ; (5, 3) ; (7 , 5) ; (3 , 7) ;

(7, 3)}

b) Por definición, la clase del elemento 2 está formada por los elementos de A que se relacionan con el 2
a través de la relación S. Es decir, cl(2)  [ 2 ]   x  A / x S 2
En este caso, cl (2) = { 2, 4}. Notemos que la clase del elemento dos es igual a la clase del elemento
cuatro.
Análogamente, cl(3)   x  A / x S 3 = {3, 5, 7} = cl(5) = cl(7). Por último, cl(10) = {10}
La partición que induce la relación S, determinada a partir de las distintas clases de equivalencia, es la
siguiente:

Ejercicio 18 Sea A el conjunto formado por los divisores positivos de 12. Se define en A la relación R / x R y si
y sólo si y es múltiplo de x
a) Pruebe que R es una relación de orden en A
b) Realice el diagrama de Hasse correspondiente a R.
c) Indique elementos minimales y maximales.

6
Trabajo Práctico 5: Relaciones Matemática Discreta

El conjunto A, formado por los divisores positivos de 12, es el siguiente: A = { 1, 2, 3, 4, 6, 12}. Tenemos que
demostrar que la relación R dada por x R y si y sólo si y es múltiplo de x, es decir, y = kx, k  N (consideramos
el conjunto de los naturales porque trabajamos con los divisores positivos de 12) es una relación de orden en
A.

 R es reflexiva:  x  A : x R x pues x es múltiplo de x ( x = 1.x, 1  N)

 R es antisimétrica:  x, y  A :   x R y  y R x   x  y 
Sean x, y pertenecientes al conjunto A tales que x R y e y R x:
- Como x R y, entonces y es múltiplo de x. Es decir, y = k1x, con k1  N
- Como y R x, entonces x es múltiplo de y. Es decir, x = k2y, con k2  N.
Luego, teniendo en cuenta ambas igualdades, llegamos a que y = k1x = k1(k2y). Es decir, y = k1k2y. Para
que esta última igualdad se verifique, necesariamente tiene que ser k1.k2 = 1. Y, dado que tanto k1 como
k2 son números naturales, la única posibilidad para que el producto entre ellos sea igual a uno es que
ambos sean iguales a uno: es decir, k1 = k2 = 1.

Por lo tanto, dado que y = k1x tenemos que y = 1.x  y = x, que es lo que queríamos demostrar.

* R es transitiva:  x , y , z  A :  x R y  y R z   x R z 
SI x R y, entonces y = k1x, k1  N. De la misma manera, si y R z, tenemos que z = k2y, con k2  N.
Por lo tanto:
z = k2y = k2 (k1x) = (k2 k1 )x

Llamando k = k2 k1 tenemos que k  N (pues el producto de dos números naturales) y z = kx, k  N por lo
que x R z como queríamos probar.

b) Para construir el diagrama de Hasse correspondiente, es útil tener en cuenta las siguientes cuestiones:

- El “1” se relaciona con todos los elementos del conjunto A, dado que cualquier número es múltiplo de
1. Por esta razón, el 1 lo ubicaremos en la parte inferior de nuestro diagrama.

- Todos los elementos del conjunto A se relacionan con 12 (12 es múltiplo de todos los elementos del
conjunto). Por esta razón, lo ubicaremos en la parte superior del diagrama.

- Como sabemos que la relación es de orden, ya conocemos que es reflexiva, por lo que no se realizan
“bucles”

- Algunos pares de la relación son (2 ; 4), (2, 6), (3, 6)

El diagrama nos quedaría de la siguiente manera:

7
Trabajo Práctico 5: Relaciones Matemática Discreta

A partir del diagrama, podemos identificar elementos maximles y minimales:

 Elementos maximales: {12}
 Elementos minimales: {1}

Ejercicio 21, ítem a) Describa los pares ordenados de la relación de orden determinada por el diagrama
de Hasse en el conjunto A. Indicar si el orden es total o parcial.

A  1,2,3,4

El diagrama de Hasse se define sólo para las relaciones de orden. Por lo tanto ya sabemos que la relación es
reflexiva, antisimétrica y transitiva. Para poder reconstruir los pares ordenaados de la relación, tenemos que
tener en cuenta que el diagrama se lee “de abajo hacia arriba”. Vayamos por partes:

 Los pares (1, 1) ; (2, 2) ; (3, 3) y (4 ; 4) pertenecen a la relación por ser reflexiva.
 Como (1, 3)  R (hay un segmento del 1 hacia el 3) y (3 4)  R, por la transitividad tenemos que (1, 4)
 R.
 Análogamente, como (2, 3)  R y (3, 4)  R por la transitividad tenemos que (2, 4)  R

Luego, los pares ordenados de la relación son:

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

El orden es parcial: si tomamos los elementos 1 y 2, (1, 2)  R y (2, 1)  R.