Aula 05 Mapa de Karnaugh

Prévia do material em texto

Sistemas Digitais
Aula 05: Mapa de Karnaugh
Apresentação
Estudaremos o Mapa de Karnaugh, um método de simpli�cação grá�ca criado por Edward Veitch e aperfeiçoado pelo
engenheiro de telecomunicações Maurice Karnaugh.
Veremos a base teórica que viabiliza o ábaco, capaz de, a partir de Tabelas Verdades, construir expressões canônicas
mínimas.
Aprenderemos também como aplicar o ábaco em situações de quatro variáveis lógicas.
Objetivos
Montar Mapas de Karnaugh de quatro variáveis;
Aplicar o mapa de Karnaugh na obtenção de expressões lógicas canônicas mínimas de tabelas de quatro variáveis;
Explicar o conceito de Don’t care e situações especiais nos Mapas de Karnaugh.
Mapa de Karnaugh de quatro variáveis
 (Fonte: Shutterstock).
Na aula anterior, vimos como aplicar o ábaco Mapa de Karnaugh para encontrar a forma canônica mínima para funções lógicas
de duas e três variáveis.
 
Nesta aula, veremos com aplicar o ábaco para encontrar a forma canônica mínima em funções de quatro variáveis.
Já sabemos que o Mapa de Karnaugh deriva do diagrama, descoberto por Karnaugh, que mostra todos os binários distantes
unitários de, neste caso especí�co, quatro bits (diagrama 1).
 Diagrama 1 – Binários distantes unitários de 4 bits. Fonte: Elaborado pelo autor, 2020.
Vamos relembrar que cada binário é associado a um termo da tabela verdade da função lógica para a qual queremos encontrar
a expressão canônica mínima. Por exemplo: O binário 1001 representa o termo: ABCD. Isso posto, vejamos a montagem do
mapa:
 Mapa 1 – Mapa de Karnaugh de quatro variáveis. Fonte: Elaborado pelo autor, 2020.
Para exempli�car a montagem do mapa, vamos utilizar como exemplo a tabela verdade 1, com quatro variáveis.
 Tabela verdade 1 – Função lógica de quatro variáveis. Fonte: Elaborada pelo autor, 2020.
A tradução da tabela verdade para o Mapa de Karnaugh é semelhante ao que vimos nos mapas de 2 e 3 variáveis, o valor
verdade de cada termo da tabela é colocado no binário associado ao termo. Por exemplo: O termo 𝐴𝐵 ̅𝐶𝐷 é associado ao
binário 1011.
 Mapa 2 – Mapa de Karnaugh de quatro variáveis. Fonte: Elaborado pelo autor, 2020.
Comentário
Relembremos que, no Mapa de Karnaugh, 0 é FALSO e 1 é VERDADEIRO, como já foi dito na aula anterior, isso é uma convenção.
Não vamos confundir com os níveis lógicos 0 e 1, que são diferenças de potencial elétrico que ativam os circuitos das portas
lógicas..
Leitura do Mapa
O processo de leitura do Mapa de Karnaugh de quatro variáveis é
semelhante aos de três e duas variáveis. Como vimos na aula anterior, um
Mapa de Karnaugh de k variáveis admite agrupamentos de 2 , 2 , ..., 2 1s.k k-1 0
Agrupamento de dezesseis 1s
O agrupamento de dezesseis 1s é análogo ao agrupamento de oito 1s no mapa de três variáveis e de quatro 1s no mapa de
duas variáveis.
Conforme vimos, o agrupamento de 2 1 só ocorre quando a função lógica é uma tautologia, isto é, a tabela verdade da função
tem todas as linhas com valor verdade VERDADEIRO.
Agrupamento de oito 1s
No mapa exemplo (mapa 2) temos a possibilidade de agrupar oito 1s. O agrupamento de oito 1s ocorre no mapa exemplo
conforme destacado no mapa 3.
k
 Mapa 3 – Agrupamento de oito variáveis modo horizontal. Fonte: Elaborado pelo autor, 2020.
