Matriz booleana

Una matriz booleana es una matriz de números cuyas componentes o entradas son exclusivamente ceros o unos. Las matrices booleanas son útiles porque pueden representar objetos abstractos como relaciones binarias o grafos.

Una matriz booleana general de nxm elementos tiene la forma: Plantilla:Ecuación Donde a_ij = 0 o a_ij = 1.

Ejemplos

Ejemplos de matrices booleanas son las siguientes:

$\left[\begin{array}{cc}1& 0\\ 1& 0\\ 0& 0\end{array}\right]\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right]$

Operaciones con matrices booleanas

Las operaciones que se pueden realizar entre matrices booleanas son tres: unión, conjunción y producto booleano. Sin embargo, estas operaciones no pueden realizarse sobre dos matrices cualesquiera, sino que deben cumplir ciertos criterios para poder llevarse a cabo. En particular, en el caso de la unión y la conjunción, las matrices que intervienen en la operación deben tener el mismo tamaño, y en el caso del producto booleano, las matrices deben cumplir con las mismas condiciones que para formar el producto de matrices.

Unión / Disyunción

Sean A, B y C matrices booleanas de nxm elementos. Se define $A\vee B=C$ la unión de A y B, por: Plantilla:Ecuación

Intersección / Conjunción

Sean A, B y C matrices booleanas de nxm elementos. Se define $A\wedge B=C$ la intersección de A y B, por: Plantilla:Ecuación

Otras operaciones matriciales

La traspuesta de una matriz booleana es también otra matriz booleana; pero las operaciones con matrices booleanas no siempre producen matrices booleanas. Un ejemplo de operación que no es interna para las matrices booleanas es la suma: Plantilla:Ecuación Sin embargo, si se consideran las operaciones no sobre números reales sino sobre elementos del cuerpo de característica 2 ${\mathbb{Z}}_2=\{\overline{0},\overline{1}\}$ queda garantizado que cualquier operación entre matrices booleana es boolena. Para el ejemplo anterior se tiene: Plantilla:Ecuación

Matriz booleana asociada a una relación

Dada relación binaria $ℛ$ sobre un conjunto de n elementos $\{a_1,\dots ,a_n\}$, para calcular la clausuara simétrica conviene representar la relación como matriz booleana definida mediante: Plantilla:Ecuación

Diagrama de un grafo con 6 vértices y 7 aristas.

El grafo no dirigido de la figura adjunta puede entenderse como una relación binaria. Dos elementos están relacionados si existe una línea que los una directamente. La matriz asociada a la relación binaria de conexión directa se llama matriz de incidencia, que es una matriz booleana que viene dada por: Plantilla:Ecuación El elemento ij de la anterior matriz es 1 si existe una línea que una directamente los círculos i y j y 0 en caso contrario.