aula6_Mapa_karnaugh_minimizacao

Prévia do material em texto

Álgebra de Boole 
Mapa de Karnaugh - Minimização 
Lógica Digital 1CC 
 
Carolina P. Almeida 
Forma Equivalente de Montagem dos Mapas 
 Coloca-se a negação da variável para as 
posições em que a variável assume o valor 0; 
Coloca-se a própria variável para as 
posições em que a variável assume o valor 1. 
Forma Equivalente de Montagem dos Mapas 
1 0 
• Para uma variável 
A A
Forma Equivalente de Montagem dos Mapas 
• Para duas variáveis 
Forma Equivalente de Montagem dos Mapas 
• Para três variáveis 
Forma Equivalente de Montagem dos Mapas 
• Para quatro variáveis 
Forma Equivalente de Montagem dos Mapas 
• Para cinco variáveis 
Simplificação de Circuitos – Mapas de Karnaugh 
 Métodos para a simplificação de circuitos: 
 Álgebra de Boole (relações); 
 Diagramas (ou mapas) de Veitch-
Karnaugh; 
 Origens: 
 Desenvolvidos por Edward Veitch (1952); 
 Aperfeiçoados por Maurice Karnaugh; 
Simplificação de Circuitos – Mapas de Karnaugh 
 Simplificação mais rápida e intuitiva; 
 Pode ser aplicado a funções bastante 
complexas; 
 Requer a tabela-verdade da expressão. 
Simplificação de Circuitos – Mapas de Karnaugh 
 O processo de minimização proposto por 
Veitch-Karnaugh consiste em um mapa com n 
células que serão preenchidas com os 
mintermos (ou eventualmente os maxtermos) 
da função; 
 Esse mapa possibilita a visualização dos 
termos redundantes e sua simplificação de 
forma imediata; 
Simplificação de Circuitos – Mapas de Karnaugh 
 Ao se utilizar os mapas de Karnaugh para 
realizar a simplificação de circuitos, devemos 
sempre buscar: 
 agrupar o maior número de uns possível, isso 
gerará o termo mais simplificado para aquele 
conjunto de uns da tabela verdade; 
 Os conjuntos possíveis são sempre 
potências de dois, ou seja, 20, 21, 22, 23, 24, 
25 e 26, ou ainda, 1, 2, 4, 8, 16, 32 ou 64 
uns. 
 
Simplificação de Circuitos – Mapas de Karnaugh 
 Os grupos podem ser formados na 
horizontal, vertical, nunca em diagonal; 
 Seguem alguns exemplos: 
 
A 0 1 
1 0 
A A
Simplificação de Circuitos – Mapas de Karnaugh 
 Note que as coordenadas que devem ser dadas, 
para descrever a posição deste 1 que está no 
mapa de karnaugh, é apenas Não A; 
 Esse Não é devido ao fato de que o 1 ocorre 
quando o A possui o valor 0, por isso ele é 
negado; 
 Devemos pensar nesta simplificação, como se 
estivéssemos construindo uma SoP (Soma de 
Produtos). 
 
AS 
Mapa para 2 Variáveis 
Mapa para 2 Variáveis 
 O processo de minimização de uma função via 
mapa de Karnaugh consiste em tentar agrupar 
regiões onde f(A,B)=1 na seguinte seqüência: 
Mapa para 2 Variáveis 
Mapa para 2 Variáveis 
Simplificação de Circuitos – Mapas de Karnaugh 
 Exemplo de simplificação em um mapa com 2 
variáveis: 
 
Simplificação de Circuitos – Mapas de Karnaugh 
 Repare que, agora, não foi possível realizar 
apenas um agrupamento; 
 Então tenta-se fazer o maior agrupamento que 
seja possível com cada um dos uns que temos; 
 Ou seja, com o primeiro 1, o maior agrupamento 
