19

A pergunta é justamente esta: O que é e para que serve este tal mapa de Karnaugh?

Não pretendo saber tudo sobre ele, uma breve definição e um pequeno exemplo é suficiente.

1

1 Resposta 1

16

É difícil resumir muito pois são muitos conceitos que precisam ser dominados para entender corretamente o mapa de Karnaugh. Abaixo tentarei simplificar ao máximo sem deixar detalhes importantes de fora.

Resumo

  • O mapa de Karnaugh é um método sistemático para simplificação de expressões lógicas;
  • Pode ser utilizado para simplificar circuitos lógicos, abreviar expressões booleanas, converter expressões de diferentes formatos, entre outros;
  • Está diretamente relacionado à Tabela Verdade então conhecê-la é trivial;
  • Fazer o agrupamento de 1 no mapa gerará uma saída no formato soma de produtos;
  • Fazer o agrupamento de 0 no mapa gerará uma saída no formato produto de somas;
  • Deve-se sempre optar por agrupar pelo valor mais presente no mapa;
  • Os grupos devem ser formados sempre em tamanho potência de 2, o maior possível;
  • Os grupos devem ser formados apenas por valores adjacentes;
  • Todos os valores devem pertencer a pelo menos um grupo;

Introdução

O mapa de Karnaugh - as vezes chamado de diagrama - é uma técnica para simplificação de expressões booleanas, surgindo basicamente para contrapor as técnicas de simplificação através da álgebra booleana, que são exaustivas, demandam profundo conhecimento de todas as regras e muito fácil de errar; por sua vez, a simplificação através do mapa de Karnaugh é um método sistemático bastando seguir todos os seus passos para obter o resultado.

É um conceito muito relacionado à tabela verdade, pois costuma-se, na prática, elaborar o mapa de Karnaugh a partir da tabela verdade, dada a facilidade que isso traz a solução e a facilidade de se construir a tabela verdade a parte de qualquer expressão booleana.

O que é e para que serve uma "tabela verdade"?

O resultado do mapa de Karnaugh, quando executado corretamente, sempre será a expressão mais simples nos formatos soma de produtos ou produto de somas, dependendo de como o mapa é resolvido, ambos não canônicos.

Aplicação

O mapa de Karnaugh pode ser utilizado para simplificar qualquer expressão booleana, ou seja, quando você está desenvolvendo um circuito lógico você pode primeiro fazê-lo funcionar, sem se preocupar muito com números de portas lógicas utilizadas e depois aplicar o mapa de Karnaugh ao sistema e reduzir ao máximo seu circuito, diminuindo assim, custo do projeto, atraso na resposta e potência elétrica consumida. Outra aplicação possível é a redução de operações lógicas executadas pela ULA para verificar uma expressão no seu código. Se você possui um if com uma expressão demasiadamente complexa, você pode utilizar o mapa de Karnaugh para simplificá-la.

Construção e Resolução

O mapa de Karnaugh funciona muito bem para expressões lógicas com 2 a 5 variáveis. Acima disso a resolução do mapa acaba se tornando exaustivo demais e geralmente inviabiliza seu uso. A título de exemplo para a resposta, sempre consideraremos as letras de A a E como sendo as variáveis da expressão lógica e S como sendo o valor de saída.

Para construir o mapa para uma expressão com n variáveis, será necessário construir uma tabela com 2^n células, no seguinte formato:

  1. Para n = 2, cria-se uma tabela com 2 linhas e 2 colunas;
  2. Para n = 3, cria-se uma tabela com 2 linhas e 4 colunas;
  3. Para n = 4, cria-se uma tabela com 4 linhas e 4 colunas;
  4. Para n = 5, cria-se uma tabela com 4 linhas e 8 colunas;

inserir a descrição da imagem aqui

Perceba que para n > 2 será necessário criar agrupamentos da entrada. No primeiro mapa, os valores de A são colocados em linha e os valores de B e coluna; no segundo mapa, os valores da combinação AB são colocados em linha e os valores de B em coluna; no terceiro mapa, os valores da combinação AB são colocados em linha e os valores da combinação de CD em coluna; por sua vez, no quarto mapa, os valores da combinação ABC são colocados em linha e os valores da combinação DE em coluna. As combinações que serão colocadas em linha ou coluna não importa muito, mas é uma questão de vida ou morte você posicionar corretamente os valores. Estes devem sempre seguirem a ordem de Gray, isto é, cada valor da linha ou coluna só deve variar em um bit para as linhas ou colunas adjacentes. Perceba que no segundo mapa, a combinação AB é posicionada na sequência 00, 01, 11 e 10, pois se fosse na ordem natural, 00, 01, 10 e 11, entre os valores 01 e 10 haveria a alteração de dois bits e isso não é permitido. Essa é, na verdade, a essência do mapa de Karnaugh. Esse processo seria o equivalente a você posicionar lado a lado os termos com mais variáveis em comum na álgebra booleana, simplificando, assim, o processo.

