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:

1. Encontrar todos os implicantes primos da função;
2. Usar esses implicantes primos num mapa de implicantes primos para encontrar os implicantes primos essenciais da função;
3. 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. Se n = 32 haverá cerca de 5.8 * 10¹³ 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.^[1]

Exemplo

Etapa 1: Implicantes primos

Minimizando uma função arbitrária:

${\displaystyle 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:

${\displaystyle 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
	m8	1000
2	m9	1001
	m10	1010
	m12	1100
3	m11	1011
	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:

${\displaystyle f_{A,B,C,D}=BC'D'+AC+AB'\ }$

${\displaystyle f_{A,B,C,D}=BC'D'+AC+AD'\ }$

Ambas as equações são mínimas e equivalentes à equação inicial:

${\displaystyle f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+A'B'CD'+ABCD.\ }$

Ver também

• Álgebra booleana
• Minimização de Circuitos
• Mapa de Karnaugh
• Willard Van Orman Quine
• Algoritmo de Buchberger (algoritmo análogo para Geometria algébrica)

Referências

1. V.P. Nelson e.a., Digital Circuit Analysis and Design, Prentice Hall, 1995, pag. 234