EDI18701 2016 1 AULA05

Apresentação

Olá Alunos!

Agora que vocês conhecem o sistema de numeração, que já tiveram álgebra booleana para simplificação de circuitos e hora de ver uma ferramenta muito utilizado em projetos de Eletrônica Digital, que facilita em muito a simplificação de circuitos. Estamos falando do mapa de Veitch-Karnaugh, ou simplesmente mapa de Karnaugh, onde uma tabela é montada de forma a facilitar o processo de minimização das expressões lógicas.

Objetivos

• Aprender como se monta o mapa de Karnaugh;
• Simplificar circuitos com até 4 variáveis.

Formas Normais (Canônicas)

Toda expressão booleana pode ser escrita em uma forma padronizada, denominada forma normal ou forma canônica. Em matemática diz forma canônica as formas ou equações simples que se possa reduzir, por meio de mudança de variáveis, ou um certo número de formas ou equações. Duas dessas formas são:

• Forma Normal Conjuntiva (FNC), Produto de Somas ou Produto de Maxtermos;
• Forma Normal Disjuntiva (FND), Soma de Produtos ou Soma de Mintermos.

Maxtermos e Mintermos

• Maxtermos (ou maxitermos)

• Variável com valor 0 é deixada intacta;
• Variável com valor 1 é alterada pela sua negação;
• Variáveis de uma mesma linha são conectadas por "+" (adição).

• Mintermos (ou minitermos)

• Variável com valor 1 é deixada intacta;
• Variável com valor 0 é alterada pela sua negação;
• Variáveis de uma mesma linha são conectadas por "." (multiplicação).

A B C	Maxtermo	Mintermo
0 0 0	$A+B+C\,$	${\bar {A}}.{\bar {B}}.{\bar {C}}$
0 0 1	$A+B+{\bar {C}}\,$	${\bar {A}}.{\bar {B}}.C$
0 1 0	$A+{\bar {B}}+C\,$	${\bar {A}}.B.{\bar {C}}$
0 1 1	$A+{\bar {B}}+{\bar {C}}\,$	${\bar {A}}.B.C$
1 0 0	${\bar {A}}+B+C\,$	$A.{\bar {B}}.{\bar {C}}$
1 0 1	${\bar {A}}+B+{\bar {C}}\,$	$A.{\bar {B}}.C$
1 1 0	${\bar {A}}+{\bar {B}}+C\,$	$A.B.{\bar {C}}$
1 1 1	${\bar {A}}+{\bar {B}}+{\bar {C}}\,$	$A.B.C\,$

Forma Normal Disjuntiva

• Mintermo (ou minitermo) é o termo produto associado à cada linha da tabela verdade, no qual todas as variáveis de entrada estão presentes.
• Dado um dado mintermo, se substituirmos os valores das variáveis associadas, obteremos "1".
• Porém, se substituirmos nesse mesmo mintermo quaisquer outras combinações de valores, obteremos "0".
• Dessa forma, se quisermos encontrar a equação para uma função a partir de sua tabela verdade, basta montarmos um OU entre os mintermos associados aos "1s" da função.

Exemplo (FND)

Situação	A B C	S	Mintermo
0	0 0 0	0
1	0 0 1	0
2	0 1 0	1	${\bar {A}}.B.{\bar {C}}$
3	0 1 1	1	${\bar {A}}.B.C$
4	1 0 0	0
5	1 0 1	1	$A.{\bar {B}}.C$
6	1 1 0	1	$A.B.{\bar {C}}$
7	1 1 1	0

• S é uma função das variáveis de entrada A, B e C.
• Os valores de (A,B,C) para os quais S=1 encontram-se nas situações 2, 3, 5 e 6.
• Os mintermos associados a essas condições (ou seja, os mintermos 1) são mostrados na tabela ao lado
• Logo, a expressão em soma de produtos (FND) para S será o OU entre estes produtos
• $S={\bar {A}}.B.{\bar {C}}+{\bar {A}}.B.C+A.{\bar {B}}.C+A.B.{\bar {C}}$

Forma Normal Conjuntiva

• Maxtermo (ou maxitermo) é o termo soma associado à cada linha da tabela verdade, no qual todas as variáveis de entrada estão presentes.
• Dado um dado maxtermo, se substituirmos os valores das variáveis associadas, obteremos "0".
• Porém, se substituirmos nesse mesmo maxtermo quaisquer outras combinações de valores, obteremos "1".
• Dessa forma, se quisermos encontrar a equação para uma função a partir de sua tabela verdade, basta montarmos um E entre os maxtermos associados aos "0s" da função.

Exemplo (FNC)

Situação	A B C	S	Maxtermos
0	0 0 0	0	$A+B+C\,$
1	0 0 1	0	$A+B+{\bar {C}}$
2	0 1 0	1
3	0 1 1	1
4	1 0 0	0	${\bar {A}}+B+C$
5	1 0 1	1
6	1 1 0	1
7	1 1 1	0	${\bar {A}}+{\bar {B}}+{\bar {C}}$

• S é uma função das variáveis de entrada A, B e C.
• Os valores de (A,B,C) para os quais S=0 encontram-se nas situações 0, 1, 4 e 7
• Os maxtermos associados a essas condições (ou seja, os maxtermos 0) são mostrados na tabela ao lado
• Logo, a expressão em produto de somas (FNC) para S será o E entre estas somas
• $S=(A+B+C).(A+B+{\bar {C}}).({\bar {A}}+B+C).({\bar {A}}+{\bar {B}}+{\bar {C}})$

Mapa de Karnaugh

Uma vez obtida a forma normal de uma função booleana, é possível simplificá-la por meio de manipulação algébrica, respeitando os postulados e propriedades da álgebra booleana, com visto anteriormente. Alternativamente ao método de simplificação algébrico por fatoração, há outro método de simplificação baseado na identificação visual de grupos de mintermos que podem ser simplificados. Para tanto, é necessário que os mintermos sejam dispostos de maneira conveniente, em tabelas conhecidas como diagramas ou mapas de Veitch-Karnaugh.

• A técnica de simplificação que será utilizada requer que a expressão esteja na forma de soma de produtos - Minitermos.
• Uma barra não pode cobrir mais de uma variável.
• Método gráfico usado para simplificar uma equação lógica ou converter uma tabela verdade no seu circuito lógico correspondente.
• Estudaremos sua aplicação para problemas com até 4 variáveis. Acima disso, os mapas se tornam muito complicados, sendo melhor fazer a análise por meio de programas de computador.

Duas variáveis

A B	S
0 0
0 1
1 0
1 1

Figura 1 - Mapa de Karnaugh para duas variáveis.

• Em um mapa de Veitch-Karnaugh, há uma região própria para cada linha da tabela verdade.
• Essas regiões são os locais onde devem ser colocados os valores que a expressão S assume nas diferentes possibilidades.
• Para obter a expressão simplificada por meio do diagrama:

- Agrupar as regiões onde S=1 no menor número possível de pares (diagonais não são permitidas no agrupamento de pares).

- As regiões onde S=1 que não puderem ser agrupadas em pares são consideradas isoladamente (sozinho).

Exemplo

• A tabela verdade mostra o estudo de uma função.
• A expressão booleana da função S obtida da tabela verdade usando mintermos é:

$S={\bar {A}}.B+A.{\bar {B}}+A.B$

• Obtenha uma expressão equivalente, simplificada usando mapa de Veitch-Karnaugh.

(desenhar a tabela e o mapa no quadro)

Três variáveis

A B C	S
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Figura 2 - Mapa de Karnaugh para três variáveis.

• De forma análoga para 2 variáveis, com 3 variáveis também há uma região própria para cada linha da tabela verdade em um mapa de Veitch-Karnaugh.
• Para obter a expressão simplificada por meio do diagrama:

- Agrupar as regiões onde S=1 no menor número possível de quadras.

- Em seguida, agrupar as regiões onde S=1 no menor número possível de pares.

- As regiões onde S=1 que não puderem ser agrupadas em quadras ou pares são consideradas isoladamente (sozinho).

Exemplo

• A expressão extraída diretamente da tabela verdade para S é:

