Matriz lógica

Matriz de valores de verdad binarios

Una matriz lógica , matriz binaria , matriz de relación , matriz booleana o matriz (0, 1) es una matriz con entradas del dominio booleano B = {0, 1}. Una matriz de este tipo se puede utilizar para representar una relación binaria entre un par de conjuntos finitos . Es una herramienta importante en matemáticas combinatorias y en informática teórica .

Representación matricial de una relación

Si R es una relación binaria entre los conjuntos indexados finitos X e Y (por lo que RX × Y ), entonces R puede representarse por la matriz lógica M cuyos índices de fila y columna indexan los elementos de X e Y , respectivamente, de modo que las entradas de M están definidas por

metro i , yo = { 1 ( incógnita i , y yo ) R , 0 ( incógnita i , y yo ) R . {\displaystyle m_{i,j}={\begin{cases}1&(x_{i},y_{j})\en R,\\0&(x_{i},y_{j})\no \en R.\end{cases}}}

Para designar los números de fila y columna de la matriz, los conjuntos X e Y se indexan con números enteros positivos : i varía de 1 a la cardinalidad (tamaño) de X , y j varía de 1 a la cardinalidad de Y. Consulte el artículo sobre conjuntos indexados para obtener más detalles.

Ejemplo

La relación binaria R en el conjunto {1, 2, 3, 4} se define de modo que aRb se cumple si y solo si a divide a b de manera exacta, sin residuo. Por ejemplo, 2 R 4 se cumple porque 2 divide a 4 sin dejar residuo, pero 3 R 4 no se cumple porque cuando 3 divide a 4, queda un residuo de 1. El siguiente conjunto es el conjunto de pares para los que se cumple la relación R.

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

La representación correspondiente como matriz lógica es

( 1 1 1 1 0 1 0 1 0 0 1 0 0 0 0 1 ) , {\displaystyle {\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}},}

que incluye una diagonal de unos, ya que cada número se divide a sí mismo.

Otros ejemplos

Algunas propiedades

Multiplicación de dos matrices lógicas utilizando álgebra de Boole .

La representación matricial de la relación de igualdad en un conjunto finito es la matriz identidad I , es decir, la matriz cuyas entradas en la diagonal son todas 1, mientras que las demás son todas 0. De manera más general, si la relación R satisface I ⊆ R , entonces R es una relación reflexiva .

Si el dominio booleano se considera como un semianillo , donde la adición corresponde a la operación OR lógica y la multiplicación a la operación AND lógica , la representación matricial de la composición de dos relaciones es igual al producto matricial de las representaciones matriciales de estas relaciones. Este producto se puede calcular en un tiempo esperado O( n 2 ). [2]

Con frecuencia, las operaciones con matrices binarias se definen en términos de aritmética modular módulo 2, es decir, los elementos se tratan como elementos del cuerpo de Galois . Surgen en una variedad de representaciones y tienen una serie de formas especiales más restringidas. Se aplican, por ejemplo, en la satisfacibilidad XOR . GRAMO F ( 2 ) = O 2 {\displaystyle {\mathbf {GF}}(2)=\mathbb {Z} _{2}}

El número de matrices binarias m por n distintas es igual a 2mn y, por lo tanto, es finito.

Enrejado

Sean n y m y sea U el conjunto de todas las matrices lógicas m × n . Entonces U tiene un orden parcial dado por

A , B , A B cuando i , yo A i yo = 1 B i yo = 1. {\displaystyle \para todo A,B\en U,\quad A\leq B\quad {\text{cuando}}\quad \para todo i,j\quad A_{ij}=1\implies B_{ij}=1.}

De hecho, U forma un álgebra de Boole con las operaciones y & o entre dos matrices aplicadas componente por componente. El complemento de una matriz lógica se obtiene intercambiando todos los ceros y unos por su opuesto.

Toda matriz lógica A = ( A ij ) tiene una transpuesta A T = ( A ji ). Supongamos que A es una matriz lógica sin columnas ni filas idénticamente cero. Entonces, el producto de matrices, utilizando aritmética booleana, contiene la matriz identidad m × m , y el producto contiene la matriz identidad n × n . A yo A {\displaystyle A^{\operatorname {T} }A} A A yo {\displaystyle AA^{\nombre del operador {T} }}

Como estructura matemática, el álgebra de Boole U forma una red ordenada por inclusión ; además es una red multiplicativa debido a la multiplicación de matrices.

