Matrices Binarias

UNIDAD 3: MATRICES BINARIAS Y RELACIONES

3.1.1 Definición de Matriz Binaria

Una Matriz es un conjunto de elementos organizados en forma rectangular por filas y columnas. Las matrices tienen aplicaciones en diversas áreas con la geometría y el algebra, pero a nivel de computación se usan fundamentalmente para la representación de arreglos o tablas de información que es una de las formas principales como se introducen los datos en el computador.

Una matriz binaria, es una disposición rectangular de dígitos binarios (0, 1), formada por m filas y n columnas; y al igual que las matrices algebraicas se dice que tienen un orden m x n. Si el número de filas es igual al de columnas, se dice que la matriz es cuadrada. Se denota por letras mayúsculas.

3 x 4 m = 3 filas y n = 4 columnas

La aritmética de matrices binarias se construye con las operaciones binarias y , sobre pares de bits.

b1  b2 = 1 Si b1= b2 = 1 b1  b2 = 1 Si b1= 1 o b2 = 1

b1  b2 = 0 en otro caso b1  b2 = 0 en otro caso

3.1.2 Operaciones con Matrices Binarias

a. Matriz Unión

Sean A = [aij] y B = [bij] matrices binarias m x n, se llama matriz unión de A y B; y se denota por

A B, a la matriz cuyo elemento (i, j) es aij  bij.

Para poder efectuar la matriz unión, ambas matrices deben tener el mismo orden.

Ejemplo:

Hallar la matriz A B:

1 0 1 0 1 0

A = B =

0 1 0 1 1 0

100110 1 1 1

A B = =

011010 1 1 0

b. Matriz Intersección

Sean A = [aiJ] y B = [biJ] matrices binarias m x n, se llama matriz intersección de A y B; y se denota por A B, a la matriz cuyo elemento (i, j) es aiJ  biJ.

Para poder efectuar la matriz intersección, ambas matrices deben tener el mismo orden.

Ejemplo:

Hallar la matriz A B:

1 0 1 0 1 0

A = B =

0 1 0 1 1 0

100110 0 0 0

A B = =

011010 0 1 0

c. Producto Binario de Matrices

Sean A = [aiJ] y B = [biJ] matrices binarias de orden m x k, y k x n respectivamente. El productor binario de A y B, denotado por A B, es la matriz m x n cuyo elemento (i, j) es ciJ, donde:

ciJ = (ai1 b1J) ai2 b2J

Para poder efectuar el producto binario de matrices, el número de columnas de la matriz A debe ser igual al número de filas de la matriz B. Se realiza de forma análoga al producto ordinario de matrices, pero se sustituye la suma por y el producto por .

Ejemplo:

Hallar la matriz A B:

1 0 1 1 0

A = 0 1 B =

1 0 0 1 1

(11)00)11)01)10)01) 10 10 00

A B = (01)10)01)11)00)11) = 00 01 01

(11)00)11)01)10)01) 10 10 00

1 1 0

A B = 0 1 1

1 1 0

d. Potencia Binaria

Sea A una matriz binaria cuadrada y r un entero positivo. La potencia binaria r-esima de A es el producto binario de r factores iguales a A.

A(r) = AAA (r veces)

A(2) = AA

A(3) = A(2) A

3.2.1 Concepto de Relación

Son estructuras discretas utilizadas en matemática para representar las relaciones entre elementos de dos o más conjuntos.

Una Relación Binaria de A en B es un subconjunto de A X B y sus elementos son pares ordenados. Se representa por la letra R y matemáticamente se expresa por:

R = {(a, b) I aA, bB, R  AxB}

3.2.2 Tipos de Relaciones

Las relaciones pueden ser:

a. Relaciones 2-arias o Binarias: Relaciones entre dos conjuntos, relación de A en B (conjuntos distintos) o relación de A en A (Relaciones en un mismo conjunto)

Una relación binaria de A en B es un conjunto R de pares ordenados, en los que el primer elemento de cada par ordenado es un elemento de A y el segundo es un elemento de B.

R = {(a, b) I aA, bB, R  AxB}

Una relación binaria de A en A es un conjunto R de pares ordenados, en los que el primer elemento de cada par ordenado es un elemento de A y el segundo es un elemento de A también.

R = {(a, b) I aA, bA, R  AxA}

b. Relaciones n-arias: Relaciones entre más de dos conjuntos.

Una relación n-aria de A en B en C en.....N es un conjunto R de arreglos ordenados, en los que el primer elemento de cada n-tupla es un elemento de A, el segundo es un elemento de B, el tercero de C y sucesivamente hasta el elemento n-esimo (N).

R = {(a, b, c,…n) I aA, bB, cC,….nN, R  AxBxCx….N}

En algunos casos la relación de A en B se puede denotar por: aRb, lo cual expresa que el par (a, b)  R, se dice que a esta relacionado con b mediante R. Si el par (a, b)  R, se denota por aIRb.

Ejemplo:

Sea A = {0, 1, 2} y B = {a, b}, entonces si se define el subconjunto de pares ordenados R1 = {(0,a), (0,b), (1,a), (2,b)} como una relación de A en B

Ejemplo:

Sea A el conjunto {1, 2, 3, 4}. Que pares ordenados están en la relación:

R = {(a, b) | el elemento a divide al elemento b}

Como (a, b) esta en R si, y solo si, a y b son enteros positivos menores o iguales a 4 tales que a divide a b, se tiene que:

R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}

Ejemplo:

Considérense las siguientes relaciones en el conjunto de enteros:

R1 = {(a, b)| a b}

R2 = {(a, b)| a b}

R3 = {(a, b)| a = b o a = -b}

R4

...