Álgebra de Boole

¿Qué es el álgebra de Boole?

El álgebra de Boole nació mucho antes que las computadoras. La publicó el matemático inglés George Boole en 1854, en su libro Una investigación de las leyes del pensamiento: la idea era poder manipular enunciados lógicos con reglas parecidas a las del álgebra de números.

Durante casi un siglo quedó como una curiosidad matemática, hasta que en 1938 Claude Shannon —trabajando para la compañía telefónica Bell— se dio cuenta de que los circuitos eléctricos con interruptores cumplen exactamente esas mismas reglas. Desde entonces, el álgebra de Boole es la herramienta con la que se diseñan y analizan los circuitos lógicos, y por eso está adentro de cada computadora, teléfono o robot: toda la información que procesan es, en el fondo, combinaciones de 0 y 1.

En el álgebra de Boole trabajamos con variables que solo pueden valer 0 o 1 —nada más— y con tres operaciones:

Para calcular el valor de una expresión se respeta la precedencia de las operaciones: primero las negaciones, después los productos y al final las sumas. Por ejemplo, con A = 0, B = 1 y C = 1:

A · B + C = 0 · 0 + 1 = 0 + 1 = 1

Primero se niega B (de 1 pasa a 0), después se multiplica (0 · 0 = 0) y recién al final se suma (0 + 1 = 1).

Leyes del álgebra de Boole

Todo lo que se puede hacer con el álgebra de Boole sale de un puñado de leyes de base. Son las reglas del juego: no se demuestran, se aceptan, y todo lo demás se deduce de ellas. Fijate que vienen de a pares: cada ley tiene una gemela que se obtiene cambiando + por · y 0 por 1.

Dos aclaraciones importantes:

• El 0 y el 1 de acá no son los números de contar: son los nombres de los dos valores posibles. Lo mismo pasa con + y ·: son la suma y el producto lógicos, que cumplen estas leyes y no todas las de los números comunes.
• La distributiva de la derecha, A + (B · C) = (A + B) · (A + C), no existe con números comunes (ahí no se puede "sacar el más como factor común"). Es una rareza propia de este álgebra, y se usa muchísimo.

Que las leyes vengan de a pares no es casualidad: se llama dualidad. El dual de una igualdad se obtiene cambiando 0 por 1, 1 por 0, + por · y · por +. Y vale la regla de oro: si una igualdad es una ley, su dual también lo es. Por eso, de acá en adelante, cada teorema se presenta con su pareja.

La tabla de valores: demostrar y contar

Para demostrar que una igualdad se cumple siempre no hace falta aplicar leyes: alcanza con probar todas las combinaciones posibles de las variables en una tabla de valores (como las tablas de verdad de lógica). Si las dos columnas coinciden fila por fila, la igualdad es una ley.

Ejemplo: demostremos que X · (Y + Z) = X·Y + X·Z:

Las columnas X · (Y + Z) y X·Y + X·Z coinciden en las ocho filas: la igualdad queda demostrada.

La misma idea de contar combinaciones responde una pregunta que conviene tener clara: ¿cuántas funciones booleanas distintas hay con n variables? Con n variables hay 2ⁿ combinaciones de entrada y, como en cada una la salida puede valer 0 o 1, la cantidad de funciones distintas es:

2²ⁿ

Con 2 variables: 2⁴ = 16 funciones. Con 3: 2⁸ = 256. Con 4: 2¹⁶ = 65.536. Casi todas se pueden escribir, pero solo nos interesan las que describen circuitos reales, y esas se simplifican con las herramientas que siguen.

Teoremas

De las leyes de base se deducen otras igualdades, los teoremas, que son las herramientas de trabajo diarias. Se demuestran aplicando las leyes; por ejemplo, el teorema de absorción sale en cuatro pasos:

X + X·Y = X·1 + X·Y = X·(1 + Y) = X·1 = X

Los teoremas 1 a 9 se demuestran de la misma manera que el de absorción, aplicando las leyes de base. Los de De Morgan se demuestran con la tabla de valores, y el consenso se usa al final de una simplificación, cuando un término sobra porque está cubierto por otros dos.

¿Qué es una función lógica?

Una función lógica (o booleana) es una regla que, para cada combinación de los valores de sus variables de entrada —todas valen 0 o 1—, produce una única salida, que también vale 0 o 1. Es la forma matemática de describir el comportamiento de un circuito digital.

La manera de escribirla es una expresión booleana: variables, 0 y 1, y los tres operadores. Por ejemplo F(A, B) = A · B es una función de dos variables, y sus cuatro valores posibles se resumen en una tabla:

