Matrices

Matrices Booleanas 

Las Matrices Booleanas están constituidas por 0 y 1 , son frecuentemente usadas para representar estructuras discretas como las relaciones.

Definición: Una Matriz Booleana es una Matrix "m*n" en los que sus elementos son 0 y 1.

REPRESENTACIÓN DE LA RELACIÓN A TRAVÉS DE MATRICES

Si los conjuntos entre los cuales están definidas las relaciones son muy grandes, los diagramas no resultan prácticos. Además, para poder representar relaciones en una computadora, necesitamos una forma algebraica de representación. Para ello, recurrimos a las matrices booleanas.

Operaciones : Unión e Intersección

Sea  A = [a(m*n)] y B = [b(m*n)] ambas matrices booleanas podremos realizar la Unión o Intercepción.

NOTA : Observe que A y B son matrices del mismo tamaño.

1) A v B = C =[c[ij]] La Unión (Disyunción) de A y B esta dada por:

2) A ∧ B = D =[d[ij]] La Intersección (Conjunción) de A y B esta dada por:

Miremos un ejemplo de Unión e Intersección de Matrices Booleanas:

CALCULE: La Unión e Intersección:

SOLUCION:

Para la Unión tenemos:

Para la Intersección tenemos:

Operaciones : Producto Booleano

Sea dos Matrices Booleanas  A = [a(ij)] (m*p) y B = [b(ij)] (p*n). El Producto Booleano de A y B será la  Matriz C (m*n) cuyos elementos están dados por:

Note que esta operación es idéntica a la multiplicación matricial ordinaria donde: La adición es sustituida por "v" y la multiplicación es sustituida por "∧".

Ejemplo de Producto Booleano:

Encuentre el Producto Booleano de A y B:

SOLUCION:

Primero anotamos como seria el producto de estas 2 Matrices.

Luego resolvemos la Uniones y posterior a ello la Intersecciones.

Note que el numero de columnas de A debe ser igual al numero de filas de B.

Potencia Booleana r-enésima

Antes que nada, debemos recordar que la potencia de una matriz no siempre se puede calcular. Sólo es posible cuando la matriz es cuadrada, es decir, cuando tiene el mismo número de filas que de columnas.

La peculiaridad de la potenciación de las matrices es que, en muchas matrices, las potencias siguen un patrón. Por tanto, para muchas matrices, podemos encontrar una fórmula que nos proporcione la potencia n-enésima sin la necesidad de calcular todas las potencias.

Para encontrar esta fórmula, tenemos que fijarnos en:

• La relación entre el exponente de la potencia y los elementos de la matriz. Por ejemplo, puede que algún elemento de la matriz sea el propio exponente.

• La paridad del exponente. Por ejemplo, puede ocurrir que las potencias pares sean de una forma y las impares de otra.

• Si hay distintos patrones. Por ejemplo, los exponentes múltiplos de un número pueden tener un patrón distinto a los que son múltiplos de otro.

• La variación de los signos. Por ejemplo, las potencias pares y las impares pueden cambiar de signos.

• Repetición. Por ejemplo, puede haya varias matrices que se repiten consecutivamente.

En definitiva, para obtener la fórmula tenemos que observar las primeras potencias y emplear nuestra intuición. Normalmente, con el cálculo de las primeras 3 ó 5 potencias, podremos deducir la fórmula.

Ejemplo de Potencia Booleana r-enésima:

  Lógica de Bits(not, and, or, xor)

NOT: La operación NOT también podría ser llamada complemento y es un operador unario. Realiza la negación lógica de cada bit, es decir, invierte su valor. Por ejemplo, la operación NOT 1010 daría como resultado 0101.

AND: La operación AND, o conjunción lógica, funciona de forma similar a una multiplicación: sólo nos devolverá 1 si todas las entradas son 1, en el resto de casos devolvería 0. Es decir 0 AND 0 es igual a 0, 1 AND 0 es igual 0 y solo 1 AND 1 es igual a 1. Por ejemplo: 100111001011010100111010 AND 010110100001101111011000 = 000110000001000100011000.

