Aplicaciones de Funciones booleanas

Matemática Discreta • Manipulación de relaciones Unidad 1: Teoría de Conjuntos, Lógica proposicional y relaciones Logro de la sesión Al finalizar la sesión, el estudiante realiza operaciones con relaciones y determina sus cerraduras. Bibliografía • Profesores UPC – Libro digital – Relaciones: Manipulación • Johnsonbaugh R. (2005). Matemáticas Discretas, sexta edición. Editorial Pearson, México. • Epp S. (2012). Matemáticas discretas con aplicaciones . México, D.F. Cengage Learning. Bibliografía textos de consulta. Bibliografía multimedia. Relación complementaria Sea 𝑅 una relación de un conjunto 𝐴 a un conjunto B . Se define la relación complementaria ത 𝑅 como sigue: Observación. Si 𝑀 𝑅 es la matriz de la relación R , 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. 𝑎, 𝑏 ∈ ത 𝑅 ⟺ (𝑎, 𝑏) ∉ 𝑅 Relación complementaria Ejemplo: Dada la relación 𝑅 en 𝐴 × 𝐵 , con 𝐴 = 1; 2; 3 y 𝐵 = {2; 3}. Halle ത 𝑅 la relación complementaria a 𝑅 . 𝑅 = { 1; 2 , 1; 3 , (2; 3), (3; 2)} La relación complementaria será ത 𝑅 = 𝐴 × 𝐵 − 𝑅 . 𝑀 𝑅 = 1 2 3 1 1 0 1 1 0 2 3 𝑀 ത 𝑅 = 1 2 3 0 0 1 0 0 1 2 3 Resultando ത 𝑅 ={(2; 2), (3; 3)} Relación inversa Sea R  A  B , se define 𝑅 −1 como sigue: ( b , a )  𝑅 −1  ( a , b )  R La relación 𝑅 −1 es una relación de B a A. Representación Matricial 𝑀 𝑅 −1 = 𝑀 𝑅 𝑇 Observación. R es simétrica si M R = ( M R ) T ; es decir, 𝑀 𝑅 = 𝑀 𝑅 −1 , lo que significa que R es simétrica si y solo si 𝑅 = 𝑅 −1 Relación inversa Ejemplo: D ada la relación R en A={1; 2; 3} y B={2; 3}. Determine 𝑅 −1 la relación inversa de R, donde : 𝑅 = { 1; 2 , 1; 3 , 2; 3 , (3; 2)} Solución: La relación inversa 𝑅 −1 es { 2; 1 , 3; 1 , 3; 2 , (2; 3)} 𝑀 𝑅 = 1 2 3 1 1 0 1 1 0 2 3 𝑀 𝑅 −1 = 2 3 1 0 1 1 1 0 1 2 3 M R -1 = ( M R ) T Note que: Unión e intersección de relaciones Sean R, S  A  B a ( R  S ) b  a R b o a S b Representación matricial: M R  S = M R  M S Sean R, S  A  B a ( R  S ) b  a R b y a S b Representación matricial: M R  S = M R  M S Unión de relaciones Intersección de relaciones Ejemplo: Solución : Dada las relaciones: 𝑅 = { 1; 2 , 2; 1 , 3; 2 } y 𝑆 = {(1; 1), (1; 2), (2; 2)} en 𝐴 × 𝐵 con 𝐴 = {1; 2; 3} y 𝐵 = {1; 2} . Halle la unión e intersección de ambas relaciones y su representación matricial. 𝑀 𝑅 = 1 2 3 0 1 1 0 0 1 1 2 𝑀 𝑆 = 1 2 3 1 1 0 1 0 0 1 2 𝑀 𝑅∪𝑆 = M R  M S = 1 2 3 1 1 1 1 0 1 1 2 𝑀 𝑅∩𝑆 = M R  M S = 1 2 3 0 1 0 0 0 0 1 2 𝑅 ∪ 𝑆 = 1; 1 , 1; 2 , 2; 1 , 2; 2 , (3; 2) 𝑅 ∩ 𝑆 = 1; 2 Composición de relaciones Sean A, B, C conjuntos, R  A  B y S  B  C. Se define la composición de R y S (𝑆 ∘ 𝑅) : a (𝑆 ∘ 𝑅) c si y solo si para alguna b  B se tiene: a R b y b S c Representación Matricial: M S o R = M R  M S Composición de relaciones Ejemplo: Dados los conjuntos y las relaciones 𝑅 y 𝑆 𝐴 = 1; 2; 3 𝐵 = 1; 2; 3; 4 𝐶 = 2; 4 𝑅 = 1; 2 , 1; 4 , 2; 2 , (2; 3), 3; 1 en 𝐴 × 𝐵 𝑆 = 1; 2 , 2; 4 , 3; 2 ; 4; 4 en 𝐵 × 𝐶 Determine la composición 𝑆 ∘ 𝑅 . La composición es: 𝑆 ∘ 𝑅 = 𝟏; 𝟒 , 𝟐; 𝟐 , 𝟐; 𝟒 , (𝟑; 𝟐) Segunda forma: Se puede obtener 𝑆 ∘ 𝑅 aprovechando la propiedad matricial. 𝑀 𝑆∘𝑅 = 𝑀 𝑅 ⊙ 𝑀 𝑆 = 1 2 3 4 1 2 3 0 1 0 1 0 1 1 0 1 0 0 0 ⊙ 2 4 1 2 3 4 1 0 0 1 1 0 0 1 𝑀 S∘𝑅 = 2 4 1 2 3 0 1 1 1 1 0 Solución: Cerraduras de relaciones Sea R una relación sobre el conjunto A 1. Cerradura reflexiva: R   donde  es la relación diagonal. 2. Cerradura simétrica: R  R -1 3. Cerradura transitiva: R ∞ Ejemplo: Sea el conjunto 𝐴 = {1; 2; 3; 4} y la relación definida en 𝐴 por 𝑅 = 1; 2 , 2; 3 , 3; 4 , 2; 1 a) Determine la cerradura reflexiva de la relación 𝑅 Solución b) Determine la cerradura simétrica de la relación 𝑅 Solución c) Determine la cerradura transitiva de la relación 𝑅 Solución ∆= 1; 1 , 2; 2 , 3; 3 , (4; 4) 𝑅 ∪ ∆= 1; 2 , 2; 3 , 3; 4 , 2; 1 , 1; 1 , 2; 2 , 3; 3 , (4; 4) 𝑅 −1 = 2; 1 , 3; 2 , 4; 3 , (1; 2) 𝑅 ∪ 𝑅 −1 = 1; 2 , 2; 3 , 3; 4 , 2; 1 , 3; 2 , (4;…