Introdução à Informática
Álgebra de Boole
Ageu Pacheco e Alexandre Meslin
Álgebra de Boole
z Objetivo
z Estudar
da Aula:
os conceitos e regras que regem
o projeto e funcionamento dos circuitos
lógicos dos computadores digitais.
Álgebra de Boole
z Álgebra
de Boole:
Criada em 1854 por George Boole com o
intuito de formalizar matematicamente o
pensamento lógico.
Álgebra de Boole
z Variável
lógica ou booleana:
Uma variável lógica só pode assumir dois
valores (estados):
verdadeiro ou falso; ligado ou desligado;
aceso ou apagado; fechado ou aberto;
branco ou preto; sim ou não; “1” ou “0”.
Álgebra de Boole
z Operações
lógicas básicas (primitivas):
São 3 as operações lógicas básicas:
1. Produto lógico
2. Soma lógica
3. Negação
porta
porta
porta
AND ( )
OR (+)
NOT ( )
Álgebra de Boole
z Todas
as operações internas a um
computador podem ser descritas por
combinações destas 3 operações
básicas.
z Na
realidade bastaria utilizar o AND
com o NOT ou o OR com o NOT
(conjuntos funcionalmente
completos).
Álgebra de Boole
z Uma
função lógica pode ser representada
pela sua expressão algébrica, pela sua
tabela verdade, pelo seu símbolo ou
circuito lógico.
A B F
Exemplo:
0 0
0
F(A,B) = A.B + A.B
A
B
F
0
1
1
1
0
1
1
1
0
Álgebra de Boole
z Função
AND
Definição:
F(A,B,C,...,N) = A.B.C....N
F(A,B,C,...,N) = 1 se e somente se
A=B=C=...=N=1
Álgebra de Boole
z AND
de duas variáveis:
F(A,B) = A.B
A
F
B
Símbolo lógico
A
B
F
0
0
0
0
1
0
1
0
0
1
1
1
Tabela verdade
Álgebra de Boole
AND de duas variáveis: (cont.)
F(A,B) = A.B
A
0
1
V+
_
B
A
B
F
0
0
0
0
1
0
1
0
1
0
0
1
1
1
I
Circuito elétrico equivalente
Álgebra de Boole
z AND
de três variáveis:
F(A,B,C) = A.B.C
A
B
C
F
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
0
0
0
0
0
0
0
1
Álgebra de Boole
z Cada
linha da tabela verdade
relaciona uma combinação específica
das variáveis de entrada ao valor
assumido pela função na saída.
zO
n
número total de linhas é igual a 2 ,
onde n é o número de variáveis.
Álgebra de Boole
z Função
OR
Definição:
F(A,B,C,...,N) = A+B+C+...+N
F(A,B,C,...,N) = 1 se e somente se
A=1 ou B=1 ou ... ou N=1
Álgebra de Boole
z OR
de duas variáveis:
F(A,B) = A+B
A
F
B
Símbolo lógico
A
B
F
0
0
0
0
1
1
1
0
1
1
1
1
Tabela verdade
Álgebra de Boole
OR de duas variáveis: (cont.)
F(A,B) = A+B
A
B
V+
_
0
1
0
1
I
Circuito elétrico equivalente
A
B
F
0
0
0
0
1
1
1
0
1
1
1
1
Álgebra de Boole
z OR
de três variáveis:
F(A,B,C) = A+B+C
A
B
C
F
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
0
1
1
1
1
1
1
1
Álgebra de Boole
z Função
NOT
Definição: F(A) = A
F(A) = 0 se A = 1
F(A) = 1 se A = 0
A
A
F
0
1
1
0
A
Álgebra de Boole
z Outras
funções lógicas importantes:
z Função NAND
Definição:
F(A,B,C,...,N) = A.B.C....N
F(A,B,C,...,N) = 0 se e somente se
A=B=C=...=N=1
Álgebra de Boole
z NAND
de duas variáveis:
variáveis
F(A,B) = A.B
A
F
B
Símbolo lógico
A
B
F
0
0
1
0
1
1
1
0
1
1
1
0
Tabela verdade
Álgebra de Boole
z Função
NOR
Definição:
F(A,B,C,...,N) = A+B+C+...+N
F(A,B,C,...,N) = 1 se e somente se
A=B=C=...=N=0
Álgebra de Boole
z NOR
de duas variáveis:
F(A,B) = A+B
A
F
B
Símbolo lógico
A
B
F
0
0
1
0
1
0
1
0
0
1
1
0
Tabela verdade
Álgebra de Boole
z Função
OU-EXCLUSIVO (XOR)
A
F(A,B) = A + B
F
B
Por inspeção na tabela verdade:
A
B
F
0
0
0
1
1
1
0
1
1
1
0
F=1 se A=0 e B=1 ou se A=1 e B=0
0
F(A,B) = A.B
+
A.B
Álgebra de Boole
z Relações
da álgebra booleana:
z Postulados:
1a.
2a.
3a.
4a.
5a.
A = 1 (se A=0)
0.0 = 0
1.1 = 1
1.0 = 0
1=0
1b.
2b.
3b.
4b.
5b.
A = 0 (se A=1)
0+0 = 0
1+1 = 1
1+0 = 1
0=1
Álgebra de Boole
z Relações
da álgebra booleana (cont.):
z Teoremas:
6a.
7a.
8a.
9a.
10a.
A.0 = 0
A.1 = A
A.A = A
A.A = 0
A=A
6b.
7b.
8b.
9b.
10b.
A+0 = A
A+1 = 1
A+A = A
A+A = 1
A=A
Álgebra de Boole
z Propriedades
algébricas:
Comutativa:
11a. AB = BA
11b. A+B = B+A
Associativa:
12a. A(BC) = AB(C)
12b. A+(B+C) = (A+B)+C
Distributiva:
13a. A(B+C) = AB + AC
13b. A + BC = (A+B) (A+C)
Álgebra de Boole
z Teorema
da absorção:
14a. A(A+B) = A
14b. A+AB = A
15a. A(A+B) = AB 15b. A+AB = A+B
Álgebra de Boole
z Teoremas
de De Morgan:
16a. A.B.C...N = A + B + C +...+N
16b. A+B+C+...+N = A . B . C ... N
Álgebra de Boole
z Consequências
diretas das leis De Morgan:
1. A.B = A + B
A
B
F
A
B
F
Álgebra de Boole
z Consequências
diretas das leis De Morgan:
1. Prova pela tabela verdade:
F1(A,B) = A.B
F2(A,B) = A + B
A.B = A + B
A
B
F1 F2
0
0
1
1
0
1
1
1
1
0
1
1
1
1
0
0
Álgebra de Boole
z Consequências
diretas das leis De Morgan:
2. A+B = A . B
A
B
F
A
B
F
Álgebra de Boole
z Consequências
diretas das leis De Morgan:
3. A.B = A+B
A.B = A + B
A.B = A + B
A
B
F
A
B
F
Álgebra de Boole
z Consequências
diretas das leis De Morgan:
4. A+B = A.B
A+B = A . B
A+B = A . B
A
B
F
A
B
F
Álgebra de Boole
z Exercícios:
1. Mostrar que A + BC = (A+B)(A+C)
(A+B)(A+C) = AA+AC+AB+BC =
= A+AC+AB+BC =
1
= A(1+C+B)+BC
= A + BC
13b
Álgebra de Boole
z Exercícios:
(cont.)
2. Mostrar que A + AB = A + B
14b
15b
A+AB = A(1+B) = A
A
A + AB = A+AB + AB = A+(A+A)B =
=A+B
Álgebra de Boole
z Exercícios:
(cont.)
3. Mostrar que A + B = A + B
M
M
A + B = AB + AB = AB . AB =
M
= (A+B)(A+B) = AA+AB+AB+BB
0
= AB + AB
0
Álgebra de Boole
z Exercícios:
(cont.)
3. Mostrar que A + B = A + B (cont.)
X + B = XB + XB
Fazendo X=A, temos:
A + B = AB + AB = AB + AB = A + B
Álgebra de Boole
z Exercícios:
(cont.)
4. Mostrar que AB + AC + BC = AB + AC
AB+AC+BC = AB+AC+BC(A+A) =
= AB + AC + ABC + ABC =
1
= AB(1+C)+AC(1+B) = AB + AC
Álgebra de Boole
z Exercícios:
(cont.)
5. Simplifique a expressão lógica de F:
F(x,y,z) = xyz + xyz + xyz +xyz
= xyz+xyz+xy(z+z) = xy+xyz+xyz =
= y(x+xz)+xyz = y(x+z)+xyz =
15b
Álgebra de Boole
z Exercícios:
(cont.)
5. (cont.)
F = xy +yz + xyz = yz + x(y+yz) =
15b
= yz + x(y+z)
F(x,y,z) = xy + xz + yz
Álgebra de Boole
z Exercícios:
(cont.)
6. Determine a expressão lógica para a
saída F no circuito abaixo:
A
B
C
F
Álgebra de Boole
z Exercícios:
6. (cont.)
(cont.)
A
B
C
F1
F
F2
F1 = AB , F2 = B + C = BC + BC
F = F1+F2 = AB + BC + BC
Álgebra de Boole
z Exercícios:
(cont.)
7. Dado o circuito abaixo, obtenha a
expressão lógica mais simples que
você puder para a saída F:
A
B
F
Álgebra de Boole
z Exercícios:
(cont.)
7. (cont.)
A
B
F1
F
F2
F1 = A + B = AB + AB , F2 = B
1
F = F1+F2 = AB+AB+B = B(1+A)+AB =
M
= B+AB = B+A = B.A = AB
Álgebra de Boole
z Exercícios:
(cont.)
7. (cont.)
A
B
F(A,B) = AB
F
A
B
F
Álgebra de Boole
z Exercícios:
(cont.)
8. Desenhe o circuito correspondente a
expressão abaixo:
A
B
C
F = ABC + BC
F
Álgebra de Boole
z Exercícios:
(cont.)
9. Simplifique a expressão de F do
exemplo anterior:
M
F = ABC + BC = A+B+C + BC =
= A+B+C+B = A+1+C = 1
1
Álgebra de Boole
z Exercícios:
(cont.)
9. (cont.)
A
B
C
F
“1”
“0”(0volts)
Álgebra de Boole
z Exercícios:
(cont.)
10. No circuito abaixo, obtenha a expressão
lógica mais simples que você puder
para a saída F:
A
B
F
C
Álgebra de Boole
z Exercícios:
10.
(cont.)
F1
A
B
F2
F
C
M
F1 = A+B = A.B
M
F2 = F1B C = ABBC = ABC = A+B+C
M
F = F1F2 = F1+F2
Álgebra de Boole
z Exercícios:
(cont.)
10. (cont.)
M
F1 = A+B = A.B
M
F2 = F1B C = ABBC = ABC = A+B+C
M
F = F1F2 = F1+F2
F = F1+F2 = A+B + ABC = A+B+ABC
F = A+BC+B = A+B+C
Álgebra de Boole
z Exercícios:
(cont.)
10. (cont.)
A
B
F
C
A
B
C
F
A
B
C
F
A
B
C
F