Algebra booleana - portas logicas1

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Álgebra booleana e portas lógicas
1
Álgebra booleana
Proposta pelo matemático inglês George Boole, em 1854
Usada para projetar e analisar circuitos digitais
Matemática dos circuitos digitais
Qualquer equipamento eletrônico digital é baseado em álgebra booleana (e.g. computador, smart phone, tablet,...)
Usada em expressões condicionais em linguagens de programação (e.g. if, while, for)
Diferente da álgebra convencional, onde as variáveis podem assumir valores no intervalo (-∞, +∞ ), as variáveis boolenas podem assumir apenas dois valores: 0 e 1
2
Álgebra booleana
Operações básicas da álgebra convencional
Soma, subtração, multiplicação e divisão
Operações básicas da álgebra boolena
AND (e lógico), OR (ou lógico) e NOT (complemento)
Exemplo
Equação da álgebra convencional
v = d/t + x
As variáveis da equação podem assumir qualquer valor intervalo (-∞, +∞ )
d = 300; t = 2,5; x = 10
v = 300/2,5 + 10
v = 120 + 10
v = 130
3
Álgebra booleana
Exemplo
Equação da álgebra booleana
X = (A.B) + C 
As variáveis da equação podem assumir apenas os valores 0 ou 1
A = 1; B = 0; C = 1
X = (1.0) + 1
X = 0 + 1
X = 1
Em programação, os valores booleanos 0 e 1 também são conhecidos como falso (false) e verdadeiro (true)
4
Álgebra booleana
Em circuitos eletrônicos digitais os dois valores booleanos são conhecidos como níveis lógicos
0: nível baixo (low)
1: nível alto (high)
Os níveis lógicos são representados por valores de tensão
O nível baixo corresponde a 0 Volt
O nível alto corresponde a um valor maior que 0 Volt, tipicamente entre 3,3 Volts ou 5 Volts 
5
0V
 5V
