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:
Primero anotamos como seria el producto de estas 2 Matrices.
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:
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.