RELACIONES

Parte 2

Karim Guevara Puente de la Vega

 • Tipos de relaciones
Propiedades de cerradura
Agenda
•

• Relaciones de equivalencia
• Relaciones de orden parcial
• Diagrama de Hasse

Fuente: Lipschutz S. Matemáticas Discretas. 3ra. Ed. 2009.

Tipos de Relaciones

1 2 3 4
Reflexiva Simétrica Antisimétrica Transitiva
Relaciones Reflexivas

Una relación R sobre un conjunto A es:

v Reflexiva, si para toda a ∈ A, el par (a, a) ∈ R
v No es reflexiva, si existe a ∈ A tal que (a,a) ∉
R

Ejemplo: Sean A = {1, 2, 3, 4}

R = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}
S = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
Q=AxA
 Relaciones Simétricas

Una relación R sobre un conjunto A es:

v Simétrica, si siempre que (a, b) ∈ R,
entonces (b, a) ∈ R
v No es simétrica, si existe a, b ∈ A tales
que (a, b) ∈ R pero (b,a) ∉ R

Ejemplo: Sean A = {1, 2, 3, 4}

R = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}
S = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
Q=AxA
Relaciones Antisimétricas
Una relación R sobre un conjunto A es
v an4simétrica siempre que aRb y bRa
entonces a = b; es decir, si a ̸= b y aRb,
entonces bR̸ a.
v No es an4simétrica si existen elementos
disGntos a y b en A tales que aRb y bRa.

Ejemplo: Sean A = {1, 2, 3, 4}

R = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}
S = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
Q=AxA
 q Las propiedades de simetría y antisimetría no
son negaciones entre sí.

Relaciones
Ejemplo: Sean A = {1, 2, 3, 4}
R = {(1, 3), (3, 2), (2, 3)} ?
S = {(1, 1), (2, 2)} ?
Relaciones Transitivas

Una relación R sobre un conjunto A

es
v Transitiva si siempre que (a, b), (b,
c) ∈ R entonces (a, c) ∈ R.
v No es transitiva si existe a,b,c ∈ A
tal que (a,b), (b, c) ∈ R pero (a, c) ∉ Ejemplo: Sean A = {1, 2, 3, 4}
R. R = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}
S = {(1, 3), (2, 1)}
Q=AxA
Potencias de la relación R
Ejemplo: Sean A = {a, b, c, d}
R = {(a, a), (b, a), (c, b), (d, c)}
Encontrar Rn
Recuerde que para una relación R
sobre A se definio:
R2 = R o R = {(a, a), (b, a), (c, a), (d, b)}
R2 = R ◦ R
R3 = R o R2 = {(a, a), (b, a), (c, a), (d, a)}
R3 = R ◦ R2
R4 = R o R3 = {(a, a), (b, a), (c, a), (d, a)}
R4 = R ◦ R3 R4 = R3
... R5 ?
Rn = R ◦ Rn-1 Por tanto, Rn = R3
Extensión Transitiva

q Sea la relación R sobre un conjunto A, la extensión transitiva de R se denota

por R2 y es la relación sobre A tal que:
§ R2 contiene a R: R Í R2 y además,
§ Sí (a,b) Î R Ù (b,c) Î R , entonces (a,c) Î R2
v Entonces:
§ R2 denota la extensión transitiva de R
§ R3 denota la extensión transitiva de R2

Ejemplo: A={a,b,c,d} y R una relación sobre A definida como:

R = {(a,b),(b,c),(c,b),(c,d)}
entonces:
R2 = {(a,b), (a,c), (b,c), (b,b), (b,d), (c,b), (c,c), (c,d)}
Relaciones de Equivalencia
q Sea S un conjunto no vacío. Una relación R sobre S es una relación de
equivalencia si R es reflexiva, simétrica y transitiva.
q Es decir, R es un relación de equivalencia sobre S si:
1. Para toda a ∈ S, aRa

2. Si aRb, entonces bRa

3. Si aRb y bRc, entonces aRc

“Es una clasificación de objetos que de alguna manera son semejantes”

 Relaciones de Equivalencia y Particiones de un
