Simplificação lógica usando mapas de Karnaugh

Uma querida amiga, no Facebook, mostrou-se interessada em aprender um bocado a respeito de eletrônica digital e topou com os mapas de Karnaugh, como recurso para tornar mais simples o esforço de realizar “simplificações” de expressões lógicas. Neste texto vou mostrar para vocês dois estilos diferentes de mapas, como montá-los e usá-los. Mas, antes, é importante entender como fazer esse tipo de simplificação manualmente.

Como na álgebra tradicional, a Booleana também é baseada em certas operações elementares. Para facilitar a compreensão, usarei o símbolo de adição (+) para representar a operação OR e multiplicações para representar AND. Assim, a expressão S=A+BC será a mesma coisa que S=A\quad OR\quad(B\quad AND\quad C).

A primeira propriedade é a de identidade. Ou seja, A+0=A e A\cdot1=A. Outra propriedade interessante é a que acontece quando invertemos o valor fixado para as operações OR e AND: A+1=1 e A\cdot0=0. Com essas quatro proriedade fica fácil de ver que: A(B+1)=A\cdot1=A, por exemplo… Também temos a propriedade distributiva, A(B+1)=AB+A, assim como na aritmética tradicional. O que não é muito evidente é que AND também pode ser distribuído: A+(BC)=(A+B)(A+C), e vice-versa, se colocarmos A “em evidência”.

Vejamos como isso funciona com uma expressão do tipo S=A+\overline{A}B: Pela propriedade distributiva podemos reescrever a expressão como S=(A+\overline{A})(A+B). Se A+\overline{A}=1 e, ao mesmo tempo, X\cdot1=X. O que nos dá: S=A+\overline{A}B=(A+\overline{A})(A+B)=1\cdot(A+B)=A+B, ou seja, eliminamos o \overline{A} da expressão.

Acontece que esse tipo de simplificação pode ser bem complicada para fazer “de cabeça”. E podemos nos confundir se podemos (ou se devemos) realizar uma distribuição usando AND ou OR. Para isso existem os mapas de Karnaugh.

Simplificação com mapa de Karnaugh

Como funciona esse mapa? Trata-se de um retângulo onde, nas colunas, temos as representações de A e seu inverso (1 e 0, ou vice-versa) e nas linhas, B e seu inverso. Uma expressão a ser simplificada deve ser interpretada como sendo constituída de “somas” de produtos… No caso da expressão S=A+\overline{A}B, o A isolado deve ser transformado para A=A(B+\overline{B})=AB+A\overline{B} e assim, obtemos a equação final S=AB+A\overline{B}+\overline{A}B. Daí, em cada termo das “adições” colocamos, no mapa, o valor 1.

Agora precisamos “agrupar” esses uns de acordo com as seguintes regras:

  1. Apenas “uns” adjacentes podem formar grupos (“uns” diagonais não!);
  2. Apenas grupos de 2^n “uns” podem ser formados. Ou seja, cada grupo pode ser formado por 1, 2, 4, 8, 16… “uns”;
  3. Apenas grupos “linhas”, “quadrados” ou “retângulos” podem ser formados (veremos isso com mapas com 3 ou mais variáveis);
  4. Devemos sempre começar pelos maiores grupos possíveis;
  5. Podemos compartilhar “uns” de grupos que já tenham sido formados, desde que pelo menos 1 deles não faça parte de outros grupos;
  6. Se não há mais “uns” fora de grupos já formados, novos grupos não devem ser formados;
  7. A menor quantidade possível de grupos deve ser formada.

Com essas regras obteremos a equação final com a menor quantidade de termos (regra 7) com menores termos (especialmente a regra 4).

No exemplo acima tivemos que formar 2 grupos com 2 “uns” (o verde e o avermelhado) porquê não pudemos criar nenhum grupo com 4 “uns”.

Para cada grupo verificamos quais variáveis não possuem complementos e as escrevemos como um produto… No caso, o grupo vermelho é composto de A, mas têm B e \overline{B}, portanto ambos são eliminados, ficando apenas A… A mesma coisa se dá com o grupo verde, ficando apenas B.

Note que, no mapa com duas variáveis, se tivéssemos uma expressão do tipo S=AB+A\overline{B}+\overline{A}B+\overline{A}\overline{B}, todos as 4 posições teriam “uns” e o resultado final serial S=1… Isso nos dá uma regra interessante:

  • Grupos com 2^n “uns” eliminam n variáveis.

Um grupo grande com 4 “uns” eliminará, necessariamente, 2 variáveis da expressão. No caso anterior, como a expressão só tem duas variáveis, o resultado só pode ser 1. Isso ficará claro, adiante, com mapas maiores.

