Universidad tecnológica de la
Riviera Maya
“Método Quine-McClusckey”
Jefte Gadiel Miranda Martinez
TIC Área de desarrollo de software
multiplataforma
1° TI11BIS
Desarrollo de pensamiento lógico
Manuel de la Rosa López
Viernes, 04 de marzo de 2022
Playa del Carmen, Quintana Roo
Método Quine-McClusckey
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 funcionalmente
idé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 determinista de
conseguir la mínima expresión de una función booleana.
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 3n/n. Si n =
32 habrá más de 6.5 * 1015 implicantes primos. Funciones con un número grande de
variables tienen que ser minimizadas con otros métodos heurísticos.
El procedimiento del método se puede dividir en 2 fases, las cuales se llevan a cabo de la
siguiente manera:
1. Tener la función expresada de forma canónica, ya sea con una suma de mini-
términos o maxitérminos, para este ejemplo se usarán mini términos.
f ( A , B , C , D)=∑ m(1 ,3 , 4 , 5 ,7 , 9 , 10 , 11, 15)
2. Determinar en una tabla en función de numeración binaria con tres columnas, una la
usaremos para escribir el termino, la siguiente columna será usada para expresar el
termino en notación binaria, en la última columna se escribirá la cantidad de “1”
que hay en cada termino.
3. Dividiremos los términos en otra tabla según su cantidad de “1” que tengan,
agregaremos una columna donde se marcara cuales dígitos pueden combinarse y
cuáles no.
4. Realizaremos una nueva tabla donde mostraremos las combinaciones de los dígitos,
si entre estas existe la diferencia de solo un digito, el termino puede combinarse,
estos se verán representados por una palomita en la última columna, los términos
que no sean capaces de combinarse serán representados con una X en su lugar.
5. Después de clasificar los términos crearemos otra tabla para etiquetar correctamente
a los implicantes primos (es decir los dígitos que pudieron combinarse) en este caso
los marcaremos con un asterisco.
6. Después usaremos la misma tabla para analizar cuáles son las columnas que solo
tengan un asterisco, las resaltaremos para pasar al siguiente ejercicio.
7. Para finalizar volveremos a usar la tabla para analizar cuáles son las columnas que
tienen al menos un asterisco, crearemos una última fila y marcaremos las columnas
donde se cumple esta condición.
8. Finalmente, si todas las columnas tienen una marca, se puede decir que se ha
terminado la simplificación por este método, ahora bien, la función final estará
formada por todos los implicantes que tengan al menos una marca encerrada en las
tablas del paso numero 4
f (A , B , C , D)=a+ b+d +c=CD + B̅D+ AB̅C + A̅BC̅
En conclusión, este método es fácil de aplicar a funciones con gran cantidad de variables
por la facilidad de este para representar varios datos y su capacidad de poder crear un
tabulado didáctico, aunque algo tedioso de realizar por la necesidad de realizar múltiples
tabulaciones.
Bibliografía: Algoritmo Quine–McCluskey. (s. f.). Wikiwand. Recuperado 4 de marzo de
2022, de https://www.wikiwand.com/es/Algoritmo_Quine%E2%80%93McCluskey
