Mapas de Karnaugh ¿Cómo se crearon y como se trabajan?

Maurice Karnaugh, ingeniero de telecomunicaciones estadounidense.

Graduado en la universidad de Yale en el 1952, es actualmente gobernador emérito del ICCC (International Council for Computer Communication). Ha trabajado como investigador en los Laboratorios Bell desde 1952 a 1966 y en el centro de investigación de IBM de 1966 a 1993. Así mismo, ha impartido de informática en el Politécnico de Nueva York de 1980 a 1999, y desde 1975 es miembro del IEEE (Institute of Electrical and Electronics Engineers) por sus aportaciones sobre la utilización de métodos numéricos en las telecomunicaciones.

Es el creador del método tabular o mapa de Karnaugh que permite la minimización de funciones Booleanas.Lo más probable es que Karnaugh ideó sus Mapas a partir de los diagramas de Venn-Euler de la Teoría de Conjuntos.
Veamos dos conjuntos A y B, que son subconjuntos de un conjunto Universal U, tal como se muestra en la figura:

Asociamos el conjunto A con una variable Booleana A, y el conjunto B a otra variable Booleana B, siendo A el Bit más significativo. La intersección de A y B corresponde en el algebra de Boole a  A.B, que en sistema binario corresponde a (11) equivalente al decimal 3 (región café). Así mismo A - B, o sea la intersección de A con el complemento de B, que en el Algebra de Boole es A.B´ corresponde al binario (10), equivalente al decimal 2 (región verde); la región rosada, corresponde a A´ B, que es el binario (01), o sea el decimal 1, y la región blanca, corresponde al complemento de la unión de los conjuntos A y B, que equivale a la intersección entre A´  y  B´, lo cual confirma el Teoremia de De Morgan, y equivale al binario (00) que es el 0 decimal. Se observa en el gráfico que cada decimal, tiene dos vecinos: el 3 es vecino de 2 y 1; el 2 es vecino del 0 y el 1; el 1 es vecino del 0 y del 3,  y el 0 es vecino del 1 y del 2.  En binario los vecinos lógicos solo cambian 1 bit con respecto al número del cual son vecinos: por ejemplo, el 1, (01), y el 2 (10), solo cambian 1 bit, respecto al 3 (11) del cual son vecinos.

Lo anterior permitió a Maurice Karnaugh idear su Mapa, tal como se muestra a continuación:

Cada cuadro corresponde a un decimal: 0,1,2,3, según el binario respectivo. Vamos a suponer que tenemos una  función con mintérminos en 0,1,2 y un maxtérmino en 3.  En los Mapas de Karnaugh se pueden formar grupos entre vecinos lógicos, que correspondan a potencias de 2, o sea grupos de 1(unitario), 2 (parejas), 4 (Cuartetos),etc. 

Para el ejemplo se pueden formar dos parejas: (0,1)  y  (0,2), donde se observa que el 0 forma parte de las dos parejas. Al formarse la pareja (0,1) cambia la variable B, y por consiguiente se cancela, debido a que en Algebra de Boole ( B +  B´ = 1);  como  la variable A no cambia y está en 0, la pareja (0,1) equivale a A´. De la misma forma podemos encontrar que la pareja (0,2) equivale a B´. Por consiguiente la función Booleana minimizada es:  A´ +  B´.   Si llamamos F la función podemos decir que: F = ( A´ + B´).

De acuerdo al maxtérmino en 3 tendremos: F´ = A.B, de donde F = (A.B)´ .

Se corrobora por el Teorema de De Morgan que F = (A.B)´ = A´ +  B´,  lo cual quiere decir que la función corresponde a una compuerta NAND.

Si miramos la tabla de verdad que incluimos en el Mapa de Karnaugh vemos que es:

A B     F
0 0      1
01       1
10       1
11       0

Que evidentemente es la tabla de verdad de la compuerta NAND.

Lo que nos permite el Mapa de Karnaugh es darnos cuenta que la función F = A´B´ +  A´ B + A B´ se puede reducir a F = A´ + B´ = (A B )´ .

Lo visto anteriormente, lo podemos extrapolar a 3 variables, trabajando un M.de K. para A,B,C, siendo A la variable correspondiente al Bit más Significativo. 

F = B´ C  +  A B  ( Por mintérminos, o Suma de productos)
F´ =  B´C´  +  A´B, luego F = (B´ C´ +  A´B)' = (B + C) ( A + B' ) (Por Maxtérminos o Producto de sumas)

Con 4 variables se tienen 16  casillas, con los números decimales del 0 al 15, tal como se muestra:

Veamos la minimización de una función, cuyos 9 mintérminos están ubicados en 3,5,6,7,8,10,12,13,14 por Suma de Productos, quedando como ejercicio para el lector obtener la minimización por Producto de Sumas:

En la práctica se trabajan Mapas de Karnaugh hasta 5 variables(32 casillas).

Para mas de 5 variables se utilizan otros métodos. El programa LOGICAID es excelente en esta tarea.