Toda matriz lógica en U corresponde a una relación binaria. Estas operaciones enumeradas en U y el ordenamiento corresponden a un cálculo de relaciones , donde la multiplicación de matrices representa la composición de relaciones . [3]

Vectores lógicos

Estructuras de tipo grupal
TotalDe asociaciónIdentidadCancelaciónConmutativo
magma parcialInnecesarioInnecesarioInnecesarioInnecesarioInnecesario
SemigrupoideInnecesarioRequeridoInnecesarioInnecesarioInnecesario
Categoría pequeñaInnecesarioRequeridoRequeridoInnecesarioInnecesario
GrupoideInnecesarioRequeridoRequeridoRequeridoInnecesario
Grupoide conmutativoInnecesarioRequeridoRequeridoRequeridoRequerido
MagmaRequeridoInnecesarioInnecesarioInnecesarioInnecesario
Magma conmutativoRequeridoInnecesarioInnecesarioInnecesarioRequerido
CuasigrupoRequeridoInnecesarioInnecesarioRequeridoInnecesario
Cuasigrupo conmutativoRequeridoInnecesarioInnecesarioRequeridoRequerido
Magma unitarioRequeridoInnecesarioRequeridoInnecesarioInnecesario
Magma unitario conmutativoRequeridoInnecesarioRequeridoInnecesarioRequerido
BucleRequeridoInnecesarioRequeridoRequeridoInnecesario
Bucle conmutativoRequeridoInnecesarioRequeridoRequeridoRequerido
SemigrupoRequeridoRequeridoInnecesarioInnecesarioInnecesario
Semigrupo conmutativoRequeridoRequeridoInnecesarioInnecesarioRequerido
Cuasigrupo asociativoRequeridoRequeridoInnecesarioRequeridoInnecesario
Cuasigrupo conmutativo y asociativoRequeridoRequeridoInnecesarioRequeridoRequerido
MonoideRequeridoRequeridoRequeridoInnecesarioInnecesario
Monoide conmutativoRequeridoRequeridoRequeridoInnecesarioRequerido
GrupoRequeridoRequeridoRequeridoRequeridoInnecesario
Grupo abelianoRequeridoRequeridoRequeridoRequeridoRequerido

Si m o n es igual a uno, entonces la matriz lógica m × n ( m ij ) es un vector lógico o una cadena de bits . Si m = 1, el vector es un vector fila, y si n = 1, es un vector columna. En cualquier caso, el índice igual a 1 se omite de la denotación del vector.

Supongamos que y son dos vectores lógicos. El producto externo de P y Q da como resultado una relación rectangular de m × n ( PAG i ) , i = 1 , 2 , , metro {\displaystyle (P_{i}),\,i=1,2,\ldots ,m} ( Q yo ) , yo = 1 , 2 , , norte {\displaystyle (Q_{j}),\,j=1,2,\ldots ,n}

metro i yo = PAG i Q yo . {\displaystyle m_{ij}=P_{i}\land Q_{j}.}

Un reordenamiento de las filas y columnas de dicha matriz puede reunir todos los unos en una parte rectangular de la matriz. [4]

Sea h el vector de todos los unos. Entonces, si v es un vector lógico arbitrario, la relación R = vh T tiene filas constantes determinadas por v . En el cálculo de relaciones, un R de este tipo se denomina vector. [4] Un caso particular es la relación universal . yo yo yo {\displaystyle hh^{\nombre del operador {T} }}

Para una relación dada R , una relación rectangular máxima contenida en R se denomina concepto en R . Las relaciones se pueden estudiar descomponiéndolas en conceptos y luego observando la red de conceptos inducida .

Considere la tabla de estructuras similares a grupos, donde "innecesario" puede denotarse por 0 y "requerido" por 1, formando una matriz lógica Para calcular elementos de , es necesario usar el producto interno lógico de pares de vectores lógicos en filas de esta matriz. Si este producto interno es 0, entonces las filas son ortogonales. De hecho, la categoría pequeña es ortogonal al cuasigrupo y el grupoide es ortogonal al magma . En consecuencia, hay ceros en , y no puede ser una relación universal . R . {\estilo de visualización R.} R R yo {\displaystyle RR^{\nombre del operador {T} }} R R yo {\displaystyle RR^{\nombre del operador {T} }}

Sumas de filas y columnas