Álgebra booleana
Toda informação em um circuito digital é codificada em binária porque ele é baseado em álgebra boolena
Veremos os inicialmente os circuitos lógicos mais elementares: portas lógicas
A partir da interconexão entre portas lógicas, circuitos mais complexos são criados (e.g. processador)
As portas lógicas são circuitos básicos que implementam fisicamente as operações da álgebra boolena (operações lógicas)
AND (e lógico)
OR (ou lógico)
NOT (complemento ou negação)
Tabelas verdade
Apresentam o comportamento do circuito lógico em forma de tabela
6
Álgebra booleana
Operações básicas
OR (ou lógico)
Também denominada adição lógica
Símbolos: + , ν, |
A + B, A v B v C, B | C
Linguagens de programação (e.g. C, Java): || 
Definição
A operação OR resulta 1 se ao menos uma das variáveis de entrada vale 1. Resulta 0 se todas variáveis de entrada valem 0.
7
A
B
S
0
0
0
0
1
1
1
0
1
1
1
1
Tabela verdade
Porta lógica
S = A + B
2n linhas
n = número de variáveis ne entrada
Álgebra booleana
Operações básicas
OR (ou lógico)
Forma de onda (wave form)
Descreve o comportamento dinâmico do circuito
Se alguma das entradas é igual a 1, a saída é 1
S 
Álgebra booleana
Operações básicas
OR (ou lógico)
Porta lógica pode ter várias entradas
Definição
A operação OR resulta 1 se ao menos uma das variáveis de entrada vale 1. Resulta 0 se todas variáveis de entrada valem 0.
9
A
B
C
S
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
Tabela verdade
Porta lógica
S = A + B + C
A
B
C
S
Se alguma das entradas é igual a 1, a saída é 1
Álgebra booleana
Operações básicas
AND (e lógico)
Também denominada multiplicação lógica
Símbolos: . , ^, &
A . B, A ^ B ^ C, B & C
Linguagens de programação (e.g. C, Java): && 
Definição
A operação AND resulta 1 se todas variáveis de entrada valem 1. Resulta 0 se ao menos uma das variáveis de entrada vale 0.
A
B
S
0
0
0
0
1
0
1
0
0
1
1
1
Tabela verdade
Porta lógica
S = A . B
Álgebra booleana
Operações básicas
AND (e lógico)
Forma de onda (wave form)
Descreve o comportamento dinâmico do circuito
S
Se alguma das entradas é igual a 0, a saída é 0
Álgebra booleana
Operações básicas
AND (e lógico)
Porta lógica pode ter várias entradas
Definição
A operação AND resulta 1 se todas variáveis de entrada valem 1. Resulta 0 se ao menos uma das variáveis de entrada vale 0.
12
A
B
C
S
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
Tabela verdade
Porta lógica
S = A . B . C
A
B
C
S
Se alguma entrada é igual a 0, a saída é 0
Álgebra booleana
Operações básicas
NOT (complemento ou negação)
Inverte o valor lógico da variável de entrada
Símbolos: ¯,, ‘, ~, ! 
Ā, A’, ~A, !A (operação unária)
Linguagens de programação (e.g. C, Java): !
Definição
A operação NOT inverte o valor da variável
13
A
Ā
0
1
1
0
Tabela verdade
Porta lógica (inversor)
S = Ā
Álgebra booleana
Operações básicas
NOT (complemento ou negação)
Forma de onda (wave form)
Descreve o comportamento dinâmico do circuito
S
Álgebra booleana
Resumo das operações básicas
OR (Se alguma entrada é 1, a saída é 1)
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
0 + 0 + 0 + 0 + 1 + 0 = 1 
AND (Se alguma entrada é 0, a saída é 0)
0 . 0 = 0
0 . 1 = 0
1 . 0 = 0
1 . 1 = 1
1 . 1 . 1 . 0 . 1 . 1 . 1 = 0 
NOT (Inverte o valor)
!0 = 1
!1 = 0
Álgebra booleana
Logisim
Álgebra booleana
Avaliação algébrica de equações booleanas
Determinar o valor da saída para uma combinação das entradas
A avaliação da equação deve respeitar a ordem de precedência entre os operadores
Parênteses (do mais interno para o mais externo) ou NOT de variável (e.g. !B)
AND (e.g. A + B . C)
OR
Exemplo: Dada a equação booleana que descreve a função F(X, Y, Z), determinar o valor de F(1,0,0)
F = X . (Y + !Z)
F = 1 . (0 + !0) → substitui variáveis de entrada pelos valores lógicos
F = 1 . (0 + 1)
F = 1 . (1)
F = 1
Álgebra booleana
Avaliação completa de equações booleanas
Tabela verdade
Mostra o valor da saída para todos os possíveis valores das entrada de uma equação
Dada uma equação booleana qualquer, pode-se criar uma tabela verdade que descreve seu comportamento 
A equação deve ser avaliada para todos as possíveis combinações de valores das variáveis de entrada
A avaliação da equação deve ser realizada em partes seguindo a ordem de precedência entre os operadores
Álgebra booleana
Tabela verdade
X = !A + B
Variáveis de entrada: A e B
A tabela verdade para uma equação com n variáveis de entrada contém 2n linhas. 4 linhas nesse caso (22).
A
B
0
0
0
1
1
0
1
1
Nestas linhas deve-se enumerar todas as possíveis
combinações das variáveis de entrada
(números de 0 até 2n -1 utilizando a representação binária)
4 linhas (22)
Álgebra booleana
Tabela verdade
X = !A + B
Variáveis de entrada: A e B
Tabela verdade com 4 linhas (22)
Avaliação de !A
A
B
!A
0
0
0
1
1
0
1
1
Álgebra booleana
Tabela verdade
X = !A + B
Variáveis de entrada: A e B
Tabela verdade com 4 linhas (22)
Avaliação de !A
A
B
!A
0
0
1
0
1
1
1
0
0
1
1
0
Álgebra booleana
Tabela verdade
X = !A + B
Variáveis de entrada: A e B
Tabela verdade com 4 linhas (22)
Avaliação de !A + B
A
B
!A
X
0
0
1
0
1
1
1
0
0
1
1
0
Álgebra booleana
Tabela verdade
X = !A + B
Variáveis de entrada: A e B
Tabela verdade com 4 linhas (22)
Avaliação de !A + B
A
B
!A
X
0
0
1
1
0
1
1
1
1
0
0
0
1
1
0
1
Álgebra booleana
Tabela verdade
X = !A + B
Variáveis de entrada: A e B
Tabela verdade com 4 linhas (22)
Avaliação de !A + B
A
B
X
0
0
1
0
1
1
1
0
0
1
1
1
A tabela verdade contém apenas entrada e saídas
Álgebra booleana
Tabela verdade
Logisim: Project → Analyze Circuit
Álgebra booleana
Tabela verdade
X = !(A + B)
Variáveis de entrada: A e B
Tabela verdade com 4 linhas (22)
A
B
0
0
0
1
1
0
1
1
Álgebra booleana
Tabela verdade
X = !(A + B)
Variáveis de entrada: A e B
Tabela verdade com 4 linhas (22)
Avaliação de (A + B)
A
B
A + B
0
0
0
1
1
0
1
1
Álgebra booleana
Tabela verdade
X = !(A + B)
Variáveis de entrada:
A e B
Tabela verdade com 4 linhas (22)
Avaliação de (A + B)
A
B
A + B
0
0
0
0
1
1
1
0
1
1
1
1
Álgebra booleana
Tabela verdade
X = !(A + B)
Variáveis de entrada: A e B
Tabela verdade com 4 linhas (22)
Avaliação de !(A + B)
A
B
A + B
X
0
0
0
0
1
1
1
0
1
1
1
1
Álgebra booleana
Tabela verdade
X = !(A + B)
Variáveis de entrada: A e B
Tabela verdade com 4 linhas (22)
Avaliação de !(A + B)
A
B
A + B
X
0
0
0
1
0
1
1
0
1
0
1
0
1
1
1
0
Álgebra booleana
Tabela verdade
X = !(A + B)
Variáveis de entrada: A e B
Tabela verdade com 4 linhas (22)
Avaliação de !(A + B)
A
B
X
0
0
1
0
1
0
1
0
0
1
1
0
Álgebra booleana
Tabela verdade
F = X . (Y + !Z)
Variáveis de entrada: X, Y e Z
A tabela verdade com 8 linhas (23).
X
Y
Z
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
Álgebra booleana
Tabela verdade
F = X . (Y + !Z)
Avaliação de !Z
X
Y
Z
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
Álgebra booleana
Tabela verdade
F = X . (Y + !Z)
Avaliação de !Z
X
Y
Z
!Z
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
Álgebra booleana
Tabela verdade
F = X . (Y + !Z)
Avaliação de !Z
X
Y
Z
!Z
0
0
0
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
0
Álgebra booleana
Tabela verdade
F = X . (Y + !Z)
Avaliação de (Y + !Z)
X
Y
Z
!Z
Y + !Z
0
0
0
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
0
Álgebra booleana
Tabela verdade
F = X . (Y + !Z)
Avaliação de (Y + !Z)
X
Y
Z
!Z
Y + !Z
0
0
0
1
1
0
0
1
0
0
0
1
0
1
1
0
1
1
0
1
1
0
0
1
1
1
0
1
0
0
1
1
0
1
1
1
1
1
0
1
Álgebra booleana
Tabela verdade
F = X . (Y + !Z)
Avaliação de X . (Y + !Z)
X
Y
Z
!Z
Y + !Z
0
0
0
1
1
0
0
1
0
0
0
1
0
1
1
0
1
1
0
1
1
0
0
1
1
1
0
1
0
0
1
1
0
1
1
1
1
1
0
1
Álgebra booleana
Tabela verdade
F = X . (Y + !Z)
Avaliação de X . (Y + !Z)
X
Y
Z
!Z
Y + !Z
F
0
0
0
1
1
0
0
1
0
0
0
1
0
1
1
0
1
1
0
1
1
0
0
1
1
1
0
1
0
0
1
1
0
1
1
1
1
1
0
1
Álgebra booleana
Tabela verdade
F = X . (Y + !Z)
Avaliação de X . (Y + !Z)
X
Y
Z
!Z
Y + !Z
F
0
0
0
1
1
0
0
0
1
0
0
0
0
1
0
1
1
0
0
1
1
0
1
0
1
0
0
1
1
1
1
0
1
0
0
0
1
1
0
1
1
1
1
1
1
0
1
1
Álgebra booleana
Tabela verdade
F = X . (Y + !Z)
X
Y
Z
F
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
1
A tabela verdade contém apenas entrada e saídas
→ F(1,0,0)
Álgebra booleana
Tabela verdade
X = (!A.B.C) . !(A + D)
Variáveis de entrada: A, B, C e D
Tabela verdade com 16 linhas (24)
A
B
C
D
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
Álgebra booleana
Tabela verdade
X = (!A.B.C) . !(A + D)
A
B
C
D
!A
0
0
0
0
1
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
1
1
1
0
Avaliação de !A
Álgebra booleana
Tabela verdade
X = (!A.B.C) . !(A + D)
A
B
C
D
!A
A + D
0
0
0
0
1
0
0
0
0
1
1
1
0
0
1
0
1
0
0
0
1
1
1
1
0
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
1
0
0
1
1
1
1
1
1
0
0
0
0
1
1
0
0
1
0
1
1
0
1
0
0
1
1
0
1
1
0
1
1
1
0
0
0
1
1
1
0
1
0
1
1
1
1
0
0
1
1
1
1
1
0
1
Avaliação de (A + D)
Álgebra booleana
Tabela verdade
X = (!A.B.C) . !(A + D)
A
B
C
D
!A
A + D
!(A + D)
0
0
0
0
1
0
1
0
0
0
1
1
1
0
0
0
1
0
1
0
1
0
0
1
1
1
1
0
0
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
0
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
0
1
0
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
1
0
1
0
1
1
0
0
0
1
0
1
1
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
1
0
1
0
Avaliação de !(A + D)
Álgebra booleana
Tabela verdade
X = (!A.B.C) . !(A + D)
A
B
C
D
!A
A + D
!(A + D)
!A.B.C
0
0
0
0
1
0
1
0
0
0
0
1
1
1
0
0
0
0
1
0
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
0
1
0
1
0
0
1
0
1
1
1
0
0
0
1
1
0
1
0
1
1
0
1
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
0
1
1
0
1
0
0
1
1
0
0
0
1
0
0
1
1
0
1
0
1
0
0
1
1
1
0
0
1
0
0
1
1
1
1
0
1
0
0
Avaliação de (!A.B.C)
Álgebra booleana
Tabela verdade
X = (!A.B.C) . !(A + D)
A
B
C
D
!A
A + D
!(A + D)
!A.B.C
X
0
0
0
0
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
1
0
1
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
0
0
1
0
1
0
0
0
1
0
1
1
1
0
0
0
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
0
1
0
1
0
0
0
0
1
0
0
0
1
0
0
1
0
1
0
0
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
1
0
0
0
1
1
0
0
0
1
0
0
0
1
1
0
1
0
1
0
0
0
1
1
1
0
0
1
0
0
0
1
1
1
1
0
1
0
0
0
Avaliação de X
Álgebra booleana
Tabela verdade
X = (!A.B.C) . !(A + D)
A
B
C
D
X
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
1
1
1
0
Álgebra booleana