Matriz lógica

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

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

${\displaystyle m_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R,\\0&(x_{i},y_{j})\not \in R.\end{cases}}}$

Para designar los números de fila y columna de la matriz, los conjuntos X e Y se indexan con 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.

La transposición${\displaystyle R^{T}}$de la matriz lógica${\displaystyle R}$de una relación binaria corresponde a la relación inversa . ^{[ 1 ]}

• Una matriz de permutación es una matriz (0, 1), cuyas columnas y filas tienen exactamente un elemento distinto de cero.
  • Una matriz de Costas es un caso especial de una matriz de permutación.
• En combinatoria y geometría finita, una matriz de incidencia tiene unos para indicar la incidencia entre puntos (o vértices) y líneas de una geometría, bloques de un diseño de bloques o aristas de un grafo .
• Una matriz de diseño en el análisis de varianza es una matriz (0, 1) con sumas de filas constantes.
• En teoría de grafos , una matriz lógica puede representar una matriz de adyacencia : las matrices no simétricas corresponden a grafos dirigidos , las matrices simétricas a grafos ordinarios , y un 1 en la diagonal corresponde a un bucle en el vértice correspondiente.
• La matriz de biadyacencia de un grafo bipartito simple y no dirigido es una matriz (0, 1), y cualquier matriz (0, 1) surge de esta manera.
• Los factores primos de una lista de m números n - suaves y libres de cuadrados se pueden describir como una matriz m × π ( n ) (0, 1), donde π es la función de conteo de primos y a _ij es 1 si y solo si el j -ésimo primo divide al i- ésimo número. Esta representación es útil en el algoritmo de factorización por criba cuadrática .
• Una imagen de mapa de bits que contiene píxeles de solo dos colores se puede representar como una matriz (0, 1) en la que los ceros representan píxeles de un color y los unos representan píxeles del otro color.
• Se puede utilizar una matriz binaria para comprobar las reglas del juego de Go . ^{[ 2 ]}
• La lógica de cuatro valores de dos bits, transformada por matrices lógicas de 2 × 2, forma un sistema de transición .
• Un diagrama de recurrencia y sus variantes son matrices que muestran qué pares de puntos están más cerca que un cierto umbral de vecindad en un espacio de fase .

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 suma corresponde a la operación lógica OR y la multiplicación a la operación lógica AND , la representación matricial de la composición de dos relaciones es igual al producto matricial de las representaciones matriciales de dichas relaciones. Este producto se puede calcular en ^un tiempo esperado O( n² ). ^{[ 3 ]}

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.${\displaystyle {\mathbf {GF}}(2)=\mathbb {Z} _{2}}$Se presentan en diversas representaciones y tienen varias formas especiales más restringidas. Se aplican, por ejemplo, en la satisfacibilidad XOR .

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

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

${\displaystyle \forall A,B\in U,\quad A\leq B\quad {\text{cuando}}\quad \forall i,j\quad A_{ij}=1\implies B_{ij}=1.}$

De hecho, U forma un álgebra booleana con las operaciones AND y OR aplicadas componente a componente entre dos matrices. El complemento de una matriz lógica se obtiene intercambiando todos los ceros y unos por sus opuestos.

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

Como estructura matemática, el álgebra booleana U forma un retículo ordenado por inclusión ; además, es un retículo multiplicativo debido a la multiplicación de matrices.

Cada 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 . ^{[ 4 ]}

Si m o n es igual a uno, 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 ambos casos, el índice igual a 1 se omite en la representación del vector.

Suponer${\displaystyle (P_{i}),\,i=1,2,\ldots ,m}$y${\displaystyle (Q_{j}),\,j=1,2,\ldots ,n}$son dos vectores lógicos. El producto exterior de P y Q da como resultado una relación rectangular m × n.

${\displaystyle m_{ij}=P_{i}\land Q_{j}.}$

Una reordenación de las filas y columnas de dicha matriz puede ensamblar todos los unos en una parte rectangular de la matriz. ^{[ 5 ]}

Sea h el vector de 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, tal R se llama vector. ^{[ 5 ]} Un caso particular es la relación universal.${\displaystyle hh^{\operatorname {T} }}$.

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

Consideremos la tabla de estructuras tipo grupo, donde "innecesario" se puede denotar con 0 y "requerido" con 1, formando una matriz lógica.${\displaystyle R.}$Para calcular elementos de${\displaystyle RR^{\operatorname {T} }}$Es necesario utilizar el producto interno lógico de pares de vectores lógicos en las 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${\displaystyle RR^{\operatorname {T} }}$y no es una relación universal .

La suma de todos los unos en una matriz lógica puede realizarse de dos maneras: sumando primero las filas o sumando primero las columnas. Al sumar las sumas de las filas, el resultado es el mismo que al sumar las sumas de las columnas. En geometría de incidencia , la matriz se interpreta como una matriz de incidencia donde las filas corresponden a "puntos" y las columnas a "bloques" (generalizando líneas formadas por puntos). La suma de una fila se denomina grado de punto , y la suma de una columna, grado de bloque . La suma de los grados de los puntos es igual a la suma de los grados de los bloques. ^{[ 6 ]}

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

• Lista de matrices
• Binatorix (un toro binario de De Bruijn)
• Matriz de bits
• Matriz disjunta
• Matriz de Redheffer
• Tabla de verdad
• Lógica trivalente

• "Matriz lógica" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]