Dos expresiones que dan el mismo resultado para todas las combinaciones son equivalentes: representan la misma función. Por ejemplo A·B, A·B + 0 y A·B·1 son tres expresiones distintas de una misma función. De ahí sale justamente la simplificación: de todas las expresiones equivalentes, se busca la más corta.

Un ejemplo con tres variables, que se va a usar en toda la página: F = A·B + A·C. La salida vale 1 cuando A y B valen 1, o bien cuando A vale 0 y C vale 1. Todas las combinaciones posibles se resumen en una tabla de verdad, que es el punto de partida del paso siguiente.

De la tabla de verdad a la función

Este es el procedimiento más importante de todo el tema: obtener la expresión de una función a partir de su tabla de verdad. Se hace en tres pasos:

1. Se buscan todas las filas en las que la salida vale 1.
2. Para cada una de esas filas se escribe un término producto: cada variable se escribe normal si en esa fila vale 1, y negada si vale 0. Todas las variables del término se multiplican entre sí.
3. Se suman todos los términos obtenidos.

Veamos la tabla de verdad de la función F = A·B + A·C:

Sumando los cuatro términos marcados se obtiene la función en su primera forma canónica:

F = ABC + ABC + ABC + ABC

Fijate que esta expresión es mucho más larga que la original, pero dice exactamente lo mismo. Ese es justamente el punto de partida para simplificar.

Formas canónicas: minitérminos y maxitérminos

Los términos que se obtienen de la tabla tienen nombre propio:

• Un literal es una variable sola, normal o negada: A o A.
• Un minitérmino (m_i) es un término producto en el que aparecen todas las variables, una sola vez cada una (un literal por variable), negadas las que valen 0. Vale 1 en una sola fila de la tabla: justo la fila i.
• Un maxitérmino (M_i) es el término suma en el que aparecen todas las variables, negadas las que valen 1. Vale 0 en una sola fila: justo la fila i.

Con esa notación, la función del ejemplo se escribe de forma abreviada como una lista de minitérminos:

F = Σ m(1, 3, 6, 7)

Las dos formas describen la misma función. En la práctica se usa casi siempre la primera, porque se corresponde directamente con el método que después aplica el mapa de Karnaugh.

Y no hace falta partir de la tabla: desde una expresión cualquiera también se llega a la primera forma canónica, aplicando las leyes. Por ejemplo, con F = (A + B) · C:

F = A·C + B·C  =  A·(B + B)·C + (A + A)·B·C

F = ABC + ABC + ABC + ABC  =  ABC + ABC + ABC = Σ m(2, 4, 6)

En la primera línea se distribuyó y después se multiplicó cada término por "1 disfrazado" (B + B y A + A); en la segunda se distribuyó de nuevo y se borró un ABC repetido por idempotencia. La tabla de la función daría los mismos tres 1: en las filas 2, 4 y 6.

Simplificación algebraica

Una función en su forma canónica funciona, pero es innecesariamente larga: cada término de más significa una compuerta más y un circuito más caro. La simplificación consiste en aplicar las leyes y los teoremas para reducirla hasta su expresión más corta posible.

Retomemos el ejemplo y agrupemos los términos de a pares:

F = (ABC + ABC) + (ABC + ABC)

Se saca factor común en cada par:

F = AC (B + B) + AB (C + C)

Pero B + B = 1 y C + C = 1 (ley del complemento), así que:

F = AC · 1 + AB · 1

Y como multiplicar por 1 no cambia nada (elemento neutro):

F = AC + AB

Llegamos exactamente a la expresión del comienzo. Pasamos de cuatro términos de tres variables a dos términos de dos variables: el circuito necesita bastante menos compuertas y hace lo mismo.

Un segundo ejemplo, para ver que la simplificación puede ser sorprendente:

F = AB + (ABC) + C · (B + A)

De Morgan sobre el paréntesis negado y distributiva en el tercer término:

F = AB + A + B + C + CB + CA

Se juntan los pares que comparten la variable (absorción, teorema 5):

F = AB + A + B + C

Y ahora, absorción con el negado (teorema 6): A + AB = A + B. Con lo que queda, el complemento remata:

F = A + B + B + C = 1

La función siempre vale 1, para cualquier combinación de las entradas: el circuito equivalente es un cable conectado a 1. La verificación con la tabla lo confirma, y por eso nunca está de más hacerla.

Cómo se resuelve, paso a paso

