EL ALGEBRA BOLEANA ( I )

Existe una forma sencilla y eficaz de analizar el comportamiento de los circuitos lógicos conocida como el álgebra Boleana, en honor de su creador el matemático inglés George Boole (1815-1864). En rigor de verdad, cuando George Boole creó el álgebra Boleana, no lo hizo precisamente con circuitos lógicos digitales en mente, ya que en su época no sólo no se habían inventado los circuitos integrados ni los transistores, ni siquiera existían los costosos bulbos electrónicos que posibilitaron el desarrollo de la radio. Fue un ingeniero de nuestros tiempos, Claude Shannon (1916-2001), a quien se le ocurrió la idea de que los principios del álgebra Boleana que había aprendido en sus estudios universitarios eran muy similares a los de los circuitos eléctricos que estaba estudiando. De hecho la hemos estado utilizando desde que se introdujeron las tres funciones lógicas básicas. Las funciones OR, AND y NOT son expresiones tomadas directamente de la lógica simbólica. Lo que haremos aquí es formalizar estos conceptos usando símbolos para representar las palabras binarias.

El álgebra Boleana consiste en utilizar literales en lugar de combinaciones de "unos" y "ceros" para el análisis de los circuitos lógicos. Empezaremos por considerar la función NOT junto con su Tabla de Verdad:

Aquí hemos prescindido temporalmente del triángulo porque en los diagramas de circuitos lógicos es la burbuja la que representa la inversión de la entrada. Obsérvese que la entrada es A y la salida es C, y la salida es llamada la negación de A (la inversión de su valor), con el efecto representado con una línea horizontal puesta sobre el símbolo A.

Puesto que la salida del NOT es siempre el inverso lógico de la entrada A, podemos representar la salida del NOT como:

Salida = A

