Matriz booleana

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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:


A = 
\begin{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 aij = 0 o aij = 1.

Ejemplos[editar]

Ejemplos de matrices booleanas son las siguientes:

  \begin{bmatrix}  1 & 0 \\  1 & 0 \\  0 & 0 \end{bmatrix}  \quad
 \begin{bmatrix}  0 & 1 & 0 \\  1 & 0 & 0 \\  0 & 0 & 1 \end{bmatrix}

Operaciones con matrices booleanas[editar]

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[editar]

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

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}

Intersección / Conjunción[editar]

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

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}

Otras operaciones matriciales[editar]

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:

 \begin{bmatrix}  1 & 0 \\  0 & 1 \end{bmatrix} +
\begin{bmatrix}  0 & 1 \\  0 & 1 \end{bmatrix} =
\begin{bmatrix}  1 & 1 \\  0 & 2 \end{bmatrix}

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

 \begin{bmatrix}  \bar{1} & \bar{0} \\  \bar{0} & \bar{1} \end{bmatrix} +
\begin{bmatrix}  \bar{0} & \bar{1} \\  \bar{0} & \bar{1} \end{bmatrix} =
\begin{bmatrix}  \bar{1} & \bar{1} \\  \bar{0} & \bar{0}  \end{bmatrix}

Matriz booleana asociada a una relación[editar]

Dada relación binaria \mathcal{R} 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:

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}

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:

 \begin{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 & 0  \end{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.