Embed Size (px)
Citation preview
Sistemas Digitais Módulo 6
Mapas de Karnaugh
Graduação em Sistemas de Informação
Prof. Dr. Daniel A. Furtado
Universidade Federal de Uberlândia Faculdade de Computação
Mapa de Karnaugh
Método gráfico para simplificar expressão lógicas;
Teoricamente, o método pode ser utilizado para simplificar expressões com qualquer número de variáveis de entrada;
Na prática, o método é comumente utilizado para simplificar expressões de até 6 variáveis;
Prof. Dr. Daniel A. Furtado 2
Mapa de Karnaugh
Assim como uma tabela verdade, o método é uma forma de relacionar todos os possíveis valores que as variáveis de entrada podem assumir e os respectivos resultados da expressão lógica;
Cada combinação de valores das variáveis é apresentada como uma célula (ou quadrado) dentro de um mapa de possibilidades, onde todas as linhas e colunas recebem uma subexpressão como rótulo;
Considere a expressão lógica x = A B + A B, representada pela tabela verdade a seguir:
1 0
0 1
A B X
0 0 1
0 1 0
1 0 0
1 1 1
A B
AB
A
A
B B
Mapa correspondente para duas variáveis Tabela verdade
Prof. Dr. Daniel A. Furtado 3
Mapa de Karnaugh
Cada linha na tabela-verdade corresponde a uma célula no mapa;
O valor 1 em uma célula do mapa indica que o produto das variáveis nas respectivas linha e coluna resulta em 1 (𝑥 = 1);
O valor 0 em uma célula indica que a respectiva combinação de variáveis resulta em 0 (𝑥 = 0).
1 0
0 1
A B X
0 0 1
0 1 0
1 0 0
1 1 1
A B
AB
A
A
B B
Mapa para duas variáveis Tabela verdade
Prof. Dr. Daniel A. Furtado 4
Mapas para 2, 3 e 4 Variáveis
Prof. Dr. Daniel A. Furtado 5
A
A
B B
Mapa para duas variáveis
A B
A B
AB
AB
C C
Mapa para três variáveis A B
A B
AB
AB
C D C D CD CD
Mapa para quatro variáveis
Mapa com 3 Variáveis As linhas do mapa são nomeadas de tal forma que os nomes adjacentes
diferem em apenas uma variável; a mesma regra se aplica para nomeação das colunas;
Consequentemente, duas células adjacentes quaisquer também terão expressões que diferem em apenas uma variável;
1 0
0 0
0 0
1 1
A B
A B
AB
AB
C C A B C 𝒙
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
A B C
𝐀𝐁 𝐂
AB C
𝐀𝐁 𝐂 AB C
Prof. Dr. Daniel A. Furtado 6
Mapa com 3 Variáveis Duas células conectadas horizontal ou verticalmente são consideradas
células adjacentes;
Entretanto, cada célula da linha superior também é considerada adjacente à célula correspondente na linha inferior, pois as expressões se diferem em apenas uma variável (pode-se imaginar que a parte superior foi “dobrada” de modo a tocar a parte inferior);
A mesma ideia se aplica para as células da primeira e última coluna;
1 0
0 0
0 0
1 1
A B
A B
AB
AB
C C
Células adjacentes
Células adjacentes
Prof. Dr. Daniel A. Furtado 7
Mapa com 4 Variáveis A B C D 𝒙
0 0 0 0 0
0 0 0 1 0
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 1
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 1
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0
A B CD
0 0 0 1
1 0 1 1
0 0 0 0
0 0 0 1
A B
A B
AB
AB
C D C D CD CD
A BC D
A BCD
A BCD
AB CD
𝑥 = A B CD + A BC D + A BCD + A BCD + AB CD
OR dos quadrados que contêm 1
Células adjacentes
Prof. Dr. Daniel A. Furtado 8
Agrupamento e Simplificação – Pares
A expressão de saída pode ser simplificada combinando adequadamente os grupos de 1’s adjacentes;
Qualquer par de 1’s adjacentes pode ser agrupado para eliminar a variável que aparece nas formas complementada e não complementada;
0 0
1 0
1 0
0 0
A B
A B
AB
AB
C C
x = A BC + ABC = BC
0 0
1 1
0 0
0 0
A B
A B
AB
AB
C C
x = A BC + A BC = A B
1 0
0 0
0 0
1 0
A B
A B
AB
AB
C C
x = A B C + AB C = B C
Prof. Dr. Daniel A. Furtado 9
Agrupamento e Simplificação – Pares
0 0 1 1
0 0 0 0
0 0 0 0
1 0 0 1
A B
A B
AB
AB
C D C D CD CD
A B C
AB D
x = A B CD + A B C + AB C D + AB CD
Expressão original
Os termos simplificados resultantes de cada agrupamento devem ser conectados por operações OR para formação da expressão simplificada final.
x = A B C + AB D
Expressão simplificada
Prof. Dr. Daniel A. Furtado 10
Agrupamento e Simplificação – Quartetos
Um grupo de quatro 1’s adjacentes é denominado quarteto;
Quando um quarteto é agrupado, duas variáveis são eliminadas, pois elas aparecem nas formas complementada e não complementada;
• Sobrará apenas as variáveis que não alteram a forma considerando todas as células 1’s do quarteto;
0 1
0 1
0 1
0 1
A B
A B
AB
AB
C C
x = C
0 0 0 0
0 0 0 0
1 1 1 1
0 0 0 0
A B
A B
AB
AB
C D C D CD CD
x = AB
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
A B
A B
AB
AB
C D C D CD CD
x = BD
Prof. Dr. Daniel A. Furtado 11
Agrupamento e Simplificação – Quartetos
0 0 0 0
0 0 0 0
1 0 0 1
1 0 0 1
A B
A B
AB
AB
C D C D CD CD
x = AD
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1
A B
A B
AB
AB
C D C D CD CD
x = B D
Prof. Dr. Daniel A. Furtado 12
Agrupamento e Simplificação – Octetos
Um grupo de oito 1’s adjacentes é denominado octeto;
Quando um octeto é agrupado, três variáveis são eliminadas, pois elas aparecem nas formas complementada e não complementada;
• Sobrará apenas as variáveis que não alteram a forma considerando todas as células 1’s do octeto;
0 0 0 0
1 1 1 1
1 1 1 1
0 0 0 0
A B
A B
AB
AB
C D C D CD CD
x = B
1 1 0 0
1 1 0 0
1 1 0 0
1 1 0 0
A B
A B
AB
AB
C D C D CD CD
x = C
Prof. Dr. Daniel A. Furtado 13
Agrupamento e Simplificação – Octetos
1 1 1 1
0 0 0 0
0 0 0 0
1 1 1 1
A B
A B
AB
AB
C D C D CD CD
x = B
1 0 0 1
1 0 0 1
1 0 0 1
1 0 0 1
A B
A B
AB
AB
C D C D CD CD
x = D
Prof. Dr. Daniel A. Furtado 14
Procedimento Completo de Simplificação
1. Construa o mapa a partir da tabela verdade ou da expressão lógica a ser simplificada;
2. Circule os 1’s isolados (aqueles que não são adjacentes a nenhum outro 1);
3. Procure os 1’s que são adjacentes a somente um outro 1; agrupe todos os pares;
4. Busque os possíveis octetos que incluam 1’s ainda não agrupados (mesmo se uma parte dos 1’s já tiver sido agrupada anteriormente);
5. Busque os possíveis quartetos que incluam 1’s ainda não agrupados (mesmo se uma parte dos 1’s já tiver sido agrupada anteriormente);
6. Agrupe os pares necessários para incluir eventuais 1’s que ainda não tenham sido agrupados;
7. Conecte os termos simplificados de cada grupo por operações OR para formação da expressão simplificada final.
OBS: nos passos 5 e 6, certifique-se de buscar o menor número possível de agrupamentos;
Prof. Dr. Daniel A. Furtado 15
Procedimento de Simplificação – Exemplo 1
Simplificar: x = A B CD + A BC D + A BCD + ABC D + ABCD + AB CD
0 0 0 1
0 1 1 0
0 1 1 0
0 0 1 0
A B
A B
AB
AB
C D C D CD CD
x = A B CD + ACD + BD
Prof. Dr. Daniel A. Furtado 16
Procedimento de Simplificação – Exemplo 2
0 0 1 0
1 1 1 1
1 1 0 0
0 0 0 0
A B
A B
AB
AB
C D C D CD CD
x = A B + BC + A CD
Prof. Dr. Daniel A. Furtado 17
Procedimento de Simplificação – Exemplo 3
0 1 0 0
0 1 1 1
1 1 1 0
0 0 1 0
A B
A B
AB
AB
C D C D CD CD
x = ABC + A C D + A BC + ACD
Prof. Dr. Daniel A. Furtado 18
Procedimento de Simplificação – Exemplo 4
0 1 0 0
0 1 1 1
0 0 0 1
1 1 0 1
A B
A B
AB
AB
C D C D CD CD
x = A C D + A BC + AB C + ACD
0 1 0 0
0 1 1 1
0 0 0 1
1 1 0 1
A B
A B
AB
AB
C D C D CD CD
x = A BD + BCD + B C D + AB D
Prof. Dr. Daniel A. Furtado 19
Preenchendo o mapa a partir de uma expressão
Um mapa de Karnaugh pode ser preenchido a partir de uma expressão booleana por meio dos passos a seguir:
1. Converta a expressão para a forma soma-de-produtos (caso ela ainda não esteja nesse formato);
2. Para cada mintermo da expressão, coloque um 1 em cada célula do mapa cuja denominação inclua o mintermo;
3. Coloque 0’s nas células restantes;
Prof. Dr. Daniel A. Furtado 20
Preenchendo o mapa a partir de uma expressão
Exemplo 1. Simplificar a expressão y = C A B D + D + AB C + D
1. Passando para a forma soma-de-produtos, obtemos:
y = C A B D + C D + AB C + D
2. Preenchendo o mapa:
A B
A B
AB
AB
C D C D CD CD
1 0
0
0
1
1 1
1 1
1
1
1
1
1 1 1
Prof. Dr. Daniel A. Furtado 21
Preenchendo o mapa a partir de uma expressão
Exemplo 1 (cont.). Simplificar y = C A B D + D + AB C + D
3. Executar os passos de simplificação utilizando o mapa;
A B
A B
AB
AB
C D C D CD CD
1 0
0
0
1
1 1
1 1
1
1
1
1
1 1 1
𝐲 = 𝐂 + 𝐃 + 𝐀𝐁 Expressão simplificada
Prof. Dr. Daniel A. Furtado 22
Exercício 1
Simplificar utilizando mapas de Karnaugh
• z = AB(C D) + A BD + B C D + A BCD
Exercício 1 – Solução
Simplificar utilizando mapas de Karnaugh
• z = AB(C D) + A BD + B C D + A BCD
Passo 1: colocar na forma soma-de-produtos:
= AB C + D + A BD + B C D + A BCD [DeMorgan]
= ABC + ABD + A BD + B C D + A BCD [Distribui]
Passo 2: preencher o mapa a partir da expressão:
A B
A B
AB
AB
C D C D CD CD
1
0 0
0
0
1
1
1 0
1
0
1 0
0
1
1 z = B C D + A BD + AC D + BC
Exercício 2
Simplificar utilizando mapas de Karnaugh
• z = AC + AB D + A + A C(B + C)
Exercício 2 – Solução
Simplificar utilizando mapas de Karnaugh
• z = AC + AB D + A + A C(B + C)
Passo 1: colocar na forma soma-de-produtos:
= A + C + ABD + ABA + (A + C )B C [DeMorgan]
= A + C + ABD + ABA + AB C + B C C [Distribui]
Passo 2: preencher o mapa a partir da expressão:
A B
A B
AB
AB
C D C D CD CD
1
0 0
1
1
1
1
1 1
1
1
1 1
1
1
1
z = A + C + B
Exercício 3
Determine a expressão mínima para o mapa a seguir:
Condição de Irrelevância (Don’t Care)
Em algumas situações, o valor de saída de um circuito lógico não é definido para algumas combinações dos valores de entrada;
Nesses casos, pode-se dizer que o nível lógico da saída é irrelevante, ou seja, não importa se estará em nível alto ou em nível baixo (don’t care);
Utiliza-se comumente um X em tais saídas para especificar essa condição de irrelevância;
O projetista do circuito é livre para fazer a saída ser 0 ou 1, conforme o que for mais conveniente;
Prof. Dr. Daniel A. Furtado 28
Condição de Irrelevância – Exemplo 1
A tabela verdade a seguir indica que a saída z é irrelevante para as entradas 𝐴, 𝐵, 𝐶 = 1, 0, 0 e 𝐴, 𝐵, 𝐶 = 0, 1, 1
Essas condições são utilizadas no mapa de Karnaugh para obtenção de uma expressão mais simples.
0 0
0 X
1 1
X 1
A B
A B
AB
AB
C C
A B C 𝒛
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 X
1 0 0 X
1 0 1 1
1 1 0 1
1 1 1 1
Irrelevante (don’t care)
0 0
0 0
1 1
1 1
A B
A B
AB
AB
C C
𝑧 = 𝐴
Prof. Dr. Daniel A. Furtado 29
Condição de Irrelevância – Exemplo 2
Projetar um circuito lógico para controlar a porta de um elevador de um prédio de três andares;
O circuito deve considerar quatro sinais de entrada: • M – Indica se o elevador está em movimento (1) ou não (0);
• F1, F2, F3 – Um valor ALTO indica que o elevador está posicionado no respectivo andar;
• Exemplo: 𝐹1 = 0, 𝐹2 = 1 e 𝐹3 = 0 indica que o elevador está parado ou passando pelo segundo andar;
• OBS 1: F1, F2 e F3 todos iguais a 0 indica que o elevador não está adequadamente alinhado com nenhum andar;
• OBS 2: Duas ou mais entradas F nunca estarão simultaneamente em nível ALTO.
A saída do circuito deve ser um sinal 𝑧 indicando que a porta deve estar aberta (z=1) ou fechada (z=0);
Circuito do Elevador
M F1 F2 F3
z (abrir)
Prof. Dr. Daniel A. Furtado 30
Condição de Irrelevância – Exemplo 2
M F1 F2 F3 𝐳
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
0
1
1
1
0
0
0
0
X
X
X
X
X
X
X
X
0 1 X 1
1 X X X
0 X X X
0 0 X 0
M F1
M F1
MF1
MF1
F2F3 F2F3 F2F3 F2F3
z = M F1 + M F2 + M F3
Expressão simplificada = M (F1 + F2 + F3)
Prof. Dr. Daniel A. Furtado 31
Representação Alternativa
Prof. Dr. Daniel A. Furtado 32
Exercício 1
Prof. Daniel A. Furtado
1 1 1 1
1 1 0 0
0 0 0 1
0 0 1 1
A B
A B
AB
AB
C D C D CD CD
x = A C + B C + ACD
1 1 1 1
1 0 1 1
0 1 X X
1 X 1 X
A B
A B
AB
AB
C D C D CD CD
Encontrar a expressão simplificada a partir dos mapas:
x = B + C + AD + A D
Simplificação no Logisim
1. Abra o programa e acesse janela Análise Combinacional
2. Definição das entradas. Clique na aba Entrada e adicione as variáveis de entrada do circuito (digite o nome da variável no campo inferior e clique no botão Acrescentar);
3. Definição da saída. Clique na aba Saída e adicione o nome da variável de saída do circuito;
4. Definição da expressão. Clique na aba Expressão, digite a expressão lógica e clique no botão Entrar;
• Dicas: utilize o carácter ~ antes do nome da variável para indicar negação; utilize um espaço entre os nomes das variáveis;
5. Clique em Construir circuito e forneça um nome;
Prof. Dr. Daniel A. Furtado 34
Simplificação no Logisim
Prof. Dr. Daniel A. Furtado 35
Simplificação no Logisim
Prof. Dr. Daniel A. Furtado 36
Simplificação no Logisim
Prof. Dr. Daniel A. Furtado 37
Simplificação no Logisim
Prof. Dr. Daniel A. Furtado 38
Logisim com Saída X (don’t care)
1. Abra a janela de análise combinacional
• Menu Janela Análise Combinacional
2. Adicione as variáveis de entrada na ordem em que aparecem na tabela verdade;
3. Adicione a variável de saída;
4. Adicione a expressão lógica e clique em entrar;
5. Vá até a tabela verdade e clique na saída cujo valor não importa (don’t care) até aparecer um X;
6. Veja a expressão minimizada;
Prof. Daniel A. Furtado
Referências e Recomendações
TOCCI, R. J.; WIDMER, N. S.; MOSS, G. L. Sistemas Digitais: princípios e aplicações. 11.ed. São Paulo: Pearson Prentice Hall, 2011.
• Leitura recomendada: páginas 112-121
Prof. Dr. Daniel A. Furtado 40