é pegá-lo em dupla, e o outro 1 que não foi 
envolvido também possui o seu maior 
agrupamento como uma dupla, desta forma, um 
dos uns acaba sendo pego duas vezes, mas 
isso não tem importância. 
Simplificação de Circuitos – Mapas de Karnaugh 
 E assim quais as coordenadas para a primeira 
dupla de uns (a linha)? 
 É apenas B 
 E a coordenada para que tenhamos apenas a 
coluna de uns é A; 
 Como temos estas duas coordenadas, e elas 
JUNTAS formam a nossa tabela verdade, 
fazemos então um OU entre eles, ou seja, uma 
SOMA, ou ainda uma UNIÃO, chegando à 
expressão: 
BAS 
Mapa para 3 Variáveis 
Mapa para 3 Variáveis 
Mapa para 3 Variáveis 
 O processo de minimização consiste em procurar 
pelos grupos a seguir na ordem apresentada: 
 
Mapa para 3 Variáveis 
Mapa para 3 Variáveis 
Mapa para 3 Variáveis 
Mapa para 3 Variáveis 
Simplificação de Circuitos – Mapas de Karnaugh 
 Exemplo de minimização para um mapa com 3 
variáveis: 
Simplificação de Circuitos – Mapas de Karnaugh 
 Devemos imaginar o mapa de Karnaugh como 
se fosse um TORÓIDE, ou seja, imagine um 
mapa mundi, ele é desenhado num plano, onde 
possui um começo e um fim, mas sabemos que 
ao chegarmos ao final dele por um dos dois 
lados, a gente volta para o lado oposto; 
 No mapa de Karnaugh é assim também, como 
se fosse o mapa do PAC-MAN, se você entra na 
passagem secreta pela direita, o PAC-MAN 
aparece no lado esquerdo do mapa, porque 
aquilo é um TORÓIDE. 
Simplificação de Circuitos – Mapas de Karnaugh 
 Imaginemos o mapa de Karnaugh assim, ou 
seja, se chegamos na parte mais de cima e 
continuarmos a subir, voltamos para baixo; 
 Se estivermos à direita, e formos mais um passo 
à direita, voltamos à esquerda; 
 Portanto, o maior grupo de uns possível neste 
mapa de Karnaugh é o grupo formado pelos 4 
uns através do TORÓIDE! 
Simplificação de Circuitos – Mapas de Karnaugh 
 Quais as coordenadas relativas a este conjunto 
de uns? 
 Note que abas as colunas estão dispostas na 
coordenada e que não existe outra posição que 
não tenha 1s para esta coordenada. Portanto, a 
simplificação ficará: 
BS 
Mapa para 4 Variáveis 
Mapa para 4 Variáveis 
Simplificação de Circuitos – Mapas de Karnaugh 
 Agora vejamos um exemplo utilizando-se de um 
mapa de Karnaugh com 4 variáveis: 
Simplificação de Circuitos – Mapas de Karnaugh 
 Neste caso, nota-se dois grupos com 4 
uns, porém lembre-se isto é um 
TORÓIDE, ou seja, este dois grupos de 4 
uns estão todos agrupados, formando um 
grupo maior com 8 uns; 
 E agora, quais as coordenadas que são 
relevantes, para descrevermos este 
conjunto de 8 uns?? 
 
Simplificação de Circuitos – Mapas de Karnaugh 
 Repare que a coordenada , usada 
anteriormente, agora não se refere às duas 
colunas que temos com valores 1; 
 Porém a coordenada descreve exatamente 
estas duas linhas, sendo que não existem 
outras posições pertencentes a que tenham 
valores diferentes de 1; 
 Portanto, a simplificação deste mapa de 
Karnaugh, será: 
 
B
DS 
Simplificação de Circuitos – Mapas de Karnaugh 
 Agora, você deve estar se questionando, e se 
eu fizesse dois conjuntos com 4 uns cada? 
 Você não está obedecendo a regra do MAIOR 
