# Algoritmo de Quine-McCluskey

O Algoritmo de Quine–McCluskey (ou método dos implicantes primos) é um método utilizado para minimização de funções booleanas desenvolvido por W.V. Quine e Edward J. McCluskey em 1956. É funcionalmente idêntico ao mapa de Karnaugh, mas a forma tabular o faz mais eficiente para uso em algoritmos computacionais, além de fornecer um algoritmo determinístico para checar se a forma mais simplificada de uma função booleana foi alcançada.
O procedimento consiste em 3 etapas:
* Encontrar todos os implicantes primos da função;
* Usar esses implicantes primos num mapa de implicantes primos para encontrar os implicantes primos essenciais da função;
* Usar os implicante primos essenciais e se necessário alguns implicantes primos para encontrar a função minimizada.

## Complexidade

Embora mais prático do que o mapa de Karnaugh ao lidar com mais de 4 variáveis, o algoritmo de Quine-McCluskey também possui limitações devido ao fato de o problema resolvido por ele ser NP-difícil: o tempo de execução do algoritmo de Quine-McCluskey cresce exponencialmente em relação ao número de variáveis. Pode-se mostrar que para uma função de n variáveis o limite superior no número de implicantes primos é 3$^n$/n. Se n = 32 haverá cerca de 5.8 * 10$^{13}$ implicantes primos. Funções com grande número de variáveis têm de ser simplificadas com heurísticas não-ótimas, das quais o ESPRESSO é considerado um padrão.

## Exemplo
### Etapa 1: Implicantes primos

Minimizando uma função arbitrária:
    $f(A,B,C,D)=\sum m(4,8,10,11,12,15)+d(9,14).\,$
Esta expressão diz que a saída da função f será 1 para os mintermos 4,8,10,11,12 e 15 (denotados por 'm'), além de haver saídas irrelevantes, chamados don't care, definidas pelos minitermos 9 e 14.
| | A | B | C | D | f |
| m0 | 0 | 0 | 0 | 0 | 0 |
| m1 | 0 | 0 | 0 | 1 | 0 |
| m2 | 0 | 0 | 1 | 0 | 0 |
| m3 | 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 |
Obtemos facilmente a soma de produtos a partir desta tabela, simplesmente somando os mintermos e desprezando os termos don't care:
    $f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'CD'+AB'CD+ABC'D'+ABCD.$
A fórmula acima não está em sua forma mais simplificada. Para encontrar os minitermos primos, primeiro agrupa-se todos os minitermos em uma tabela. Separando em grupos baseado na quantidade de 1's presentes.
| Número de 1s | Mintermo | Representação Binária |
| 1 | m4 | 0100 |
| 1 | m8 | 1000 |
| 2 | m9 | 1001 |
| 2 | m10 | 1010 |
| 2 | m12 | 1100 |
| 3 | m11 | 1011 |
| 3 | m14 | 1110 |
| 4 | m15 | 1111 |
Começando pelo primeiro elemento do primeiro grupo da tabela, compare-o com todos os termos do grupo seguinte. Toda vez que que a combinação for possível a menos de um dígito deve-se anotar o código resultante em uma outra tabela, substituindo o dígito divergente pelo sinal -. Toda vez que um termo não possuir combinação deve-se marcá-lo pois este representa um implicante primo. Repete-se o procedimento para cada termo do primeiro grupo. Faça o mesmo para o segundo grupo, comparando seus termos com os termos do terceiro grupo.
Depois de realizar o procedimento em toda a tabela. Repita o procedimento para a tabela gerada. O algorítimo continua até que não haja mais combinações possíveis.
| Número de 1's | Coluna 1 | Marca | Coluna 2 | Marca | Coluna 3 | Marca |
| 0 | | | |
| 1 | 0100 | ok | 100- | ok | 10-- | * |
| | 1000 | ok | 10-0 | ok | 1--0 | * |
| | | | 1-00 | ok |
| | | | -100 | * |
| 2 | 1001 | ok | 10-1 | ok | 1-1- | * |
| | 1010 | ok | 101- | ok |
| | 1100 | ok | 1-10 | ok |
| | | | 11-0 | ok |
| 3 | 1011 | ok | 1-11 | ok |
| | 1110 | ok | 111- | ok |
| 4 | 1111 | ok |
Neste exemplo, nenhum dos termos da coluna 3 pôde ser combinado. Se não fosse o caso, o algorítimo continuaria.

### Etapa 2: Implicantes primos essenciais

Usando os implicantes primos essenciais constrói-se o mapa a seguir. A primeira linha do mapa representa os minitermos envolvidos. A primeira coluna mostra os implicantes primos e quais minitermos ele pode representar. Para definir quais os minitermos cada implicante primo pode representar usa-se o código substituindo o - por 0 e por 1 de forma a gerar todas as combinações possíveis.
| Implicante primo | minitermos representáveis | 4 | 8 | 10 | 11 | 12 | 15 | A | B | C | D |
| -100 | m(4,12)* | X | | | | X | | - | 1 | 0 | 0 |
| 10-- | m(8,9,10,11) | | X | X | X | | | 1 | 0 | - | - |
| 1--0 | m(8,10,12,14) | | X | X | | X | | 1 | - | - | 0 |
| 1-1- | m(10,11,14,15)* | | | X | X | | X | 1 | - | 1 | - |
Olhando as colunas da tabela observa-se que os implicantes primos são aqueles que possuem apenas um X e uma das colunas. Se um implicante primo é essencial, então será necessário incluí-lo na equação booleana simplificada. Em alguns casos, os implicantes primos essenciais não cobrem todos os minitermos. Nesses casos deve-se adicionar termos não essenciais de forma a cobrir todos os minitermos. Esse procedimento deve visar a menor quantidade possível de adições. Para proceder forma mais analítica pode ser usado o método de Petrick. Neste exemplo podemos combinar os implicantes essenciais com um dos não essenciais para cobrir todos os minitermos e obter uma das equações:
    $f_{A,B,C,D}=BC'D'+AC+AB'\$
    $f_{A,B,C,D}=BC'D'+AC+AD'\$
Ambas as equações são mínimas e equivalentes à equação inicial:
    $f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+A'B'CD'+ABCD.\$