OR: La operación OR, o disyunción lógica, dará como salida 1 siempre que una o más de sus entradas sean 1. Es decir, 1 OR 1 es igual a 1, 1 OR 0 es igual a 1 y solo 0 OR 0 es igual a 0. Por ejemplo: 1000 OR 0011 = 1011.

XOR: La operación XOR, u OR exclusivo, dará como salida 1 siempre que solo una de las dos entradas sea 1. Es decir, que 0 XOR 0 será igual a 0, 1 XOR 1 será igual a 0 pero 1 XOR 0 o 0 XOR 1 serán igual a 1. Por ejemplo 1010 XOR 1001 = 0011. Dado que es complicado revertir su resultado es muy utilizada en algoritmos de cifrado.

Compuertas lógicas y algebra de Boole

Las Compuertas Lógicas son circuitos electrónicos conformados internamente por transistores que se encuentran con arreglos especiales con los que otorgan señales de voltaje como resultado o una salida de forma booleana, están obtenidos por operaciones lógicas binarias (suma, multiplicación). También niegan, afirman, incluyen o excluyen según sus propiedades lógicas. Estas compuertas se pueden aplicar en otras áreas de la ciencia como mecánica, hidráulica o neumática.

Compuerta AND

Esta compuerta es representada por una multiplicación en el Algebra de Boole. Indica que es necesario que en todas sus entradas se tenga un estado binario 1 para que la salida otorgue un 1 binario.

Compuerta OR

En el Algebra de Boole esta es una suma. Esta compuerta permite que con cualquiera de sus entradas que este en estado binario 1, su salida pasara a un estado 1 también. No es necesario que todas sus entradas estén accionadas para conseguir un estado 1 a la salida pero tampoco causa algún inconveniente.

Compuerta NOT

En este caso esta compuerta solo tiene una entrada y una salida y esta actúa como un inversor. Para esta situación en la entrada se colocara un 1 y en la salida otorgara un 0 y en el caso contrario esta recibirá un 0 y mostrara un 1.

Compuerta NAND

También denominada como AND negada, esta compuerta trabaja al contrario de una AND ya que al no tener entradas en 1 o solamente alguna de ellas, esta concede un 1 en su salida, pero si esta tiene todas sus entradas en 1 la salida se presenta con un 0.

 

Compuerta NOR

Así como vimos anteriormente, la compuerta OR también tiene su versión inversa. Esta compuerta cuando tiene sus entradas en estado 0 su salida estará en 1, pero si alguna de sus entradas pasa a un estado 1 sin importar en qué posición, su salida será un estado 0.

Compuerta XOR

También llamada OR exclusiva, esta actúa como una suma binaria de un digito cada uno y el resultado de la suma seria la salida.

Compuerta XNOR

Esta es todo lo contrario a la compuerta XOR, ya que cuando las entradas sean iguales se presentara una salida en estado 1 y si son diferentes la salida será un estado 0.

Compuerta IF

Esta compuerta no es una muy utilizada o reconocida ya que su funcionamiento en estados lógicos es parecido a si solo hubiera un cable conectado porque exactamente lo que se le coloque en la entrada.

Algebra de Boole

Se denomina así en honor a George Boole, matemático inglés autodidacta, que fue el primero en definirla como parte de un sistema lógico en su libro las leyes del pensamiento en (1854). El álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional.

El álgebra de Boole proporciona las operaciones y las leyes para trabajar en el conjunto [0,1]. Las tres operaciones del algebra de Boole que se usan Habitualmente son: (el Complemento, la suma, y el Producto Booleanos.)

El complemento de un elemento denotado por una barra, o por NOT, se define por 0 = 1 y 1 = 0.

La suma booleana denotada por, + o por OR. Y se la define de la siguiente forma: 1 * 1 = 1, 1 + 0 = 1, 0 + 1 = 1 y 0 + 0 = 0

El producto Booleano denotado por; o por AND se define de la siguiente forma

1 * 1 = 1, 1 * 0 = 0, 0 * 1 = 0 y 0 * 0 = 0.