Mapa de Karnaugh

Mapa de Karnaugh es un procedimiento directo para optimizar funciones booleanas con un máximo de 4 variables. Se pueden también hacer mapas con 5 o 6 variables pero estas son muy incómodas de usar.

El mapa es un diagrama que esta hecho con cuadros, cada cuadrado representa un mini-termino de la función.

Reconociendo diferentes patrones podemos derivar expresiones algebraicas alternativas para la misma función, de las cuales se puede seleccionar la más sencilla.

Las expresiones optimizadas que el mapa produce siempre se expresan en forma de suma de productos o producto de sumas.

Ahora si vamos a lo bueno, resolvamos algunos ejemplos que inventé con diferente número de variables:

Mapa de dos variables

F = ¬XY + ¬Y¬X + XY 

Lo primero que hay que hacer es construir la tabla de verdad:

Entonces hay que empezar a crear el Mapa-K, para esto creamos un 4 cuadros ya que teniendo dos variables son 4 las combinaciones posibles 2^2 = 4, los renglones representaran la X y las columnas la Y. De la siguiente manera:

Llenamos los cuadrantes de adentro con la respuesta correspondiente que obtuvimos en la tabla de verdad para la combinación indicada.

Tenemos que armar grupos de 1, solo podemos unir de manera vertical y horizontal, no en diagonal, y también nuestros grupos deben del tamaño correspondiente a una potencia de 2 (2, 4, 8, 16).

Entonces nos queda de la siguiente manera:

Lo siguiente es ahora si formar nuestra nueva expresión booleana:

Se hace así:

Tomamos la que esta encerrada en rojo, y queda solamente la X ya que la Y cambia de valores de 0 a 1, y como la X se mantiene constante solo tendremos X, pero como la X esta en 0 tenemos que ponerla negativa para que sea 1 entonces ya tenemos la ¬X.

Ahora de la que esta encerrada en azul vemos que la X cambia de valores entonces se queda la Y sola positiva.

La expresión final es: ¬X + Y. 

De tener al principio F = ¬XY + ¬Y¬X + XY ahora tenemos algo más pequeño F = ¬X + Y

Mapa de tres variables

Aquí tenemos que utilizar 3 variables por lo tanto este problema será un poquito más largo, he creado la siguiente función para mostrar el método:

F = ABC + A¬BC + AB¬C + ¬A¬B¬C + ¬A¬BC

Aquí esta la tabla de verdad:

a:
F = AB + CD

Ahora formamos el mapa-K, en este ejemplo de 3 variables tendremos 8 cuadrantes ya que hay 8 combinaciones posibles 2^3 = 8. La manera de distribuir las combinaciones es teniendo la A en los renglones y la B y C en las columnas, mostrando ahi todas las combinaciones posibles entre estas dos variables, el primer valor que aparece en el renglón como encabezado del mismo es el valor de la B, el segundo es el de la C.

A continuación empezamos a encerrar los grupos que más nos convengan, podemos ver que encerraremos en el primer renglón el grupo de unos, y en el segundo renglón tenemos un grupo de unos de 3 unos, lo que no es posible debido a que 3 no es potencia de dos por lo que tendremos que repetir algún termino que ya este en grupo lo cual es totalmente válido y nos quedara de la siguiente manera:

Entonces podemos ver del grupo rojo la expresión queda ¬A¬B (la C no debido a que cambia de 0 a 1), del grupo azul queda ¬BC (la A no porque cambia de 0 a 1) y del grupo azul vemos AB (la C no porque cambia). 

Y el resultado es de tener la expresión así: F = ABC + A¬BC + AB¬C + ¬A¬B¬C + ¬A¬BC

la hemos minimizado a: F = ¬A¬B + ¬BC + AB.

Mapa de cuatro variables

Ahora una función con 4 variables, usaremos esta expresión que se me ocurrió para mostrar el ejemplo:

F = ABCD + ¬ABCD + A¬BCD + AB¬CD + ABC¬D + ¬A¬BCD + AB¬C¬D

Tabla de verdad:

Lo que sigue es formar el mapa de 4x4 osea 16 cuadrantes que se forman de las combinaciones 2^4 = 16, ahora los renglones los forman A y B con todas sus combinaciones posibles, y las columnas C y D también con todas las combinaciones:

Ahora formamos los grupos de unos, recordemos que tienen que ser potencias de 2, nos quedó bastante cómodo el ejemplo, en la siguiente imagen les muestro como es que podemos resolver nuestro mapa:

Podemos empezar a formar la expresión simplificada tomando el circulo que queramos, yo elegí el rojo, entonces nos queda AB (C y D no porque cambian de valores) y del circulo azul nos queda CD (A y B no porque cambian de valores).
Nuestra expresión paso de ser así:
F = ABCD + ¬ABCD + A¬BCD + AB¬CD + ABC¬D + ¬A¬BCD + AB¬C¬D
a:
F = AB + CD

Y finalmente les muestro como es que compruebo las expresiones, no crean que lo hago manualmente, uso un programita muy sencillo de python, y es así como me puedo dar cuenta que lo optimicé correctamente.


La ejecución:

Referencias

Ejemplo sencillo mapa-karnaugh