Mapas de 3 ou 4 variáveis

A diferença de um mapa com mais de duas variáveis é que ele pode se “fechar” lateralmente. No mapa abaixo, para colocarmos mais uma variável, decidi particionar as colunas A e \overline{A} em duas, mas note que para que a porção \overline{C} fique completa, os lados direito e esquerdo do mapa precisam “se tocar”. Ou seja, o mapa deixou de ser plano para ser cilíndrico.

Exemplo com 3 variáveis

No exemplo acima, temos que começar com um grupo de 4 “uns” (o avermelhado). Note que os “uns” continuam adjacentes, mas  não formam uma linha. Formam um “quadrado”… Com isso fica “sobrando” um “1” no mapa que, infelizmente, não pode formar nenhum outro grupo de 4, restando apenas uma possibilidade: um grupo de 2 “uns”, usando um já usado no grupo anterior.

O grupo de 4 “uns” elimina duas das três variáveis. Se prestarmos atenção o grupo usa A, \overline{A}, B e \overline{B}, mas usa apenas \overline{C}… O grupo de dois “uns” elimina uma única variável, permanecendo apenas A\overline{B}.

Um mapa de 4 variáveis faz e mesma coisa que o mapa de 3, mas ele dividirá as linhas de B e \overline{B}, da mesma forma que fiz com C e \overline{C}, mas do lado direito no mapa… Assim, ele se fechará nos dois sentidos, formando uma “toroide” (um cilindro fechado dos dois lados… ou um “pneu”):

Mapa com 4 variáveis

Mapas com mais de 4 variáveis e a codificação de Gray

Mapas com mais de 4 variáveis podem ser montados de acordo com o esquema anterior, porém em 3D. Eu acho particularmente difícil conceber tais mapas tridimensionais e, portanto, para continuar usando Karnaugh, um outro esquema, mais tradicional, é necessário. O mapa pode ser montado de forma bidimensional onde cada linha ou coluna varie, entre uma e outra, em apenas 1 bit, como mostrado abaixo:

Esse tipo de mapa tem que usar uma codificação para cada linha/coluna chamada de código de Gray, já que, assim como mapa de 4 variáveis, ele se “fecha” nos dois sentidos… Isso fica meio chato de montar, mas o código de Gray pode ser obtido para n bits assim:

Começamos pelos dois primeiros valores: 0 e 1. Os dois próximos são os mesmos dois primeiros, porém revertidos, com o próximo bit setado. Ou seja, se temos 0 e 1, obtemos 11 e 10 e teremos a sequência {00,01,11,10}. A próxima sequência é essa mesma, revertida, com o próximo bit setado, ou seja, {110,111,101,100}, o que nos dá a sequência completa {000,001,011,010,110,111,101,100}, para 3 bits… Esse mesmo algoritmo pode ser usado para n bits…

No que concerne o uso do mapa, você coloca os “uns” em cada uma das posições dos produtos, onde 0 significa a variável “negada”, e segue as mesmas regras anteriores (grupos grandes, poucos grupos e grupos de 2^n “uns”). A chatice é determinar quais das variáveis não sofreram alterações nos grupos… Suponha que tenhamos um grupo de 8 “uns” e verificamos que apenas A e B não sofreram variações (A=0 e B=1, no grupo todo, por exemplo)… Assim, para esse grupo de 8 “uns” (e, por causa disso 3 variáveis serão eliminadas, necessariamente, já que 2^3=8), obteremos \overline{A}B.

Desse jeito podemos montar mapas de qualquer tamanho. Mas, atenção que apenas 4 bits nos darão uma linha com 16 possibilidades diferentes. Um mapa com 8 bits, agrupados de 4 em 4, nos dará um mapa com 256 posições!

Usando mapas de Karnaugh com comparações, num if…then…else

Claro que usei variáveis booleanas A, B, C, … levando em conta que elas podem assumir apenas dois valores: true ou false. A mesma coisa pode ser feita com uma comparação como (x < 0), só temos que tomar cuidado com os complementos… Por exemplo, o contrário de (x < 0) é (x >= 0)… Assim, um if do tipo:

if ((x < 0) || ((x >= 0) && (a == b))) { ... }

Pode ser decrito como tendo A=(x < 0), \overline{A}=(x >= 0) e B=(a==b). O que nos daria a expressão A+\overline{A}B. Como vimos, isso pode ser simplificado para A+B e, portanto, o if acima ficaria:

if ((x < 0) || (a == b)) { ... }

O compilador pode fazer essa simplificação para nós, mas nem sempre ele consegue.

Anúncios