conjunto
Sea S un conjunto no vacío. Recuerde una partición P de S es una colección {Ai} de
subconjuntos no vacíos de S con las siguientes propiedades:
1. Cada a ∈ S pertenece a algún Ai
2. Si Ai ≠ Aj entonces Ai ∩ Aj = ∅
Es decir, una partición P de S es una subdivision de S en conjuntos ajenos no vacíos.

Suponga que R es una relación de equivalencia sobre el conjunto S. Para toda a ∈

S, sea [a] el conjunto de elementos de S con los que a está relacionada bajo R:
[a] = {x | (a,x) ∈ R}
[a] : clase de equivalencia de a en S
Cualquier b ∈ [a]: representante de la clase de equivalencia
 Relaciones de Equivalencia y Particiones de un
conjunto
La colección de todas las clases de equivalencia de elementos de S bajo una
relación de equivalencia R se denomina conjunto cociente de S entre R y se
denota por S/R:
S/R = {[a] | a ∈ S}

q Teorema 2.6: sea R una relación de equivalencia sobre un conjunto S.

Entonces S/R es una partición de S. En especifico:
i. Para todo a en S, se tiene a ∈ [a].
ii. [a] = [b] si y solo si (a,b) ∈ R
iii. Si [a] ≠ [b], entonces [a] y [b] son ajenos
 Relaciones de Equivalencia y Par5ciones de un
conjunto
Ejemplo: Sea la relacion R = {(1,1), (1,2), (2,1), (2,2), (3,3)}
a) R es una relación de equivalencia?
b) Determine las clases de equivalencia.
c) Determine S/R.
d) Determine un conjunto de representantes de las clases de equivalencia.

a) Si es de equivalencia.
b) [1] = {1,2} [2] = {1, 2} [3] = {3}
c) S/R = {[1], [3]}
d) {1,3} o {2,3}
 Relaciones de Equivalencia y Particiones de un
conjunto
Ejemplo: Sea A = {a, b, c, d, e, f} y P(A) = {{a,c,e}, {b,f}, {d}} una partición de
A.
¿Cuál es la relación de equivalencia R sobre A?

R = {(a,a), (a,c), (a,e), (c,a), (c,c), (c,e), (e,a), (e,c), (e,e), (b,b), (b,f), (f,b), (f,f), (d,d)}
 Propiedades de Cerradura

q No todas las relaciones son de equivalencia, pero es posible hacer que tengan esta
propiedad agregando pares ordenados necesarios mínimos para que cumplan con
ser: reflexivas, simétricas y transitivas.

q Tipos de cerraduras:
(R)reflexiva, (R)simétrica y (R)transitiva
Cerradura reflexiva y simétrica
Recuerde que: ∆A = ∆ = {(a, a) | a ∈ A}

q Teorema 2.3: Sea R y una relación sobre un conjunto A. Entonces:

i. R ∪ ∆A es la cerradura reflexiva de R
ii. R ∪ R-1 es la cerradura simétrica de R

Ejemplo: R= {(1,1),(1,3), (2,4), (3,1), (3,3), (4,3)}, sobre el conjunto A = {1,2,3,4}

Entonces:
(R)reflexiva = R U {(2, 2), (4, 4)}
(R)simétrica = R U{(4, 2), (3, 4)}
Cerradura transitiva

Sea R una relación sobre un conjunto A. Recuerde que: Rn = R ◦ Rn-1

La cerradura transitiva se define: $
∗
𝐑 = # 𝑅𝑖
!"#

q Teorema 2.4: R* es la cerradura transitiva de R.

q Teorema 2.5: sea R una relación sobre un conjunto A con n elementos.
Entonces:
(R)transitiva = R ∪ R2 ∪ . . . ∪ Rn
Ejemplo: R= {(1,2), (2,3), (3,3)}, sobre el conjunto A = {1, 2, 3}.
Entonces
R2 = R ◦ R = {(1,3}, (2,3), (3,3)} y
R3 = R ◦ R2 = {(1,3}, (2,3), (3,3)}
En consecuencia:
(R)transitiva = {(1,2), (2,3), (3,3), (1,3)}

Observe que: (R)transitiva = R* = R ∪ R2 ∪ . . . ∪ Rn

