Matriz lógica

Una matriz lógica, una matriz binaria, una matriz de relaciones, una matriz booleana o una (0 , 1)-matrix es una matriz con entradas del dominio booleano B = {0, 1}. Dicha matriz puede ser Se utiliza 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.

Representación matricial de una relación

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

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

Para designar los números de fila y columna de la matriz, los conjuntos X y Y están indexados con números enteros positivos: rangos i 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 sólo si a divide b uniformemente, sin resto. Por ejemplo, 2R4 se cumple porque 2 divide a 4 sin dejar resto, pero 3R4 no se cumple porque cuando 3 divide a 4, queda un resto de 1. El siguiente conjunto es el conjunto de pares para los cuales 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

${\displaystyle {\begin{pmatrix}1 tendría1 tendría1\0 tendría1\0}}}$

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

Otros ejemplos

• Una matriz de permutación es un (0, 1)-matrix, todas cuyas columnas y filas tienen exactamente un elemento no cero.
  • Una matriz de Costas es un caso especial de una matriz de permutación.
• Una matriz de incidencia en combinatoria y geometría finita tiene una incidencia entre puntos (o vértices) y líneas de una geometría, bloques de un diseño de bloques o bordes de un gráfico.
• Una matriz de diseño en análisis de varianza es una (0, 1)-matrix con sumas de fila constantes.
• Una matriz lógica puede representar una matriz de adyacencia en la teoría del gráfico: matrices no simétricas corresponden a gráficos dirigidos, matrices simétricas a gráficos ordinarios, y un 1 en la diagonal corresponde a un bucle en el vértice correspondiente.
• La matriz biadyacency de un gráfico bipartito sencillo y no dirigido es un (0, 1)-matrix, y cualquier (0, 1)-matrix surge de esta manera.
• Los principales factores de una lista m números sin cuadrado, n-smooth se puede describir como un m × π(n) (0, 1)-matrix, donde π es la función de contabilidad principal, y a_ij 1 si y sólo si jth prime divide el inúmero. Esta representación es útil en el algoritmo de factorización de sieve cuadrática.
• Una imagen bitmap que contiene píxeles en sólo dos colores puede ser representado como un (0, 1)-matrix en el que los ceros representan píxeles de un color y los que representan píxeles del otro color.
• Una matriz binaria se puede utilizar para comprobar las reglas del juego en el juego de Go.
• La lógica de cuatro bits, transformada por 2x2 matrices lógicas, forma un sistema de transición.
• Una parcela de recurrencia y sus variantes son matrices que muestran qué pares de puntos están más cerca que un determinado umbral de proximidad en un espacio de fase.

Algunas propiedades

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 ve como un semiring, donde la suma corresponde al OR lógico y la multiplicación al AND lógico, 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 el tiempo esperado O(n²).

Con frecuencia, las operaciones en matrices binarias se definen en términos de módulo aritmético mod 2 – es decir, los elementos se tratan como elementos del campo de Galois ${\displaystyle {\Mathbf}(2)=\mathbb {Z} _{2}$. Se presentan en diversas representaciones y tienen una serie de formas especiales más restringidas. Se aplican, por ejemplo, en XOR-satisfiabilidad.

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

Enrejado

Sean n y m y sea U el conjunto de todos los m × n matrices. Entonces U tiene un orden parcial dado por

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

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

Cada matriz lógica A =A_ij) tiene un transpose A^T =A_ji). Suppose A es una matriz lógica sin columnas o filas idénticamente cero. Luego el producto de matriz, usando aritmética booleana, ${\displaystyle A^{\ nombre del operador {T}A}$ contiene m × m matriz de identidad y el producto ${\displaystyle AA^{\ nombre del operador {T}$ contiene n × n identidad.

Como estructura matemática, el álgebra booleana U forma una red ordenada por inclusión; además, es una red multiplicativa 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 las relaciones.

Vectores lógicos

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

Suppose ${\displaystyle (P_{i}),\,i=1,2,\ldotsm}$ y ${\displaystyle (Q_{j}),\,j=1,2,\ldotsn}$ son dos vectores lógicos. El producto exterior P y Q resultados en un m × n relación rectangular

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

Una reordenación de las filas y columnas de dicha matriz puede ensamblarlas todas en una parte rectangular de la matriz.

Vamos. h ser el vector de todos. Entonces si v es un vector lógico arbitrario, la relación R = v h^T tiene constantes filas determinadas por v. En el cálculo de las relaciones tal R se llama vector. Una instancia particular es la relación universal ${\displaystyle hh^{\ nombre del operador {T}$.

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

Considere la tabla de estructuras similares a grupos, donde "sin necesidad" se puede denotar 0, y "required" denotado por 1, formando una matriz lógica ${\displaystyle R.$ Para calcular elementos de ${\displaystyle RR^{\ nombre del operador {T}$, es necesario utilizar 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 pequeña categoría es ortogonal a quasigroup, y groupoid es ortogonal a magma. En consecuencia, hay ceros en ${\displaystyle RR^{\ nombre del operador {T}$, y no es una relación universal.

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). La suma de una fila se denomina grado de punto y la suma de una columna es el grado de bloque. La suma de los grados de los puntos es igual a la suma de los grados de los bloques.

Uno de los primeros problemas en el área fue “encontrar las condiciones necesarias y suficientes para la existencia de una estructura de incidencia con grados de puntos y grados de bloques determinados; o en lenguaje matricial, para la existencia de una matriz (0, 1) de tipo v × b con sumas de filas y columnas dadas". Este problema se resuelve mediante el teorema de Gale-Ryser.