Álgebra Booleana

Equações

Uma equação de lógica booleana pode possuir uma ou mais 'entradas' e apenas uma saída, na equação exemplo a seguir, X é uma saída (e pode assumir apenas valor 1 ou 0) e A e B são entradas também do tipo binária.

    X(A,B) = A . B

X = A and B

X = A . B

X = A ^ B

A operação de and pode ser entendida como uma multiplicação: A saída (X) só é verdadeira se as entradas A e B forem verdadeiras: 1 . 1 = 1. Como A e B são números binários, é possível encontrar uma tabela que relaciona o TODOS os valor da saída X com todas as entradas possiveis: A e B

Também podemos representar essa equação X = A . B como sendo um circuito digital:

Operações

O and utilizado no exemplo anterior é um operador da lógica booleana, operadores possuem uma ou mais entradas e geram uma saída. Os operadores mais comuns são: not, and, or, nand, nor, xor.

not

O operador not atua sobre uma variável, tornando a saída o inverso da entrada, ou seja, se a entrada do operador for 1 sua saída será 0 e vice versa.

Uso: a luz interna do carro será acesa ('1') quando a porta estiver fechada ('0').

Notação: not, -, ~, ¬:

X = not A  /  X = A  /  X = Ã / X = ¬ A

Tabela Verdade:

Simbologia:

and

O operador and atua sobre duas variável, tornando a saída verdadeira somente se as duas entradas forem verdadeiras, se uma das entradas forem falsa a saída será falsa.

Uso: o cofre será aberto somente quando as duas chaves de seguranças forem inseridas.

Notação: and, ., ^:

X = A and B  /  X = A . B   /  X = A ^ B

Tabela Verdade:

Simbologia:

or

O operador or atua sobre duas variável, tornando a saída verdadeira sempre que uma das entradas forem verdadeira.

Uso: O alarme de incêndio será acionado caso alguns dois dois botões sejam pressionados.

Notação: or, +, v:

X = A or B  /  X = A + B   /  X = A v B

Tabela Verdade:

Simbologia:

nand

Podemos começar a 'unir' operadores para formar novos comportamentos, o nand é a inversão (not) da porta lógica and. Na porta nand a saída só é verdadeira quando as entradas são falsas.

Uso: Soar o alarme se os sensores de batimento cardíaco e o de pressão falharem.

Notação: nand, ¬( ∧ )

                    _____
X = A nand B  /  X = A . B  / X = ¬(A ∧ B)

Tabela Verdade:

Simbologia:

nor / xor / xnor

Para as demais portas lógicas, consulte a referência: https://en.wikipedia.org/wiki/Logic_gate#Symbols

Estudar as portas pois iremos precisar que vocês saibam.

Tabela Verdade

Nessa tabela criamos colunas para cada variável de entrada e de saída e colocamos as situações possíveis (resultado). Para construirmos uma tabela verdade basta seguir as regras a seguir (na sequência):

1. Criar uma coluna para cada entrada do sistema (n)
2. Criar uma coluna para cada saída do sistema
3. A tabela verdade vai ter 2^n números de linhas (onde n é a quantidade de entradas)
   • um sistema com 2 entradas possui 2² = 4 linhas
   • um sistema com 3 entradas possui 2³ = 8 linhas ...
4. Preencher as entradas (com '1's e '0's ) de forma a cobrir todas as possibilidades.
5. Para cada linha, analisar se a combinação de '1's e '0' torna a saída '1' e '0'

Exercise 6

Qual tabela verdade a seguir foi montada correta?

{width=440}

{width=440}

{width=440}

Answer

.

Funções geradas a partir de Tabelas Verdade

É possível a partir de uma tabela verdade obter uma equação lógica que a represente (caminho inverso), podemos fazer isso por duas técnicas diferentes (chamadas de forma canônicas):

• Soma dos Produtos (SoP)
• Produto das Somas (PoS)

Soma Dos Produtos

Na soma dos produtos iremos encontrar uma equação booleana que possui a seguinte forma:

 X = ( . . . ) + ( . . . ) + ... + ( . . . )
       ----- 
         |
         | = '1'

Nesse método, precisamos encontrar as linhas da tabela verdade que resultam em uma saída '1' (Verdadeira) e invertendo (ou não) as entradas fazendo com que o termo ( . . . .) resulte em '1' para a linha em questão.

Produto das somas

 X = ( + + + ) . ( + + + ) . ... . ( + + + )
       -----
         |
         | = '0'

Nesse método, precisamos encontrar as linhas da tabela verdade que resultam em uma saída '0' e invertendo (ou não) as entradas fazendo com que o termo ( . . . .) resulte em '0' para a linha em questão.

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:

Para simplificarmos uma equação, aplicamos as propriedades da tabela anterior a fim de encontrarmos uma equação que:

1. Tenha uma forma mais explicita de sua propriedade
   • exe: \(A . B + A . C\) -> \(A (B + C)\)
2. Minimize o uso de 'portas lógicas'
   • exe: \((A . B) . C + A . B . D\) -> \((A . B)(C + D)\)
3. Elimine minimize as entradas necessárias
   • exe: \(( (A + \overline{A}).B)\) -> \(B\)

Exemplos

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:

1. Gerar a tabela verdade
2. Gerar o mapa de Karnaugh
3. Criar os grupos
4. 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!

AB \ 11 10 00 01

AB \ 01 11 10 00

Exercise 12

Qual mapa de K. foi montado certo?

{width=120}

{width=120}

{width=120}

{width=120}

Answer

.

Exercise 13

Qual mapa de K. foi montado certo?

{width=120}

{width=120}

{width=120}

{width=120}

Answer

.

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.

Devemos agrupar sempre na maior quantidade possível! A seguir exemplos do que não deve ser feito!

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:

  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

 ---------
[0000 0100]
 ---------

 ----
[0000 
     0110]
     ----

----              ----
0000]            [1000
----              ----

----
0000]
----
                   ----
                  [1010
                   ----

Exercise 14

Qual agrupamento é o mais correto?

{width=180}

{width=180}

{width=180}

{width=180}

Answer

.

Exercise 15

Qual agrupamento é o mais correto?

{width=180}

{width=180}

{width=180}

{width=180}

Answer

.

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.

AB: 00
AB: 01