Álgebra Booleana em Circuitos Digitais

Prévia do material em texto

Circuitos Digitais
Aula 3 – Álgebra Booleana
DCC/IM/UFRRJ
Marcel William Rocha da Silva
Objetivos da aula
• Aula passada
– Uso de transistores em circuitos lógicos
– Formas de representação
• Aula de hoje
– Álgebra booleana e teoremas
– Teoremas de DeMorgan
• Universalidade das portas NAND e NOR
Álgebra booleana
• Parte da matemática que lida com números binários
– 0 ou 1, baixo ou alto, aberto ou fechado, desligado ou 
ligado, falso ou verdadeiro
• Variáveis booleanas → assumem apenas dois valores
– A = estado da porta da sala
– B = estado da lâmpada
• Equações booleanas → Servem para expressar a 
relação entre as entradas e saídas de um circuito lógico
– Compostas por variáveis booleanas
Operações booleanas
• Três operações da álgebra booleana
– AND
• X = A.B
– OR
• X = A+B
– NOT
• X = A’ = A
• Qualquer função lógica pode ser descrita com 
estas operações básicas!
A . B = X
0 . 0 = 0
0 . 1 = 0
1 . 0 = 0
1 . 1 = 1
A + B = X
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
A’ = X
0’ = 1
1’ = 0
Exemplo de aplicação (OR)
• Sistema de controle de alarme
Sensor 
Temp.
Sensor 
Pressão
Comparador
Comparador
Tref
Pref
Alarme
Exemplo de aplicação (AND)
• Circuito inibidor
A
B
X
A
B
X
Equações booleanas
• Usadas para descrever circuitos lógicos
– X = A . B + C
– X = (A + B) . C
A
B X=(A+B).C
C
A+B
A
B X=A.B+C
C
A.B
Precedência das operações
• Como avaliar a expressão X=A.B+C ?
– AND tem precedência sobre o OR
• Como avaliar a expressão X=(A+B).C ?
– Parênteses tem precedência
• Como avaliar a expressão X=A’.B ?
– NOT tem precedência
• Parênteses servem para eliminar ambiguidades!
Exemplos
• Assumindo os valores abaixo avalie as 
expressões X=ABC(A+D) e Y=[D+(A+B)C]E
– A=0
– B=1
– C=1
– D=1
– E=1
E o XOR e o XNOR?
• Na prática, são construídos com as operações básicas
– XOR
– XNOR
• Observações
– Possuem sempre duas entradas
– XOR possui porta lógica e operador booleano especial ()
A
B
X=A’B+AB’
A’
B’
A’B
AB’
A
B
X=A’B’+AB
A’
B’
A’B’
AB
Exemplo de aplicação (XOR)
• Comparador bit a bit
– Dois números binários de 2 bits
x1
x0
y1
y0
z
Teoremas booleanos
• Semelhante aos teoremas e propriedades da 
aritmética decimal
– Igualdades entre expressões
– Servem para simplificar equações booleanas
• Útil para o projeto de circuitos lógicos!
– Simplificar expressões que representam o circuito que 
se deseja projetar
– Expressões mais simples = menos operações = menos 
portas lógicas = menor custo
Teoremas booleanos
• Teoremas com uma variável (A) e operadores 
básicos
– Operador OR
• A + 0 = A
• A + 1 = 1
• A + A = A
• A + A’ = 1
• Provas pelas tabelas verdade!
– Operador AND
• A . 0 = 0
• A . 1 = A
• A . A = A
• A . A’ = 0
Teoremas booleanos
• Teoremas com mais de uma variável
– Leis comutativas
• A+B = B+A
• A.B = B.A
– Leis associativas
• A + (B + C) = (A + B) + C = A + B + C
• A . (B . C) = (A . B) . C = A . B . C
– Leis distributivas
• A . (B + C) = A . B + A . C
• (A + B) . (C + D) = A . C + A . D + B . C + B . D
• Provas pelas tabelas verdade!
Teoremas booleanos
• Leis anteriores idênticas às leis da álgebra 
convencional
• Teoremas exclusivos da álgebra booleana
– A + A . B = A
– A + A’ . B = A + B
– A’ + A . B = A’ + B
• Prova via tabelas verdade ou simplificação
Exercícios
• Simplifique as expressões abaixo
D.B.AD.AT
D.C.B.AD.C.B.AS
C.B.AC.AR
D.C.B.AD.C.AZ
)BA).(BA(Y
D.B.AD.B.AX
+=
+=
+=
+=
++=
+=
Teoremas de DeMorgan
• Úteis para a simplificação de produtos ou somas que 
aparecem negadas (barradas)
• (A + B)’ = A’ . B’
• (A . B)’ = A’ + B’
• Também valem para mais de duas variáveis
– (A + B + C)’ = A’ . B’ . C’
– (A . B . C)’ = A’ + B’ + C’
• Serve para remover negações de expressões complexas até 
que tenhamos apenas variáveis simples negadas
Exemplos
• Simplifique as expressões abaixo para que 
tenham apenas variáveis simples invertidas
).).(.(
)).((
FEDCBAZ
CBAY
DBCAX
++=
++=
++=
Universalidade
• Qualquer circuito pode ser descrito apenas com 
portas AND, OR e INV
• Portas NAND e NOR têm a propriedade da 
universalidade
– Comportamento das portas básicas podem ser 
obtidos apenas com operações NAND ou NOR
– Qualquer circuito pode ser construído apenas com 
portas NAND ou portas NOR!
• Prova?
Universalidade portas NAND
• INV
• AND
• OR
A
X
B
A
X
B
A X
Universalidade portas NOR
• INV
• AND
• OR
A X
A
X
B
	Slide 1: Circuitos Digitais
	Slide 2: Objetivos da aula
	Slide 3: Álgebra booleana
	Slide 4: Operações booleanas
	Slide 5: Exemplo de aplicação (OR)
	Slide 6: Exemplo de aplicação (AND)
	Slide 7: Equações booleanas
	Slide 8: Precedência das operações
	Slide 9: Exemplos
	Slide 10: E o XOR e o XNOR?
	Slide 11: Exemplo de aplicação (XOR)
	Slide 12: Teoremas booleanos
	Slide 13: Teoremas booleanos
	Slide 14: Teoremas booleanos
	Slide 15: Teoremas booleanos
	Slide 16: Exercícios
	Slide 17: Teoremas de DeMorgan
	Slide 18: Exemplos
	Slide 19: Universalidade
	Slide 20: Universalidade portas NAND
	Slide 21: Universalidade portas NOR