Upload
roger-martinez-dx
View
330
Download
2
Embed Size (px)
Citation preview
Matriz booleanaDe Wikipedia, la enciclopedia libreSaltar 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:
Donde aij = 0 o aij = 1.
Contenido
[ocultar]
1 Ejemplos 2 Operaciones con matrices booleanas
o 2.1 Unión / Disyunción o 2.2 Intersección / Conjunción o 2.3 Otras operaciones matriciales
3 Matriz booleana asociada a una relación
[editar] Ejemplos
Ejemplos de matrices booleanas son las siguientes:
[editar] 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.
[editar] Unión / Disyunción
Sean A, B y C matrices booleanas de nxm elementos. Se define la unión de A y B, por:
[editar] Intersección / Conjunción
Sean A, B y C matrices booleanas de nxm elementos. Se define la intersección de A y B, por:
[editar] 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:
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:
[editar] Matriz booleana asociada a una relación
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:
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:
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