CSI XVII: El álgebra de Boole

Demasiado tiempo hacía que no escribía acerca de las Cosas que Sí se dan en Informática. Pero mi retiro veraniego me ha despertado del letargo y me ha traído, con el viento levantino, los recuerdos de una de las primeras asignaturas que estudié en la carrera y que constituye una base esencial de la propia informática. Me refiero al Diseño Lógico. Mi idea era ir más allá y hablar de lenguajes de descripción de sistemas electrónicos, que tan olvidados e inútiles les resultan a los informáticos que se decantaron por los lenguajes de alto nivel.

Pero para entender de qué trata éste es necesario disminuir un poco las pretensiones e introducir algo todavía más elemental, que se estudia en el primer curso de la carrera y que, a menos que la especialización te conduzca por áreas de informática industrial o electrónica, se pierde con facilidad. Se trata del Álgebra de Boole, que hoy, en este capítulo de Cosas que Sí se dan en Informática, presentaremos: tanto en su definición matemática, como en su utilidad electrónica.

El Álgebra de Boole toma su nombre de George Boole, matemático y filósofo inglés del s. XIX. Sus estudios acerca de la lógica le llevaron a desarrollar un modelo matemático con el fin de analizar el razonamiento humano y de realizar operaciones con sentencias. De su trabajo surgió la estructura matemática que asigna a cada sentencia el valor de VERDADERO (o 1) y FALSO (o 0) y define las operaciones matemáticas que pueden realizarse sobre estos elementos.

Porque es eso mismo lo que conforma una estructura algebraica: un conjunto de elementos y un conjunto de operaciones definidas sobre los elementos. El álgebra de Boole tiene forma de anillo: esto significa que las operaciones definidas satisfacen ciertas propiedades. En la wikipedia pueden continuar con este tema.

Los elementos del álgebra de Boole son pues dos, que llamaremos 0 y 1. Las operaciones básicas que se pueden realizar sobre estos elementos son 3: disyunción (OR, o suma), conjunción (AND, o multiplicación) y negación (NOT, o inversión). Los dos primeros son operadores binarios, esto es, requieren dos elementos como entrada. La negación se aplica sobre un sólo operando: es unario, pues. Bien, si hasta ahora ha sido sencillo, lo que viene ahora lo es más.

Las tablas de verdad básicas definen el comportamiento de los operadores para las entradas. O lo que es lo mismo: su resultado.

OR A B A OR B 0 0 0 0 1 1 1 0 1 1 1 1

AND A B A AND B 0 0 0 0 1 0 1 0 0 1 1 1

NOT A NOT A 0 1 1 0

Explicar una tabla de verdad es casi innecesario: la primera tabla describe la operación OR: 0 OR 0 da como resultado 0. En cambio, 0 OR 1, 1 OR 0 y 1 OR 1 dan como resultado 1.

Aunque no es adecuado, viene bien evaluar una sentencia disyuntiva a un valor de verdad para acabar de entender la correspondencia lógica. La frase Marta tiene un abrigo azul o tiene una chaqueta colorada es cierta (verdadera: 1) si alguna de las sentencias que la forman -tiene un abrigo azul, tiene una chaqueta colorada- es verdadera. Para que la conjunción sea cierta (Marta tiene un abrigo azul y tiene una chaqueta colorada) es necesario que las dos sentencias individuales -los operandos- sean verdaderos. De este modo se entiende la tabla de verdad de la AND.

XOR

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

Mediante sencillas combinaciones de los tres operadores básicos podemos obtener los operadores derivados, que nos sirven para representar otras relaciones lógicas, entre las que se encuentran la o exclusiva, la implicación o la equivalencia. Es posible que a muchos de los lectores les suene esto, ya que las tablas de verdad son las herramientas empleadas en el estudio de la lógica proposicional, que se cursa típicamente en el instituto. Los operadores derivados más frecuentes tienen sus propios símbolos. En la tabla de al lado se muestra una o exclusiva o XOR. La función XOR puede ser construida a partir de operaciones básicas, aunque no de modo sencillo. Sin embargo, resulta muy útil a los informáticos y es ampliamente empleada, como veremos enseguida.

Las representaciones de estos operandos son muy diversas y los informáticos preferimos la que emplea puertas lógicas. Y sin embargo... ¡un momento! ¿qué pintamos los informáticos aquí?. ¿Quién nos ha dado vela en este entierro?.

Pues en realidad fue Claude Shannon, uno de los grandes, quien nos dio vela. Ya hablamos de Shannon cuando describíamos el mínimo de información necesaria para codificar una cadena de bits. Pero antes de ocuparse de la teoría de la información, Shannon demostró que el álgebra de Boole se podía utilizar en el análisis y la síntesis de la conmutación y de los circuitos digitales.

Un circuito digital es un circuito electrónico que emplea señales eléctricas que representan (mediante la tensión) dos valores: 0 y 1. El circuito, visto como una caja negra consta de una serie de entradas y unas salidas. Lo que Shannon demostró es que cualquier salida puede ser producida a partir de las entradas mediante una combinación de operadores booleanos, esto es, mediante un conjunto de puertas lógicas, interconectadas de cierto modo. De este modo podemos ver cualquier transformación de entradas en salidas como la aplicación de cierta función (operación) lógica¹. A esto se le llama circuito, o sistema, combinacional.

SUMADOR A B Suma Carry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1

Así, por ejemplo, un circuito básico podría ser el el que suma dos bits. Recordemos que la suma de dos bits era sencilla: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 y me llevo 1 (acarreo). Un sumador simple (half-adder) de un bit tiene dos entradas y dos salidas (la suma y el acarreo). Lo llamamos simple para diferenciarlo del completo, que añadiría como nueva entrada el acarreo del anterior. De este modo podríamos construir sumadores de cualquier número de bits sin más que encadenar la salida del acarreo de uno a la entrada del otro. Pero nosotros nos quedaremos con el simple, para no complicar el circuito.

El sumador que vemos emplea una puerta AND (la de abajo de la imagen) y una puerta XOR, la superior, que ya presentamos anteriormente. Con las tablas de verdad de ambas puertas, es muy sencillo jugar a poner unos y ceros en las entradas y ver cómo los resultados coinciden con los de la suma.

Puede parecer que un sumador de un bit sólo sirve para jugar, pero de hecho, es la base del cálculo de todas las operaciones que realizan los computadores. Sin embargo es cierto que los ingenieros que construyen circuitos lógicos tienen herramientas para no tener que estar trabajando con miles de puertas lógicas cada vez que pretenden diseñar una nueva unidad aritmética para un computador, por poner ejemplo. Qué pinta tiene alguno de los lenguajes para expresar circuitos lógicos de manera sencilla y potente será explicado en posteriores entregas.

¡Un saludo y hasta la próxima!

¹ ¿De qué manera se produce "físicamente" la transformación de dos niveles de tensión a las entradas de una puerta en un nivel de tensión a la salida que corresponda al resultado de la puerta?. Bien eso depende la tecnología empleada y sería necesario entender física de semiconductores para explicarlo. Queda fuera del alcance de este blog.

Infinidad de circuitos digitales construidos de forma incremental.
Álgebra de Boole en la wikipedia en español: se incide en la representación como como conmutación de circuitos.
La imagen del half adder es de dominio público

Posts relacionados

Compresión de datos
Los números de los computadores