con lo cual con la barra horizontal puesta encima queremos decir que la salida es el inverso o el complemento de la entrada. Esto se lee puede leer de diversas maneras tales como "el inverso de A", "el complemento de A", o "A negado", todas ellas equivalentes. En este libro, siempre y cuando ello ha sido posible, se ha hecho además otra cosa con fines didácticos: se ha escrito el símbolo de una variable invertida lógicamente con color azul. Además, por las dificultades tipográficas para poder representar símbolos con una barra horizontal puesta encima de ellos, en muchos libros y muchos monitores de computadora con ciertas combinaciones de sistemas operativos y navegadores de Internet se hace preferible o inclusive mandatorio recurrir a otro tipo de representación por medio del apóstrofe ('). Bajo esta representación, algo que tiene puesto un apóstrofe inmediatamente a su derecha se debe tomar como una variable invertida en el sentido Boleano. Si el apóstrofe está puesto inmediatamente a la derecha de una expresión entre paréntesis, entonces toda la expresión entre paréntesis se debe considerar negada lógicamente. Todo esto quiere decir que en este libro las siguientes expresiones deben tomarse como completamente equivalentes:

A = A'

A + B = (A + B)'

A • B = (A • B)'

ā = (a')'

Siempre y cuando sea posible o conveniente, cuando se escriban variables negadas se utilizarán ambos sistemas de notación para que el lector se vaya acostumbrando al uso de los dos sistemas tipográficos.

Consideremos ahora la función OR junto con su Tabla de Verdad:

Obsérvese en la Tabla de Verdad cómo la salida del OR asemeja la suma de los valores a sus entradas. Por ejemplo, en el primer renglón tenemos que cero (0) más cero (0) es igual a cero (0). En el segundo renglón tenemos que cero (0) más uno (1) es igual a uno (1), y en el tercer renglón también tenemos que uno (1) más cero (0) es igual a uno (1). Guiados por esta observación, podemos postular que la salida del OR será igual a algo que llamamos la suma lógica de los valores a sus entradas, o sea:

Salida = A + B

Tal vez el lector ya se haya dado cuenta de que, según lo que podemos ver en el cuarto renglón de la Tabla de Verdad, uno (1) más uno (1) es igual a uno (1), o sea:

1 + 1 = 1

Esta relación puede dejar perplejos a muchos a primera vista. Es aquí cuando se le advierte al lector que una cosa es la suma lógica de dos variables llevada a cabo con un bloque OR, y otra cosa muy diferente es la suma binaria de dos variables. La suma lógica o suma Boleana de 1 y 1 es igual a 1, mientras que la suma binaria de 1 y 1 será igual (en el sistema de numeración binaria) a 10.

Sobre esto último debemos recordar que estamos manejando un álgebra diferente al álgebra clásica. Debemos, por lo tanto, adaptar nuestra mente a las estructuras matemáticas requeridas para el estudio de los circuitos lógicos, porque es el álgebra Boleana y no nuestra álgebra clásica el "álgebra" que entienden las máquinas en su mundo de "encendidos" o "unos" y "apagados" o "ceros". El descubrimiento de este hecho por Claude Shannon fue lo que posibilitó el manejo matemático adecuado de los circuitos lógicos, los cuales se llaman así porque son circuitos cuyo comportamiento es descrito con las leyes de la lógica simbólica (utilizadas originalmente para el estudio de los pensamientos humanos en cuanto tales sin ninguna referencia a circuitos eléctricos) asentadas por George Boole.

Pasamos a estudiar ahora la función AND con su Tabla de Verdad:

Obsérvese en la Tabla de Verdad cómo la salida C del bloque AND asemeja el producto de los valores a sus entradas A y B. Por ejemplo, en el primer renglón tenemos que cero (0) por cero (0) es igual a cero (0). En el segundo renglón tenemos que cero (0) por uno (1) sigue siendo igual a cero (0). En el tercer renglón también seguimos teniendo que uno (1) por cero (0) es igual a cero (0). Es en el cuarto renglón en donde tenemos que uno (1) por uno (1) es igual a uno (1). Guiados por esta observación, podemos asegurar que la salida del AND es igual al producto de los valores de las entradas, o sea:

Salida = A • B

En el álgebra Boleana, hay además una serie de teoremas relativamente fáciles de demostrar (esto se lleva a cabo en la sección de problemas resueltos), que son los siguientes:

(1) A + 1 = 1

(2) A • 1 = A

(3) A + 0 = 0

(4) A • 0 = 0

(5) A + A = A

(6) A • A = A

(7) ā = a

(8) A + A = 1

(9) A • A = 0

Usando los resultados anteriores, se puede analizar cualesquier circuito lógico y, muy a menudo, simplificarlo. Por ejemplo, supóngase que un circuito lógico tiene la siguiente salida:

AB + B + C + CD

El primer paso es factorizar los términos comunes como se muestra a continuación:

(A + 1) • B + (C + 1) •D

Usando el primer teorema de los dados arriba, esta expresión se reduce de inmediato a lo siguiente:

B + D

Se ve claramente que es más fácil y económico construír el circuito usando esta última expresión (sólo se requiere un OR de dos entradas) que usando la expresión original con la cual se requieren dos bloques AND y un OR de cuatro entradas.

Anteriormente, al carecer de los recursos del álgebra Boleana, la única manera de descubrir el comportamiento de un circuito lógico construído a partir de las tres funciones lógicas básicas era aplicar en las entradas todas las combinaciones posibles de "unos" y "ceros" y rastrear los cambios para cada una de estas combinaciones a lo largo del circuito obteniendo las salidas resultantes, y con ello construír una Tabla de Verdad. Y no había una forma obvia de poder simplificar el circuito reduciendo el número de componentes requeridos para su construcción. Pero ahora, con el recurso del álgebra Boleana en nuestras manos, en vez de rastrear a lo largo de un circuito lógico todas las combinaciones posibles de "unos" y "ceros" hasta llegar a la salida del circuito, podemos rastrear el efecto de los componentes sobre las variables simbólicas a la entrada, y sin necesidad de recurrir a los "unos" y "ceros" podemos incluso intentar llevar a cabo una simplificación del circuito que antes no estábamos posibilitados para hacer. A continuación tenemos un ejemplo de cómo podemos "rastrear" las entradas hasta llegar a la salida de un circuito lógico para obtener una expresión simbólica para su salida en función de las variables de entrada:

Podemos ver cómo en el AND que está en el extremo izquierdo del diagrama, las variables de entrada B y C son puestas en la salida del mismo como BC, y esto sirve como una de las entradas al NOR en la parte superior del diagrama, el cual suma (en el sentido Boleano) BC a la otra entrada A, llevando a cabo inmediatamente tras esto la inversión lógica para obtener la expresión A+BC a la salida de dicho NOR. Por otro lado, el NAND que está situado debajo de este NOR recibe como entrada a la señal que le llega de la terminal A junto con la señal que le llega de la terminal B procesada previamente por el inversor NOT, de modo tal que las dos entradas a este NAND son A y B. El NAND procesa estas dos entradas llevando a cabo primero el proceso de multiplicación (en el sentido Boleano) de estas entradas produciendo el término AB, el cual es invertido inmediatamente por la burbuja inversora del NAND convirtiéndose en el término mostrado en el diagrama. Continuando el rastreo de las variables simbólicas, llegamos hasta la expresión final de la salida Q, la cual ciertamente parece ser una expresión susceptible de ser simplificada mediante álgebra Boleana.

Un concepto importante en nuestro estudio es el concepto del minterm, el cual nos permite obtener la expresión de salida para un circuito a partir de su Tabla de Verdad.

Considérese un circuito cuya Tabla de Verdad sea la siguiente:

Concentremos nuestra atención en aquellas salidas que tengan el valor de 1. En este caso, son las salidas f₂ y f₃.

Por definición, un minterm correspondiente a la salida de un circuito es igual al producto de las literales A y B que representan las variables de entrada de modo tal que se produzca una salida de 1. En el segundo renglón de la Tabla de Verdad, puesto que A=0 hay que invertir A para que su producto con B=1 produzca una salida de 1. De este modo, vemos que el primer minterm es:

f₂ = A B___[ = A' B ]

Usando el mismo razonamiento, el segundo minterm será:

f₃ = A B_____[AB']

Recurrimos ahora a un teorema fundamental (la demostración no es difícil pero no se llevará a cabo en este libro para beneficio de quienes las demostraciones matemáticas no es su fuerte) que nos dice que la salida de un circuito lógico es igual a la suma de los minterms de su Tabla de Verdad.

Entonces, la salida del circuito en este caso será:

Salida = f₂ + f₃

Salida = A B + A B

Otro concepto importante es el concepto del maxterm.

Considérese un circuito lógico cuya Tabla de Verdad es la siguiente:

Concentramos ahora nuestra atención en aquellas salidas que son cero. En este caso, son las salidas f₂ y f₄ .

Por definición, un maxterm correspondiente a la salida de un circuito es igual a la suma de las literales A y B que representan las variables de entrada de modo tal que se produzca una salida de 0 (compárese con la definición del minterm). En el segundo renglón de la Tabla de Verdad, puesto que B=1, hay que invertir la variable B para que su suma con A=0 produzca una salida de 0. De este modo, vemos que el primer maxterm es:

f₂ = A + B

Usando el mismo razonamiento, el segundo maxterm será:

f₄ = A + B

Recurrimos ahora a otro teorema fundamental de la teoría de los circuitos lógicos que nos dice que la salida de un circuito lógico es igual al producto de los maxterms de su Tabla de Verdad.

La salida del circuito lógico en este caso será:

Salida = f₂ • f₄

Salida = ( A + B) • (A + B)

Podemos remover los paréntesis y simplificar esta expresión llevando a cabo las multiplicaciones requeridas en forma parecida a la forma en la cual estamos acostumbrados en el álgebra tradicional:

Salida = AA + AB + A B + B B

Según uno de los teoremas enunciados anteriormente:

A • A = 0

y aplicando otro de los teoremas se tiene que:

B • B = B

Tenemos entonces que la salida se reduce a:

Salida = AB + A B + B

Podemos factorizar los primeros dos términos como sigue:

Salida = (A + A)•B + B

Usando el teorema que nos dice que A + A = 1, la expresión se simplifica a:

Salida = B + B

Pero otro de los teoremas nos dice que cualquier variable lógica sumada a sí misma nos produce la misma variable (este teorema aplica por igual a todas las variables, así se trate de variables invertidas), o sea el teorema:

A + A = A

Entonces la expresión final se reduce simplemente a:

Salida = B

Entonces el circuito de dos entradas A y B representado por la última Tabla de Verdad lo único que hace es invertir la entrada B e ignorar la entrada A. Es, en esencia, simplemente un inversor conectado a la señal lógica B. Una nueva inspección a la Tabla de Verdad nos confirma esto que al principio no nos era tan obvio.

Podemos, por lo tanto, obtener la expresión de salida para cualesquier circuito lógico a partir de su Tabla de Verdad ya sea por medio de minterms o por medio de maxterms. La decisión de utilizar minterms o maxterms es meramente una cuestión de conveniencia. Por ejemplo, si la Tabla de Verdad para un circuito tiene menos minterms que maxterms, posiblemente usando minterms se llegue más rápidamente a una expresión final.