Sistemas Digitais - Álgebra Booleana

Prévia do material em texto

Sistemas Digitais I
Introduc¸a˜o
Myle`ne Christine Queiroz de Farias
Departamento de Engenharia Ele´trica
Universidade de Bras´ılia (UnB)
Bras´ılia, DF 70910-900
mylene@unb.br
March 10, 2018
Aula 02: A´lgebra Booleana
Suma´rio
Portas Lo´gicas
A´lgebra de Boole
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 2 / 41
A´lgebra de Boole
A´lgebra Booleana e´ uma sub-a´rea da a´lgebra na qual os valores das
varia´veis sa˜o verdadeiro e falso, indicados por ‘1’ e ‘0’,
respectivamente.
Introduzida em 1854 por George Boole (“An Investigation of the Laws
of Thought”)
Anos 30: Claude Shannon (Engenheiro Eletricista e Matema´tico)
observou que poderia utilizar a a´lgebra Booleana para analisar
circuitos chaveados.
“A Symbolic Analysis of Relay and Switching Circuits” — “possibly the
most important, and also the most famous, master’s thesis of the
century.”
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 3 / 41
A´lgebra de Boole
A´lgebra Booleana e´ uma sub-a´rea da a´lgebra na qual os valores das
varia´veis sa˜o verdadeiro e falso, indicados por ‘1’ e ‘0’,
respectivamente.
Introduzida em 1854 por George Boole (“An Investigation of the Laws
of Thought”)
Anos 30: Claude Shannon (Engenheiro Eletricista e Matema´tico)
observou que poderia utilizar a a´lgebra Booleana para analisar
circuitos chaveados.
“A Symbolic Analysis of Relay and Switching Circuits” — “possibly the
most important, and also the most famous, master’s thesis of the
century.”
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 3 / 41
A´lgebra de Boole
Revisando:
Varia´veis bina´rias: 1 ou 0, V ou F, ALTO ou BAIXO;
Func¸o˜es ba´sicas: E, OU, NO (INVERSORA).
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 4 / 41
A´lgebra de Boole
Func¸a˜o E (AND):
S´ımbolos: . , ˆ , ∗ , E
Z = X · Y
Z = X ∧ Y
Z = X ∗ Y
Z e´ igual a ‘1’ se todas as
entradas X e Y forem iguais a
‘1’
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 5 / 41
A´lgebra de Boole
Func¸a˜o OU (OR):
S´ımbolos: + , v , OU
Na˜o e´ adic¸a˜o!
Z = X + Y
Z = X ∨ Y
Z e´ igual a ‘1’ se pelo menos
uma das entradas X OU Y (ou
ambas) forem iguais a ‘1’
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 6 / 41
A´lgebra de Boole
Func¸a˜o NA˜O ou INVERSORA:
S´ımbolos: –, ! , ˜
Z = X
Z = X˜
Z =!X
Z e´ igual a inverso do sinal de
entrada X .
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 7 / 41
Portas Lo´gicas
Diagramas de circuitos que implementam as func¸o˜es lo´gicas
Importante: ‘0’ e ‘1’ sa˜o representados por tenso˜es!
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 8 / 41
Portas Lo´gicas
Diagramas de Tempo da Porta AND (E)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 9 / 41
Portas Lo´gicas
Diagramas de Tempo da Porta OR (OU)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 10 / 41
Portas Lo´gicas
Diagramas de Tempo da Porta NOT (Inversora)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 11 / 41
Portas Lo´gicas
Nu´mero de entradas: Mesmo princ´ıpio de funcionamento!
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 12 / 41
Circuitos digitais
Representac¸a˜o: Esquema´tico = diagrama do circuito
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 13 / 41
Circuitos digitais
Representac¸a˜o: a´lgebra de Boole ou booleana
Equac¸o˜es com as func¸o˜es ba´sicas (E, OU e NA˜O);
Os termos podem ser reduzidos ate´ a forma final.
A´lgebra de Boole
F = X + Y · Z
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 14 / 41
Circuitos digitais
Tabela Verdade
2n linhas onde n e´ o nu´mero de varia´veis de entrada.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 15 / 41
Circuitos digitais
Observac¸a˜o 1:
Func¸o˜es diferentes podem ter a mesma tabela verdade
F = X + Y · Z
e
F = (X + Y )(X + Z )
Geralmente, a func¸a˜o mais simples e´ utilizada
Menor nu´mero de portas!
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 16 / 41
A´lgebra de Boole
Precedeˆncia das func¸o˜es lo´gicas
NA˜O > E > OU
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 17 / 41
A´lgebra de Boole
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 18 / 41
A´lgebra de Boole
I. Dupla Negac¸a˜o
X = X (1)
II. Operac¸o˜es com “0” e “1”
X · 1 = X (2)
X + 0 = X (3)
X · 0 = 0 (4)
X + 1 = 1 (5)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 19 / 41
A´lgebra de Boole
III. Complementos
X · X = 0 (6)
X + X = 1 (7)
IV. Tautologia
X · X = X (8)
X + X = X (9)
V. Absorc¸a˜o
X1 · (X1 + X2) = X1 (10)
X1 + X1 · X2 = X1 (11)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 20 / 41
A´lgebra de Boole
VI. Comutatividade
X1 · X2 = X2 · X1 (12)
X1 + X2 = X2 + X1 (13)
VII. Distributividade
X1 · (X2 + X3) = X1 · X2 + X1 · X3 (14)
X1 + X2 · X3 = (X1 + X2) · (X1 + X3) (15)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 21 / 41
A´lgebra de Boole
VIII. Dualidade
Os axiomas do tipo I...IV.a e I...IV.b sa˜o duais:
Substituir E por OU e ‘0’s por ‘1’s.
A operac¸a˜o e´ independente da ordem das varia´veis;
Pode-se substituir, arbitrariamente, expresso˜es alge´bricas grandes por
varia´veis.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 22 / 41
A´lgebra de Boole
IX. Associatividade
X1 · (X2 · X3) = (X1 · X2) · X3 (16)
X1 + (X2 + X3) = (X1 + X2) + X3 (17)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 23 / 41
A´lgebra de Boole
X. Teorema De Morgan
X1 · X2 = X1 + X2 (18)
X1 + X2 = X1 · X2 (19)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 24 / 41
A´lgebra de Boole
X. Teorema De Morgan
X1 · X2 = X1 + X2 (20)
X1 + X2 = X1 · X2 (21)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 25 / 41
Manipulac¸a˜o de Func¸o˜es
Exemplo 1: Usando DeMorgan
A · B = A + B
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 26 / 41
Manipulac¸a˜o de func¸o˜es
Exemplo 2: Usando DeMorgan
A + B = A · B
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 27 / 41
A´lgebra de Boole
F = X · Y · Z + X · Y · Z + X · Z
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 28 / 41
A´lgebra de Boole
F = X · Y · Z + X · Y · Z + X · Z
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 28 / 41
A´lgebra de Boole
F = X · Y · Z + X · Y · Z + X · Z
Aplicando propriedade distributiva
.A · (B + C ) = A · B + A · C
F = X · Y · (Z + Z ) + X · Z
Aplicar propriedade distributiva
A + A = 1 e A · 1 = A
F = X · Y · 1 + X · Z
F = X · Y + X · Z
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 29 / 41
A´lgebra de Boole
F = X · Y · Z + X · Y · Z + X · Z
Aplicando propriedade distributiva
.A · (B + C ) = A · B + A · C
F = X · Y · (Z + Z ) + X · Z
Aplicar propriedade distributiva
A + A = 1 e A · 1 = A
F = X · Y · 1 + X · Z
F = X · Y + X · Z
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 29 / 41
A´lgebra de Boole
F = X · Y · Z + X · Y · Z + X · Z
Aplicando propriedade distributiva
.A · (B + C ) = A · B + A · C
F = X · Y · (Z + Z ) + X · Z
Aplicar propriedade distributiva
A + A = 1 e A · 1 = A
F = X · Y · 1 + X · Z
F = X · Y + X · Z
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 29 / 41
A´lgebra de Boole
de
F = X · Y · Z + X · Y · Z + X · Z
para
F = X · Y + X · Z
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 30 / 41
A´lgebra de Boole
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 31 / 41
A´lgebra de Boole
Exemplos
Exemplos simples no quadro.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 32 / 41
A´lgebra de Boole
Complemento de uma func¸a˜o:
Definic¸a˜o: 1’s & 0’s trocados de posic¸a˜o na tabela verdade
Partir da func¸a˜o complementar (dual)
Trocar E’s por OU’s e 1’s & 0’s (e vice-versa)
Func¸o˜es Duais
f = A + B −→ f D = A · B (22)
f = A(B + C ) −→ f D = A + B · C (23)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 33 / 41
Circuitos digitais
Exemplo:
Como obter´ıamosa tabela verdade?
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 34 / 41
Circuitos digitais
Exemplo:
Como obter´ıamos a tabela verdade?
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 34 / 41
Circuitos digitais
Exemplo:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 35 / 41
Circuitos digitais
Exemplo:
F = ((X + Y ) · Z ) + (X · Y · Z )
Podemos mudar esta expressa˜o? No quadro!
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 36 / 41
Circuitos digitais
Exemplo:
F = ((X + Y ) · Z ) + (X · Y · Z )
Podemos mudar esta expressa˜o? No quadro!
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 36 / 41
Circuitos digitais
Exemplo:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 37 / 41
Circuitos Digitais
Na˜o esquecer que:
Dentro dessas portas lo´gicas, temos circuitos ele´tricos com limitac¸o˜es.
A lo´gica digital so´ funcionara´, se forem respeitadas condic¸o˜es de:
Velocidade ma´xima de operac¸a˜o
Alimentac¸a˜o adequada
Limites de cascateamento (fan-in e fan-out)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 38 / 41
Circuitos Digitais
Velocidade ma´xima de operac¸a˜o: circuitos digitais na˜o respondem
instantaneamente!
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 39 / 41
Circuitos Digitais
Alimentac¸a˜o:
Para que o circuito digital opere, ele deve ser alimentado com uma
tensa˜o igual ou ligeiramente superior a` tensa˜o do n´ıvel lo´gico ‘1’
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 40 / 41
Circuitos Digitais
Limite de cascateamento:
Qualquer circuito tem limitac¸o˜es de fornecimento de corrente ele´trica.
Por menor que seja a corrente ele´trica absorvida na entrada de um
circuito digital, ela deve ser levada em considerao.
Fan-in : corrente ma´xima absorvida na entrada
Fan-out : corrente ma´xima fornecida na sa´ıda
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 41 / 41