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:
Ejemplos de matrices booleanas son las siguientes:
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.
Sean A, B y C matrices booleanas de nxm elementos.
la unión de A y B, por:
[ i , j ] =
[ i , j ] = 1
[ i , j ] = 1
[ i , j ] =
{\displaystyle C[i,j]={\begin{cases}1,&{\mbox{si }}A[i,j]=1\ {o\ }B[i,j]=1\\0,&{\mbox{si }}A[i,j]=B[i,j]=0\end{cases}}}
Sean A, B y C matrices booleanas de nxm elementos.
la intersección de A y B, por:
{\displaystyle C[i,j]={\begin{cases}1,&{\mbox{si }}A[i,j]=B[i,j]=1\\0,&{\mbox{si }}A[i,j]=0\ {o\ }B[i,j]=0\end{cases}}}
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:
Sin embargo, si se consideran las operaciones no sobre números reales sino sobre elementos del cuerpo de característica 2
queda garantizado que cualquier operación entre matrices booleana es boolena.
Para el ejemplo anterior se tiene:
Dada relación binaria
sobre un conjunto de n elementos
, para calcular la clausuara simétrica conviene representar la relación como matriz booleana definida mediante:
{\displaystyle B_{\mathcal {R}}=[b_{ij}]\quad \land \quad b_{ij}={\begin{cases}1&{\mbox{si}}\ a_{i}{\mathcal {R}}a_{j}\\0&{\mbox{si}}\ \lnot a_{i}{\mathcal {R}}a_{j}\end{cases}}}
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:
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.
