Willard Van
Orman Quine
Edward J.
McCluskey
Mathyan Motta Beppu (Aluno do sexto período de Telecomunicações)
Pet-Tele
21 setembro de 2010
Niterói-RJ






Técnicas de minimização;
Padronização da linguagem utilizada;
O passo a passo do algoritmo;
Um exemplo executado manualmente;
Particularidades do algoritmo;
O algoritmo implementado em Lua.
OBS: Motivação para simplificar.



Manipulação Algébrica
Mapa de karnaugh
Método de Quine-McCluskey




Muito trabalhoso
Exige o conhecimento de inúmeros postulados
Dificuldade de obter a melhor simplificação
Definição de mínimo bastante subjetivo




Mais simples que o método algébrico
Método visual
Menos subjetivo e mais sistemático
Para funções de mais de 6 variáveis o método
torna-se impraticável




Método sistemático e procedural
Apresenta TODAS as combinações de mintermos(ou Max - termos) e seleciona a
combinação mínima
Pode ser aplicado para funções dependentes de
n variáveis
Possibilidade de ser implementado por um
algoritmo computacional
Termos conhecidos:
 Tabela verdade
 Soma de produtos(SOP)
 Produto de somas(POS)
Termos não conhecidos;
 Min-termos e Max - termos
 Implicantes e implicados





Min-termos: Soma de min-termos ou soma de
produtos padrão.
Max - termos: Produto de max-termos ou
produto de somas padrão.
Implicantes:Termos que geram F( )=1;
Implicados:Termos que geram F( )=0;
Por definição:
-Max-termos são implicados
-Min-termos são implicantes
1.
2.
3.
4.
Listar os min-termos e colocá-los na forma
binária;
Agrupá-los de acordo com a quantidade de
1’s(0-cubos);
Comparar os min-termos de grupos adjacentes
agrupando os que diferem de uma posição
apenas(1-cubos);
Organizar os 1-cubos encontrados e comparálos da mesma maneira da etapa anterior,
formando 2-cubos;
5.
6.
7.
Repetir o procedimento de comparações até
não haver mais possibilidade de se formar
n-cubos;
Construir uma nova tabela com os implicantes
primos,visando obter a melhor minimização
possível;
Expressão simplificada final.
F(a,b,c,d)= ∑m(0,2,3,6,7,8,9,10,13)
Mapa “K”
X
Quine-McCluskey
“Voluntário”
O algoritmo básico não abrange as seguintes
situações:


Funções com mais de uma SOP(ou POS)
mínima;
Decisões com o mesmo custo;
Decisão extra
Branching ou algoritmo de Petricle
Definições para entendimento do resultado
algoritmo:
0 equivale a variável negada (ex: A~)
1 equivale a variável não negada(ex: A)
-1 equivale a variável simplificada
Email: [email protected]
Grupo Pet-tele