Resolver una función lógica no es calcular su valor para ciertas entradas: eso es evaluarla. Resolver es llegar a la expresión mínima, la que tiene la menor cantidad de términos y de variables por término. El motivo es concreto: cada término es una compuerta AND y cada variable repetida es una entrada más, así que una expresión más corta es un circuito más chico, más barato y más rápido.

Paso 1: partir de algo seguro

Si tenés la tabla de verdad, el punto de partida es la primera forma canónica: un término producto por cada fila que vale 1 (cada variable directa si en esa fila vale 1, negada si vale 0) y todos los términos sumados. Es larga, pero no puede estar mal, porque sale de la tabla. Si te dan directamente una expresión, se puede simplificar sin pasar por la tabla, pero conviene tener la tabla a mano para verificar al final.

Paso 2: las herramientas, de la más útil a la menos

Paso 3: la técnica que más rinde, buscar el par

Es juntar las dos primeras herramientas. Dos términos que son idénticos salvo por una variable, que en uno está negada y en el otro directa, se combinan y esa variable desaparece:

XY + XY = X(Y + Y) = X · 1 = X

Todo el método consiste en repetir eso: agrupar de a dos, ver qué variable desapareció y volver a empezar con lo que quedó. Es exactamente lo que hace el mapa de Karnaugh al agrupar celdas vecinas, pero dibujado.

Paso 4: un ejemplo completo

Simplifiquemos F = Σ m(0, 1, 2, 3, 7), de tres variables.

a) Escribimos los minitérminos con A, B y C en ese orden:

F = ABC + ABC + ABC + ABC + ABC

b) Agrupamos los que se diferencian en una sola variable (los dos primeros cambian en C, los dos siguientes también):

(ABC + ABC) + (ABC + ABC) + ABC

c) Sacamos factor común en cada par:

F = AB(C + C) + AB(C + C) + ABC

d) Como C + C = 1, y multiplicar por 1 no cambia nada:

F = AB + AB + ABC

e) Los dos primeros se diferencian solo en B, así que los volvemos a combinar:

F = A(B + B) + ABC = A + ABC

f) Por absorción (teorema 6, con X = A e Y = BC): A + A · BC = A + BC. Entonces:

F = A + BC

Pasamos de cinco términos de tres variables a dos términos. Y esa expresión es la mínima: los 1 de esta función no se pueden cubrir con un solo término.

Paso 5: verificar (no es opcional)

La simplificación se comprueba contra la tabla: la expresión original y la simplificada tienen que dar lo mismo en todas las filas. Con dos o tres filas bien elegidas alcanza para darse cuenta de un error:

Si alguna fila no coincide, en algún paso se perdió un 1. En ese caso se vuelve atrás para encontrar dónde, no se "arregla" la expresión a ojo.

Dos casos más, para tener vistos

Con De Morgan (cuando hay una barra sobre un paréntesis), sea F = (A + B)(A + C):

F = (A + B) + (A + C) = AB + AC

Factorizando al revés (la distributiva de la suma, la ley que en los números no existe), sea F = (A + B)(A + B):

F = A + B · B = A + 0 = A

En un solo paso, una función de dos factores queda reducida a una sola variable: en los dos factores la A aparece igual, así que se saca como factor común al revés.

Las tres trampas donde se cae siempre

1. De Morgan con la negación mal repartida. A · B = A + B, y no A · B: al negar un producto, el producto se convierte en suma (y al negar una suma, la suma se convierte en producto), y cada variable queda negada.
2. Confundir las dos formas de la ley del complemento. X + X = 1 y X · X = 0. Si se mezclan, todo lo que sigue sale mal.
3. "Cancelar" términos. De X + Y = X + Z no se puede concluir que Y = Z: en el álgebra de Boole la suma no se cancela (con X = 1, cualquier Y y cualquier Z dan 1). Todo lo que se haga tiene que salir de aplicar una ley, no de "pasar restando" como en el álgebra común.

Cuándo conviene el mapa de Karnaugh

Con dos o tres variables el álgebra es manejable. Con cuatro o más es fácil perder un término, no ver que dos grupos se pueden juntar, o no darse cuenta de un grupo que da la vuelta por los bordes del mapa. Ahí conviene el mapa de Karnaugh, que hace lo mismo pero de forma visual y sistemática: para el ejemplo de arriba se ve de un vistazo que los cuatro 1 de la fila A = 0 forman el grupo A, y que las celdas 3 y 7 forman el grupo BC.

La teoría del mapa está en Karnaugh, y para dibujarlo y practicar está el Resolvedor de mapas de Karnaugh, que valida los grupos y entrega la hoja como imagen.