RELACIONES BINARIAS 1

Vista previa del material en texto

TEMA: Relaciones binarias (parte 1)
Semana 4
FACULTAD DE INGENIERÍA INDUSTRIAL Y 
SISTEMAS
PAR ORDENADO
Definición.- Dados 𝐴 y 𝐵 conjuntos no vacios. Un par ordenado
consiste en dos componentes, 𝑎 ∈ 𝐴 y 𝑏 ∈ 𝐵 representado por (𝑎; 𝑏).
Igualdad de pares ordenados.
Sean 𝑎; 𝑏 = 𝑐; 𝑑 si y solo si 𝑎 = 𝑐 y 𝑏 = 𝑑
Una generalización natural es una n-upla que es conformado por 𝑛
componentes que pertenecen a 𝑛 conjuntos no vacios. Se representa 
por 
(𝑎1; 𝑎2; … ; 𝑎𝑛)
FIIS - UNI
PRODUCTO CARTESIANO
Definición.- Dados 𝐴 y 𝐵 conjuntos no vacios. El producto cartesiano 
de 𝑨 × 𝑩 consiste del conjunto
𝐴 × B ={ 𝑎; 𝑏 / 𝑎 ∈ 𝐴 ∧ 𝑏 ∈ 𝐵 }
▪ Si B = 𝐴 entonces 𝐴 × 𝐵 = 𝐴2, además en general no se satisface la 
igualdad 𝐴 × 𝐵 ≠ 𝐵 × 𝐴.
Ejemplo: 
Sean los conjuntos, 𝐴 = {𝑎, 𝑏} y 𝐵 = {1; 2 ; 3 }, entonces:
𝐴 × 𝐵 = 𝑎; 1 , 𝑎; 2 , 𝑎; 3 , 𝑏; 1 , 𝑏; 2 , 𝑏; 3
𝐵 × 𝐴 = 1; 𝑎 , 1; 𝑏 , 2; 𝑎 , 2; 𝑏 , 3; 𝑎 , 3; 𝑏
FIIS - UNI
FORMA DE REPRESENTACIÓN
Dados los conjuntos 𝐴 = {𝑎; 𝑏; 𝑐} y 𝐵 = {1; 2; 3; 4}, el producto cartesiano 𝑨 × 𝑩
consiste del conjunto
𝐴 × B =
𝑎; 1 , 𝑎; 2 , 𝑎; 3 , 𝑎; 4 , 𝑏; 1 , 𝑏; 2 , 𝑏; 3 , 𝑏; 4 , 𝑐; 1 , 𝑐; 2 , 𝑐; 3 , (𝑐; 4)
Una primera forma de representar 𝐴 × 𝐵 es por el plano cartesiano, ubicando a 
cada para ordenado como un punto del plano.
FIIS - UNI
4
3
2
1
a b c
B
A
FORMA DE REPRESENTACIÓN
otra formas es usar un diagrama sagital o flechas y también por medio de 
un diagrama de árbol. Veamos,
FIIS - UNI
RELACIONES BINARIAS
Una relación binaria 𝑅, de un conjunto A a un conjunto B, es un 
subconjunto de 𝐴𝑥𝐵. 𝑅: 𝐴 → 𝐵, 
𝑅 = { 𝑥; 𝑦 ∈ 𝐴 × 𝐵/ 𝑥 e 𝑦 verifican una propiedad}, 𝑅 ⊂ 𝐴𝑥𝐵
Si 𝑎, 𝑏 ∈ 𝑅, se denota 𝑎𝑅𝑏 y se lee 𝑎 está relacionado con 𝑏. Si 𝐴 = 𝐵, 
𝑅 se llama relación binaria sobre A.
▪ Dominio: Dom 𝑅 = 𝑥 ∈ 𝐴/(𝑥, 𝑦) ∈ 𝑅, 𝑝𝑎𝑟𝑎 𝑦 ∈ 𝐵
▪ Rango: Ran 𝑅 = 𝑦 ∈ 𝐵/(𝑥, 𝑦) ∈ 𝑅, 𝑝𝑎𝑟𝑎 𝑥 ∈ 𝐴
Ejemplo: 
Sean los conjuntos, 𝐴 = {𝑎, 𝑏} y 𝐵 = {1; 2 ; 3 }, entonces algunas 
relaciones 𝑅 ⊂ 𝐴 × 𝐵, son:
𝑅1 = ∅, 𝑅2= 𝑎; 1 , 𝑅3 = 𝑎, 1 , 𝑏; 1 }, 𝑅4= { 𝑎; 3 , 𝑎; 2 , 𝑏; 1 , (𝑏; 2) ,
𝑅5 = 𝐴 × 𝐵.
FIIS - UNI
RELACIÓN BINARIA
Representación de una relación binaria 
▪ Diagramas ( ver en producto cartesiano)
▪ Dígrafos
▪ Matriz booleana
Dígrafo (Grafo dirigido)
Los elementos del conjunto se representan como vértices y los pares ordenados 
como flechas.
Ejemplo
▪ La relación R sobre 𝐴 = 1,2,3,4 , 
definida por “ 𝑥, 𝑦 ∈ 𝑅 si 𝑥 ≤ 𝑦”:
R = {(1,1); (1,2); (1,3); (1,4); (2,2); (2,3), (2,4); (3,3); 
(3,4); (4,4)} 
El dominio de R es______________________
El rango de R es________________________
FIIS - UNI
Dígrafo de la relación R
PROPIEDADES: RELACIÓN BINARIA
1. Sea 𝑅 la relación definida sobre 𝐴, 𝑅 se dice que es reflexiva si 
𝑎, 𝑎 ∈ 𝑅, para todo 𝑎 ∈ 𝐴.
Ejemplo:
➢Sea 𝐴 = 1,2,3,4 𝑠𝑒 𝑑𝑒𝑓𝑖𝑛𝑒 𝑥; 𝑦 ∈ 𝑅 si 𝑥 ≤ 𝑦 , veamos que 𝑅 es 
reflexiva.
𝑅 = {(1,1); (1,2); (1,3); (1,4); (2,2); (2,3), (2,4); (3,3);
(3,4); (4,4)}
➢Sea 𝑅 = { 𝑎; 𝑎 , 𝑏; 𝑐 , 𝑐; 𝑐 , 𝑐; 𝑑 , (𝑑; 𝑑)} definida sobre 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}. 
En este ejemplo 𝑅 no es reflexiva porqué 𝑏; 𝑏 ∉ 𝑅.
FIIS - UNI
PROPIEDADES: RELACIÓN BINARIA
2. Sea 𝑅 la relación definida sobre 𝐴, 𝑅 se dice que es simetrica si para todo 
𝑎, 𝑏 ∈ 𝑅, entonces (𝑏, 𝑎) ∈ 𝑅.
Ejemplo:
➢Sea 𝑅 = { 𝑎; 𝑎 , 𝑏; 𝑐 , 𝑐; 𝑏 , (𝑑; 𝑑)} definida sobre 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}. En este ejemplo 
𝑅 es simétrica porqué 𝑏, 𝑐 ∈ 𝑅, (𝑐; 𝑏) también pertenece a 𝑅.
➢Sea 𝐴 = 1,2,3,4 𝑠𝑒 𝑑𝑒𝑓𝑖𝑛𝑒 𝑥; 𝑦 ∈ 𝑅 si 𝑥 ≤ 𝑦 , veamos que 𝑅 no es simètrica.
𝑅 = {(1,1); (1,2); (1,3); (1,4); (2,2); (2,3), (2,4); (3,3);(3,4); (4,4)}
porqué por ejemplo para 1; 2 ∈ R no existe 2; 1 ∈ 𝑅.
Los dígrafos de una relación simétrica 𝑅 tienen la propiedad que siempre existe, para 
cada arista que va de 𝑎 a 𝑏 otra que va de 𝑏 a 𝑎.
FIIS - UNI
PROPIEDADES: RELACIÓN BINARIA
3. Sea 𝑅 la relación definida sobre 𝐴, 𝑅 se dice que es antisimétrica si para todo 
𝑎, 𝑏 ∈ 𝑅 y 𝑎 ≠ 𝑏 entonces 𝑏, 𝑎 ∉ 𝑅.
Ejemplo:
➢Sea 𝐴 = 1,2,3,4 𝑠𝑒 𝑑𝑒𝑓𝑖𝑛𝑒 𝑥; 𝑦 ∈ 𝑅 si 𝑥 ≤ 𝑦 , veamos que 𝑅 es antisimètrica.
𝑅 = {(1,1); (1,2); (1,3); (1,4); (2,2); (2,3), (2,4); (3,3);(3,4); (4,4)}
➢Sea 𝑅 = { 𝑎; 𝑎 , 𝑏; 𝑐 , 𝑐; 𝑏 , (𝑑; 𝑑)} definida sobre 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}. En este ejemplo 
𝑅 no es antisimétrica porqué 𝑏, 𝑐 y (𝑐; 𝑏) pertenecen a 𝑅.
Los dígrafos de una relación antisimétrica 𝑅 tienen la propiedad que siempre a lo mas, 
existe una arista dirigida que va entre dos vértices diferentes.
FIIS - UNI
PROPIEDADES: RELACIÓN BINARIA
4. Sea 𝑅 la relación definida sobre 𝐴, 𝑅 se dice que es transitiva si para todo 
𝑎, 𝑏 ∈ 𝑅 y 𝑏; 𝑐 ∈ R entonces 𝑎, 𝑐 ∈ 𝑅.
Ejemplo:
➢Sea 𝐴 = 1,2,3,4 𝑠𝑒 𝑑𝑒𝑓𝑖𝑛𝑒 𝑥; 𝑦 ∈ 𝑅 si 𝑥 ≤ 𝑦 , veamos que 𝑅 es transitiva.
𝑅 = {(1,1); (1,2); (1,3); (1,4); (2,2); (2,3), (2,4); (3,3);(3,4); (4,4)}
Demostrarlo!!!
➢Sea 𝑅 = { 𝑎; 𝑎 , 𝑏; 𝑐 , 𝑐; 𝑏 , (𝑑; 𝑑)} definida sobre 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}. En este ejemplo 
𝑅 no es transitiva porqué 𝑏, 𝑐 y (𝑐; 𝑏) pertenecen a 𝑅 pero 𝑏; 𝑏 ∈ 𝑅.
Los dígrafos de una relación transitiva 𝑅 tienen la propiedad que si existe una arista 
dirigida de 𝑎 a 𝑏 e 𝑏 e c también habrá una para 𝑎 a c.
FIIS - UNI
PROPIEDADES: RELACIÓN BINARIA
5. Cuando todo elemento del conjunto 𝐴 no está relacionado con sí 
mismo. Es decir para todo 𝑎 ∈ 𝐴 → 𝑎; 𝑎 ∈ 𝑅.
Ejemplo.-Sea A = {-2, 1, 2, 3} y una relación R definida en A como: 
“menor que” 
R = {(-2, 1), (-2, 2), (-2, 3), (1, 2), (1, 3), (2, 3)}
FIIS - UNI
OPERACIONES RELACIÓNES BINARIAS
Sean los conjuntos 𝐴 y 𝐵 se define las relaciones 𝑅 y 𝑆 sobre 𝐴 × 𝐵, 
entonces se define las operaciones
➢Union: 𝑅 ∪ 𝑆 = 𝑎; 𝑏 ∈ 𝐴 × 𝐵: 𝑎; 𝑏 ∈ 𝑅 ∨ 𝑎; 𝑏 ∈ 𝑆 .
➢Intersección: 𝑅 ∩ 𝑆 = 𝑎; 𝑏 ∈ 𝐴 × 𝐵: 𝑎; 𝑏 ∈ 𝑅 ∧ 𝑎; 𝑏 ∈ 𝑆
➢Diferencia: 𝑅 − 𝑆 = { 𝑎; 𝑏 ∈ 𝐴 × 𝐵: 𝑎; 𝑏 ∈ 𝑅 ∧ 𝑎; 𝑏 ∉ 𝑆}
➢Complemento: 𝑅𝑐 = { 𝑎; 𝑏 ∈ 𝐴 × 𝐵: 𝑎; 𝑏 ∉ 𝑅}
FIIS - UNI
RELACIÓNES BINARIAS
Relación Inversa
Sea 𝑅 sobre A × 𝐵, se denomina relación inversa de 𝑅, y se representa por 𝑅−1, al 
conjunto.
𝑅−1 = { 𝑏; 𝑎 ∈ 𝐴 × 𝐵: 𝑎; 𝑏 ∈ 𝑅}
Ejemplo.
Sea la relación R = {(2,1); (3,1); (4,1); (4,3); (5,1); (5,3)}, su relación inversa estará 
dado por 𝑅−1 = {(1,2); (1,3); (1,4); (1,5); (3,4); (3,5)} 
Relación compuesta 
Sea las relaciones 𝑅 sobre A × 𝐵 y 𝑆 sobre 𝐵 × 𝐶 una relación entre 𝐵 y 𝐶, se define 
la relación compuesta de 𝑅 a 𝑆 como el conjunto 
𝑆 ∘ 𝑅 = 𝑥, 𝑧 ∈ 𝐴𝑥𝐶/ ∃𝑦 ∈ 𝐵 tal que 𝑥, 𝑦 ∈ 𝑅 ∧ 𝑦, 𝑧 ∈ 𝑆
▪ Es decir 𝑥 𝑆 ∘ 𝑅 𝑧 equivale a ∃𝑦 ∈ 𝐵 tal que 𝑥𝑅𝑦 ∧ 𝑦𝑆𝑧
FIIS - UNI
MATRIZ DE RELACIONES
Sean los conjuntos 𝐴 = 𝑎1,𝑎2…… . . 𝑎𝑚 , B = 𝑏1,𝑏2…… . . 𝑏𝑛
La relación 𝑅:𝐴 → 𝐵, la matriz de la relación R se representa por
𝑀𝑅 = 𝑚𝑖𝑗 𝑚𝑛
, la cual se define por:
𝑚𝑖𝑗 = ቐ
1, 𝑠𝑖 𝑎𝑖 , 𝑏𝑗 ∈ 𝑅
0, 𝑠𝑖 𝑎𝑖 , 𝑏𝑗 ∉ 𝑅
Ejemplo
Sean los conjuntos A = {a, b, c}, B = {1, 2, 3, 4} y la relación R = {(a,2), (b,2), 
(b,3), (b,4)}, la matriz asociada a la relación R estará dado por.
1 2 3 4 
a 0 1 0 0
b 0 1 1 1 → 𝑀𝑅 =
c 0 0 0 0
FIIS - UNI
OPERACIONES ENTRE MATRICES
Operaciones con matrices booleanas
Sean las matrices booleanas 𝐴 = 𝑎𝑖𝑗 y 𝐵 = 𝑏𝑖𝑗 de orden 𝑚𝑥𝑛
i) La operación union (∨) de las matrices A y B se define 
𝐶 = 𝐴 ∨ 𝐵 = 𝑐𝑖𝑗
donde 𝐶𝑖𝑗 = ൝
1, 𝑠𝑖 𝑎𝑖𝑗 = 1 𝑜 𝑏𝑖𝑗 = 1
0, 𝑠𝑖 𝑎𝑖𝑗 , 𝑦 𝑏𝑖𝑗 𝑠𝑜𝑛 𝑎𝑚𝑏𝑜𝑠 𝑐𝑒𝑟𝑜𝑠
Ejemplo.
Sean la matrices booleanas
𝐴 =
1 0 0
0 0 1
1 0 1
y 𝐵 =
1 1 1
1 1 1
1 0 0
Entonces 𝐴 ∨ 𝐵 =
1 1 1
1 1 1
1 0 1
FIIS - UNI
OPERACIONES ENTRE MATRICES
ii) La operación conjuncion (∧ ) de las matrices A y B se define 
𝐷 = 𝐴 ∧ 𝐵 = 𝑑𝑖𝑗
donde 𝐷𝑖𝑗 = ቊ
1, 𝑠𝑖 𝑎𝑖𝑗 , 𝑦 𝑏𝑖𝑗 𝑠𝑜𝑛 𝑎𝑚𝑏𝑜𝑠 𝑢𝑛𝑜𝑠
0, 𝑒𝑛 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
Ejemplo.Sean la matrices booleanas
𝐴 =
1 0 0
0 0 1
1 0 1
y 𝐵 =
1 1 1
1 1 1
1 0 0
Entonces 𝐴 ∧ 𝐵 =
1 0 0
0 0 1
1 0 0
FIIS - UNI
OPERACIONES ENTRE MATRICES
iii) La operación producto de las matrices (⊙)
Sean las matrices booleanas 𝐴 = 𝑎𝑖𝑗 de orden 𝑚𝑥𝑝 y 𝐵 = 𝑏𝑖𝑗 de orden 𝑝𝑥𝑛, se define la 
operación, 𝐸 = 𝐴⊙𝐵 = 𝑒𝑖𝑗
donde 𝑒𝑖𝑗 = ቊ
1, 𝑠𝑖 𝑎𝑖𝑘 = 1 𝑦 𝑏𝑘𝑗 = 1 𝑝𝑎𝑟𝑎 𝑎𝑙𝑔𝑢𝑛 𝑘, 1 ≤ 𝑘 ≤ 𝑝
0, 𝑒𝑛 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
Ejemplo.
Sean la matrices booleanas
𝐴 =
1 0 0
0 0 1
1 0 1
y 𝐵 =
1 1 1
1 1 1
1 0 0
Entonces 𝐴⊙ 𝐵 =
1 0 0
0 0 1
1 0 1
⊙
1 1 1
1 1 1
1 0 0
=
1 1 1
1 0 0
1 1 1
Donde
𝑒11 = 1 ∧ 1 ∨ 0 ∧ 1 ∨ 0 ∧ 1 = 1 ∨ 0 ∨ 0 = 1
𝑒12 = 1 ∧ 1 ∨ 0 ∧ 1 ∨ 0 ∧ 0 = 1 ∨ 0 ∨ 0 = 1
⋮
FIIS - UNI
PROPIEDADES
Propiedades de las matrices booleanas 
Sean las matrices booleanas A, B, C, donde tenemos las siguientes 
propiedades.
a) 𝐴 ∨ 𝐵 = 𝐵 ∨ 𝐴
b) 𝐴 ∧ 𝐵 = 𝐵 ∧ 𝐴
c) 𝐴 ∨ (𝐵 ∨ 𝐶) = (𝐴 ∨ 𝐵) ∨ 𝐶
d) 𝐴 ∧ (𝐵 ∧ 𝐶) = (𝐴 ∧ 𝐵) ∧ 𝐶
e) 𝐴 ∨ (𝐵 ∧ 𝐶) = (𝐴 ∨ 𝐵) ∧ (A ∨ 𝐶)
f) 𝐴 ∧ (𝐵 ∨ 𝐶) = (𝐴 ∧ 𝐵) ∨ (A ∧ 𝐶)
g) 𝐴 ∨ (𝐵 ∨ 𝐶) = (𝐴 ∨ 𝐵) ∨ 𝐶
FIIS - UNI
RELACION DE EQUIVALENCIA
Una relación binaria 𝑅 sobre un conjunto A es de equivalencia si se cumple 
las propiedades: Reflexiva, simétrica y transitiva
▪ Ejemplo 1
▪ Consideremos un conjunto de rectas incluidas en un plano con la relacion
▪ 𝐿1𝑅𝐿2 ↔ 𝐿1, 𝑒𝑠 𝑝𝑎𝑟𝑎𝑙𝑒𝑙𝑎 𝑎 𝐿2
▪ Cumple las propiedades:
▪ Reflexiva: toda recta 𝐿 es paralela 𝐿 sí misma.
▪ Simétrica: si 𝐿1 es paralela 𝐿2 → 𝐿2es paralela 𝐿1.
▪ Transitiva: si 𝐿1 es paralela 𝐿2 y 𝐿2 es paralela 𝐿3 → 𝐿1 es paralela 𝐿3.
▪ Por lo tanto esta relación es una relación de equivalencia.
FIIS - UNI
RELACIÓN DE EQUIVALENCIA
Ejemplo 2
Sobre el conjunto 𝐴 = 1,2,3,4,5 se da una relación definida por el dígrafo que se 
muestra en la figura 1.
¿Esta es una relación de equivalencia?
FIIS - UNI
RELACIÓN DE EQUIVALENCIA
Ejemplo 2
FIIS - UNI
PARTICIÓN DE UN CONJUNTO
Una partición de un conjunto no vacío 𝑨, es una colección 𝑷 = 𝑨𝟏, 𝑨𝟐, ………𝑨𝒏 , de subconjuntos 
de A talque:
a) 𝑨𝒊 ∩ 𝑨𝒋 = ∅, 𝒔𝒊 𝑨𝒊 ≠ 𝑨𝒋
b) 𝑨𝒊 ∪⋯……𝑨𝒋 = 𝑨
Los subconjuntos 𝑨𝒊 ∈ 𝑷 son llamados bloques de partición
FIIS - UNI
CLASE DE EQUIVALENCIA
Dada 𝑅 una relación de equivalencia sobre el conjunto 𝐴, se llama clase de equivalencia 
de 𝑎 ∈ 𝐴 denotado por 𝑎 , al conjunto:
𝑎 = {𝑥 ∈ 𝐴/ 𝑥𝑅𝑎}
El conjunto de todas las clases de equivalencia forman una partición de 𝐴
Ejemplo: Sean el conjunto A = {1, 2, 3, 4, 5} y la relación de equivalencia R = {(1,1),
(2,2), (3,3), (2,3), (3,2), (4,5), (4,4), (5,5), (5,4)}
Entonces las clases de equivalencia son:
.
FIIS - UNI
[4] = {4, 5}
[5] = {4, 5}
[1] = {1}
[2] = {2, 3}
[3] = {2, 3}
En definitiva, dado que se repiten [2] con [3] y 4 con 5 , las clases de equivalencia son:
{1} {2, 3} {4, 5}
CONJUNTO COCIENTE
Dada 𝑅 una relación de equivalencia sobre el conjunto 𝐴, se llama conjunto cociente:
𝐴/𝑅 = {[𝑎]/ 𝑎 ∈ 𝐴}
Ejemplo: Sean el conjunto A = {1, 2, 3, 4, 5} y la relación de equivalencia 
R = {(1,1), (2,2), (3,3), (2,3), (3,2), (4,5), (4,4), (5,5), (5,4)}
Entonces el conjunto cociente es:
FIIS - UNI
Es decir que A / R = 𝟏 , 𝟐 , 𝟒 = 𝟏 , 𝟑 , 𝟓 = {{1}, {2, 3}, {4, 5}}