LIMBERT LUNA

Ejemplos

Ejemplos de matrices booleanas son las siguientes:

$Descripción: \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

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 $Descripción: A \vee B = C$ la unión de A y B, por:

$Descripción: 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

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

$Descripción: 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

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:

$Descripción: \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 $Descripción: \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:

$Descripción: \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

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

$Descripción: 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}$

Descripción: http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/260px-6n-graf.svg.png

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:

$Descripción: \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

LIMBERT LUNA

LIMBERT LUNA

domingo, 30 de junio de 2013

EJERCICIOS PROPUESTOS

MATRIZ BOOLEANA