Aprenda › Tema 5
Método de Quine-McCluskey passo a passo
Leitura de 7 min · Equipe bitGateLab
O mapa de Karnaugh é rápido para quatro variáveis, mas depende da sua visão e deixa de ser prático com cinco ou mais. O método de Quine-McCluskey faz o mesmo trabalho com tabelas e regras mecânicas: não exige intuição, sempre encontra todos os implicantes primos e é a base dos programas que simplificam funções lógicas. Aqui você vai entender as suas duas etapas, identificar os implicantes primos essenciais e resolver um exemplo completo de quatro variáveis.
Vocabulário: implicantes e primos
- Um implicante de F é um termo-produto que, quando vale 1, garante que F vale 1. Cada mintermo de F é um implicante, e também o é qualquer grupo válido de um mapa de Karnaugh.
- Um implicante primo é um implicante que não pode ser mais ampliado; se você retira uma variável dele, ele passa a cobrir alguma linha em que F vale 0. Equivale a um grupo máximo do mapa.
- Um implicante primo essencial é um primo que cobre pelo menos um mintermo que nenhum outro primo cobre. Ele tem de aparecer em qualquer solução mínima.
O método tem duas etapas: primeiro encontra todos os implicantes primos combinando termos; depois escolhe o menor conjunto de primos que cubra todos os mintermos.
Etapa 1: combinar termos
Cada termo é escrito em binário, e a posição de uma variável eliminada é marcada com um traço. Por exemplo, com as variáveis A, B, C, D, o termo 0-11 significa ACD (B foi eliminada).
- Agrupe os mintermos de acordo com a quantidade de uns do seu código binário.
- Compare cada termo de um grupo com cada termo do grupo seguinte. Se diferirem em um único bit, combine-os colocando um traço nessa posição e marque os dois originais como usados.
- Repita com a nova lista. Só se combinam termos que têm os traços nas mesmas posições.
- Quando não for mais possível combinar nada, os termos que nunca foram marcados são os implicantes primos.
Etapa 2: tabela de implicantes primos
Monta-se uma tabela com uma linha para cada implicante primo e uma coluna para cada mintermo da função (as condições irrelevantes não têm coluna). Marca-se quais mintermos cada primo cobre. Em seguida:
- Procure colunas com uma única marca. O primo dessa linha é essencial: selecione-o e risque todas as colunas que ele cobre.
- Com as colunas que restarem, escolha o menor número de primos que as cubra. Se dois primos cobrem a mesma coisa, qualquer um serve; prefira o de menos literais.
Exemplo completo. Simplifique F(A, B, C, D) = Σm(0, 2, 3, 5, 7, 8, 10, 11, 13, 15).
Passo 1. Agrupar pela quantidade de uns.
| Uns | Mintermos |
|---|---|
| 0 | 0 (0000) |
| 1 | 2 (0010), 8 (1000) |
| 2 | 3 (0011), 5 (0101), 10 (1010) |
| 3 | 7 (0111), 11 (1011), 13 (1101) |
| 4 | 15 (1111) |
Passo 2. Primeira combinação (pares). Comparam-se grupos vizinhos. O 8 não se combina com o 3 nem com o 5 porque diferem em mais de um bit.
| Grupos | Pares formados |
|---|---|
| 0 e 1 | (0,2) 00-0; (0,8) -000 |
| 1 e 2 | (2,3) 001-; (2,10) -010; (8,10) 10-0 |
| 2 e 3 | (3,7) 0-11; (3,11) -011; (5,7) 01-1; (5,13) -101; (10,11) 101- |
| 3 e 4 | (7,15) -111; (11,15) 1-11; (13,15) 11-1 |
Os dez mintermos ficaram marcados como usados; há 13 pares.
Passo 3. Segunda combinação (quadras). Combinam-se pares que têm o traço na mesma posição e diferem em um bit:
- (0,2) com (8,10), ou então (0,8) com (2,10): -0-0, cobre 0, 2, 8, 10.
- (2,3) com (10,11), ou (2,10) com (3,11): -01-, cobre 2, 3, 10, 11.
- (3,7) com (11,15), ou (3,11) com (7,15): --11, cobre 3, 7, 11, 15.
- (5,7) com (13,15), ou (5,13) com (7,15): -1-1, cobre 5, 7, 13, 15.
Os 13 pares foram usados em alguma quadra. As quatro quadras já não se combinam entre si (nenhuma tem os traços nas mesmas posições que outra e difere dela em um único bit). Portanto, os implicantes primos são:
- P1 = -0-0 = BD
- P2 = -01- = BC
- P3 = --11 = CD
- P4 = -1-1 = BD
Passo 4. Tabela de cobertura.
| Primo | 0 | 2 | 3 | 5 | 7 | 8 | 10 | 11 | 13 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|
| P1 BD | ✔ | ✔ | ✔ | ✔ | ||||||
| P2 BC | ✔ | ✔ | ✔ | ✔ | ||||||
| P3 CD | ✔ | ✔ | ✔ | ✔ | ||||||
| P4 BD | ✔ | ✔ | ✔ | ✔ |
Passo 5. Essenciais. As colunas 0 e 8 só têm marca em P1, portanto P1 é essencial. As colunas 5 e 13 só têm marca em P4, portanto P4 também é essencial. Juntos, eles cobrem 0, 2, 5, 7, 8, 10, 13 e 15.
Passo 6. Cobrir o restante. Faltam os mintermos 3 e 11. P2 cobre os dois, e P3 também. Qualquer um dos dois completa a solução com o mesmo número de literais.
Resultado: F = BD + BD + BC, ou então F = BD + BD + CD. Ambas têm três termos e seis literais.
Se você desenhar essa função em um mapa de Karnaugh, P1 são os quatro cantos, P4 é o bloco central, P2 são as colunas 11 e 10 das linhas 00 e 10 (unidas pela borda) e P3 é a coluna 11 completa. O método tabular chega ao mesmo resultado sem precisar ver o mapa.
Condições irrelevantes e tabelas cíclicas
As condições X são incluídas na etapa 1 como se fossem uns, porque podem ajudar a formar implicantes maiores. Na etapa 2 elas são omitidas: não têm coluna, já que não é obrigatório cobri-las. Um primo formado só por X nunca é necessário.
Às vezes, depois de escolher os essenciais, ou desde o início, cada coluna tem pelo menos duas marcas e não há uma forma óbvia de decidir. Essa situação é chamada de tabela cíclica. Ela se resolve por tentativa: você escolhe um primo, retira o que ele cobre e repete, comparando as soluções obtidas. Para tabelas grandes existe um procedimento algébrico (o método de Petrick) que enumera todas as coberturas possíveis.
Erros comuns
- Combinar termos com traços em posições diferentes, como 0-01 com 00-1. Não é válido, embora pareçam diferir em um bit.
- Esquecer de marcar como usados os dois termos de cada combinação e depois listar como primo algo que não é.
- Colocar colunas para as condições X na tabela de cobertura, o que obriga a cobri-las sem necessidade.
- Escolher primos não essenciais antes dos essenciais. Primeiro garanta os essenciais; depois decida o restante.
- Escrever errado o termo a partir do código: em -0-1 a variável B vai negada (vale 0), a D vai sem negar (vale 1), e A e C desaparecem.
Experimente no simulador
O simulador simplifica as funções com esse tipo de procedimento, de modo que você pode usá-lo para conferir cada etapa do seu trabalho à mão.
- Crie uma tabela-verdade de quatro variáveis e marque com 1 os mintermos do exemplo.
- Faça as etapas 1 e 2 no papel e escreva o seu resultado.
- Observe a expressão mínima que a ferramenta fornece e o mapa de Karnaugh correspondente; identifique qual grupo corresponde a cada implicante primo.
- Converta as duas soluções possíveis em circuito no mesmo desenho e mude as entradas para confirmar que elas sempre dão a mesma saída.
Exercícios
- Encontre os implicantes primos e a expressão mínima de F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 11, 15).
Resposta
Primos: -00- (BC), -0-1 (BD) e --11 (CD). A coluna 0 só é coberta por BC, e a 7 só é coberta por CD: ambos são essenciais e juntos cobrem tudo. F = BC + CD. O primo BD sobra.
- Resolva F(A, B, C) = Σm(0, 1, 2, 5, 6, 7). Há primos essenciais?
Resposta
Os pares são 00-, 0-0, -01, -10, 1-1 e 11-, e nenhum se combina em quadra: são seis primos. Cada mintermo é coberto por exatamente dois, portanto não há essenciais (tabela cíclica). Duas soluções mínimas: AB + BC + AC, ou AC + BC + AB.
- Simplifique F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15).
Resposta
Incluindo os X na etapa 1, obtêm-se quatro primos: -0-1 (BD), -01- (BC), --11 (CD) e 1--1 (AD). Na tabela, sem colunas para 1, 10 e 15: o 2 só é coberto por BC, o 7 só por CD e o 13 só por AD. Os três são essenciais e cobrem também 3, 9 e 11. F = BC + CD + AD.
- Por que, na etapa 1, não se compara o grupo dos códigos com apenas um bit igual a um com o grupo dos códigos com três uns?
Resposta
Porque um código com apenas um bit igual a um e outro com três uns diferem em pelo menos dois bits, e para se combinarem devem diferir em exatamente um.