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.
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.
É 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 - 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.
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.
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:
n = 2
, cria-se uma tabela com 2 linhas e 2 colunas;n = 3
, cria-se uma tabela com 2 linhas e 4 colunas;n = 4
, cria-se uma tabela com 4 linhas e 4 colunas;n = 5
, cria-se uma tabela com 4 linhas e 8 colunas;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.
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:
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.
Primeiro, vamos resolver o mapa agrupando os uns para obter a resposta em soma de produtos. Os possíveis grupos são:
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:
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.
O mesmo pode ser feito ao agrupar os zeros:
Ficando assim:
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.