# Mapas de Karnaugh

Agrupar mintermos e maxtermos com adjacência, fronteiras e condições indiferentes.

Página: https://resumos.rgo.pt/cadeiras/fsc/karnaugh/

As linhas `ABC=001` e `011` diferem só em B. Os seus mintermos somam $\overline A\overline BC+\overline ABC=\overline AC$: B desaparece porque pode valer 0 ou 1. Um mapa de Karnaugh coloca estas combinações em células vizinhas para tornar visíveis os grupos que eliminam variáveis.

## Ordem e adjacência

As etiquetas usam código Gray: `00, 01, 11, 10`. Passar de uma coluna à seguinte muda um só bit, e a primeira e a última também são adjacentes; nos mapas de quatro variáveis, o mesmo acontece com as linhas, e os quatro cantos formam um grupo possível.

Não há adjacência diagonal. Os grupos são retângulos com $1,2,4,8,\ldots$ células. Um retângulo pode atravessar uma fronteira do mapa. Um grupo de três células não elimina uma quantidade inteira de variáveis e não é válido.

## Exemplo de soma de produtos

Considera $F(A,B,C)=\Sigma m(1,3,5,6,7)$, representada na tabela seguinte em código Gray:

| $A\backslash BC$ | 00 | 01 | 11 | 10 |
| --- | --- | --- | --- | --- |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |

![Mapa de Karnaugh de duas linhas, A=0 e A=1, e quatro colunas BC em código Gray: 00, 01, 11, 10. Os índices são 0, 1, 3, 2 na primeira linha e 4, 5, 7, 6 na segunda. Há 1 nos mintermos 1, 3, 5, 6 e 7 e 0 nos restantes. O contorno contínuo agrupa 1, 3, 5 e 7, dando C; o tracejado agrupa 6 e 7, dando AB. O mintermo 7 pertence aos dois grupos.](https://resumos.rgo.pt/cadeiras/fsc/karnaugh/figura-1.svg)

Observa as variáveis que ficam constantes dentro de cada contorno. Uma variável desaparece porque aparece negada numa metade do grupo e direta na outra: $AB+A\overline B=A(B+\overline B)=A\cdot 1=A$, por distributividade e complemento. É a identidade aplicada às células vizinhas, não um atalho gráfico; no contínuo, $C=1$ enquanto $A$ e $B$ variam, por isso obtemos $C$, e no tracejado, $A=B=1$ enquanto $C$ varia, por isso obtemos $AB$.

Falta a célula 6 depois de formar o grupo de quatro, por isso agrupa-a com a célula 7 na coluna `11`, mesmo que esta já pertença ao grupo $C$.

Portanto $F=C+AB$. A célula 7 pertence aos dois grupos, o que é permitido. Sem essa sobreposição precisaríamos de um termo maior. Cada 1 tem de ficar coberto; cobrir uma célula 0 tornaria a expressão errada.

## Implicantes essenciais

Um grupo de 1 que não pode ser alargado sem incluir um 0 é um implicante primo. Maximal não significa maior do mapa: o grupo AB tem duas células e também é primo. Um primo é essencial quando cobre algum 1 que nenhum outro primo cobre.

No exemplo, a célula 1 só pode entrar no grande grupo $C$, e a célula 6 só pode entrar no grupo $AB$. Ambos são necessários. Noutros mapas, vários grupos não essenciais podem completar a cobertura. Escolhe uma combinação que cubra os 1 restantes, preferindo menos termos e menos literais quando esse é o custo pedido.

Um grupo pequeno válido pode ser redundante. Acrescentá-lo não muda a função, mas aumenta o circuito. Não é obrigatório desenhar todos os grupos possíveis.

## Produto de somas

Para obter POS, agrupa os **zeros**. As células 0 e 4, na coluna `00`, têm $B=C=0$, por isso o fator é $(B+C)$: só fica 0 quando ambos são 0. As células 0 e 2, na linha $A=0$ e nas colunas `00,10` que se tocam pela fronteira, dão $(A+C)$.

Assim, com

$$
F=(B+C)(A+C)=C+AB.
$$

Nos fatores de zeros, uma variável constante em 0 fica direta e uma constante em 1 fica negada. É a regra inversa da usada nos produtos dos grupos de 1. Não negues a função inteira ao passar de SOP para POS. Confirma cada fator substituindo um zero coberto: esse zero tem de anular o fator e, por isso, toda a expressão.

## Quatro variáveis

Para $F(A,B,C,D)=\Sigma m(0,2,8,10)$, usamos $AB$ nas linhas e $CD$ nas colunas, ambas em código Gray, com

| $AB\backslash CD$ | 00 | 01 | 11 | 10 |
| --- | --- | --- | --- | --- |
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 0 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 |
| 10 | 1 | 0 | 0 | 1 |

Os quatro cantos pertencem ao mesmo grupo, atravessando as duas fronteiras. $A$ e $C$ mudam, mas $B=D=0$ em todos os cantos. O produto é $\overline B\overline D$. Escolher a ordem binária `00,01,10,11` esconderia esta adjacência e poderia levar a grupos errados.

## Condições indiferentes

Uma célula $X$ significa que a especificação permite qualquer saída nessa combinação. Podes tratá-la como 1 para alargar um grupo de 1, ou como 0 para alargar um grupo de 0, sem obrigação de usar todos os $X$.

Por exemplo, $G=\Sigma m(1,3,7)$ com indiferentes 5 e 6 permite agrupar 1,3,5,7 e obter $G=C$. No índice 5, o circuito dará 1, mas isso é permitido. Se 5 fosse um zero obrigatório, o grupo seria inválido.

Um estado não usado só pode ser indiferente se o comportamento nesse estado for realmente livre. Se o circuito tiver de recuperar de um estado inválido, essa recuperação impõe valores nas equações.

## Função correta e tempo

Para além da tabela: hazards

Simplificar uma função não elimina os atrasos das portas. Num circuito $AB+\overline AC$ com $B=C=1$, mudar $A$ pode causar uma breve saída 0 se um caminho se desligar antes de o outro ligar. O termo de consenso $BC$ pode cobrir a transição e evitar este hazard estático no modelo de atrasos considerado.

A tabela de verdade descreve estados estáveis. Uma pergunta sobre impulsos transitórios exige seguir os caminhos e os atrasos, além de simplificar a expressão.

## Exercícios

Usar as bordas

Simplifica $F(A,B,C,D)=\Sigma m(1,3,9,11)$ num mapa 4×4. Indica o grupo.

Pista

As linhas e colunas usam 00,01,11,10.

Mais uma pista

As linhas 00 e 10 são adjacentes pela fronteira; as colunas 01 e 11 também são adjacentes.

Solução

As células nas linhas AB=00,10 e colunas CD=01,11 formam um grupo de quatro que atravessa a fronteira das linhas. Em 0001,0011,1001,1011, A e C variam, enquanto B=0 e D=1. Logo $F=\overline BD$. Não são quatro células isoladas.

Confere a tua resposta:

*   Agrupa as duas linhas exteriores e as duas colunas centrais.
*   Obtém B negado AND D.

Erros frequentes

Não uses a distância geométrica dentro da folha para decidir adjacência.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fsc/karnaugh/#ordem-e-adjac%C3%AAncia)

A condição é obrigatória?

Uma função de três entradas tem 1 nos índices 1,3,7 e X no índice 5; nos restantes índices é 0. Simplifica e indica o valor que o circuito escolhido produz no índice 5.

Pista

X pode completar um grupo maior.

Solução

Escolhe X como 1 e agrupa as quatro células; F=C. Portanto no índice 5 o circuito produz 1. Isso é permitido pela especificação, mas seria incorreto se 5 fosse um zero obrigatório. Não é necessário implementar uma saída física chamada X.

Confere a tua resposta:

*   Obtém F=C usando o índice 5.
*   Explica que o circuito produz 1 no X escolhido.

Erros frequentes

X significa liberdade de especificação, não uma terceira saída lógica.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fsc/karnaugh/#condi%C3%A7%C3%B5es-indiferentes)

Agrupar zeros

F é 0 nos índices 0,1,4,5 de uma função ABC; nos restantes índices é 1. Obtém um produto de somas simplificado.

Pista

Procura a variável que se mantém em todas as linhas a zero, porque é ela que forma o fator.

Solução

Os quatro zeros têm B=0 e A,C variáveis. O fator que vale 0 nesse grupo é B. Assim F=B, uma POS com um único fator. O grupo dos 1 também dá B, confirmando as restantes linhas.

Confere a tua resposta:

*   Agrupa zeros com B=0.
*   Obtém o fator B, sem negar a função.

Erros frequentes

Agrupar zeros não significa que a resposta final seja o complemento de F.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fsc/karnaugh/#produto-de-somas)

Saída estável, circuito transitório

Em $F=AB+\overline AC$, B=C=1 e A muda de 0 para 1. Explica um possível impulso indesejado e um termo que o evita no modelo de portas com atrasos.

Pista

A saída lógica deveria ficar sempre 1.

Mais uma pista

Os caminhos direto e negado de A podem chegar em instantes diferentes.

Solução

Antes da mudança, $\overline AC=1$; depois, AB=1. Se o primeiro produto cair antes de o segundo subir, a OR vê brevemente dois zeros: hazard estático de 1. O termo BC permanece 1 durante a mudança e cobre o intervalo. Adicioná-lo não altera a tabela estável porque é um termo de consenso.

Confere a tua resposta:

*   Descreve a possível janela em que os dois produtos ficam zero.
*   O termo BC mantém a saída 1 durante a transição.

Erros frequentes

A equivalência algébrica não prova que as transições são livres de glitches, porque a tabela só descreve estados estáveis.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fsc/karnaugh/#fun%C3%A7%C3%A3o-correta-e-tempo)