Cada célula do mapa de Karnaugh é referente a uma célula da tabela verdade e deve ser preenchido como tal. Após preenchido o mapa, deve-se verificar se existem mais zeros ou uns, pois, para se obter a forma mais simplificada da expressão final, deve-se sempre considerar os valores em maior quantidade. Se houverem mais uns que zeros, você os agrupará e obterá uma resposta no formado soma de produtos; já se houverem mais zeros que uns, você os agrupará e obterá uma resposta no formato produto de somas. Inclusive, outra aplicação do mapa de Karnaugh é a conversão entre o formato soma de produtos para produto de somas, ou vice-versa. O agrupamento deve ser feito sempre considerando quantidades potência de 2, obtendo os maiores grupos possíveis. A única regra para o agrupamento, além de o tamanho ser potência de 2, é que os valores do grupo devem ser adjacentes entre si na linha ou na coluna, considerando a tabela como um cilindro, ou seja, a primeira linha é considerada adjacente à última, assim como a primeira coluna é adjacente à última. Feito o agrupamento, cada grupo irá gerar um operando do resultado e esse operando será definido conforme as variáveis que mantém seu valor dentro do respectivo grupo. Isso ficará mais claro no exemplo.

Exemplo

Para um exemplo prático, vamos considerar que o programa irá calcular um processo matemático de 4 formas distintas paralelamente, retornando o resultado quando pelo menos três processos foram finalizados com o mesmo valor, ou quando dois deles finalizarem, sendo que um deles é o processo A. Ou seja, se todos os processos ABCD finalizarem, se BCD finalizarem ou se AB, AC ou AD finalizarem, o programa deve retornar o resultado.

A expressão lógica canônica para esta verificação seria:

S = (A.B.C.D) + (~A.B.C.D) + (A.B.C.~D) + (A.B.~C.D) + (A.~B.C.D) + (A.B.~C.~D) + (A.~B.C.~D) + (A.~B.~C.~D)

Isso demanda a realização de 41 operações lógicas. Imagina escrever um if com tudo isso? Mas montando a tabela verdade, temos:

| A | B | C | D | S |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | -> B.C.D
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | -> A.D
| 1 | 0 | 1 | 0 | 1 | -> A.C
| 1 | 0 | 1 | 1 | 1 | -> A.C.D
| 1 | 1 | 0 | 0 | 1 | -> A.B
| 1 | 1 | 0 | 1 | 1 | -> A.B.D
| 1 | 1 | 1 | 0 | 1 | -> A.B.C
| 1 | 1 | 1 | 1 | 1 | -> A.B.C.D

Ao construir o mapa de Karnaugh, obtemos algo como:

inserir a descrição da imagem aqui

Temos a mesma quantidade de zeros e uns no mapa, então será indiferente qual agrupar. A título de exemplo, farei as duas maneiras.

Grupos de 1

Primeiro, vamos resolver o mapa agrupando os uns para obter a resposta em soma de produtos. Os possíveis grupos são:

inserir a descrição da imagem aqui

Vale lembrar que todos os valores devem estar agrupados e que um mesmo valor pode fazer parte de vários grupos. Desta forma, analisando cada grupo, temos:

  • Azul: as variáveis A e B possuem o mesmo valor em todo o grupo, então o operando gerado será A.B;
  • Vermelho: as variáveis A e D possuem o mesmo valor em todo o grupo, então o operando gerado será A.D;
  • Preto: as variáveis A e C possuem o mesmo valor em todo o grupo, então o operando gerado será A.C;
  • Verde: as variáveis B, C e D possuem o mesmo valor em todo o grupo, então o operando gerado será B.C.D;

Portanto, a expressão simplificada será:

S = (A.B) + (A.C) + (A.D) + (B.C.D)

Que demandará apenas 8 operações lógicas, contra as 41 iniciais.

Grupos de 0

O mesmo pode ser feito ao agrupar os zeros:

inserir a descrição da imagem aqui

Ficando assim:

  • Azul: as variáveis A e B possuem o mesmo valor em todo o grupo, então o operando gerado será A+B;
  • Vermelho: as variáveis A e C possuem o mesmo valor em todo o grupo, então o operando gerado será A+C;
  • Preto: as variáveis A e D possuem o mesmo valor em todo o grupo, então o operando gerado será A+D;
  • Verde: as variáveis B, C e D possuem o mesmo valor em todo o grupo, então o operando gerado será B+D;

Portanto, a expressão simplificada será:

S = (A+B).(A+C).(A+D).(B+C+D)

Que demandará, também, apenas 8 operações lógicas.

1
  • Pode explicar porque um mapa de karnaugh nao funciona se as colunas nao respeitarem a ordem de Gray? Ah já entendi. Se a ordem de Gray nao for respeitada voce nao vai puder formar os grupos. Eu fazia os meus duma forma diferente :p Commented 4/09/2017 às 9:04

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .