RELACIONES BINARIAS

Vista previa del material en texto

TEMA: Relaciones binarias (parte 2)
Semana 5
FACULTAD DE INGENIERÍA INDUSTRIAL Y 
SISTEMAS
RELACION DE ORDEN
Relación de orden parcial: Es toda relación binaria 𝑅 sobre un conjunto A, tal 
que 𝑅 es: Reflexiva, antisimétrica y transitiva. 
Permite ordenar los elementos a través de la relación. Al para (𝐴, 𝑅) se le llama 
conjunto parcialmente ordenado.
Ejemplo: Sobre el conjunto 𝐴 = {1, 2, 3, 4, 6, 12} se define la relación 𝑅 sobre A, como 
𝑥𝑅𝑦 si 𝑥 divide a 𝑦.
Pueden definirse dos tipos de relación orden parcial: orden amplio y orden estricto.
FIIS - UNI
RELACIONES DE ORDEN PARCIAL
FIIS - UNI
Relación de orden amplio
Una relación de orden parcial es aquella que cumple las propiedades
reflexiva, antisimétrica y transitiva.
Ejemplo:
Sea el conjunto A = {1, 2, 3, 4, 5}, y en él la Relación:“menor o igual “
Relación de orden estricto
Una relación de orden estricto es aquella que cumple con las
propiedades antireflexiva, antisimétrica y transitiva
Ejemplo:
Sea el conjunto A = {1, 2, 3, 4, 5}, y en él la Relación:“menor que “
RELACION DE ORDEN TOTAL FIIS - UNI
Elementos comparables 
Si 𝑅 es una relación de orden parcial sobre 𝐴, los elementos a y b son 
comparables, si 𝑎𝑅𝑏 𝑜 𝑏𝑅𝑎. 
Relación de Orden total 
Sea (𝐴, 𝑅) un conjunto parcialmente ordenado, decimos que 𝐴 es 
totalmente ordenado si para todos 𝑥, 𝑦 ∈ 𝐴 ocurre que 𝑥𝑅𝑦 𝑜 𝑦𝑅𝑥. En este 
caso decimos que 𝑅 es un orden total.
Ejemplo: 
➢En el conjunto 𝑁, la relación 𝑅 dada por 𝑥𝑅𝑦 si 𝑥 ≤ 𝑦 es un orden total
➢La relación de inclusión aplicada sobre 𝐴 ⊂ 𝑃(𝑈), es un orden parcial 
pero no total, tome U={1, 2, 3}
RELACION DE ORDEN
Ejercicio: Defina la relación 𝑅 sobre el conjunto 𝑍 de la forma siguiente: 𝑎𝑅𝑏 si 𝑎 − 𝑏
es un entero no negativo. Demuestre que 𝑅 es de orden parcial en 𝑍. ¿Es 𝑅 de orden 
total?
FIIS - UNI
DIAGRAMA DE HASSE
Es un diagrama simplificado para representar una relación orden. Para trazar el 
diagrama de Hasse se borran todos los lazos, porque la relación es reflexiva, se 
eliminan las aristas que están implicadas por la propiedad transitiva, los vértices se 
remplazan por puntos.
Ejemplo: Sea el conjunto 𝐴 = 1,2,3,4 , y R, aRb, “a divide a b”, entonces
𝑅 = 1,1 , 1,2 , 1,3 , 1,4 , 2,2 , 2,4 , 3,3 , 4,4 , es un orden parcial y 𝐴, 𝑅 es un 
conjunto parcialmente ordenado
FIIS - UNI
ELEMENTOS EXTREMOS DE UN CONJUNTO 
PARCIALMENTE ORDENADO
Sea (𝐴, 𝑅) un conjunto parcialmente ordenado se definen:
a. Elemento máximo: 𝒂 ∈ 𝑨 es un elemento máximo de A, si 𝑥𝑅𝑎, para todo 𝑥 ∈ 𝐴.
b. Elemento mínimo: 𝒂 ∈ 𝑨 es un elemento mínimo de A, si 𝑎𝑅𝑥, para todo 𝑥 ∈ 𝐴.
Ejemplo
Sea el conjunto 𝐴 = 0,2,4,7,12,14 , donde la relación orden 
parcial sobre el conjunto A es 𝑥𝑅𝑦 𝑠𝑖 𝑥 ≤ 𝑦, y el diagrama de 
Hasse de la relación es dado por:
Elemento máximo: 14
Elemento mínimo: 0 
FIIS - UNI
ELEMENTOS EXTREMOS DE UN CONJUNTO 
PARCIALMENTE ORDENADO
c. Elemento maximal: 𝒂 ∈ 𝑨 es un elemento maximal de A, si no existe un elemento 
𝑥 ∈ 𝐴, tal que 𝑎𝑅𝑥. De forma equivalente si para cualquier 𝑥 ∈ A tal que 𝑎𝑅𝑥 ⇒ 𝑎 = 𝑥.
d. Elemento minimal:𝒂 ∈ 𝑨 es un elemento minimal de A, si no existe un elemento 
𝑥 ∈ 𝐴, tal que 𝑥𝑅𝑎. De forma equivalente si para cualquier 𝑥 ∈ A tal que 𝑥𝑅𝑎 ⇒ 𝑎 = 𝑥.
Teoremas 
1.-Un conjunto parcialmente ordenado tiene a lo más un elemento máximo (mínimo). Si 
existe máximo (mínimo), este elemento es único.
2.- Un conjunto parcialmente ordenado tiene al menos un elemento máximal y al menos 
un elemento mínimal.
FIIS - UNI
EJEMPLO
Sea un conjunto A parcialmente ordenado, cuyo diagrama de Hasse se muestra en la 
figura. Determinar los elementos maximal, minimal, máximo y mínimo.
▪ Elementos maximales: 𝑎1, 𝑎2, 𝑎3
▪ Elementos minimales: 𝑑1, 𝑑2, 𝑑3
▪ Elemento maximo: ∄
▪ Elemento minimo: ∄
FIIS - UNI
𝑎3𝑎2
𝑎1
𝑏1
𝑏2
𝑏3
𝑑2
𝑑1
𝑏4
𝑏5
𝑑3
𝑑4
SUPREMO E INFIMO
Sea 𝑨, 𝑹 un conjunto parcialmente ordenado y B un subconjunto de A se definen 
los siguientes elementos.
▪ Cota superior.- Un elemento 𝑎 ∈ 𝐴 es una cota superior de B, si 𝑥𝑅𝑎, ∀𝑥 ∈ 𝐵. 
▪ Cota inferior.- Un elemento 𝑎 ∈ 𝐴 es una cota inferior de B, si 𝑎𝑅𝑥, ∀𝑥 ∈ 𝐵. 
▪ Supremo de B.- Es la mínima cota superior de B.
▪ Ínfimo de B.- Es la máxima cota inferior de B
Teorema
Si (𝐴, 𝑅) es un conjunto parcialmente ordenado y 𝐵 ⊂ 𝐴, entonces 𝐵 tiene a lo sumo 
un ínfimo (supremo).
FIIS - UNI
EJEMPLO
Consideremos el conjunto parcialmente ordenado 𝐴 = 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ , cuyo diagrama 
de Hasse se muestra en la figura. Determine las cotas superiores e inferiores de los 
siguientes subconjuntos de A.
a) 𝐴1 = 𝑎, 𝑏 b) 𝐴2 = 𝑐, 𝑑, 𝑒
➢Cotas superiores de 𝑨𝟏: c, d,e,f,g,h
➢Cotas inferiores de 𝑨𝟏: no existe
➢Cotas superiores de 𝑨𝟐: f,g,h
➢Cotas inferiores de 𝑨𝟐: a, b ,c
➢Supremo de 𝑨𝟏: c
➢Infimo de 𝑨𝟏 : no existe
➢ Supremo de 𝑨𝟐: no existe
➢ Infimo de 𝑨𝟐 : c
FIIS - UNI