1. O que é um mapa de Karnaugh
Um mapa de Karnaugh é uma tabela de verdade redesenhada como grelha. Maurice Karnaugh apresentou-o nos Bell Labs em 1953 como forma de simplificar circuitos de comutação a olho, e continua a ser a maneira mais rápida de minimizar à mão uma função booleana pequena: sem álgebra, sem leis para decorar, apenas retângulos.
Cada célula do mapa contém uma linha da tabela de verdade. O que torna o mapa mais do que uma reordenação é a ordem em que essas linhas são colocadas: células vizinhas diferem em exatamente uma variável.
Essa única propriedade faz todo o trabalho. Se duas células vizinhas são ambas verdadeiras, a variável que muda entre elas não pode ser o que torna a expressão verdadeira: desaparece, e um único termo cobre as duas células. Simplificar passa a ser desenhar os maiores retângulos possíveis.
2. Porque as colunas parecem fora de ordem
As colunas de um mapa de Karnaugh não contam 00, 01, 10, 11. Vão 00, 01, 11, 10: código de Gray refletido, uma ordenação em que cada valor difere do seguinte num só bit. Contar em binário poria 01 ao lado de 10, que diferem em dois bits, e as células vizinhas deixariam de dizer alguma coisa.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
As bordas também são vizinhas. A primeira e a última coluna diferem numa variável, tal como a primeira e a última linha, pelo que um grupo pode sair por uma borda e continuar na outra - é por isso que os quatro cantos de um mapa de quatro variáveis formam um único grupo. Um mapa de Karnaugh está na verdade desenhado sobre um toro; a folha plana é apenas uma conveniência.
3. Agrupar os uns
Para ler no mapa uma soma de produtos mínima, cubra todas as células que contêm um 1 com grupos retangulares, seguindo quatro regras:
- Um grupo é um retângulo de 1, 2, 4, 8 … células: uma potência de dois em cada lado.
- Um grupo pode dar a volta pelas bordas do mapa, na horizontal, na vertical ou em ambas.
- Os grupos podem sobrepor-se. Cobrir uma célula duas vezes não custa nada; deixar uma por cobrir muda a função.
- Faça cada grupo tão grande quanto possível e depois use o menor número de grupos que cubra todos os uns.
Cada grupo dá um termo. Lê-se perguntando que variáveis se mantêm iguais em todo o grupo: essas aparecem no termo - tal como estão onde valem 1, negadas onde valem 0 - e todas as que mudam desaparecem. Um grupo de duas células perde uma variável, um de quatro perde duas, um de oito perde três. A expressão mínima é a disjunção dos termos.
4. Um exemplo resolvido
Tomemos (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). O seu mapa tem quatro variáveis: A e B nas linhas, C e D nas colunas.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
Dois grupos cobrem todos os uns. Um é o bloco de quatro células nas duas linhas onde A = 0 e nas duas colunas onde C = 1: lá dentro mudam B e D, que por isso desaparecem, e o termo é ¬A ∧ C. O outro é a linha inteira em que A e B valem 1, ao longo das quatro colunas: C e D mudam nela e resta A ∧ B.
A forma mínima é, portanto, (¬A ∧ C) ∨ (A ∧ B). O terceiro termo do original, B ∧ C ∧ D, desapareceu: cada célula que cobria já estava coberta por um dos dois grupos. É assim que a absorção se parece quando se pode ver.
5. Implicantes primos e essenciais
Um grupo que já não pode crescer chama-se implicante primo. Enumerar os implicantes primos é a metade fácil do problema; escolher quais manter é a metade que corre mal.
Se alguma célula é coberta por um único implicante primo, esse implicante é essencial: nenhuma forma mínima pode dispensá-lo, porque mais nada cobre aquela célula. Tome primeiro os implicantes essenciais e cubra depois o que sobrar com o menor número possível dos grupos restantes.
Ser ganancioso - escolher repetidamente o maior grupo ainda disponível - é tentador e nem sempre resulta. Numa tabela cíclica, onde nenhum implicante é essencial e cada célula é coberta duas vezes, a escolha gananciosa pode terminar com mais um termo do que a melhor resposta. O mapa deste site percorre exaustivamente as escolhas restantes, o que com quatro variáveis não custa nada.
6. Agrupar antes os zeros
Tudo o que ficou dito funciona igualmente bem com os zeros. Cubra-os com os mesmos retângulos, leia cada grupo com os seus literais negados - uma variável que vale 1 em todo o grupo aparece negada, uma que vale 0 aparece tal como está - e junte os grupos com ∧ em vez de ∨.
O resultado é um produto de somas: uma conjunção de disjunções falsa exatamente nas células em que a expressão é falsa e, portanto, verdadeira em todas as outras. Qual das duas formas é mais curta depende da função - uma fórmula com poucos uns tem uma soma de produtos curta, uma com poucos zeros um produto de somas curto - por isso vale a pena ler ambas no mapa antes de escolher.
7. Mapas maiores e condições indiferentes
Cinco e seis variáveis podem desenhar-se como dois ou quatro mapas de quatro variáveis empilhados, contando como adjacentes as células na mesma posição de camadas vizinhas. Funciona, mas a adjacência que tornava o método visual passa a ser algo a lembrar em vez de ver. Para além disso, o algoritmo de Quine-McCluskey faz o mesmo trabalho em forma de tabela: é a versão mecânica exatamente deste agrupamento, e é o que corre por trás dos mapas daqui.
O projeto de hardware acrescenta mais uma ideia. Algumas combinações de entrada nunca ocorrem - um dígito decimal codificado em binário nunca é 1010 - por isso ao projetista é indiferente o que o circuito faz com elas. Essas células marcam-se com um X e podem ser lidas com qualquer dos valores, aquele que aumentar os grupos. Os mapas desta calculadora são construídos a partir de uma fórmula, que dá um valor a cada atribuição, pelo que nenhuma célula é indiferente.
8. Experimente
Escreva na calculadora uma expressão de duas a quatro variáveis e o seu mapa aparece por baixo da tabela de verdade, com cada grupo contornado na sua própria cor e a forma mínima escrita em baixo. Mude para produto de somas para ver os zeros agrupados.