GuíaCompl 2-Relaciones

Matemática Discreta
Guı́a complementaria 2: Relaciones

12 marzo 2024
Problema 1: Considere el conjunto A = {1, 2, 3, 4, 5, 6} de enteros positivos y la relación R sobre el mismo

conjunto. ¿Qué pares ordenados están en la relación R = {(a, b) | a divide a b}?
a) Encuentre el dominio y la imagen de esta relación;
b) represente esta relación en forma de diagrama sagital; en forma de tabla relacional, indicando con una
cruz los pares que están relacionados;
c) en un diagrama cartesiano, esto es, considere el conjunto A × A e indique con puntos los pares rela-
cionados y construya la matriz relacional.
Recuerde: la matriz relacional, también conocida como matriz booleana se define como: MR = [mij ],
donde: (
1 si (ai , bj ) ∈ R
mij =
0 si (ai , bj ) ∈
/R
Esto representa un arreglo en general rectangular de 0′ s y 1′ s dispuestos en una tabla de dimensión
n × m (con n, m ∈ N) donde n es el número de filas y m es el número de columnas del arreglo
rectangular.
Problema 2: ¿Cuántas relaciones hay en un conjunto de n elementos?

Problema 3: Considere las siguientes relaciones en el conjunto X = {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.
a) Encuentre el dominio e imagen de cada una.
b) Indique cuáles de entre las relaciones dadas son: reflexivas, simétricas y cuáles antisimétricas y tran-
sitivas.
c) Para aquellas relaciones reflexivas, simétricas, antisimétricas y transitivas, represente cada una en un
diagrama cartesiano X × X y construya la matriz relacional, ¿qué conclusión puede extraer de los
diagramas y de cada matriz?
Problema 4: Dado los conjuntos X = {a1 , a2 , a3 } y Y = {b1 , b2 , b3 , b4 , b5 }, ¿Qué pares ordenados están en
la relación R representada por la matriz rectangular MR de dimensión 3 × 5?
 
0 1 0 0 0
MR = 1 0 1 1 0
 
1 0 1 0 1
1
Problema 5: La matriz de una relación en un conjunto, que es cuadrada, es decir, de dimensión n × n
(con n ∈ N), puede usarse para determinar si la relación cumple o no con ciertas propiedades, como son:
reflexiva, (anti)-simétrica.
a) De acuerdo a las definiciones de estas propiedades, indique cómo se distribuyen los ceros (0) y unos (1)
respecto de la diagonal principal de la matriz MR que representa a la relación R.
Ayuda: Consulte el problema 3.c).
 
□  
1 1 0
 □ 
a) MR =   b) MS = 1 1 1
 □ 
0 1 1
□
b) ¿Qué propiedades tiene la relación S representada por la matriz dada en b)?
Problema 6: Considere la relación ((divide a)) en el conjunto de los Z+ . Discuta si esta relación es reflexiva,
simétrica, antisimétrica, transitiva. Recuerde que en los enteros, x|y si existe z ∈ Z : y = z · x.
Problema 7: Sea R : A → B. Definimos en clase que la relación inversa de B a A como R−1 : B → A =
{(b, a) | (a, b) ∈ R}. Definimos ahora la relación complementaria como:
R = {(a, b) | (a, b) ∈
/ R}.
a) Encuentre la relación inversa y complementaria de algunas relaciones dadas en el Problema 3.

b) Considere las siguientes relaciones: R = {(a, b) ∈ Z2 | a < b} y S = {(a, b) ∈ Z+ × Z+ | a divide a b}.
Hallar la relación inversa y complementaria de cada una.
Problema 8: Considere los conjuntos A = {1, 2, 3} y B = {1, 2, 3, 4} y las siguientes relaciones:

R1 = {(1, 1), (2, 2), (3, 3)} y R2 = {(1, 1), (1, 2), (1, 3), (1, 4)}.
Encuentre: a) R1 ∪ R2 . b) R1 ∩ R2 . c) R1 − R2 . d) R2 − R1 .
Problema 9: Encontrar la composición de las relaciones R◦S. Donde R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)}
relaciona los conjuntos {1, 2, 3} → {1, 2, 3, 4} y S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)} relaciona los conjuntos
{1, 2, 3, 4} → {0, 1, 2}.
Problema 10: Sea la relación R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Hállense las potencias Rn , n = 2, 3, 4, . . . .
Problema 11: Composición de la relación de paternidad consigo misma. Sea R la relación en el conjunto
de todas las personas tal que (a, b) ∈ R si la persona a es padre o madre de la persona b. Construya la
relación R2 = R ◦ R e interprete su significado.
Un grafo dirigido o dı́grafo, consta de un conjunto V de vértices (o nodos) junto con un conjunto E de
pares ordenados de elementos de V llamados aristas (o arcos). Al vértice a se le llama vértice inicial de la
arista (a, b), y al vértice b se le llama vértice final de esta arista. Una arista de la forma (a, a) se representa
usando un arco que conecta el vértice a consigo mismo, y recibe el nombre de bucle.
Una relación R en un conjunto A se puede representar por un grafo dirigido que tendrá por vértices a los
elementos de A y por aristas los pares ordenados (a, b) tales que (a, b) ∈ R. Esta asignación establece un
idea y vuelta entre las relaciones en un conjunto de A y los grafos dirigidos cuyo conjunto de vértices es A.
De este modo, cada afirmación acerca de las relaciones se corresponden con una afirmación acerca de grafos
dirigidos, y viceversa. Estos grafos ofrecen información de manera visual de las relaciones. Las relaciones de
un conjunto A en un conjunto B se pueden representar mediante un grafo dirigido con un vértice por cada
elemento de A y otro vértice por cada elemento de B.
Problema 12: El grafo dirigido mostrado en la figura, representa una relación R en un conjunto A =
{a, b, c, d}.
2
a) ¿Cuántos vértices y aristas tiene el grafo?
b) Escriba la relación R.
Problema 13: Identifique las siguientes relaciones construidas sobre el conjunto A (indique los elementos
de A) con sus correspondientes grafos.
R1 = {(1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), (4, 3)}
R2 = {(1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 1)}
Problema 14: Determine si las relaciones R y S asociadas a los grafos dirigidos mostrados en la figura
siguiente son reflexivas, simétricas, antisimétricas y/o transitivas.
Problema 15: Considere la siguiente partición de un conjunto A generada por una relación de equivalencia
R: A = {{1, 7}, {2, 3, 4}, {5, 6}}. Encuentre la relación R y el espacio cociente A/R.
Problema 16: ¿Cuáles de estas colecciones de subconjuntos son particiones de {1, 2, 3, 4, 5, 6}? Para
aquellos casos afirmativos, indique por extensión la relación R y el espacio cociente.
a) {1, 2}, {2, 3, 4}, {4, 5, 6}; c) {2, 4, 6}, {1, 3, 5};
b) {1}, {2, 3, 6}, {4}, {5}; d) {1,4,5}, {2,6}.
Problema 17: Determinar si la relación cuyo grafo dirigido se muestra en las figuras representan relaciones
de equivalencia.
3
Problema 18: Determina si las relaciones representadas por estas matrices booleanas son relaciones de
equivalencia.
Problema 19: Relación de orden. Si una relación es reflexiva, antisimétrica y transitiva, es un orden amplio
o simplemente orden. Si una relación es asimétrica y transitiva es un orden estricto. A su vez estas relaciones
pueden ser de orden total si todos los pares de elementos están relacionados o de orden parcial si hay algunos
pares sin relacionar.
a) Considere la colección de conjuntos M = {A, B, C, D, E} mostrada en la figura y las relaciones R1 =⊂

y R2 =⊆. Represente estas relaciones en forma de grafo dirigido e indique cuál de las dos es un orden
amplio y un orden estricto.
b) Considere la colección de conjuntos X = {F, G, H, I, J} mostrado en la figura y la relación ⊂. Re-

presente el grafo dirigido de esta relación y compárelo con los grafos dirigidos de las relaciones en-
contradas en a). Clasifique las relaciones ⊆ y ⊂ en los conjuntos M y X según sean de orden am-
plio/estricto/parcial/total.

GuíaCompl 2-Relaciones

Cargado por

Copyright:

Formatos disponibles

GuíaCompl 2-Relaciones

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

GuíaCompl 2-Relaciones

Cargado por

Copyright:

Formatos disponibles

Matemática Discreta

Guı́a complementaria 2: Relaciones

Problema 1: Considere el conjunto A = {1, 2, 3, 4, 5, 6} de enteros positivos y la relación R sobre el mismo

a) Encuentre el dominio y la imagen de esta relación;

Problema 2: ¿Cuántas relaciones hay en un conjunto de n elementos?

a) Encuentre el dominio e imagen de cada una.

a) Encuentre la relación inversa y complementaria de algunas relaciones dadas en el Problema 3.

Problema 8: Considere los conjuntos A = {1, 2, 3} y B = {1, 2, 3, 4} y las siguientes relaciones:

a) Considere la colección de conjuntos M = {A, B, C, D, E} mostrada en la figura y las relaciones R1 =⊂

b) Considere la colección de conjuntos X = {F, G, H, I, J} mostrado en la figura y la relación ⊂. Re-

También podría gustarte