sesión virtual semana 07

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 Manipulación de relaciones CONTENIDO Unidad 3: RELACIONES Y FUNCIONES 3.5 Manipulación de relaciones ▪ Relación complementaria ▪ Relación inversa ▪ Unión e intersección de relaciones ▪ Composición de relaciones ▪ Cerraduras de relaciones UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 Manipulación de relaciones Relación complementaria Sea 𝑹 una relación de un conjunto A a un conjunto B. Se define la relación complementaria 𝑅̅ como sigue: (𝑎, 𝑏) ∈ 𝑅̅ ⇔ (𝑎, 𝑏) ∉ 𝑅 Si 𝑀 es la matriz de la relación 𝑅 , la matriz de la relación complementaria se obtiene a partir de 𝑀 al reemplazar cada 1 en 𝑀 por un 0 y cada 0 por un 1. Ejemplo: Dada la relación 𝑅 = {(2; 3), (3; 1), (1; 3); (2; 1), (3; 3), (2; 4), (3; 4)} , en 𝐴 × 𝐵 , con 𝐴 = {1, 2, 3} y 𝐵 = {1, 2, 3, 4} . Determine la relación complementaria a 𝑅 . Solución La relación complementaria a 𝑅 es 𝑅̅ = {(1; 1), (1; 2), (1; 4), (2; 2), (3; 2)} . Nota: Es fácil ver que se cumple la siguiente propiedad, |𝑅̅| + |𝑅| = |𝐴 × 𝐵| . También el ejemplo anterior se resuelve muy fácilmente usando matrices y complementado en binario cada término. Relación inversa Sea 𝑅 ⊆ 𝐴 × 𝐵 , se define 𝑅 −1 como sigue: (𝑏, 𝑎) ∈ 𝑅 −1 ⟺ (𝑎, 𝑏) ∈ 𝑅 La relación 𝑅 −1 es una relación de 𝐵 a 𝐴 . • Representación Matricial: 𝑀 𝑅 −1 = 𝑀 𝑅 𝑇 • Se sabe que 𝑅 es simétrica si: 𝑀 𝑅 = 𝑀 𝑅 𝑇 . • Debido a que 𝑀 𝑅 𝑇 = 𝑀 𝑅 −1 se ve que 𝑅 es simétrica sí y solo si 𝑅 = 𝑅 −1 . 𝑀 𝑅 = 1 2 3 ൥ 0 0 1 0 1 0 1 1 1 0 1 1 ൩ 1 2 3 4 𝑀 𝑅 ̅ = 1 2 3 ൥ 1 1 0 1 0 1 0 0 0 1 0 0 ൩ 1 2 3 4 UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 A continuación, veremos un ejemplo sencillo para entender el concepto, dicho ejemplo se puede resolver analizando el conjunto relación o mejor aun pasando a su matriz de relaciones Ejemplo: En el conjunto 𝐴 = {1, 2, 3} , se tiene la siguiente relación 𝑅 = {(2 ; 3), (3; 1), (1; 3), (2; 1), (3; 3)} Luego la relación inversa 𝑅 −1 = {(3; 2), (1; 3), (3; 1), (1; 2), (3; 3)} . Note que se cumple: 𝑀 𝑅 −1 = 𝑀 𝑅 𝑇 Unión de relaciones Sean 𝑅, 𝑆 ⊆ 𝐴 × 𝐵 𝑎 (𝑅 ∪ 𝑆)𝑏 ⟺ 𝑎 𝑅 𝑏 𝑜 𝑎 𝑆 𝑏 • Representación matricial: 𝑀 𝑅∪𝑆 = 𝑀 𝑅 ∨ 𝑀 𝑆 Ejemplo: Dada las relaciones 𝑅 = {(1; 2), (3; 2), (2; 1)} y 𝑆 = {(1; 1), (1; 2), (2; 2)} en 𝐴 × 𝐵 con 𝐴 = {1,2,3} y 𝐵 = {1,2} . Solución: Entonces la relación T= 𝑅 ∪ 𝑆 está dado por: 𝑇 = {(1; 1), (1; 2), (2; 1), (2; 2), (3; 2)} . El mismo ejemplo como representación matricial. Intersección de relaciones Sean 𝑅, 𝑆 ⊆ 𝐴 × 𝐵 𝑎 (𝑅 ∩ 𝑆)𝑏 ⟺ 𝑎 𝑅 𝑏 𝑦 𝑎 𝑆 𝑏 • Representación matricial: 𝑀 𝑅∩𝑆 = 𝑀 𝑅 ∧ 𝑀 𝑆 𝑀 𝑅 = 1 2 3 ൥ 0 0 1 1 0 1 1 0 1 ൩ 1 2 3 𝑀 𝑅 −1 = 1 2 3 ൥ 0 1 1 0 0 0 1 1 1 ൩ 1 2 3 𝑀 𝑅 = ൥ 0 1 1 0 0 1 ൩ y 𝑀 𝑆 = ൥ 1 1 0 1 0 0 ൩ , entonces tenemo s 𝑀 𝑅∪𝑆 = ൥ 1 1 1 1 0 1 ൩ UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 4 Ejemplo: Dada las relaciones 𝑅 = {(1; 2), (2; 1), (3; 2), (3; 1)} y 𝑆 = {(1; 1), (1; 2), (2; 2)} en 𝐴 × 𝐵 con 𝐴 = {1,2,3} y 𝐵 = {1,2} . Solución: Entonces la relación T= 𝑅 ∩ 𝑆 está dado por 𝑇 = {(1; 2)} . El mismo ejemplo como representación matricial. Composición de relaciones Sean 𝐴, 𝐵, 𝐶 conjuntos, 𝑅 ⊆ 𝐴 × 𝐵 y 𝑆 ⊆ 𝐵 × 𝐶 . Se define la composición de 𝑅 y 𝑆 (𝑆 ∘ 𝑅) : 𝑎(𝑆 ∘ 𝑅)𝑐 sí y solo si para alguna 𝑏 ∈ 𝐵 se tiene que 𝑎 𝑅 𝑏 y 𝑏 𝑆 𝑐 • Representación Matricial: 𝑀 𝑆∘𝑅 = 𝑀 𝑅 ⨀𝑀 𝑆 Ejemplo: Dados los conjuntos 𝐴 = { 1 ; 2 ; 3 } , 𝐵 = { 1 ; 2 ; 3 ; 4 } , 𝐶 = { 2 ; 4 }, y las relaciones 𝑅 y 𝑆 : 𝑅 = { ( 1; 2 ) , ( 1; 4 ) , ( 2; 2 ) , ( 2 ; 3 ), ( 3 ; 1 ) } en 𝐴 × 𝐵 𝑆 = { ( 1 ; 2 ) , ( 2 ; 4 ) , ( 3 ; 2 ) ; ( 4 ; 4 ) } en 𝐵 × 𝐶 Determine la composición 𝑆 ∘ 𝑅 . Solución La composición es 𝑆 ∘ 𝑅 = {( 1 ; 4 ) , ( 2 ; 2 ) , ( 2 ; 4 ) , ( 3 ; 2) } . También se puede obtener 𝑆∘𝑅 aprovechando la propiedad matricial: 𝑀 𝑆 ∘ 𝑅 = 𝑀 𝑅 ⊙ 𝑀 𝑆 = ൥ 0 1 0 1 0 1 1…