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:

${displaystyle A={egin{pmatrix}a_{11}&a_{12}&a_{13}&.&.&.&a_{1m}\a_{21}&a_{22}&a_{23}&.&.&.&a_{2m}\a_{31}&a_{32}&a_{33}&.&.&.&a_{3m}\.&.&.&.&.&.&.\.&.&.&.&.&.&.\.&.&.&.&.&.&.\a_{n1}&a_{n2}&a_{n3}&.&.&.&a_{nm}\end{pmatrix}}}$

Donde a_ij = 0 o a_ij = 1.

Ejemplos de matrices booleanas son las siguientes:

${displaystyle {egin{bmatrix}1&0\1&0\0&0end{bmatrix}}quad {egin{bmatrix}0&1&0\1&0&0\0&0&1end{bmatrix}}}$

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. Se define ${displaystyle Avee B=C}$ la unión de A y B, por:

${displaystyle C[i,j]={egin{cases}1,&{mbox{si }}A[i,j]=1 {o }B[i,j]=1\0,&{mbox{si }}A[i,j]=B[i,j]=0end{cases}}}$

Sean A, B y C matrices booleanas de nxm elementos. Se define ${displaystyle Aland B=C}$ la intersección de A y B, por:

${displaystyle C[i,j]={egin{cases}1,&{mbox{si }}A[i,j]=B[i,j]=1\0,&{mbox{si }}A[i,j]=0 {o }B[i,j]=0end{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:

${displaystyle {egin{bmatrix}1&0\0&1end{bmatrix}}+{egin{bmatrix}0&1\0&1end{bmatrix}}={egin{bmatrix}1&1\0&2end{bmatrix}}}$

Sin embargo, si se consideran las operaciones no sobre números reales sino sobre elementos del cuerpo de característica 2 ${displaystyle scriptstyle mathbb {Z} _{2} = {{ar {0}},{ar {1}}}}$ queda garantizado que cualquier operación entre matrices booleana es boolena. Para el ejemplo anterior se tiene:

${displaystyle {egin{bmatrix}{ar {1}}&{ar {0}}\{ar {0}}&{ar {1}}end{bmatrix}}+{egin{bmatrix}{ar {0}}&{ar {1}}\{ar {0}}&{ar {1}}end{bmatrix}}={egin{bmatrix}{ar {1}}&{ar {1}}\{ar {0}}&{ar {0}}end{bmatrix}}}$

Dada relación binaria ${displaystyle {mathcal {R}}}$ sobre un conjunto de n elementos ${displaystyle {a_{1},dots ,a_{n}}}$, 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}={egin{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:

${displaystyle {egin{bmatrix}0&1&0&0&1&0\1&0&1&0&1&0\0&1&0&1&0&0\0&0&1&0&1&1\1&1&0&1&0&0\0&0&0&1&0&0end{bmatrix}}}$

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.