Álgebra Booleana

• Conteúdo: Equações; Operações (portas lógicas); Tabela Verdade; Sintetização de funções; Soma dos Produtos; Produto das Somas;

Estudando
Bibliografia
	[Cap1. Cap2. NISAN, 2005]
	[Cap6. TOCCI, 2011]
	[Cap1. FLOYD, 2007]
	[LAING, 2004]
Vídeos (extra)
	Logic 101 (#11): Truth Tables
	Logic 101 (#12): Truth Table Practice
	Computer Science: Karnaugh Maps – Introduction
	Computer Science: Karnaugh Maps - 4 vars

A álgebra booleana foi desenvolvida por George Boole, um matemático britânico que desenvolveu os conceitos em 1847, base da computação moderna. Muito tempo depois, nos anos 30, Claude Shannon, um importante engenheiro na história da computação moderna, aplicou as ideias de Boole em circuitos elétricos. Ele trabalhava no Analisador Diferencial de Vannevar Bush, e logo percebeu a relação dos relés com álgebra booleana. Ele fazia um relé acionar o outro usando usando uma lógica binária do relé fechado ou aberto. Sua dissertação e artigos, levaram outras pessoas a perceber os benefícios da álgebra booleana em eletrônica e consequentemente computação.

Em Álgebra Booleana as variáveis só podem assumir dois valores. Desligado e ligado, ou falso e verdadeiro, 0 volt e 5 volts, branco e preto. Porém normalmente na computação usamos 0 e 1 pela conveniência. Todos os computadores tem como sua menor unidade de dado, esse elemento. Em computação chamamos isso de bit. que vem de dígito binário (ou do inglês binary digit).

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

Qual tabela verdade a seguir foi montada correta?

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.