Algoritmo Quine Mc.Cluskey

Algoritmo Quine–McCluskey
El Algoritmo Quine–McCluskey es un método de simplificación de funciones booleanas desarrollado por Willard Van Orman Quine y Edward J. McCluskey. Es funcionalmenteidéntico a la utilización del mapa 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ínimaexpresió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 implicantesprimos para encontrar los implicantes primos esenciales, los cuales son necesarios y suficientes para generar la función.
Complejidad
Aunque es más práctico que el mapa de Karnaugh, cuando se trata detrabajar con más de cuatro variables, el tiempo de resolución del algoritmo Quine-McCluskey crece de forma exponencialcon el aumento del número de variables. Se puede demostrar que para una funciónde n variable el límite superior del número de implicantes primos es 3n/n. Si n = 32 habrá más de 6.5 * 1015implicantes primos. Funciones con un número grande de variables tienen que ser minimizadas conotros métodos heurísticos.
Ejemplo
Paso 1: Encontrando implicantes primos
Minimizando una función arbitraria:
|
| A | B | C | D | f |
m0 | 0 | 0 | 0 | 0 | 0 |
m1 | 0 | 0 | 0 | 1 | 0 |
m²| 0 | 0 | 1 | 0 | 0 |
m³ | 0 | 0 | 1 | 1 | 0 |
m4 | 0 | 1 | 0 | 0 | 1 |
m5 | 0 | 1 | 0 | 1 | 0 |
m6 | 0 | 1 | 1 | 0 | 0 |
m7 | 0 | 1 | 1 | 1 | 0 |
m8 | 1 | 0 | 0 | 0 | 1 |
m9 | 1 | 0 |0 | 1 | X |
m10 | 1 | 0 | 1 | 0 | 1 |
m11 | 1 | 0 | 1 | 1 | 1 |
m12 | 1 | 1 | 0 | 0 | 1 |
m13 | 1 | 1 | 0 | 1 | 0 |
m14 | 1 | 1 | 1 | 0 | X |
m15 | 1 | 1 | 1 | 1 | 1 |
Uno fácilmentepuede formar la expresión canónica suma de productos de esta tabla, simplemente sumando minitérminos (dejando fuera las redundancias) donde la función se evalúa con 1:

Por supuesto, esta expresión...