Mapas de Karnaugh

1. Qué es un mapa de Karnaugh

Un mapa de Karnaugh es una tabla de verdad redibujada como cuadrícula. Maurice Karnaugh lo presentó en los Bell Labs en 1953 como una forma de simplificar circuitos de conmutación a simple vista, y sigue siendo la manera más rápida de minimizar a mano una función booleana pequeña: sin álgebra, sin leyes que recordar, solo rectángulos.

Cada celda del mapa contiene una fila de la tabla de verdad. Lo que hace que el mapa sea más que una reordenación es el orden en que se colocan esas filas: las celdas contiguas se diferencian en exactamente una variable.

Esa única propiedad hace todo el trabajo. Si dos celdas vecinas son ambas verdaderas, la variable que cambia entre ellas no puede ser la que hace verdadera la expresión, así que desaparece y un solo término cubre las dos celdas. Simplificar se convierte en dibujar los rectángulos más grandes posibles.

2. Por qué las columnas parecen desordenadas

Las columnas de un mapa de Karnaugh no cuentan 00, 01, 10, 11. Van 00, 01, 11, 10: código Gray reflejado, un orden en el que cada valor se diferencia del siguiente en un solo bit. Contar en binario pondría el 01 junto al 10, que difieren en dos bits, y las celdas vecinas no dirían nada.

Los bordes también son vecinos. La primera y la última columna se diferencian en una variable, igual que la primera y la última fila, así que un grupo puede salir por un borde y continuar por el otro; por eso las cuatro esquinas de un mapa de cuatro variables forman un único grupo. Un mapa de Karnaugh está dibujado en realidad sobre un toro: la hoja plana es una comodidad.

3. Agrupar los unos

Para leer en el mapa una suma de productos mínima, cubre con grupos rectangulares todas las celdas que contienen un 1, siguiendo cuatro reglas:

• Un grupo es un rectángulo de 1, 2, 4, 8 … celdas: una potencia de dos en cada lado.
• Un grupo puede envolver los bordes del mapa, en horizontal, en vertical o en ambos.
• Los grupos pueden solaparse. Cubrir una celda dos veces no cuesta nada; dejar una sin cubrir cambia la función.
• Haz cada grupo tan grande como se pueda y usa después tan pocos grupos como basten para cubrir todos los unos.

Cada grupo se convierte en un término. Se lee preguntando qué variables se mantienen iguales en todo el grupo: esas aparecen en el término -sin negar donde valen 1, negadas donde valen 0- y las que cambian desaparecen. Un grupo de dos celdas pierde una variable, uno de cuatro pierde dos y uno de ocho pierde tres. La expresión mínima es la disyunción de los términos.

4. Un ejemplo resuelto

Tomemos (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). Su mapa tiene cuatro variables: A y B en las filas, C y D en las columnas.

Dos grupos cubren todos los unos. Uno es el bloque de cuatro celdas en las dos filas donde A = 0 y las dos columnas donde C = 1: dentro de él cambian B y D, así que desaparecen y el término es ¬A ∧ C. El otro es la fila entera en la que A y B valen 1, a lo ancho de las cuatro columnas: C y D cambian a lo largo de ella y queda A ∧ B.

La forma mínima es, por tanto, (¬A ∧ C) ∨ (A ∧ B). El tercer término del original, B ∧ C ∧ D, ha desaparecido: cada celda que cubría ya estaba cubierta por uno de los dos grupos. Eso es la absorción cuando se puede ver dibujada.

5. Implicantes primos y esenciales

Un grupo que ya no puede agrandarse se llama implicante primo. Enumerar los implicantes primos es la mitad fácil del problema; elegir cuáles conservar es la mitad que sale mal.

Si alguna celda está cubierta por un solo implicante primo, ese implicante es esencial: ninguna forma mínima puede prescindir de él, porque nada más cubre esa celda. Toma primero los implicantes esenciales y cubre después lo que quede con los menos grupos posibles de los restantes.

Ser codicioso -tomar una y otra vez el grupo más grande disponible- es tentador y no siempre funciona. En una tabla cíclica, donde ningún implicante es esencial y cada celda está cubierta dos veces, la elección codiciosa puede acabar con un término más que la mejor respuesta. El mapa de este sitio explora en cambio todas las opciones restantes, algo que con cuatro variables no cuesta nada.

6. Agrupar los ceros en su lugar

Todo lo anterior funciona igual de bien con los ceros. Cúbrelos con los mismos rectángulos, lee cada grupo con sus literales negados -una variable que vale 1 en todo el grupo aparece negada y una que vale 0 aparece sin negar- y une los grupos con ∧ en lugar de ∨.

El resultado es un producto de sumas: una conjunción de disyunciones que es falsa exactamente en las celdas en las que la expresión es falsa y, por tanto, verdadera en todas las demás. Cuál de las dos formas es más corta depende de la función -una fórmula con pocos unos tiene una suma de productos corta, y una con pocos ceros un producto de sumas corto-, así que conviene leer ambas en el mapa antes de elegir.

7. Mapas más grandes y las condiciones indiferentes

Cinco y seis variables pueden dibujarse como dos o cuatro mapas de cuatro variables apilados, contando como adyacentes las celdas que ocupan la misma posición en capas vecinas. Funciona, pero la adyacencia que hacía visual el método pasa a ser algo que hay que recordar en lugar de ver. Más allá, el algoritmo de Quine-McCluskey hace el mismo trabajo en forma de tabla: es la versión mecánica de exactamente esta agrupación, y es lo que se ejecuta detrás de los mapas de aquí.

El diseño de hardware añade una idea más. Algunas combinaciones de entrada no ocurren nunca -un dígito decimal codificado en binario nunca es 1010-, así que al diseñador le da igual qué haga el circuito con ellas. Esas celdas se marcan con una X y pueden leerse con cualquiera de los dos valores, el que agrande más los grupos. Los mapas de esta calculadora se construyen a partir de una fórmula, que da un valor a cada asignación, así que ninguna celda es indiferente.

8. Pruébalo tú mismo

Escribe en la calculadora una expresión de dos a cuatro variables y su mapa aparecerá debajo de la tabla de verdad, con cada grupo rodeado de su propio color y la forma mínima escrita debajo. Cambia a producto de sumas para ver agrupados los ceros.