Algoritmo de Quine
Como ya se ha indicado, el m´etodo de Quine-McCluskey, lo mismo que el de Karnaugh, se basa en utilizar repetidamente la ley a + a = 1. Dada una funci´on f en
forma can´onica de suma de m min-terms, el algoritmo es el siguiente:
1. Poner todos los min-terms en una lista, ordenados de alguna forma de 1 a m.
2. para i desde 1 hasta m − 1 hacer
Elegir el t´ermino i-´esimo, Ti
, de la lista
para j desde i + 1 hasta m hacer
Tomar el t´ermino j-´esimo, Tj, de la lista
Simplificar, si es posible, la expresi´on Ti +Tj, aplicando la ley a+a = 1
y poner el t´ermino simplificado en una nueva lista.
3. Volver al paso 1 con la nueva lista obtenida y repetir el algoritmo
4. El algoritmo termina cuando no es posible simplificar m´as.
Gran coste computacional si el n es elevado.
Facebook