MA265 Sesión 2.1 Cuantificadores[Libro]

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 Matrices Booleanas CONTENIDO Unidad 1: PRELIMINARES 1.2 Matrices booleanas: ▪ Operaciones con matrices booleanas ▪ Unión ▪ Conjunción ▪ Producto ▪ Ejercicios propuestos UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 Introducción Si vamos a una agencia de viajes y preguntamos si va directo de una ciudad a otra; podemos modelar esta información con matrices booleanas. Ponemos cero si no va directamente y uno si va, de esa manera practica lo manipulamos. La pregunta que surge es si no va directamente, pero hace escala en otras ciudades antes de llegar al destino; podría hacer una escala, dos escalas, tres escalas y así sucesivamente. Estas interrogantes lo trataremos más adelante. Matrices Una matriz es un arreglo bidimensional de números. Dicho arreglo es de forma rectangular, formado por filas y columnas. Veamos un ejemplo de matriz. 𝐴 = ( 2 3 −4 1 4 0 ) Cada uno de los números que conforma una matriz se le llama elementos, así los elementos de dicha matriz son 2, 3, -4, 1, 4, 0. El número de filas y columna de una matriz se denomina dimensión de una matriz. En nuestro ejemplo vemos que la matriz A tiene 2 filas y 3 columnas, así decimos que la dimensión de la matriz A es de 2x3. UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 Una matriz A de m filas y n columnas la podemos denotar como 𝐴 𝑚×𝑛 . La matriz 𝐴 de orden 𝑚𝑥𝑛 , se puede abreviar de la siguiente forma 𝐴 = (𝑎 𝑖𝑗 ) , con i=1,2,..,m, j=1,2,….,n. El subíndice indica la posición del elemento dentro de la matriz. El primer índice i indica la fila y el segundo índice j indica la columna. Transpuesta de una matriz: Dada la matriz 𝐴 = [𝑎 𝑖𝑗 ] 𝑚𝑥𝑛 . Se define la Matriz transpuesta de 𝐴 como 𝐴 𝑇 = [𝑎 𝑗𝑖 ] 𝑛𝑥𝑚 . Ejemplo 𝐴 = [ 1 0 0 1 1 1 0 1 0 ] ⇒ 𝐴 𝑇 = [ 1 1 0 0 1 1 0 1 0 ] Matrices booleanas La matriz 𝐴 de orden 𝑚𝑥𝑛 es una matriz booleana si en cada uno de sus elementos son ceros o unos. Ejemplo 𝐴 = [ 1 0 0 1 1 1 0 1 0 0 0 1 ] 3𝑥4 Ejemplo 𝐴 = [ 1 0 0 1 1 1 0 1 0 ] ⇒ 𝐴 𝑇 = [ 1 1 0 0 1 1 0 1 0 ] UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 4 Operaciones con Matrices booleanas Unión Sean 𝐴 = [𝑎 ij ] y 𝐵 = [𝑏 ij ] matrices booleanas de orden m × n . La unión de A y B, simbolizada por: 𝐴 ∨ 𝐵 = 𝐶 = [𝐶 𝑖𝑗 ] 𝑚𝑥𝑛 Se define como: 𝐶 𝑖𝑗 = { 1, 𝑠𝑖 𝑎 𝑖𝑗 = 1 𝑜 𝑏 𝑖𝑗 = 1 0, 𝑠𝑖 𝑎 𝑖𝑗 𝑦 𝑏 𝑖𝑗 𝑠𝑜𝑛 𝑎𝑚𝑏𝑜𝑠 𝑐𝑒𝑟𝑜𝑠 Ejemplo Dados las matrices A y B halle la unión 𝐴 = [ 1 0 1 0 0 1 0 1 1 1 0 0 ] , 𝐵 = [ 0 1 1 0 1 1 0 0 1 0 0 1 ] Solución : Para hallar la unión 𝐴 ∨ 𝐵 , tomaremos la regla de correspondencia 𝐶 𝑖𝑗 anterior 𝐴 ∨ 𝐵 = [ 1 ∨ 0 0 ∨ 1 1 ∨ 1 0 ∨ 0 0 ∨ 1 1 ∨ 1 0 ∨ 0 1 ∨ 0 1 ∨ 1 1 ∨ 0 0 ∨ 0 0 ∨ 1 ] ⇒ 𝐴 ∨ 𝐵 = [ 1 1 1 0 1 1 0 1 1 1 0 1 ] Conjunción Sean 𝐴 = [𝑎 ij ] y 𝐵 = [𝑏 ij ] matrices booleanas de orden m × n . La conjunción de A y B, simbolizada por: 𝐴 ∧ 𝐵 = 𝐶 = [𝐶 𝑖𝑗 ] 𝑚𝑥𝑛 Se define como: 𝐶 𝑖𝑗 = { 1, 𝑠𝑖 𝑎 𝑖𝑗 𝑦 𝑏 𝑖𝑗 𝑠𝑜𝑛 𝑎𝑚𝑏𝑜𝑠 1 0, 𝑠𝑖 𝑎 𝑖𝑗 = 0 𝑜 𝑏 𝑖𝑗 = 0 Ejemplo Dados las matrices A y B halle la conjunción de ambas matrices. 𝐴 = [ 1 0 1 0 1 0 1 1 0 0 1 1 ] , 𝐵 = [ 1 1 0 1 1 1 0 1 1 1 0 1 ] UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 5 Solución : Para hallar la conjunción 𝐴 ∧ 𝐵 , tomaremos la regla de correspondencia 𝐶 𝑖𝑗 anterior 𝐴 ∧ 𝐵 = [ 1 ∧ 1 0 ∧ 1 1 ∧ 0 0 ∧ 1 1 ∧ 1 0 ∧ 1 1 ∧ 0 1 ∧ 1 0 ∧ 1 0 ∧ 1 1 ∧ 0 1 ∧ 1 ] ⇒ 𝐴 ∧ 𝐵 = [ 1 0 0 0 1 0 0 1 0 0 0 1 ] Producto Sean 𝐴 = [𝑎 ij ] y 𝐵 = [𝑏 ij ] matrices booleanas de orden m × p y p × n respectivamente . El producto de A y B, simbolizado por: 𝐴 ⊙ 𝐵 = 𝐶 = [𝐶 𝑖𝑗 ] 𝑚𝑥𝑛 Se define como: 𝐶 𝑖𝑗 = { 1, 𝑠𝑖 𝑎 𝑖𝑘 = 1 𝑦 𝑏 𝑘𝑖 = 1 , 𝑝𝑎𝑟𝑎 𝑎𝑙𝑔ú𝑛 𝑘, 1 ≤ 𝑘 ≤ 𝑝 0, 𝑒𝑛 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜 Importante Una fila por una columna de igual número de elementos. [0 1 0 1] ⊙ [ 1 0 0 1 ] Si…