Simplificação
Existem duas formas bastante populares de simplificar uma equação booleana: algébrica ou via mapa de Karnaugh. Veremos as duas com mais detalhes.
Simplificação algébrica
Na simplificação algébrica iremos utilizar as seguintes propriedades de lógica booleana para nos ajudar a simplificar uma equação:
| Propriedade | Operação |
|---|---|
| Lei da Identidade | A = A |
| \(\bar{A} = \bar{A}\) | |
| Lei da Comutatividade | A . B = B . A |
| A + B = B + A | |
| Lei da Associatividade | A . (B . C) = A B C |
| A + (B + C) = A + B + C | |
| Lei da Idempotência | A . A = A |
| A + A = A | |
| Lei do Complemento Duplo | \(\overline{\overline{A}} = A\) |
| Lei da Complementariedade | \(A \, \overline{A} = 0\) |
| \(A + \overline{A} = 1\) | |
| Lei da Intersecção | A . 1 = A |
| A . 0 = 0 | |
| Lei da União | A + 1 = 1 |
| A + 0 = A | |
| Lei da Distributividade | A . (B + C) = (A . B) + (A . C) |
| A + (B . C) = (A + B) (A + C) | |
| Teorema de DeMorgan | \(\overline{A \, B} = \bar{A} + \bar{B}\) |
| \(\overline{A + B} = \bar{A} \, \bar{B}\) |
Explicação da tabela
Para essas simplificações nós usaremos as propriedades das operações básicas de álgebra booleana, representada na tabela anterior. As leis da identidade, comutatividade, associatividade e distributividade são bem similares ao que já fazemos normalmente em expressões matemáticas. A idempotência mostra que um AND ou OR com duas variáveis é exatamente a mesma variável. A lei do complemento duplo mostra que se negarmos duas vezes uma variável, teremos a mesma variável. A lei da complementariedade já mostra que fazermos um AND com a negação da mesma variável acabaremos com zero, ou seja, 0 vezes 1 ou 1 vezes 0 sempre dará zero. Já com o OR é o oposto e sempre teremos 1 como resposta. Na lei da interseção temos que uma variável vezes 1 é sempre ela mesma, e se for vezes 0, acabara zerando o resultado. Já a lei da união diz que uma variável mais um é sempre um, e uma variável mais zero é a própria variável. O teorema de DeMorgam é bem interessante, pois mostra uma propriedade bem peculiar da álgebra booleana, no caso o conjunto de A vezes B negado, é o mesmo que A negado, mais B negado, e da mesma forma A negado mais B negado é igual ao A vezes B, e esse resultado negado.
Para simplificarmos uma equação, aplicamos as propriedades da tabela anterior a fim de encontrarmos uma equação que:
- Tenha uma forma mais explicita de sua propriedade
- exe: \(A . B + A . C\) -> \(A (B + C)\)
- Minimize o uso de 'portas lógicas'
- exe: \((A . B) . C + A . B . D\) -> \((A . B)(C + D)\)
- Elimine minimize as entradas necessárias
- exe: \(( (A + \overline{A}).B)\) -> \(B\)
Exemplos
Exemplo 1
Exemplo 2
Exemplo 3
Tip
O vídeo a seguir possui as resoluções de forma detalhada:
Mapa de Karnaugh (MK)
A simplificação por mapa de Karnaugh é uma técnica visual de encontrarmos uma equação reduzida, porém para isso precisamos primeiro:
- Gerar a tabela verdade
- Gerar o mapa de Karnaugh
- Criar os grupos
- Gerar as equações
2. Criando o Mapa
O mapa pode ser criado para N entradas, mas só iremos tratar nesse curso sistemas de 2, 3 ou 4 variáveis (entradas). A seguir exemplos do mapa para 2, 3 e 4 entradas:
Para criar o mapa basta seguir a receitinha anterior, note que a sequência das entras: AB e CD é da forma:
__ _ _
AB AB AB AB
-----------
AB \ 00 01 11 10
e não:
AB \ 00 01 10 11
Como seria mais lógico (já que em binário: 00 = 0; 01 = 1; 10 = 2; 11 = 3). Porém o mapa de Karnaugh assume que as variáveis estão ordenadas na forma de código gray, onde um bit é alterado por vez!
Warning
Colocar qualquer sequência na criação do mapa é um dos erros mais comuns dos anos anteriores!
Tip
Podemos começar a sequência com qualquer combinação, se seguirmos a ordem de só mudar um bit por vez, exemplo:
AB \ 11 10 00 01
AB \ 01 11 10 00
Exercise
Exercise
3. Grupos
No MK podemos agrupar '1's na quantidade de: \(2^n\), onde n=0,1,2,3, ou seja, grupos de: 1, 2, 4, 8, ..., o agrupamento só pode ser feito na vertical ou horizontal, nunca na diagonal.
Tip
- Os grupos podem se sobrepor!
- Agrupar sempre na maior quantidade possível (2, 4, 8, ...)
Devemos agrupar sempre na maior quantidade possível! A seguir exemplos do que não deve ser feito!
Note
Não agrupar na maior quantidade de uns possível impacta em não obter a equação reduzida.
Podemos pensar no MK não como sendo uma tabela plana, mas sim uma superfície mapeada em uma esfera, logo as pontas estão conectadas. Com isso podemos criar grupos nas situações a seguir:
Tip
O agrupamento no mapa de Karnaugh só pode ser realizado quando juntamos uns que estão a um bit de distância. Essa é a razão de não podermos juntar na diagonal.
AB 00 01 11 10
CD \---------------------
00 | 0000 0100 1100 1000
10 | 0010 0110 1110 1010
11 | 0011 0111 1111 1011
10 | 0010 0110 1110 1010
Note que no exemplo anterior se juntarmos duas possibilidades na horizontal (as duas primeira):
---------
[0000 0100]
---------
Apenas o bit referente a entrada B muda. Mas se considerarmos a diagonal:
----
[0000
0110]
----
Temos duas mudanças de bit, a da entrada B e a da entrada C, isso não pode!
O ultimo caso são os cantos, por exemplo:
---- ----
0000] [1000
---- ----
Nesse caso apenas o bit A muda, logo podemos juntar!
Um caso que não pode juntar são as extremidades:
----
0000]
----
----
[1010
----
Nesse caso A e C mudam!
Exercise
Exercise
4. Gerando as equações
Gera-se uma equação por agrupamento, cada grupo irá fornecer um componente na forma da equação da Soma Dos Produtos: (. . . ) + (. . . ). O truque é identificar no grupo quais são as variáveis que assumem todas as possibilidades.
Exemplo 1
Nesse caso, a variável B pode assumir tanto 0 quanto 1 para A fixo em 0, para o grupo em questão as entradas A e B são:
AB: 00
AB: 01
\(\bar{A}.B + \bar{A} . \bar{B}\) que pode ser reduzida para \(\bar{A} (\bar{B} + B)\) e então para: \(\bar{A}\)
O mapa de Karnaugh já nos fornece o resultado de forma direta!
Exemplo 2
Nesse caso, a variável A pode assumir tanto 0 quanto 1 para B fixo em 0, ou seja, A não impacta nesse grupo.
Exemplo 3
Aqui temos um caso particular, para todas as combinações de entrada A e B a saída é sempre 1, logo essa equação é sempre verdadeira: \(F = 1\).
Exemplo 4
Nesse exemplo não foi possível agrupar uns em maior quantidade, logo, não iremos conseguir obter um resultado melhor que a tabela verdade. Nenhuma variável é descartável.
Exemplo 5
Nesse caso criamos dois grupos um na horizontal outro na vertical. Cada grupo irá gerar um termo da equação na forma da SoP.
Casos extras
