ELTD01-3

Prévia do material em texto

Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
CAPÍTULO 3 
ÁLEGBRA DE BOOLE 
A álgebra lógica foi apresentada pelo matemático Britânico George Boole em 1847 
(The Mathematical Analysis of Logic) em resposta a uma controvérsia entre Augustus De 
Morgan e William Hamilton e mais detalhadamente em 1854 (An Investigation of the Laws 
of Thought) e lida com a análise lógica. Em 1937 Claude Shannon provou que a álgebra de 
Boole e a aritmética binária poderiam ser usadas em circuitos com relês, usados em 
telefonia, e estabeleceu-se a álgebra digital ou álgebra binária. 
A álgebra de Boole descreve as operações lógicas dos circuitos lógicos, e 
consequentemente as iterações dos sinais digitais. Essas iterações permitem a 
implementação de blocos e circuitos maiores, que encontram infinitas aplicações, desde 
relógios digitais até complexos sistemas computacionais. 
A álgebra de Boole é baseada em dois valores lógicos; 0 e 1. Estes valores podem 
representar condições com as quais estão associadas, tais como verdadeiro e falso, ligado e 
desligado, aberto e fechado, energizado e desenergizado, etc. Em particular, poderia haver a 
relação 0 para falso e 1 para verdadeiro (ou vice-versa), 0 para aberto e 1 para fechado (ou 
vice versa) e assim sucessivamente. Como a álgebra de Boole contempla apenas dois 
valores, 0 e 1, pode-se inferir que o contrário de 0 é 1, e vice-versa. 
3.1 OPERAÇÕES BÁSICAS 
As três operações básicas da álgebra de Boole são os blocos elementares na 
construção de todos os circuitos digitais. 
3.1.1 Inversão 
A operação de inversão, também chamada de Não (NOT em Inglês), Negação ou 
Complemento, executa a inversão lógica do sinal de entrada. A operação de inversão de 
uma variável A tem tipicamente as representações mostradas em (3-1). A Tabela 3.1 
apresenta a sua operação e a Figura 3.1 mostra a sua representação gráfica. 
'AAY  (3-1) 
 
 
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
Tabela 3.1 – Operação inversão. 
A Y 
0 1 
1 0 
 
YA
 
Figura 3.1 – Operador inversor. 
3.1.2 Operação E 
Pela operação E (AND em Inglês) uma expressão, composta por duas ou mais 
variáveis, só é verdadeira se todas as variáveis forem verdadeiras ao mesmo tempo. As 
representações da operação E entre duas variáveis A e B é dada por (3-2). A Tabela 3.2 
apresenta a sua operação e a Figura 3.2 mostra a sua representação gráfica. 
ABBAY  . (3-2) 
 
Tabela 3.2 – Operação E. 
A B Y 
0 0 0 
0 1 0 
1 0 0 
1 1 1 
 
Y
A
B
 
Figura 3.2 – Operdor E. 
A e B podem representar sinais elétricos, condições mecânicas ou mesmo expressões. 
Como exemplo considere uma empresa que deseja contratar um funcionário que seja 
engenheiro E que saiba Inglês. O candidato tem que ser engenheiro e tem que saber Inglês. 
Somente uma das condições satisfeitas não permite contratação. Pode-se usar a notação: 
E = Engenheiro, 
I = Inglês, 
C = Contratatação. 
 
Assim, tem-se C = E.I. 
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
3.1.3 Operação Ou 
Pela operação Ou (OR em Inglês) uma expressão, composta por duas ou mais 
variáveis, é verdadeira se pelo menos uma das variáveis for verdadeira. As representações 
da operação OU entre duas variáveis A e B é dada por (3-3). A Tabela 3.3 apresenta a sua 
operação e a Figura 3.3 mostra a sua representação gráfica. 
BAY  (3-3) 
 
Tabela 3.3 – Operação OU. 
A B Y 
0 0 0 
0 1 1 
1 0 1 
1 1 1 
 
Y
A
B
 
Figura 3.3 – Operadorca OU. 
Novamente, A e B podem representar sinais elétricos, condições mecânicas ou 
mesmo expressões. Como exemplo considere uma empresa que deseja contratar um 
funcionário que seja engenheiro OU economista. O candidato tem que ser engenheiro ou 
tem que ser economista ou ainda pode ter as duas formações. Pode-se usar a notação: 
EN = Engenheiro, 
EC = Economista, 
C = Contratatação. 
 
Assim, tem-se C = EN + EC. 
3.2 EXPRESSÕES DUAIS E COMPLEMENTARES 
Expressões duais servem para simplificar as provas dos teoremas da álgebra de 
Boole, a serem vistos na próxima seção. As expressões duais são obtidas pelo seguinte 
procedimento: 
a. Trocam-se ∙ por + e + por ∙, 
b. Trocam-se 0 por 1 e 1 por 0, 
c. Mantêm-se as prioridades da expressão original pela adição ou remoção de 
parêntesis. 
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
Exemplos: 
1. 1... BDCBAF  , 
)0).().((  BDCBAFDUAL 
 
2. )( SRNTKLMX  
)).(( RSTNMLKX DUAL  
Uma importante propriedade da álgebra de Boole é a dualidade, que garante que toda 
expressão se mantém válida pela troca dos operadores E e Ou. 
Expressões complementares servem para obter o valor complementar ou negado da 
expressão original, para as mesmas variáveis. As expressões complementares são obtidas 
pelo seguinte procedimento: 
a. Trocam-se ∙ por + e + por ∙, 
b. Trocam-se 0 por 1 e 1 por 0, 
c. Mantêm-se as prioridades da expressão original pela adição ou remoção de 
parêntesis, 
d. Complementam-se todas as variáveis. 
 
Exemplos: 
1. 1... BDCBAF  , 
)0).().((  BDCBAF 
 
2. )( EDCCBAS  
)).(( EDCCBAS  
3.3 TEOREMAS 
Em 1904 E. V. Huntington estabeleceu os postulados da álgebra de Boole que foram 
empregados por Claude Shannon. O formalismo da álgebra de Boole, assim como alguns 
axiomas e postulados serão omitidos nesse material ou serão apresentados sob a forma de 
teoremas. 
Os teoremas serão apresentados em pares, onde um dos elementos é o dual do outro. 
Assim, ao provar um dos lados, pela propriedade da dualidade, o seu dual também está 
validado. 
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
3.3.1 Elemento Unitário (Aniquilador) 
T1.a. 11X T1.b. 00. X 
 
 Prova feita através da tabela verdade. Como a coluna 1X resulta em 1, fica provado! 
X 1X 
0 1 
1 1 
 
 
Deve-se observar que X pode ser uma variável ou uma expressão. Exemplo: 
00).1...()0..)(1...(  edcbakxedcbaf 
3.3.2 Elemento Nulo (Identidade) 
T2.a. XX  0 T2.b. XX 1. 
 
Prova feita através da tabela verdade. Como X e 1X são iguais, fica provado! 
X 0X 
0 0 
1 1 
 
Exemplo: 
pnmpnmzypnmg ..0..0....  
3.3.3 Idempotência 
T3.a. XXX  T3.b. XXX . 
 
Prova feita através da tabela verdade. Como X e XX  são iguais, fica provado! 
X XX  
0 0 
1 1 
 
Exemplo: 
)...()...)(...( edcbaedcbaedcbah  
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
3.3.4 Complementaridade 
T4.a. 1 XX T4.b. 0. XX 
 
 Prova feita através da tabela verdade. Como a coluna 1X resulta em 1, fica provado! 
X X XX  
0 1 1 
1 0 1 
 
Exemplo: 
110....0....0....  zypnmsszypnmszyspnmi 
3.3.5 Comutativa 
T5.a. XYYX  T5.b. XYYX ..  
 
Prova feita através da tabela verdade. Como as colunas YX  e XY  são iguais, fica 
provado! 
X Y YX  YX  
0 0 0 0 
0 1 1 1 
1 0 1 1 
1 1 1 1 
 
Exemplo: 
kfrssrfkj )()(  
3.3.7 De Morgan 
T7.a. XYYX . T7.b. XYYX . 
 
O lado a dos teoremas anteriores são muito intuitivos e similares à álgebra 
convencional. O teorema de De Morgan foge dessa regra e deve ser observado com atenção! 
X Y X Y YX  YX  YX . 
0 0 1 1 0 1 1 
0 1 1 0 1 0 0 
1 0 0 1 1 0 0 
1 1 0 0 1 0 0 
 
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
Prova feita através da tabela verdade. Como as colunas YX  e YX . são iguais, fica 
provado! Exemplo: 
1 yxyxyyxxk 
3.3.6 Associativa 
T6.a. )()( ZYXZYXZYX  T6.b. )..()..(.. ZYXZYXZYX  
 
Prova feita através da tabela verdade. Como as colunas ZYX  )( , ZYX  )( e 
ZYX  )( são iguais, fica provado! 
X Y Z YX  ZX  ZY  ZYX  )( ZYX  )( ZYX  )( 
0 0 0 0 0 0 0 0 0 
0 0 1 0 1 1 1 1 1 
0 1 0 1 0 1 1 1 1 
0 1 1 1 1 1 1 1 1 
1 0 0 1 1 0 1 1 1 
1 0 1 1 1 1 1 1 1 
1 1 0 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 
 
3.3.8 Distributiva 
T8.a. XZXYZYX  )( T8.b. ))(( ZXYXYZX  
 
Prova feita através da tabelaverdade. Como as colunas ZXXY  e )( ZYX  são 
iguais, fica provado! 
X Y Z XY XZ ZY  ZXXY  )( ZYX  
0 0 0 0 0 0 0 0 
0 0 1 0 0 1 0 0 
0 1 0 0 0 1 0 0 
0 1 1 0 0 1 0 0 
1 0 0 0 0 0 0 0 
1 0 1 0 1 1 1 1 
1 1 0 1 0 1 1 1 
1 1 1 1 1 1 1 1 
 
 
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
3.3.9 Combinação 
T9.a. XYXXY  T9.b. XYXYX  ))(( 
 
Prova feita através de teoremas anteriores. Observa-se que a variável que varia é 
eliminada e a parte constante é preservada. 
X
bTX
aTYYX
aTYXXY
.21.
.4)(
.8



 
Exemplo: 
rstutursuttursurstrsrstul  )()( 
3.3.10 Absorção ou Cobertura 
T10.a. XXYX  T10.b. XYXX  )( 
 
Prova feita através de teoremas anteriores. Se um termo aparece em outro termo com 
mais variáveis, esse termo com mais variáveis é eliminado (incorporado). 
X
bTX
aTYX
aTXYX
bTXYX
.21.
.1)1(
.81.
.2




 
Exemplo: 
abfadecababm  ))(( 
3.3.11 Eliminação 
T11.a. YXYXX  T11.b. XYYXX  )( 
 
Prova feita através de teoremas anteriores. Se um termo aparece complementado em 
outro termo com mais variáveis, esse termo complementado é eliminado, mantendo-se as 
demais variáveis. 
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
YX
bTYX
aTYXXX
bTYXX




.2).(1
.4))((
.8
 
Exemplo: 
dcbadcbaban  )(. 
3.3.12 Consenso ou Fantasma 
T12.a. YZZXXYZXXY  T12.b. ))()(())(( ZYZXYXZXYX  
 
Prova feita através de teoremas anteriores. Uma parte de um termo aparece 
complementada em outro termo. As partes que sobram nos dois termos formam o termo 
fantasma. 
YXXY
aTZYXZXY
aTXYZYZXZXXY
aTXXZYZXYX
aTZYZXYX
bTZYZXYX






.10)1()1(
.8
.8)(...
.41....
.2...
 
 
O termo fantasma é uma redundância e portanto pode ser inserida ou removida sem 
prejuízo para a expressão. A inclusão ou remoção do termo fantasma pode (e deve) ser 
usada para simplificar expressões. 
Exemplo: 
dccaabdcbccaabbddcbccaabbddccaabp  
Observe que inicialmente foi inserido o termo fantasma bc (obtido de ab e ca ). 
Esse termo fantasma bc juntamente com dc mostra que bd é temo fantasma e pode ser 
eliminado. A seguir o termo fantasma bc é eliminado. 
 
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
3.3.13 Conversão 
T13.a.   YXZXZXXY  T13.b.    YXXZZXYX  
 
Prova feita através de teoremas anteriores. Esse teorema é empregado para fazer 
mudanças entre os formatos das expressões. 
  
XYXZ
aTYZXYXZ
aTYZXYXZ
aTYZXYXZXX
aTZXYX





.12
.20
.4
.8
 
3.3.14 Teoremas – Sumário 
A Tabela 3.4 apresenta a compilação dos teoremas da álgebra de Boole. 
Tabela 3.4 – Teoremas da álgebra de Boole. 
T a. b. 
1 11X 00. X 
2 XX  0 XX 1. 
3 XXX  XXX . 
4 1 XX 0. XX 
5 XYYX  XYYX ..  
6 )()( ZYXZYXZYX  )..()..(.. ZYXZYXZYX  
7 XYYX . XYYX . 
8 XZXYZYX  )( ))(( ZXYXYZX  
9 XYXXY  XYXYX  ))(( 
10 XXYX  XYXX  )( 
11 YXYXX  XYYXX  )( 
12 YZZXXYZXXY  ))()(())(( ZYZXYXZXYX  
13   YXZXZXXY     YXXZZXYX  
 
 
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
3.3.15 Problemas de Aplicação de Teoremas 
Considere os dois exemplos a seguir, que podem ser solucionados com os recursos 
da álgebra de Boole. 
1. Um sistema de irrigação de jardins deve operar sobe as seguintes premissas: 
 Inverno e baixa umidade do solo, 
 Temperatura alta, verão e baixa umidade do solo, 
 Temperatura alta, alta umidade do solo e verão, 
 Temperatura baixa, verão e baixa umidade do solo, 
 Temperatura alta e baixa umidade do solo. 
Deve-se determinar a expressão que estabelece a operação desse sistema. Para isso, 
algumas considerações devem ser estabelecidas e devem-se usar o menor número de 
variáveis. Assim, tem-se: 
I = Inverno I = Verão 
U = Baixa umidade do solo U =Alta umidade do solo 
T = Baixa temperatura T = Alta temperatura 
 
 
 
 
UIT
bTaTIUIT
aTTTIUIT
aTTITIUIT
aTUTUITITIU
bTaTUTUITUITUITIU






.
.2&.11.
.4.
.11.
.8....
.2&.8.......
 
 
Assim, o sistema irá funcionar quando tiver baixa temperatura Ou temperatura alta E 
verão. 
 
2. Um sistema de ar condicionado deverá atuar se: 
 Temperatura acima de 21
o
C e estar entre 9:00 e 17:00hs, 
 Ser fim de semana com umidade relativa do ar acima de 85%, 
 Umidade relativa do ar acima de 85%, temperatura acima de 21
o
C e ser fim de semana, 
 Umidade relativa do ar acima de 85%, temperatura acima de 21
o
C e estar entre 9:00 e 
17:00hs. 
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
Deve-se determinar a expressão que estabelece a operação desse sistema. Para isso, 
as variáveis adotadas são: 
H = Estar entre 9:00 e 17:00hs H = Não estar entre 9:00 e 17:00hs 
U = Umidade relativa acima de 85% U = Umidade relativa abaixo de 85% 
T = Temperatura acima de 21
o
C T = Temperatura abaixo de 21
o
C 
F= Fim de semana F = Dia de semana 
 
FUTHUTHFUTHUTHUTFFUTHUTHUTFFUTH  
 
Assim, o sistema de ar-condicionado deverá funcionar se temperatura acima de 21
o
C 
E estar entre 9:00 e 17:00hs, Ou fim de semana E umidade relativa do ar acima de 85%. 
3.4 EXERCÍCIOS 
1. Usando os Teoremas da álgebra de Boole, simplifique as seguintes expressões: 
YXWXYZA  
XYXB  
)())(( 22221121 XXXXXXXXC  
)()( YXXWYXWYWXWWXYD  
ZXYYXE  
)( 2131231321 AAAAAAAAAAF  
BCAG  
)( BCAABH  
)(. DCBAI  
)()( YZXYZXJ  
CBABCACBACBAK  
)()( BACDCAL  
AABABCM  
)()( ABCBAN  
YZXYO . 
ABCBAP  
ZYYXQ )(  
Notas de Aula – ELTD01 Prof. Tales C Pimenta, PhD 
BCBACBAR  
))(()( 2332133433 XXXXXXXXXXS  
)())(( YXWXWXYZWXT  
3211221 ZZZZZZZU  
))(( ABABAABV  
ACBACBAX ))((  
BABAY  
21212121 XXXXXXXXZ  
)( ACABCABW  
 
2. Determine a operação lógica do circuito de controle de submersão de um micro-
submarino de pesquisa dever subir automaticamente à tona se: 
 bateria descarregada e oxigênio em nível baixo; ou 
 água potável em nível baixo, bateria carregada e oxigênio em nível baixo; ou 
 água potável e oxigênio em níveis baixos. 
3. Simplifique o circuito da Figura 3.4. 
Y X S T Z
R X L M S
A
N
M
R
X
L
N A
S
 
Figura 3.4 – Representação de circuito lógico. 
 
4. Prove o lado b de cada teorema. 
5. Simplifique as seguintes expressões: 
XYZWYWXWZXYA  
))()(( WZYAZXZXB  
wzxyzzyxC  )(