Cap.3 - Álgebra Booleana e Códigos

Prévia do material em texto

Sistemas Digitais
Cap. 3 – Álgebra Booleana e 
Portas Lógicas
Prof. Ubiratan Ramos
Álgebra de Boole
George Boole (1815-1864): Matemático Britânico, que através
de trabalhos publicados a partir de 1847 sobre Análise
Matemática da Lógica, divulgou idéias sobre Lógica Simbólica
- assim, a Lógica apresentada por Aristóteles poderia ser
apresentada por Equações Algébricas. Seu trabalho de 1854,
intitulado “Uma investigação das leis do pensamento”,
descreve o modo como tomamos decisões lógicas com base
em circunstâncias verdadeiras ou falsas.
Em 1938, com 22 anos, Claude Shannon publica sua
tese de mestrado, “Uma Análise Simbólica de Relés e
Circuitos de Comutação”, que utilizava álgebra de
Boole para estabelecer a base teórica de circuitos
digitais usados até hoje. Ele percebeu que a natureza
binária da lógica de Boole era análoga aos 1’s e 0’s
usados nos circuitos digitais. Foi o primeiro a utilizar
a terminologia bit. Também colaborou com Alan
Turing e seus trabalhos sobre Criptografia durante a
2ª. Guerra Mundial.
3
Tabelas verdade
� Seja um sistema digital que implemente a função lógica F.
� A,B : Variáveis lógicas de entrada
� Z : Variável lógica de saída
FA
B
Z
A B Z
0 0 1
0 1 0
1 0 1
1 1 0
SaídaEntradas
Combinações
4
Funções para 2 variáveis
A B Z
0 0 0 ou 1
0 1 0 ou 1
1 0 0 ou 1
1 1 0 ou 1
∴
A B Z
0 0 0
0 1 0
1 0 0
1 1 0
A B Z
0 0 0
0 1 0
1 0 0
1 1 1, ,
A B Z
0 0 0
0 1 0
1 0 1
1 1 0 ,
A B Z
0 0 0
0 1 0
1 0 1
1 1 1 ...
A B Z
0 0 1
0 1 1
1 0 1
1 1 1
5
Funções para 2 variáveis
6
Funções para 2 variáveis
7
Funções para 2 variáveis
8
Funções para 2 variáveis
9
Portas Lógicas
� Operação Inversora (NOT)
A Z
0 1
1 0
A Z
Tabela Verdade Representação Gráfica
Função Lógica Diagrama Temporal
Z = A
10
Portas Lógicas
� Operação E (AND)
A B Z
0 0 0
0 1 0
1 0 0
1 1 1
Tabela Verdade Representação Gráfica
Função Lógica Diagrama Temporal
Z = A·B
A Z
B
11
Portas Lógicas
� Operação Ou (OR)
A B Z
0 0 0
0 1 1
1 0 1
1 1 1
Tabela Verdade Representação Gráfica
Função Lógica Diagrama Temporal
Z = A+B
A Z
B
12
Portas Lógicas
� Operação Ou Exclusivo (XOR)
A B Z
0 0 0
0 1 1
1 0 1
1 1 0
Tabela Verdade Representação Gráfica
Função Lógica Diagrama Temporal
A Z
B
Z = A+B
13
Portas Lógicas
� Precedência das Operações
Z=A·B+C
Z=(A+B)·C
Z=A+B
Z=A+B
14
Portas Lógicas
� Operação NOR
� Operação NAND
≡
≡
15
Portas Lógicas
� Operação XNOR
≡
� Inversão de Entrada
≡
16
Avaliação das Expressões Booleanas
� Construção da Tabela Verdade:
� Combinações das n variáveis de entrada: 2n
� Criar n colunas com as 2n linhas de combinações
� Criar colunas para variáveis de entrada complementadas
� Avaliar a equação:
� Parênteses
� Operação NÃO
� Operação E
� Operação OU
� Exemplo
Z = A+B·C
17
Axiomas de Boole
(A1) X = 0 se X ≠ 1
(A2) Se x = 0, então 
(A3) 0.0 = 0
(A5) 0.1 = 1.0 = 0
(A1’) X = 1 se x ≠ 0
1=x (A2’) Se x = 1, então 0=x
(A4) 1.1 = 1
(A3’) 1 + 1 = 1
(A5’) 1 + 0 = 0 + 1 = 1
(A4’) 0 + 0 = 0
� Conjunto mínimo de definições assumidas como verdadeiras a 
partir do qual todas as outras definições são derivadas.
� Lei da Dualidade: substituindo-se o operador E pelo OU (e 
vice-versa), e os 0’s por 1’s (e vice-versa), obtém-se uma nova 
expressão algébrica também verdadeira.
18
Teoremas de Boole
(T1) X.1 = X
(T2) X.0 = 0
(T3) X.X = X
(T5) X.X = 0
(T1’) X + 0 = X
(T2’) X + 1 = 1
(T3’) X + X = X
(T5’) X + X = 1
� Afirmações que permitem manipular expressões algébricas 
objetivando simplificar a análise e a síntese de circuitos lógicos.
(T4) X = x
(Identidade)
(Elemento Nulo)
(Idempotência)
(Convolução)
(Complemento)
(T6) X.Y = Y.X (T6’) X + Y = Y + X (Comutatividade)
(T7) X.(Y.Z) = (X.Y).Z = X.Y.Z
(T7’) X+(Y+Z) = (X+Y)+Z = X+Y+Z (Associatividade)
19
Teoremas de Boole
(T8) X.Y + X.Z = X.(Y + Z)
(T8’) (X + Y).(X + Z) = X + Y.Z (Distributividade)
(T9) X + X.Y = X
(T9’) X.(X + Y) = X (Cobertura)
(T10) X.Y + X.Y = X
(T10’) (X + Y).(X + Y) = X (Combinação)
(T11) X.Y + X.Z + Y.Z = X.Y + X.Z
(T11’) (X+Y).(X+Z).(Y+Z) = (X+Y).(X+Z) (Consenso)
(T12) X + X.Y = X + Y
(T12’) X.(X + Y) = X.Y
(T13) X.Y + X.Z = (X + Z).(X + Y)
(T13’) (X+Y).(X+Z) = (X.Z) + (X.Y)
“O complemento de uma ‘soma’ de elementos é igual ao ‘produto’ dos seus 
complementos”
(T14) X + Y = X · Y
20
Teoremas de De Morgan
≡
≡
“O complemento de um “produto’ de elementos é igual à ‘soma’ dos seus 
complementos”
(T14’) X · Y = X + Y
21
Teoremas de Boole
Importante! Importante! Importante! Importante! XOR e XNOR:
X.Y + X.Y = X + Y (XOR)
X.Y + X.Y = X + Y (XNOR)
22
Universalidade das portas NAND
23
Universalidade das portas NOR
24
Descrever Circuitos Lógicos Algebricamente
Existem diferentes técnicas para a DESCRIÇÃO, ANÁLISE e SÍNTESE de 
circuitos digitais. Entre elas, destacam-se:
• Tabelas Verdade
• Expressões Lógicas ou Algébricas
• Símbolos Esquemáticos
• Diagramas de Tempo
• Forma de Proposição
25
Descrever Circuitos Lógicos Algebricamente
26
Descrever Circuitos Lógicos Algebricamente
27
Descrever Circuitos Lógicos Algebricamente
28
Descrever Circuitos Lógicos Algebricamente
29
Descrever Circuitos Lógicos Algebricamente
30
Exercícios
� Para cada um dos circuitos:
� Escrever a equação lógica que represente o circuito;
� Desenvolver a Tabela Verdade no MS-Excel e preenchê-la;
� Simular no Digital Works;
� Comparar os resultados;
� Fazer o relatório com os diagramas, tabelas e resultados;
� Salvar os arquivos e as Tabelas.