$S={\bar {A}}.{\bar {B}}.{\bar {C}}+{\bar {A}}.B.{\bar {C}}+{\bar {A}}.B.C+A.{\bar {B}}.{\bar {C}}+A.B.{\bar {C}}$

• Como antes, o diagrama é preenchido com cada situação da tabela verdade.

(desenhar a tabela e o mapa no quadro)

Quatro variáveis

A B C D	S
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

Figura 3 - Mapa de Karnaugh para quatro variáveis.

• Para obter a expressão simplificada por meio do diagrama é preciso:

- Agrupar as regiões onde S=1 no menor número possível de oitavas.

- Em seguida, agrupar as regiões onde S=1 no menor número possível de quadras.

- Em seguida, agrupar as regiões onde S=1 no menor número possível de pares.

- As regiões onde S=1 que não puderem ser agrupadas em oitavas, quadras ou pares são consideradas isoladamente (sozinho).

- No diagrama, os lados extremos opostos se comunicam, podendo formar oitavas, quadras ou pares.

Exemplo

Simplifique a expressão usando mapa de Veitch- Karnaugh:

$S={\bar {A}}.{\bar {B}}.{\bar {C}}.D+{\bar {A}}.{\bar {B}}.C.{\bar {D}}+{\bar {A}}.{\bar {B}}.C.D+{\bar {A}}.B.{\bar {C}}.D+{\bar {A}}.B.C.D+A.{\bar {B}}.{\bar {C}}.{\bar {D}}+A.{\bar {B}}.{\bar {C}}.D+$

$A.{\bar {B}}.C.D+A.B.{\bar {C}}.{\bar {D}}+A.B.{\bar {C}}.D+A.B.C.D$

(desenhar a tabela e o mapa no quadro)

Casos sem Simplificação

Seja a expressão:

$S={\bar {A}}.B+A.{\bar {B}}$

• Ao tentar simplificar a expressão pelo diagrama de Veitch-Karnaugh, nota-se que não é possível agrupar termos. Nesse caso, a expressão dada já se encontra minimizada.
• O mesmo ocorre com a expressão

$S=A.B+{\bar {A}}.{\bar {B}}$

Que também se encontra minimizada.

Estes casos também ocorrem para 3, 4 ou mais variáveis de entrada que também não admitem simplificação.

(desenhar a tabela e o mapa no quadro)

Outras formas de Mapa

Note que nessa forma de construção do Mapa de Karnaugh, há uma anotação das filas (linhas ou colunas) de quadrículos onde a variável independente não muda de valor. Também observe que, de uma fila de quadrículos para outra fila, só há uma mudança de valor nas variáveis. Observe que a ordem de numeração das linhas e colunas, representativas de combinações de variáveis, obedece o código GRAY. A Figura 4 mostra como fica essa distribuição vertical.

Figura 4 - Mapa de Karnaugh para quatro variáveis na vertical.

A Figura 5 mostra um uma outra distribuição para a mapa de Karnough diferente das anteriormente utilizadas.

Figura 5 - Exemplo de Mapa de Karnaugh com outra distribuição.

Exercício de Fixação

Monte a tabela verdade que deu origem ao mapa e encontre a simplificação algébrica para o exemplo visto na Figura 5.

A B C D	S
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

Resumo

Nesta aula apresentamos como trabalhar com o Mapa de Karnaugh sendo que é importante lembrar que qualquer expressão booleana pode ser escrita de forma padronizada, obtida a partir da tabela verdade na forma de:

• Produto de Maxtermos
• Soma de Mintermos

Uma vez obtida a expressão booleana de um circuito, é possível realizar simplificações que visam reduzir redução de custo de fabricação dos circuitos através de dois métodos:

• Fatoração (simplificação algébrica)
• Diagrama de Veitch-Karnaugh (simplificação visual)

Mapa de Karnaught On-line

http://www.32x8.com/

Material de Apoio

[1] Apresentação - José Augusto Baranauskas USP (2012)

[2] http://www.ufjf.br/daniel_silveira/files/2011/06/aula_4.pdf

[3] http://endigital.orgfree.com/combinacional/MapadeKarnaugh.htm

---

<<	<>	>>