La suma de todos los unos en una matriz lógica se puede lograr de dos maneras: primero sumando las filas o primero sumando las columnas. Cuando se suman las sumas de las filas, la suma es la misma que cuando se suman las sumas de las columnas. En geometría de incidencia , la matriz se interpreta como una matriz de incidencia con las filas correspondientes a "puntos" y las columnas como "bloques" (generalizando líneas hechas de puntos). Una suma de filas se llama su grado de punto , y una suma de columnas es el grado de bloque . La suma de los grados de los puntos es igual a la suma de los grados de los bloques. [5]

Un problema temprano en el área fue "encontrar condiciones necesarias y suficientes para la existencia de una estructura de incidencia con grados de puntos y grados de bloques dados; o en lenguaje matricial, para la existencia de una matriz (0, 1) de tipo v  ×  b con sumas de filas y columnas dadas". [5] Este problema se resuelve mediante el teorema de Gale-Ryser .

Véase también

Notas

  1. ^ Petersen, Kjeld (8 de febrero de 2013). "Binmatriz" . Consultado el 11 de agosto de 2017 .
  2. ^ O'Neil, Patrick E.; O'Neil, Elizabeth J. (1973). "Un algoritmo de tiempo esperado rápido para la multiplicación de matrices booleanas y el cierre transitivo". Información y control . 22 (2): 132–8. doi :10.1016/s0019-9958(73)90228-3.— El algoritmo se basa en que la adición es idempotente , cf. p. 134 (abajo).
  3. ^ Copilowish, Irving (diciembre de 1948). "Desarrollo matricial del cálculo de relaciones". Journal of Symbolic Logic . 13 (4): 193–203. doi :10.2307/2267134. JSTOR  2267134.
  4. ^ ab Schmidt, Gunther (2013). "6: Relaciones y vectores". Matemáticas relacionales . Cambridge University Press. pág. 91. doi :10.1017/CBO9780511778810. ISBN 978-0-511-77881-0.
  5. ^ ab Por ejemplo, véase Beth, Thomas; Jungnickel, Dieter ; Lenz, Hanfried (1999). "I. Ejemplos y definiciones básicas". Teoría del diseño . Enciclopedia de matemáticas y sus aplicaciones . Vol. 69 (2.ª ed.). Cambridge University Press . pág. 18. doi :10.1017/CBO9780511549533.001. ISBN . 978-0-521-44432-3.

Referencias

  • Brualdi, Richard A. (2006). "Clases de matrices combinatorias". Enciclopedia de matemáticas y sus aplicaciones . Vol. 108. Cambridge University Press. doi :10.1017/CBO9780511721182. ISBN . 978-0-521-86565-4.
  • Brualdi, Richard A.; Ryser, Herbert J. (1991). "Teoría de matrices combinatorias". Enciclopedia de matemáticas y sus aplicaciones . Vol. 39. Cambridge University Press. doi :10.1017/CBO9781107325708. ISBN. 0-521-32265-0.
  • Botha, JD (2013), "31. Matrices sobre campos finitos §31.3 Matrices binarias", en Hogben, Leslie (ed.), Handbook of Linear Algebra (Matemáticas discretas y sus aplicaciones) (2.ª ed.), Chapman & Hall/CRC, doi :10.1201/b16113, ISBN 978-0-429-18553-3
  • Kim, Ki Hang (1982), Teoría de matrices booleanas y aplicaciones , Dekker, ISBN 978-0-8247-1788-9
  • Ryser, HJ (1957). "Propiedades combinatorias de matrices de ceros y unos". Revista Canadiense de Matemáticas . 9 : 371–7.
  • Ryser, HJ (1960). "Trazas de matrices de ceros y unos". Revista Canadiense de Matemáticas . 12 : 463–476. doi :10.4153/CJM-1960-040-0.
  • Ryser, HJ (1960). "Matrices de ceros y unos" (PDF) . Boletín de la Sociedad Matemática Americana . 66 : 442–464.
  • Fulkerson, DR (1960). "Matrices cero-uno con traza cero" (PDF) . Pacific Journal of Mathematics . 10 : 831–6.
  • Fulkerson, DR; Ryser, HJ (1961). "Anchos y alturas de matrices (0, 1)". Revista Canadiense de Matemáticas . 13 : 239–255. doi :10.4153/CJM-1961-020-3.
  • Ford Jr., LR ; Fulkerson, DR (2016) [1962]. "II. Teoremas de viabilidad y aplicaciones combinatorias §2.12 Matrices compuestas de 0 y 1". Flujos en redes . Princeton University Press . págs. 79–91. doi :10.1515/9781400875184-004. ISBN 9781400875184.Sr. 0159700  .
Obtenido de "https://es.wikipedia.org/w/index.php?title=Matriz_lógica&oldid=1256839045"