Vamos à leitura do agrupamento do mapa 3:
ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD = D(ABC + ABC + ABC + ABC + ABC + ABC + ABC + ABC) = D(AB(C +
Também como vimos na aula passada, o Mapa de Karnaugh tem por objetivo não fazer a manipulação algébrica. A leitura é
feita encontrando-se a variável que não tem o valor lógico alterado em todos os 1s do agrupamento. Nesse agrupamento
temos: A0B0C0D1, A0B0C1D1, A0B1C0D1, A0B1C1D1, A1B1C0D1, A1B1C1D1, A1B0C0D1, A1B0C1D1: Observe que D não tem
o valor lógico negado em todos os 1s do agrupamento. Assim como já esperado, a leitura do agrupamento é D.
No próprio exemplo existe um outro agrupamento de oito 1s. Lembremos que as extremidades do mapa são distantes
unitárias, assim, o agrupamento do mapa 4 é um agrupamento de oito 1s.
 Mapa 4 – Agrupamento de oito variáveis modo horizontal. Fonte: Elaborado pelo autor, 2020.
A leitura é feita da mesma forma, os termos para cada 1 do agrupamento são: A0B0C0D0, A0B0C0D1, A0B0C1D1, A1B0C0D0,
A1B0C0D0, A1B0C0D1, A1B0C1D1, A1B0C1D0. Destacado, temos a variável B com o valor lógico negado; assim, a leitura do
agrupamento é B.
Agrupamento de quatro 1s
No exemplo, temos um agrupamento de quatro 1s. O mapa 5 destaca esse agrupamento.
 Mapa 5 – Agrupamento de quatro 1s modo quadrado. Fonte: Elaborado pelo autor, 2020.
A leitura é feita de forma análoga, bastando destacar os termos correspondentes a cada 1 do grupamento: A1B1C1D1,
A1B1C1D0, A1B0C1D1, A1B0C1D0. Observa-se que as variáveis A e B estão presentes em todos os termos com mesmo valor
verdade, assim, a leitura é 𝐴𝐶.
O agrupamento de quatro 1s pode ser linear, conforme podemos ver no mapa 6.
 Mapa 6 – Agrupamento de quatro 1s modo linear. Fonte: Elaborado pelo autor, 2020.
A leitura é A0B0 C1D1 , A0B1 C1D1 , A1B1 C1D1 , A1B0 C1D1 , resultando no termo: 𝐶𝐷
 
No mesmo mapa 6, existe outro agrupamento de quatro 1s, aberto para as laterais. Com �ns didáticos, o mapa 5 será
transcrito para o mapa 7.
 Mapa 7 – Agrupamento de quatro 1s modo aberto para as laterais. Fonte: Elaborado pelo autor, 2020.
Destacando os termos, A0B0C1D1, A0B0C1D0, A1B0C1D1, A1B0C1D0, temos a leitura: BC.
Existe um quarto agrupamento de quatro 1s: Os da extremidade do mapa, transcrito no mapa 8.
 Mapa 8 – Agrupamento de quatro 1s das extremidades. Fonte: Elaborado pelo autor, 2020.
Esse agrupamento é válido uma vez que os binários das extremidades das linhas e das colunas são distantes unitários.
A leitura do mapa 8 é: A0B0C0D0, A0B0C1D0, A1B0C0D0, A1B0C1D0, resultando no termo: BD.
Agrupamento de dois 1s
O agrupamento de dois 1s é muito semelhante ao que vimos nos mapas de duas e três variáveis, podendo ser: Vertical,
horizontal e aberto nas extremidades, como no mapa de três variáveis. Vejamos um exemplo com as três possibilidades no
mapa 9.
 Mapa 9 – Agrupamento de dois 1s. Fonte: Elaborado pelo autor, 2020.
No mapa 8, o agrupamento A é horizontal, os termos correspondentes aos 1s são A0B0C1D1 e A0B1C1D1, resultando na
leitura: ACD. O agrupamento B é vertical, os termos correspondentes aos 1s são: A0B1C0D1 e A0B1C1D1, resultando na leitura
ABD. Finalmente, o agrupamento C é aberto nas extremidades e resulta nos termos: A1B0C0D0 e A1B0C1D0, com leitura: ABD.
Agrupamento de 1 isolado
O ultimo tipo de agrupamento é o do 1 isolado, cuja leitura é direta. O mapa 10 mostra um exemplo.
 Mapa 10 – Agrupamento de 1 isolado. Fonte: Elaborado pelo autor, 2020.
A leitura do termo é A0B0C0D0, resultando no termo: ABCD.
O algoritmo de agrupamento de 1 é semelhante ao do mapa de três variáveis, sendo descrito como:
O último passo do ábaco é a leitura. Cada agrupamento é um termo de uma conjunção, terminando assim o ábaco.
Como exemplo, vamos realizar o ábaco completo na função lógica representada pela tabela verdade 1, que resulta no mapa 1,
transcrito a seguir para �ns didáticos (mapa 11):
 Mapa 11 – Mapa exemplo. Fonte: Elaborado pelo autor, 2020.
Leitura: 
Grupamento A: B; 
Grupamento B: D; 
Grupamento C: AC; 
resultando na função lógica F = B + D + AC.
O termo X – não relevante ou Don’t care
Em algumas situações, algumas entradas na tabela verdade de um Função Lógica podem não ter sentido prático. Isso ocorre
quando a combinação de valores lógicos da entrada não tem sentido na semântica do problema que está sendo resolvido pela
função lógica.
Quando isso ocorre, inserimos na tabela verdade da função lógica o valor X em vez de 0 ou de 1. Isso ocorre para que, no
momento dos agrupamentos, utilizemos o X da forma mais conveniente possível. Isto é, caso seja vantajoso, consideramos X
como 1; caso não seja, consideramos X como 0.
Exemplo
CDF = (ABD + ABD) (C + C) + ABC + ACD + ABC + ACDF = ABCD + ABCD + ABCD + ABCD + ABC + ACD + ABC + ACDF= ACD(1 + B) + ABC(1 + D) + ABC(1 + D) + ACD(1 + B)F = ACD + ABC + ABC + ACD
Imaginemos um prédio de 6 andares: Um térreo (0), três comerciais (1, 2 e 3) e os dois últimos (4 e 5) residenciais. Por motivo de
segurança, o elevador pode ser con�gurado para atender chamadas somente para o uso residencial ou o comercial. O circuito que
decide se a chamada será aceita recebe quatro sinais lógicos: O sinal R que, caso verdadeiro, indica que o elevador só atenderá às
residências e, caso contrário, os andares comerciais; e A, B, C é um número binário de três bits indicando o andar de chamada. A
saída da função lógica F é V, caso a chamada seja aceita, e 0, no caso contrário.
Veja a resolução desta simulação.
O exemplo mostra o uso prático do Don’t care, X no mapa. Observe que, para os andares que não existem no prédio, utilizamos
X na função e o agrupamos conforme a conveniência. No mapa 12, utilizamos os valores X como 1s, para minimizar a
expressão lógica da função.
A última observação sobre Mapas de Karnaugh é que o resultado precisa ser criticado antes de ser aceito. O algoritmo
mostrado pode resultar em leituras não ótimas. Vejamos um exemplo. Seja o mapa a seguir (mapa 13):a
 Mapa 13 – Caso patológico. Fonte: Elaborado pelo autor, 2020.
Pelo algoritmo, devemos agrupar primeiro os quatro 1s centrais, resultando no mapa 14.
 Mapa 14 – Caso patológico agrupamento de quatro 1s. Fonte: Elaborado pelo autor, 2020.
Em seguida, grupar os 1s ainda não grupados em duplas, resultando no Mapa 15.
 Mapa 15 – Caso patológico grupamento de duplas 1s. Fonte: Elaborado pelo autor, 2020.
Segundo o algoritmo apresentado, todos os 1s estão agrupados e podemos ler a forma canônica mínima, resultando na função
F = BD + ABC + ACD + ABC + ACD, a qual, segundo vimos, é mínima pela a aplicação do ábaco. Mas será que isso é de
fato verdade?
 
Vamos manipular algebricamente:
javascript:void(0);
Observe que a manipulação resultou nos mesmos termos de F = BD + ABC + ACD + ABC + ACD, exceto o termo BD. Ou
seja, o mapa não resultou na forma canônica mínima. Vamos analisar o motivo.
Observe que o primeiro passo do ábaco é agrupar os quatro elementos centrais, que resultam no termo 𝐵𝐷. Em seguida,
fazemos os agrupamentos das duplas. Esta é a aplicação do ábaco! Isso está correto? Sim, vimos que sim. Então, onde está o
erro? Não existe erro, porém devemos analisar o resultado dos agrupamentos para ver se existem redundâncias e se devemos
eliminá-las.
Observe que, após os agrupamentos das duplas de 1s, o agrupamento dos quatro 1s centrais �ca redundante uma vez que
todos os 1s desse agrupamento estão agrupados nas duplas. Assim, o agrupamento de quatro 1s pode ser excluído. Isso
resulta no já conhecido mapa 15, cuja leitura é: F = ACD + ABC + ABC + ACD.
 Mapa 15 – Caso patológico grupamento de duplas 1s. Fonte: Elaborado pelo autor, 2020.
Notas
Referências
MALVINO, A.; BATES, D. Eletrônica. 8. ed. Porto Alegre: AMGH, 2016. v. 1.
TOKHEIM, R. Fundamentos de eletrônica digital: sistemas combinacionais. 7. ed. Porto Alegre: AMGH, 2013. v. 1. (Série Tekne)
Próxima aula
Projeto de circuitos combinacionais.
Explore mais
Leia o livro O básico sobre eletrônica digital