MA265 Sesión 10.1b Ejercicios de Funciones booleanas y mapa de Karnaugh-Solucionario

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 Manipulación de relaciones Respuestas de los ejercicios propuestos 1. Respuestas a) 𝑀 𝑅 = [ 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1] 𝑀 𝑆 = [ 0 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0] b) 𝑀 𝑆 −1 = [ 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0 0] 𝑀 𝑅̅ = [ 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0] c) 𝑀 𝑅∪𝑆 −1 = [ 0 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1] 𝑀 𝑅̅∩𝑆 = [ 0 1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0] d) 𝑀 𝑆∘𝑅 = 𝑀 𝑅 ⊙ 𝑀 𝑆 = [ 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0] 2. Respuestas a) 𝑀 𝑅 = [ 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0] 𝑀 𝑆 = [ 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0] b) 𝑀 𝑅 −1 = [ 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0] 𝑀 𝑆̅ = [ 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 1] c) 𝑀 𝑆̅∪𝑅 −1 = [ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 1] 𝑀 𝑆̅∩𝑅 = [ 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0] UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 d) 𝑀 𝑆∘𝑅 −1 = [ 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 0 1 1 1 0] 3. Respuestas Cerradura reflexiva: 𝑅 ∪△= {(1; 1), (1; 2), (1; 3), (1; 6), (2; 2), (2; 6), (3; 3), (3; 6), (6; 6)} Cerradura simétrica: 𝑅 ∪ 𝑅 −1 = {(1; 2), (1; 3), (1; 6), (2; 1), (2; 6), (3; 1), (3; 6), (6; 1), (6; 2), (6; 3), (6; 6)} Cerradura transitiva: 𝑅 ∞ = {(1; 2), (1; 3), (1; 6), (2; 6), (3; 6)} 4. Respuestas a) 𝑅̅ = {(0; 0), (0; 1), (0; 2), (1; 0), (1; 1), (1; 3), (2; 0), (2; 2), (2; 3), (3; 1), (3; 2), (3; 3)} 𝑆̅ = {(1; 0), (2; 0), (2; 1), (3; 0), (3; 1), (3; 2)} b) 𝑅 −1 = {(0; 3), (1; 2), (2; 1), (3; 0)} 𝑆 −1 = {(0; 0), (1; 0), (1; 1), (2; 0), (2; 1), (2; 2), (3; 0), (3; 1), (3; 2), (3; 3)} c) 𝑅 ∪ 𝑆 = {(0; 0), (0; 1), (0; 2), (0; 3), (1; 1), (1; 2), (1; 3), (2; 1), (2; 2), (2; 3), (3; 3), (3; 3)} 𝑅 ∩ 𝑆 = {(0; 3), (1; 2)} d) 𝑅 ∘ 𝑆 = {(0; 0), (0; 1), (0; 2), (0; 3), (1; 0), (1; 1), (1; 2), (2; 0), (2; 1), (3; 0)} 5. Respuestas a) 𝑅̅ = {(1; 4), (1; 5), (2; 5), (4; 1), (5; 1), (5; 2)} 𝑆̅ = {(1; 1), (1; 3), (1; 5), (2; 2), (2; 4), (3; 1), (3; 3), (3; 5), (4; 2), (4; 4), (5; 1), (5; 3), (5; 5)} b) 𝑅 −1 = {(1; 1), (1; 2), (1; 3), (2; 1), (2; 2), (2; 3), (2; 4), (3; 1), (3; 2), (3; 3), (3; 4), (3; 5), (4; 2), (4; 3), (4; 4), (4; 5), (5; 3), (5; 4), (5; 5) } 𝑆 −1 = {(1; 2), (1; 4), (2; 1), (2; 3), (2; 5), (3; 2), (3; 4), (4; 1), (4; 3), (4; 5), (5; 2), (5; 4)} c) 𝑅 ∪ 𝑆 = {(1; 1), (1; 2), (1; 3), (1; 4), (2; 1), (2; 2), (2; 3), (2; 4), (2; 5), (3; 1), (3; 2), (3; 3), (3; 5), (3; 6), (4; 1), (4; 2), (4; 3), (4; 4), (4; 5), (5; 2), (5; 3), (5; 4), (5; 5) } 𝑅 ∩ 𝑆 = {(1; 2), (2; 1), (2; 3), (3; 2), (3; 4), (4; 3), (4; 5), (5; 4)} d) 𝑅̅ ∘ 𝑆 −1 = {(1; 1), (1; 5), (2; 1), (2; 2), (2; 4), (2; 5), (3; 1), (3; 5), (4; 1), (4; 2), (4; 4), (4; 5), (5; 1), (5; 5)} UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 6. Respuestas a) 𝑅̅ = {(−1; −1), (−1; 0), (−1; 1), (−1; 2), (0; −1), (0; 0), (0; 1), (0; 3), (1; −1), (1; 0), (1; 2), (1; 3), (2; −1), (2; 1), (2; 2), (2; 3), (3; 0), (3; 1), (3; 2), (3; 3)} 𝑆̅ = {(−1; 2), (0; 0), (0; 2), (1; −1), (1; 0), (1; 1), (1; 2), (1; 3), (2; −1), (3; −1)} b) 𝑅 −1 = {(−1; 3), (0; 2), (1; 1), (2; 0), (3; −1)} 𝑆 −1 = {(−1; −1), (−1; 0), (0; −1), (0; 2), (0; 3), (1; −1), (1; 0), (1; 2), (1; 3), (2; 2), (2; 3), (3; −1), (3; 0), (3; 2), (3; 3)} c) 𝑅 ∪ 𝑆 = {(−1; −1), (−1; 0), (−1; 1), (−1; 3), (0; −1), (0; 1), (0; 2), (0; 3), (1; 1), (2; 0), (2; 1), (2; 2), (2; 3), (3; −1), (3; 0), (3; 1), (3; 2), (3; 3)} 𝑅 ∩ 𝑆 = {(−1; 3), (2; 0)} d) 𝑅 ∘ 𝑆 = {(−1; −1), (−1; 1), (−1; 2), (−1; 3), (0; −1), (0; 1), (0; 3), (2; −1), (2; 0), (2; 1), (2; 2), (3; −1), (3; 0), (3; 1), (3; 2)} 7. Respuestas a) 𝑀 𝑅̅ = [ 1 0 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1…