MA265 Sesión 10.1b Funciones booleanas y mapas de Karnaugh

RESPUESTAS DE La lista de ejercicios 1. a. 𝑅 es reflexiva, ∆⊆ 𝑅 𝑅 es antisimétrica, 𝑅 ∩ 𝑅 −1 ⊆ ∆ 𝑅 es transitiva, 𝑅 2 ⊆ 𝑅 b. c. Si son comparables, pues (𝑒, 𝑑) ∈ 𝑅 d. No son comparables, pues (𝑎, 𝑏) ∉ 𝑅 2. a. 𝑆 es reflexiva, ∆⊆ 𝑆 𝑆 es antisimétrica, 𝑆 ∩ 𝑆 −1 ⊆ ∆ 𝑆 es transitiva, 𝑆 2 ⊆ 𝑆 b. 3. a. 𝑅 = {(𝑎, 𝑎), (𝑏, 𝑏), (𝑐, 𝑐), (𝑑, 𝑑), (𝑒, 𝑒), (𝑓, 𝑓), (𝑎, 𝑑), (𝑏, 𝑑), (𝑐, 𝑎), (𝑐, 𝑏), (𝑐, 𝑑), (𝑒, 𝑎) , (𝑒, 𝑏), (𝑒, 𝑐), (𝑒, 𝑑), , (𝑒, 𝑓), (𝑓, 𝑏), (𝑓, 𝑑) } b. Si son comparables, pues (𝑒, 𝑏) ∈ 𝑅 c. No son comparables, pues (𝑎, 𝑓) ∉ 𝑅 d. 𝑎 = 6, 𝑏 = 15, 𝑐 = 3, 𝑑 = 30, 𝑒 = 1, 𝑓 = 5 4. a. 𝑅 = { (1,1), (1,2), (1,4), (1,8), (1,16), (2,2), (2,4), (2,8), (2,16), (4,4), (4,8), (4,16), (8,8), (8,16), (16,16) } b. 𝑅 es reflexiva, ∆⊆ 𝑅 𝑅 es antisimétrica, 𝑅 ∩ 𝑅 −1 ⊆ ∆ 𝑅 es transitiva, 𝑅 2 ⊆ 𝑅 c. R es un orden lineal, pues cualquier par de elementos de A están relacionados. d. Si, pues 2 es divisor de 8 e. 5. a. 𝑀 𝑅 2 = 𝑀 𝑅 = [ 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1] , 𝑀 𝑅 −1 = [ 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1] 𝑅 es reflexiva, ∆⊆ 𝑅 𝑅 es antisimétrica, 𝑅 ∩ 𝑅 −1 ⊆ ∆ 𝑅 es transitiva, 𝑅 2 ⊆ 𝑅 b. 6. a. 𝑨 = { (∅, {1}), (∅, {3}), (∅, {1,2}), (∅, {1,3}), ({1}, {1,2}), ({1}, {1,2}), ({1}, {1,3}), ({3}, {1,3}), (∅, ∅), ({1}, {1}), ({3}, {3}), ({1,2}, {1,2}), ({1,3}, {1,3}) } b. 𝑅 es reflexiva, ∆⊆ 𝑅 𝑅 es antisimétrica, 𝑅 ∩ 𝑅 −1 ⊆ ∆ 𝑅 es transitiva, 𝑅 2 ⊆ 𝑅 c. 𝑅 no es un orden lineal, pues ({3}, {1,2}) ∉ 𝑅 d. ∅ { 𝟏 } { 𝟑 } { 𝟏, 𝟐 } { 𝟏, 𝟑 } 7. a. 𝑅 es reflexiva, ∆⊆ 𝑅 𝑅 es antisimétrica, 𝑅 ∩ 𝑅 −1 ⊆ ∆ 𝑅 es transitiva, 𝑅 2 ⊆ 𝑅 b. 8. a. 𝑅 es reflexiva, ∆⊆ 𝑅 𝑅 es antisimétrica, 𝑅 ∩ 𝑅 −1 ⊆ ∆ 𝑅 es transitiva, 𝑅 2 ⊆ 𝑅 b. c. Si son comparables, pues (𝑐, 𝑏) ∈ 𝑅 d. No son comparables, pues (𝑎, 𝑑) ∉ 𝑅 9. 𝑥𝑅𝑦 ⇔ 𝑥 ≤ 𝑦 𝑅 es reflexiva, 𝑥 ≤ 𝑥 𝑅 es antisimétrica, 𝑥 ≤ 𝑦 ∧ 𝑦 ≤ 𝑥 ⇒ 𝑥 = 𝑦 𝑅 es transitiva, 𝑥 ≤ 𝑦 ∧ 𝑦 ≤ 𝑧 ⇒ 𝑥 ≤ 𝑧 10. a. 𝑀 𝑅 = [ 1 0 1 1 1 1 0 1 0 0 0 1 0 0 0 1 ] 𝑅 es reflexiva, ∆ ⊆ 𝑅 𝑅 es antisimétrica, 𝑅 ∩ 𝑅 −1 ⊆ ∆ 𝑅 es transitiva, 𝑅 2 ⊆ 𝑅 b. 11. a. 𝐴𝑅𝐵 ⇔ 𝐴 ⊆ 𝐵 𝑅 es reflexiva, 𝐴 ⊆ 𝐴 𝑅 es antisimétrica, 𝐴 ⊆ 𝐵 ∧ 𝐵 ⊆ 𝐴 ⇒ 𝐴 = 𝐵 𝑅 es transitiva, 𝐴 ⊆ 𝐵 ∧ 𝐵 ⊆ 𝐶 ⇒ 𝐴 ⊆ 𝐶 b. c. No es de orden lineal, pues {𝑎} no es comparable con {𝑏} 12. a. |: es reflexiva, pues 𝑎|𝑎 |: es antisimétrica Si 𝑎 ≠ 𝑏 ⟹ (𝑎|𝑏 ⟹ 𝑏 ∤ 𝑎) |: es transitiva, 𝑎|𝑏 ⇒ 𝑏 = 𝑎𝑞 1 y 𝑏|𝑐 ⇒ 𝑐 = 𝑏𝑞 2 ⇒ 𝑐 = (𝑎𝑞 1 )𝑞 2 = 𝑎(𝑞 1 𝑞 2 ) ⇒ 𝑎|𝑐 b. 𝐷 60 = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} d. 1 8 5 3 4 2 1 2 30 1 5 24 6 1 0 1 20 60 40 20