Mapas k Quine–McCluskey

El Algoritmo Quine–McCluskey es un método de simplificación de funciones boleanas desarrollado por ,Willard van orman quine y Edward mccluskey es funcionalmente identico a los mapas de karnaugh pero su forma tabular lo hace más eficiente para su implementación en lenguajes computacionales, y provee un método determinístico de conseguir la mínima expresión de una función booleana.

Pasos:

El método consta de dos pasos:

1. Encontrar todos los Implicantes primos de la función.
2. Usar esos implicantes en una tabla de implicantes primos para encontrar los implicantes primos esenciales, los cuales son necesarios y suficientes para generar la función.

Aunque es más práctico que el mapa de Karnaugh, cuando se trata de trabajar con más de cuatro variables, el tiempo de resolución del algoritmo Quine-McCluskey crece de forma exponencial con el aumento del número de variables. Se puede demostrar que para una función de n variables el límite superior del número de implicantes primos es 3ⁿ/n. Si n = 32 habrá más de 6.5 * 10¹⁵ implicantes primos. Funciones con un número grande de variables tienen que ser minimizadas con otros métodos heuristicos

Paso 1: Encontrando implicantes primos

Uno fácilmente puede formar la expresion canonica suma de productos de esta tabla, simplemente sumando miniterminos (dejando fuera las redundancias) donde la función se evalúa con 1:

Por supuesto, esta expresión no es mínima. Para optimizarla, primero son colocados todos los minitérminos evaluados en la función como 1 en una tabla. Las redundancias también son agregadas a la tabla, estas pueden combinarse con los minitérminos:

Paso 2: tabla de implicantes primos

Los términos marcados con "*" ya no pueden combinarse más, en este punto ya tenemos la tabla de implicantes primos. En el costado van los implicantes primos recientemente generados, y en la parte superior los minitérminos utilizados. Los minitérminos correspondientes a las redundancias son omitidos en este paso, no se colocan en la parte superior.

En esta tabla vemos los minitérminos que "cubre" cada implicante primo. Ninguno de los implicantes de esta tabla está incluido dentro de otro (esto queda garantizado en el paso uno), pero si puede estar "cubierto" por dos o más implicantes. Es el caso de m(8,9,10,11) que esta cubierto por m(8,10,12,14) y m(10,11,14,15)

Por este motivo, cada uno de estos dos implicantes sólo son esenciales en ausencia del otro. Un proceso adicional simple para reducir estos implicantes es prueba y error, pero un proceso más sistemático es el metodo petrick. En el caso que estamos analizando, los dos implicantes primos m(4,12) y m(10,11,14,15) no llegan a incluir todos los minitérminos por lo que podemos combinar estos implicantes con cada uno de los implicantes no esenciales para conseguir dos funciones mínimas: