Matriz booleana

Matriz booleana

Una matriz de nxm elementos:


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}

es una matriz booleana si A[j,i] = 0 o A[j,i]=1 para todo i = 1,2,3,...,n y j = 1,2,3,...m.

Contenido

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 / conjunción

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 / Disyunción

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}

Matriz booleana asociada a una relación

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}


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Clausura simétrica — Sea R una relación binaria aplicada sobre un conjunto A, la clausura simétrica o cierre simétrico de R, denotada CS(R), es la relación simétrica más pequeña aplicada sobre A que contiene a R. En otras palabras, CS(R) es la relación binaria que… …   Wikipedia Español

  • Clausura transitiva — La clausura transitiva o cierre transitivo de una relación binaria es la relación binaria más pequeña que siendo transitiva contiene al conjunto de pares de la relación binaria original. La clausura transitiva de una relación se denotada . En… …   Wikipedia Español

  • Algoritmo de Floyd-Warshall — En informática, el algoritmo de Floyd Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de… …   Wikipedia Español

  • Clausura reflexiva — Sea R una relación binaria aplicada sobre un conjunto A, la clausura reflexiva o cierre reflexivo de , denotada , es la relación reflexiva más pequeña aplicada sobre que contiene a . En otras palabras, es …   Wikipedia Español

  • Computación basada en ADN — La Computación basada en ADN consiste en usar moléculas de ADN en vez de procesadores basados en silicio. Las ventajas de la computación por ADN se basan en dos características fundamentales: El gran paralelismo de las hebras de ADN. Muchos de… …   Wikipedia Español

  • CPLD — Un CPLD (del acrónimo inglés Complex Programmable Logic Device) es un dispositivo electrónico. Los CPLD extienden el concepto de un PLD (del acrónimo inglés Programmable Logic Device) a un mayor nivel de integración ya que permite implementar… …   Wikipedia Español

  • Jerga informática — Anexo:Jerga informática Saltar a navegación, búsqueda El lenguaje de la informática está caracterizado por emplear numerosos anglicismos, puesto que el idioma inglés se ha convertido en la lengua franca de la informática. El uso de algunas… …   Wikipedia Español

  • Anexo:Jerga informática — El lenguaje de la informática está caracterizado por emplear numerosos anglicismos, puesto que el idioma inglés se ha convertido en la lengua franca de la informática. El uso de algunas palabras difiere en España e Hispanoamérica. Índice: A B C D …   Wikipedia Español

  • Vuelta Atrás — Este artículo o sección sobre matemáticas necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 29 de mayo de 2011. También puedes… …   Wikipedia Español

  • Problema de la suma de subconjuntos — Saltar a navegación, búsqueda El problema de la suma de subconjuntos es un problema importante en la teoría de la complejidad y en la criptografía. El problema es este: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”