ALGEBRA BOOL

En 1854, George Boole introdujo un tratamiento sistemático de la lógica y desarrolló para este propósito un sistema algebraico que ahora se conoce como álgebra booleana. En 1938, C.E. Shannon introdujo un álgebra booleana de dos valores, denominada álgebra de interruptores, en la cual demostró que las propiedades de los circuitos eléctricos y estables con interruptores pueden representarse con esta álgebra. Para la definición formal del álgebra booleana se emplean los postulados formulados por E. V. Huntington en 1904. Estos postulados o axiomas no son únicos para definir el álgebra booleana. Se han usado otros conjuntos de postulados. Revisemos de qué se trata esto.

2.2.1 Las operaciones del álgebra de Boole

En el álgebra de Boole hay dos operaciones, denotadas con los símbolos + y • pero que ¡no tienen nada que ver con las operaciones que todos conocemos de suma y producto!. ¡No hay que confundirlas!. El + y el • del álgebra de Boole se aplican a bits, es decir, a números que sólo pueden ser el 0 o el 1.

La operación +

Esta operación se define de la siguiente manera:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1

Las tres primeras operaciones nos resultan obvias, son iguales que la suma que conocemos, sin embargo, la expresión 1 + 1 = 1 nos puede resultar chocante. ¿Pero no me habían dicho toda la vida que 1 + 1 = 2?, nos podemos estar preguntando. Sí, pero hay que recordar que aquí estamos utilizando otra operación que no es la suma, la denotamos con el mismo símbolo +, ¡pero no es una suma norma! ¡Hay que cambiar el “chip”! ¡Ahora estamos con álgebra de Boole!

Pasado el pánico inicial, si nos fijamos en esta nueva operación, notamos lo siguiente: El resultado siempre es igual a 1 cuando alguno de los bits sumandos es igual a 1. O lo que es lo mismo, el resultado de esta suma sólo da 0 si los dos bits que estamos sumando son iguales a cero. En caso contrario valdrá 1.

¿Y para qué nos sirve esta operación tan extraña? Veamos un ejemplo. Imaginemos que hay una sala grande a la que se puede acceder a través de dos puertas. En el techo hay una única lámpara y existen dos interruptores de luz, uno al lado de cada puerta de entrada. Como es lógico, la luz se enciende cuando algunos de los dos interruptores (o los dos) se activan. Esto lo podemos expresar mediante una ecuación booleana. Para denotar el estado de uno de los interruptores utilizaremos la variable booleana A, que puede valer 0 (interruptor apagado) o 1 (interruptor activado). Para el otro interruptor usaremos la variable B. Y para el estado de la luz, 0 (apagada) y 1 encendida, usaremos la variable F. El estado en el que se encuentra la luz, en función de cómo estén los interruptores, viene dado por la ecuación booleana:

F = A + B

que indica que F = 1 (luz encendida) si alguno de los interruptores está a 1 (activado).

Ya lo veremos más adelante, pero podemos ir adelantando unas propiedades muy interesantes.

Si A es una variable booleana, se cumple:

A + A = A
1 + A = 1
0 + A = A

La operación •

Esta operación se define así:

0 • 0 = 0
0 • 1 = 0
1 • 0 = 0
1 • 1 = 1

En este caso, la operación es más intutitiva, puesto que es igual que el producto de números reales. Si nos fijamos, vemos que el resultado sólo vale 1 cuando los dos bits están a 1, o visto de otra manera, el resultado es 0 cuando alguno de los dos bits es 0.

Vamos a ver un ejemplo. Imaginemos una caja de seguridad de un banco que sólo se abre cuando se han introducido dos llaves diferentes, una la tiene el director y la otra el jefe de seguridad. Si sólo se introduce una de ellas, la caja no se abrirá. Modelaremos el problema así.

Utilizaremos la variable A para referirnos a una de las llaves (0 no introducida, 1 introducida) y la variable B para la otra llave. Con la variable F expresamos el estado de la caja de seguridad (0 cerrada y 1 abierta). El estado de la caja lo podemos expresar con la ecuación:

F = A • B

que indica que la caja se abrirá (F = 1) sólo si A = 1 (una llave introducida) y B = 1 (la otra llave introducida). En cualquier otro caso, F = 0, y por tanto la caja no se abrirá.

Podemos ir adelantando algunas propiedades de esta operación:

A • A = A
A • 0 =0
A • 1 =1

La negación.

La operación de negación nos permite obtener el estado complementario del bit o variable booleana al que se lo aplicamos. Se define de la siguiente manera:

Es decir, que si se lo aplicamos a 0 obtenemos 1 y si se lo aplicamos al 1 obtenemos 0. Esta operación nos permite cambiar el estado de una variable booleana. Si A es una variable booleana, Ā tiene el estado contrario

2.2.2 Las propiedades del álgebra de Boole

Las operaciones del álgebra de Boole las podemos definir utilizando tablas de verdad:

Operación +

Operación •

Las propiedades del álgebra de Boole son las siguientes:

1. Las operaciones + y • son conmutativas:

2. Elemento neutro.

A + 0 = A
A • 1 = A

3. Distributiva.

4. Elemento inverso

Operación de negación definida por:

2.2.3 Teoremas importantes

Derivados de las propiedades fundamentales, existe una serie de teoremasmuy interesantes e importantes que usaremos a lo largo de todo el curso. Algunos los utilizaremos en la teoría y otros para los problemas.

Asociatividad

Idempotencia

Ley de absorción

Este teorema es muy importante puesto que nos permite realizar simplificaciones en las expresiones.

Leyes de De Morgan

Este teorema es también muy importante y lo usaremos constantemente. Vamos a hacer algunos ejemplos para aprender a utilizarlo:

Teorema de Shannon

Este teorema es una generalización de las leyes de DeMorgan. Lo que nos dice es que si tenemos cualquier expresión booleana negada, es igual a la misma expresión en la que todas las variables estén negadas y en la que se sustituyan las operaciones + por • y viceversa.

Veamos algunos ejemplos:

En este ejemplo se podrían haber aplicado las leyes de DeMorgan sucesivas veces, como hemos hecho en ejemplos anteriores, sin embargo, podemos aplicar el teorema de Shannon.

Teorema de expansión

Este teorema es más teórico y no tiene aplicación directa en los problemas.