Kmaps - Gil Eduardo de Andrade

EXPESSÕES BOOLEANAS E MAPAS DE KARNAUGH (Kmaps)
AULA 05 – Arquitetura de Computadores
Gil Eduardo de Andrade
O conteúdo deste documento é baseado no livro “Princípios Básicos de Arquitetura e
Organização de Computadores” – Linda Null e Julia Labur.
1.
Introdução
Como visto na aula anterior, a Álgebra booleana é utilizada para manipulação de objetos
que podem assumir somente dois valores, normalmente 0 e 1 ou verdadeiro e falso, embora eles
também possam ser quaisquer outros dois pares de valores. Sabendo que os computadores são
construídos como coleções de chaves que estão “ligadas” ou “desligadas”, a álgebra booleana é
uma maneira natural de representar informação digital.
2.
Identidades booleanas
Frequentemente, uma expressão booleana não está em sua forma mais simples, lembre-se
da álgebra, onde uma expressão como 2x + 6x não está em sua forma mais simples; ela pode ser
reduzida (representada por menos termos ou por termos mais simples) para 8x. Expressões
booleanas também podem ser simplificadas, mas necessitamos de novas identidades, ou leis,
que se apliquem à álgebra booleana em vez de à álgebra comum. Essas identidades, que se
aplicam a variáveis booleanas simples, bem como a expressões booleanas, são relacionadas na
Tabela 01. Note que cada relacionamento (com exceção do último) possui tanto uma forma AND
(ou produto) quanto uma forma OR (ou soma). Isto é conhecido como princípio da dualidade.
A Lei da Identidade afirma que qualquer variável booleana que faz um AND com 1 ou um
OR com 0 simplesmente resulta na variável original (1 é o elemento identidade para AND; 0 é o
elemento identidade para OR). A Lei da Dominância afirma que qualquer variável booleana que
faz um AND com 0 é 0 e que uma variável que faz um OR com 1 é sempre 1. A Lei da
Idempotência afirma que fazer um AND ou um OR de uma variável com ela mesma produz a
variável original. A Lei da Inversão afirma que fazer um AND ou um OR de uma variável com
seu complemento produz a identidade para dada operação. Variáveis booleanas podem ainda ser
reordenadas (comutadas) e reagrupadas (associadas) sem afetar o resultado final. A Lei da
Distributividade mostra como OR se distribui sobre AND e vice-versa.
A Lei da Absorção e da Lei DeMorgan não são assim tão óbvias, mas podemos provar
estas identidades criando uma tabela-verdade das várias expressões: se o lado direito é igual ao
lado esquerdo, as expressões representam a mesma função e resultam na mesma tabela-verdade.
A Tabela 02 representa uma tabela-verdade do lado esquerdo e do lado direito da Lei DeMorgan
par AND.
Tabela 01: Identidades Básicas da Álgebra booleana.
Tabela 02: Tabela-verdade da forma AND da Lei DeMorgan.
3.
Simplificação de Expressões booleanas
As identidades algébricas que estudamos nas aulas de álgebra nos permitem reduzir
expressões algébricas (como 10x + 2y - x + 3y) para sua forma mais simples (9x + 5y). As
identidades booleanas podem ser usadas para simplificar expressões booleanas de uma maneira
similar. Nos exemplos a seguir as identidades apresentadas são aplicadas:
→ Exemplo 01: suponha a função F(x,y) = xy + xy. Usando a forma OR da Lei da Idempotência
e tratando a expressão xy como uma variável booleana, simplificamos a expressão original para
xy. Portanto, F(x,y) = xy + xy = xy.
→ Exemplo 02: Dada a função F(x, y, z) = x'yz + x'yz' + xz, simplificamos como segue:
F(x,y,z) = x'yz + x'yz' + xz
F(x,y,z) = x'y(z + z) + xz (Distributiva)
F(x,y,z) = x'y(1) + xz (Inversa)
F(x,y,z) = x'y + xz (Identidade)
As vezes, a simplificação é razoavelmente direta, como nos exemplos anteriores.
Entretanto, usar as identidades pode ser complicado. Sendo assim alguns outros métodos são
aconselhados, como por exemplo o apresentado a seguir: Mapas de Karnough – Kmaps.
4.
Mapas de Karnough – Kmaps
Podemos reduzir expressões booleanas usando identidades booleanas; entretanto, usar
identidades booleanas pode ser muito difícil porque não existem regras sobre como ou quando
usar as identidades e não existe um conjunto bem definido de passos a seguir. Em certos
aspectos, minimizar expressões booleanas é bastante parecido com fazer uma prova: você sabe
quando está no caminho certo, mas, chegar lá, algumas vezes, pode ser frustrante e demorado.
Mapas de Karnough, ou Kmaps, são uma maneira gráfica de representar funções
booleanas. Um mapa é simplesmente uma tabela usada para enumerar os valores de uma dada
expressão booleana para diferentes valores de entrada. As linhas e colunas correspondem aos
possíveis valores de entrada de uma função. Cada célula representa as saídas de uma função para
aquelas possíveis entradas.
Se um termo produto inclui todas as variáveis apenas uma vez, sejam complementadas ou
não complementadas, este termo produto é chamado de minitermo. Por exemplo, se existem dois
valores de entrada, x e y, existem quatro minitermos x'y', x'y, xy' e xy, que representam todas as
possíveis combinações de entrada para uma função. Se as variáveis de entrada são x, y e z, então
existem oito minitermos: x'y'z', x'y'z, x'yz', x'yz, xy'z', xy'z, xyz' e xyz.
Tabela 03: (a) minitermos para duas variáveis; (b) minitermos para três variáveis.
Como exemplo vamos considerar a função booleana F(x, y) = xy + x'y. O minitermo x'y'
representa o par de entrada (0,0). Similarmente, o minitermo x'y representa (0,1), o minitermo
xy' representa (1,0) e xy representa (1,1).
O Kmap é uma tabela com uma célula para cada minitermo, o que significa que existe
uma célula para cada linha de uma tabela verdade de uma função. Considere a função F(x,y) =
xy e sua tabela verdade, como visto no exemplo abaixo:
Figura 01: minitermos e kmap para duas variáveis (AND)
Note que a única célula no mapa com valor 1 ocorre quando x = 1 e y = 1, os mesmos
valores para os quais xy = 1. Vamos ver outro exemplo, F(x,y) = x + y.
Figura 02: minitermos e kmap para duas variáveis (OR)
Três dos minitermos no exemplo 02 têm valor de 1, exatamente os minitermos para os
quais a entrada para função nos dá 1 para a saída. Para atribuir 1s no Kmap, simplesmente
colocamos 1s onde encontramos 1s correspondentes na tabela verdade.
5.
Simplificação de Kmap para duas variáveis
Quando usamos simplificação através de Kmap, ao contrário das identidades, não
precisamos nos preocupar com quais termos adicionar ou quais identidades booleanas utilizar. Os
mapas cuidam disso por nós. Vamos ver novamente o Kmap para F(x,y) = x + y.
Para usar este mapa a fim de reduzir uma função booleana, precisamos simplesmente
agrupar os 1s. Este agrupamento é bastante similar a como agrupamos termos quando reduzimos
usando identidades booleanas, exceto pelo fato de que precisamos seguir regras específicas.
Primeiro, agrupamos somente os 1s. Segundo, podemos agrupar os 1s no Kmap se eles estiverem
na mesma linha ou na mesma coluna, mas eles não podem estar na diagonal (isto é, eles devem
estar em células adjacentes). Terceiro, podemos agrupar 1s se o número total no grupo é uma
potência de 2. A quarta regra especifica que devemos fazer os grupos tão grandes quanto o
possível. Como última e quinta regra, todos os 1s devem estar em um grupo (mesmo que alguns
estejam em um grupo de um). Vamos examinar alguns agrupamentos corretos e incorretos,
mostrados na figura 03.
Figura 03: Exemplo de grupos corretos e incorretos em um Kmap.
Para simplificar usando Kmaps, primeiro crie os grupos como especificado pelas regras
acima. Depois de você ter encontrado todos os grupos, examine cada grupo e descarte a variável
diferente em cada grupo. Por exemplo, a figura 3A.7(b) mostra o agrupamento correto para
F(x,y) = x + y. Vamos iniciar com o grupo representado pela segunda linha (onde x = 1). Os dois
minitermos são xy' e xy. Este grupo representa o OR lógico destes dois termos, ou xy' + xy. Estes
termos diferem em y, de modo que y é descartado, deixando somente x. O segundo grupo
representa x'y + xy. Eles diferem em x, de modo que x é descartado, deixando y. Se fizermos um
OR dos resultados do primeiro e do segundo grupo, temos x + y, que é a redução correta para
função original, F.
6.
Simplificação de Kmap para três variáveis
Kmaps podem ser aplicados a expressões com mais de duas variáveis. Como mostrado
anteriormente, já sabemos a maneira de organizar Kmaps envolvendo duas variáveis. Vamos
simplesmente estender esta ideia para três variáveis, como indicado pela Figura 3A.8.
A primeira diferença a ser notada é que duas variáveis, y e z, são agrupadas juntas na
tabela. A segunda diferença é que a numeração das colunas não é sequencial. Em vez de rotular
as colunas como 00, 01, 10, 11 (uma progressão numérica normal), as rotulamos como 00, 01,
11, 10. Os valores de entrada para o Kmap devem ser ordenados de modo que cada minitermo
difira de seu vizinho em somente uma variável. Ao usar esta ordem (por exemplo 01 seguido por
11), os minitermos correspondentes x'y'z e x'yz, diferem somente na variável y. Lembre, para
reduzir necessitamos descartar a variável que é diferente. Portanto, devemos assegurar que cada
grupo de dois minitermos diferem em somente uma variável.
Os maiores grupos que encontramos em nosso exemplos de duas variáveis eram
compostos por dois 1s. É possível ter grupos de quatro ou mesmo oito 1s, dependendo da função.
Vamos ver alguns exemplos de simplificação de mapas para expressões de três variáveis.
Figura 03: Exemplo simplificação de Kmpas com três variáveis.
Vamos novamente seguir as regras para fazer grupos. Você deve ter visto que pode fazer
grupos de dois de diversas maneiras. Entretanto, as regras estipulam que devemos criar os
maiores grupos cujos tamanhos sejam potências de dois. Existe um grupo de quatro, de modo
que podemos agrupá-los como segue:
Não é necessário criar grupos adicionais de dois. Quanto menos grupos você tiver, menos
termos restarão. Lembre, queremos simplificar uma expressão, e tudo o que temos a fazer é
garantir que cada 1 está em algum grupo.
Como, exatamente, simplificamos quando temos um grupo de 1s? Dois 1s em um grupo
nos permitiram descartar uma variável. Quatro 1s em um grupo nos permitem descartar duas
variáveis: as duas variáveis nas quais todos os quatro termos se diferem. No grupo de quatro do
exemplo anterior, temos os seguintes minitermos: x'y'z, x'yz, xy'z e xyz. Todos têm z em comum,
mas as variáveis x e y diferem. Assim descartamos x e y, ficando com F(x, y, z) = z como redução
final. Para ver como isto se compara com a simplificação usando identidades booleanas,
considere a mesma redução usando identidades.
O resultado final usando identidades lógicas é exatamente igual ao resultado usando
simplificação com mapas. Alguns agrupamentos podem ser um pouco mais complicados, como
no exemplo a seguir:
Este é um problema complicado por duas razões: temos grupos sobrepostos e temos um
grupo que 'se enrola'. Os 1s mais à esquerda da primeira coluna podem ser agrupados com os 1s
mais à direita da última coluna porque a primeira e a última coluna são logicamente adjacentes.
Os agrupamentos corretos são os seguintes:
O primeiro grupo se reduz para x' (este é o único termo que os quatro têm em comum) e
o segundo grupo se reduz para z', de modo que a função minimizada final é F(x, y, z) = x' + z'.