CONJUNTO DE UNS POSSÍVEL!; 
 Mas e se eu fizesse, não estaria certo? 
 Não está errado, mas não será encontrada a 
expressão mais simplificada! 
 E aí você terá que terminar a simplificação 
algebricamente, o que nem sempre é fácil! 
 
Simplificação de Circuitos – Mapas de Karnaugh 
 Se você ainda não se convenceu, façamos a 
simplificação utilizando os 2 grupos de 4 uns 
existentes à cima, ou seja, você esqueceu que o 
mapa de Karnaugh é um toróide. 
Simplificação de Circuitos – Mapas de Karnaugh 
 Note que as coordenadas para a primeira linha 
serão e para a última linha, serão . 
 Portanto, a sua expressão “simplificada” ficaria: 
 
 
DCDCS .. 
DC . DC.
Simplificação de Circuitos – Mapas de Karnaugh 
 E lembre-se da relação onde e aplique 
na expressão acima, obtendo: 
 
 
 Porém, lembre-se ainda da relação onde e 
aplique na expressão acima, obtendo: 
 
 
1 AA
1.DS 
AA 1.
DS 
Simplificação de Circuitos – Mapas de Karnaugh 
 Chegamos na mesma resposta! 
 Esta sim é a expressão mais simplificada! 
 Então lembre-se que o MAIOR GRUPO DE 
UNS NOS DÁ A EXPRESSÃO MAIS 
SIMPLIFICADA PARA AQUELES UNS DA 
TABELA VERDADE! 
 
 
Mapa para 5 Variáveis 
Mapa para 5 Variáveis 
Mapa para 5 Variáveis-Simplificação 
 Procurar pelas figuras abaixo nesta ordem: 
a) grupo de 32 (S=1); 
b) grupo de 16; 
c) oitava; 
d) quadra; 
e) par; 
f) termos isolados; 
 
 
Mapa para 5 Variáveis-Simplificação 
 O mapa a partir de 5 variáveis para facilitar a 
simplificação deve ser enxergadode forma 
sobreposta: 
 
 
 
Simplificação de Circuitos – Mapas de Karnaugh 
 Vejamos o último exemplo, um mapa de 
Karnaugh com 5 variáveis. 
 
 
Mapa para 5 Variáveis-Simplificação 
 Na prática, não é necessário desenhar os dois 
planos do mapa de Karnaugh sobrepostos; 
 Basta o entendimento deste conceito e sua 
aplicação para os dois planos dispostos 
lateralmente. 
 
 
 
Mapa para 5 Variáveis-Simplificação 
Mapa para 5 Variáveis-Simplificação 
 A expressão resultante é: 
 
!B!D + !B!C!E + ABD + AB!CE 
 
 
 
Simplificação de Circuitos – Mapas de Karnaugh 
 Para realizar a simplificação de mapas de 
Karnaugh com 5 variáveis, temos que imaginar 
como se um desses mapas estivesse em cima 
do outro; 
 Como na imagem a seguir: 
 
 
 
Simplificação de Circuitos – Mapas de Karnaugh 
Simplificação de Circuitos – Mapas de Karnaugh 
 E note agora, que podemos formar um conjunto 
com 16 uns, que está selecionado na figura 
acima! 
 A coordenada referente a estes uns é D, pois 
todos os campos onde a coordenada é D, existe 
1. 
 A simplificação fica: 
 
 
 
DS 
Atenção! 
 Pode-se extrair a função usando SoP: 
 Agrupando-se uns - Mintermos; 
 Formando Produtos e agrupando-os por somas; 
 Forma mas comum e utilizada nos exemplos da aula. 
 Mas também pode-se extrair a função usando 
PoS: 
 Agrupando-se zeros - Maxtermos; 
 Formando Somas e agrupando-as por produtos; 
 
 
 
Simplificação MK: Exercício 1 
Simplificação MK: Exercício 2 
Simplificação MK: Exercício 3 
 Simplificação 
MK: 
Exercício 4