por definición:
R ⊆ R2 ⊆ R3 ⊆. . . ⊆ Rn
Entonces:
R* = Rn
Ejemplo: Sea A = {a, b, c, d} y R una relación sobre A definida por:
R = {(a,b), (b,c), (c,b), (c,d)}

Halle la cerradura transitiva de R.

R2 = { (a,b), (a,c), (b,c), (b,b), (b,d), (c,b), (c,c), (c,d) }

R3 = { (a,b), (a,c), (a,d), (b,c), (b,b), (b,d), (c,b), (c,c), (c,d) }

Como R3 es transi(va, entonces:

R* = R3 = { (a,b), (a,c), (a,d), (b,c), (b,b), (b,d), (c,b), (c,c), (c,d) }

Ejemplo: Sea A = {a, b, c, d} y R una relación sobre A definida por:
R = {(a,b), (b,c), (c,b), (c,d)}

R R2 R3 = R*
Relaciones de Orden Parcial
q Sean A un conjunto y R una relación. Se dice que R es una relación de
orden parcial si R es reflexiva, antisimétrica y transitiva.

Relación que no es Relación de

Orden Parcial Orden Parcial
Relaciones de Orden Parcial
Ejemplo: Sea A = {1, 2, 3, 4, 5} y R una relación sobre A definida por:
R = { (1,1), (1,2), (1,3), (1,4), (1,5), (2,2), (2,3), (2,5), (3,3),
(3,5), (4,4), (4,5), (5,5)}
¿R es una relación de orden parcial sobre el conjunto A?

R 1 2 3 4 5
1 1 1 1 1 1
2 1 1 1
3 1 1
4 1 1
5 1
Conjunto parcialmente ordenado
q Un conjunto S junto con un orden parcial R se llama conjunto
parcialmente ordenado o conjunto PO (Partially Ordered) / POSET
(Partially Ordered SET)

Ejemplo: los siguientes conjuntos son de orden parcial?

a) La relación de inclusion de conjuntos
b) La relación “a divide a b” (a|b) sobre N (enteros positivos)
c) La relación “a divide a b” (a|b) sobre Z (enteros)
 q Es la representación simplificada del
Diagrama de dígrafo de un conjunto parcialmente
ordenado (PO), debido a que es
Hasse reflexiva y transitiva.

q ¿Como se elabora?
q Se eliminan las aristas reflexivas
q Se eliminar las aristas involucradas por la
propiedad transitiva
q Se eliminan las flechas de las aristas
q Se reemplazan los círculos de los nodos por
puntos.
Diagrama de Hasse
Ejemplo

v Sean el conjunto A = {1, 2, 3, 4, 12} y R un orden parcial sobre el

conjunto A definido como: R = {(a,b), tal que a|b}
Obtener el diagrama de Hasse
v Sol.
R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 12), (2, 2), (2, 4),
(2, 12), (3, 3), (3, 12), (4, 4), (4, 12), (12, 12)}
 R R {(1,R{(1,
1), 1),
{(1,(1,
(1, 2),1),2),
(1,(1,(1,
2),3),
3), (1,(1,(1,
3),4),
4), (1,4),12),
(1,(1,12), (2,
2), 2),
(1, 12),
(2, (2,(2,
(2, 2), 4),
4), (2, (2,
4), 12),
12), (2, (3, (3,
(3, 12),
3), 3), (3,
3), 12),
(3,12), (3, (4, (4,
(4, 12),
4), 4),12),
(4, (4, (4,
4), 12), (12,
(12,12), 12)}12)}
12)}(12,
AAcontinuación,
continuación, sese
A continuación, representa
se representa
representa (A,(A, ) (A, ) como
como ) como el dígrafo
el dígrafo de de
el dígrafo la
defigura
la figura 3.21.3.21.3.21.
la figura
Luego,
Luego, seseeliminan
Luego, eliminanloslos
se eliminan lazos
lazoslos del del
lazos dígrafo
del
dígrafo dígrafo (véase
(véase (véasefigura
figura 3.22).
figura
3.22). 3.22).
AAcontinuación,
continuación, sese
A continuación, eliminan laslas
se eliminan
eliminan aristas
dedeloslos
las aristas
aristas de elementos (a, (a,
los elementos
elementos (a,que
c)
c) que están
que
c)están involucradas
están porpor
involucradas
involucradas la propiedad
la por la propiedad
propiedad transitiva
transitiva
transitiva
3.23).3.23). R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 12), (2, 2), (2, 4),
del
Ejemplo
deldígrafo
dígrafo
Enseguida,
(véase
del dígrafo
(véase
seseredibuja
Enseguida,
Enseguida,
figura
(véase
figura
redibuja
figura
3.23).
el el
se redibuja dígrafo para
el dígrafo
dígrafo para queque
para todas
que
todas (2,las
todas
las 12),
aristas(3,apunten
las aristas
aristas apunten3), (3,hacia
apunten
hacia 12), (4,
arriba
hacia
arriba 4),(véase
(véase
arriba
(véase (4,figura
figura 12), (12,
3.24). 12)}
3.24).
figura
3.24).
Luego,
Luego, seseeliminan
Luego, eliminan laslas
se eliminan flechas dede
las flechas
flechas laslas
de aristas (véase
las aristas
aristas (véase figura
(véase
figura 3.25).
figura
3.25). 3.25).
Porúltimo,
Por último,sese
Por último,reemplazan
reemplazan loslos
se reemplazan círculos
porpor
los círculos
círculos puntos
por
puntos y ely diagrama
puntos elydiagramade de
el diagrama Hasse
de
Hasse queda
Hasse
queda listolisto
queda (véase
listo
(véase figura
(véase
figura 3.26).
figura
3.26). 3.26).

3 3 3 4 3 3 3 4 4
3 3 3 4 4 4
4 4 4

2 2 2 2 2 2 2 2 2

12 12 12 12 12 12 12 12 12

1 1 1
1 1 1 1 1 1

Figura
FiguraFigura
3.21 3.21 Representación
3.21Representación
Representación deldel del ordenFigura
orden
orden Figura
3.22
Figura 3.223.22 Eliminación
Eliminación de lazos.
de lazos.
Eliminación de lazos. FiguraFigura
3.233.23
Figura 3.23 Eliminación
Eliminación de los
Eliminación dedeloslos
parcial parcial
como
parcial como como dígrafo.
dígrafo.
dígrafo. elementos
elementos
elementos transitivos
transitivos (a, c).(a, (a,
transitivos c). c).
Por último, se reemplazan los círculos por puntos y el diagrama de Hasse queda listo (véase figura 3.26).
2 2 2
2 2 3 2 24 3 4 2 2
3 4
12 12 12
12 12 12 12
12 12

Ejemplo
2 2 2
1
1 1 12 12 1 12 1
1 1 1 1

1
Figura 3.21
Figura Representación
3.21 Representación del orden
del orden
1
Figura
Figura 3.22
3.22 Eliminación
Figura 3.22 Eliminación de lazos.lazos.
Eliminación
1
de de lazos. Figura Figura
Figura
3.23 3.23
3.23 Eliminación
Eliminación
Eliminación de losde los
de los
Figura 3.21 Representación del orden
parcial como
parcial
parcial dígrafo.
como dígrafo. elementos
elementos
Figura 3.23 Eliminación de los elementos
transitivos
(a, c).(a, c). (a, c).
transitivos
transitivos
Figura 3.21 como dígrafo.
Representación del orden Figura 3.22 Eliminación de lazos.
parcial como dígrafo. elementos transitivos (a, c).

12 12 12 12 12 12
12 12 12 12 1212

4 4
44 4 4 44
4

2
4 4
2
3 4
2 2 3 3
2 2 2
2 3 3
2
3
3 3 3 3
1 2 2
1 3 1 3 2
Figura 3.26 Mediante el reemplazo
Figura 3.24 Redibujando el grafo para Figura 3.25 Eliminación de flechas. de círculos por puntos el diagrama
que las aristas apunten hacia arriba. de Hasse queda listo. 1 1
1 1 1 1
1 www.full-ebook.com 1 Figura 3.26 3.26
Figura Mediante el reemplazo
Mediante el reemplazo
1

Figura 3.243.24
Figura Redibujando el grafo
Redibujando para para Figura
el grafo 3.25 3.25
Figura Eliminación de flechas.
Eliminación de flechas. de círculos por puntos
de círculos
Figura 3.26 el diagrama
por puntos el diagrama
Mediante el reemplazo