Introdução à Informática_TSC-CEDERJ_07

Prévia do material em texto

Introdução à InformáticaIntrodução à Informática
Álgebra de Álgebra de BooleBoole
Ageu Pacheco e Alexandre Ageu Pacheco e Alexandre MeslinMeslin
Álgebra de Álgebra de BooleBoole
zz ObjetivoObjetivo da Aulada Aula::
zz Estudar os conceitos e regras que regem Estudar os conceitos e regras que regem 
o projeto e funcionamento dos circuitos o projeto e funcionamento dos circuitos 
lógicos dos computadores digitais.lógicos dos computadores digitais.
Álgebra de Álgebra de BooleBoole
zz Álgebra de Álgebra de BooleBoole::
Criada em 1854 por George Criada em 1854 por George BooleBoole com o com o 
intuito de formalizar matematicamente o intuito de formalizar matematicamente o 
pensamento lógicopensamento lógico. . 
Álgebra de Álgebra de BooleBoole
zz Variável lógica ou Variável lógica ou booleanabooleana::
Uma variável lógica só pode assumir dois Uma variável lógica só pode assumir dois 
valores (estados): valores (estados): 
verdadeiro ou falso; ligado ou desligado; verdadeiro ou falso; ligado ou desligado; 
aceso ou apagado; fechado ou aberto; aceso ou apagado; fechado ou aberto; 
branco ou preto; sim ou não; “1” ou “0”.branco ou preto; sim ou não; “1” ou “0”.
Álgebra de Álgebra de BooleBoole
zz Operações lógicas básicas (primitivas):Operações lógicas básicas (primitivas):
São 3 as operações lógicas básicas:São 3 as operações lógicas básicas:
1. Produto lógico 1. Produto lógico porta AND ( )porta AND ( )
2.2. Soma lógicaSoma lógica porta OR (+)porta OR (+)
3.3. NegaçãoNegação porta NOT ( )porta NOT ( )
Álgebra de Álgebra de BooleBoole
zTodas as operações internas a um 
computador podem ser descritas por 
combinações destas 3 operações 
básicas.
zNa realidade bastaria utilizar o AND 
com o NOT ou o OR com o NOT 
(conjuntos funcionalmente 
completos).
Álgebra de Álgebra de BooleBoole
zz Uma função lógica pode ser representada Uma função lógica pode ser representada 
pela sua expressão algébrica, pela sua pela sua expressão algébrica, pela sua 
tabela verdade, pelo seu símbolo ou tabela verdade, pelo seu símbolo ou 
circuito lógico. circuito lógico. 
Exemplo:Exemplo:
F(A,B) = A.B + A.BF(A,B) = A.B + A.B
001111
110011
111100
000000
FFBBA A 
FFAA
BB
Álgebra de Álgebra de BooleBoole
zFunçã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 Álgebra de BooleBoole
zAND de duas variáveis:
F(A,B) = A.B
111111
000011
001100
000000
FFBBA A 
AA
BB
FF
Símbolo lógicoSímbolo lógico Tabela verdadeTabela verdade
Álgebra de Álgebra de BooleBoole
AND de duas variáveis: (cont.)
F(A,B) = A.B
111111
000011
001100
000000
FFBBA A 
Circuito elétrico equivalenteCircuito elétrico equivalente
AA BB
IIVV ++
__
0000
1111
Álgebra de Álgebra de BooleBoole
zAND de três variáveis:
F(A,B,C) = A.B.C
AA
BB FF
CC
11111111
00001111
00110011
00000011
00111100
00001100
00110000
00000000
FFCCBBAA
Álgebra de Álgebra de BooleBoole
zCada 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úmero total de linhas é igual a 2n, 
onde n é o número de variáveis.
Álgebra de Álgebra de BooleBoole
zFunçã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 Álgebra de BooleBoole
zOR de duas variáveis:
F(A,B) = A+B
111111
110011
111100
000000
FFBBA A 
AA
BB
FF
Símbolo lógicoSímbolo lógico Tabela verdadeTabela verdade
Álgebra de Álgebra de BooleBoole
OR de duas variáveis: (cont.)
F(A,B) = A+B
111111
110011
111100
000000
FFBBA A 
Circuito elétrico equivalenteCircuito elétrico equivalente
AA
BB
II
VV ++
__
00
00
11
11
Álgebra de Álgebra de BooleBoole
zOR de três variáveis:
F(A,B,C) = A+B+C
AA
BB
CC
FF
11111111
11001111
11110011
11000011
11111100
11001100
11110000
00000000
FFCCBBAA
Álgebra de Álgebra de BooleBoole
zFunção NOT
Definição: F(A) = A
F(A) = 0 se A = 1
F(A) = 1 se A = 0
0011
1100
FFAA
AA A
A
Álgebra de Álgebra de BooleBoole
zz Outras funções lógicas importantes:Outras funções lógicas importantes:
zz Função NANDFunção NAND
Definição:Definição:
F(A,B,C,...,N) = A.B.C....NF(A,B,C,...,N) = A.B.C....N
F(A,B,C,...,N) = 0 se e somente seF(A,B,C,...,N) = 0 se e somente se
A=B=C=...=N=1A=B=C=...=N=1
Álgebra de Álgebra de BooleBoole
zzNAND de duas variáveisNAND de duas variáveis:
F(A,B) = A.B
001111
110011
111100
110000
FFBBA A 
AA
BB
FF
Símbolo lógicoSímbolo lógico Tabela verdadeTabela verdade
Álgebra de Álgebra de BooleBoole
zz Função NORFunção NOR
Definição:Definição:
F(A,B,C,...,N) = A+B+C+...+NF(A,B,C,...,N) = A+B+C+...+N
F(A,B,C,...,N) = 1 se e somente seF(A,B,C,...,N) = 1 se e somente se
A=B=C=...=N=0A=B=C=...=N=0
Álgebra de Álgebra de BooleBoole
zNOR de duas variáveis:
F(A,B) = A+B
001111
000011
001100
110000
FFBBA A 
AA
BB
FF
Símbolo lógicoSímbolo lógico Tabela verdadeTabela verdade
Álgebra de Álgebra de BooleBoole
zz Função OUFunção OU--EXCLUSIVO (XOR) EXCLUSIVO (XOR) 
F(A,B) = A + BF(A,B) = A + B
Por inspeção na tabela verdade:Por inspeção na tabela verdade:
F=1F=1 se A=0 e B=1 ou se A=1 e B=0se A=0 e B=1 ou se A=1 e B=0
F(A,B) = A.B F(A,B) = A.B ++ A.B A.B 
001111
110011
111100
000000
FFBBA A 
FFAA
BB
Álgebra de Álgebra de BooleBoole
zz Relações da álgebraRelações da álgebra booleanabooleana::
zz Postulados:Postulados:
1a. A = 1 (se A=0)1a. A = 1 (se A=0) 1b. A = 0 (se A=1)1b. A = 0 (se A=1)
2a. 0.0 = 02a. 0.0 = 0 2b. 0+0 = 02b. 0+0 = 0
3a. 1.1 = 13a. 1.1 = 1 3b. 1+1 = 13b. 1+1 = 1
4a. 1.0 = 04a. 1.0 = 0 4b. 1+0 = 14b. 1+0 = 1
5a. 1 = 05a. 1 = 0 5b. 0 = 15b. 0 = 1
Álgebra de Álgebra de BooleBoole
zz Relações da álgebraRelações da álgebra booleanabooleana (cont.):(cont.):
zz Teoremas:Teoremas:
6a. A.0 = 06a. A.0 = 0 6b. A+0 = A6b. A+0 = A
7a. A.1 = A7a. A.1 = A 7b. A+1 = 17b. A+1 = 1
8a. A.A = A8a. A.A = A 8b. A+A = A8b. A+A = A
9a. A.A = 09a. A.A = 0 9b. A+A = 19b. A+A = 1
10a. A = A10a. A = A 10b. A = A10b. A = A
Álgebra de Álgebra de BooleBoole
zz Propriedades algébricas:Propriedades algébricas:
Comutativa:Comutativa:
11a. AB = BA11a. AB = BA 11b. A+B = B+A11b. A+B = B+A
Associativa:Associativa:
12a. A(BC) = AB(C)12a. A(BC) = AB(C)
12b. A+(B+C) = (A+B)+C12b. A+(B+C) = (A+B)+C
Distributiva:Distributiva:
13a. A(B+C) = AB + AC13a. A(B+C) = AB + AC
13b. A + BC = (A+B) (A+C)13b. A + BC = (A+B) (A+C)
Álgebra de Álgebra de BooleBoole
zz Teorema da absorção:Teorema da absorção:
14a. A(A+B) = A 14a. A(A+B) = A 14b. A+AB = A14b. A+AB = A
15a. A(A+B) = AB15a. A(A+B) = AB 15b. A+AB = A+B15b. A+AB = A+B
Álgebra de Álgebra de BooleBoole
zz Teoremas de De Morgan:Teoremas de De Morgan:
16a. A.B.C...N = A + B + C +...+N16a. A.B.C...N = A + B + C +...+N
16b. A+B+C+...+N = A . B . C ... N16b. A+B+C+...+N = A . B . C ... N
Álgebra de Álgebra de BooleBoole
zz ConsequênciasConsequências diretas das leis De Morgan:diretas das leis De Morgan:
1.1. A.B = A + BA.B = A + B
AA
BB
FF AA FF
BB
Álgebra de Álgebra de BooleBoole
zz ConsequênciasConsequências diretas das leis De Morgan:diretas das leis De Morgan:
1. 1. Prova pela tabela verdadeProva pela tabela verdade::
F1(A,B) = A.BF1(A,B) = A.B
F2(A,B) = A + BF2(A,B) = A + BA.B = A + BA.B = A + B
00
11
11
11
F2F2
001111
110011
111100
110000
F1F1BBA A 
Álgebra de Álgebra de BooleBoole
zz ConsequênciasConsequências diretas das leis De Morgan:diretas das leis De Morgan:
2.2. A+B = A . BA+B = A . B
AA
BB
FFAA
BB
FF
Álgebra de Álgebra de BooleBoole
zz ConsequênciasConsequências diretas das leis De Morgan:diretas das leis De Morgan:
3.3. A.B = A+B A.B = A+B A.B = A + BA.B = A + B
A.B = A + BA.B = A + B
AA
BB
FFAA
BB
FF
Álgebra de Álgebra de BooleBoole
zz ConsequênciasConsequências diretas das leis De Morgan:diretas das leis De Morgan:
4.4. A+B = A.B A+B = A.B A+B = A . BA+B = A . B
A+B = A . BA+B = A . B
AA
BB
FFAA
BB
FF
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios:
1.1. Mostrar que A + BC = (A+B)(A+C) Mostrar que A + BC = (A+B)(A+C) 13b13b
(A+B)(A+C) = AA+AC+AB+BC =(A+B)(A+C) = AA+AC+AB+BC =
= A+AC+AB+BC == A+AC+AB+BC =
= A(1+C+B)+BC = A(1+C+B)+BC 
= A + BC= A + BC
11
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
2.2. Mostrar que A + AB = A + B Mostrar que A + AB = A + B 15b15b
14b14b A+AB = A(1+B) = AA+AB = A(1+B) = A
A + AB = A+AB + AB = A+(A+A)B = A + AB = A+AB + AB = A+(A+A)B = 
= A + B= A + B
AA
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
3.3. Mostrar que A + B = A + B Mostrar que A + B = A + B 
A + B = AB + AB = AB . AB =A + B = AB + AB = AB . AB =
= (A+B)(A+B) = AA+AB+AB+BB= (A+B)(A+B) = AA+AB+AB+BB
= AB + AB= AB + AB
MM MM
MM
00 00
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
3.3. Mostrar que A + B = A + B (cont.) Mostrar que A + B = A + B (cont.) 
X + B = XB + XBX + B = XB + XB
Fazendo X=A, temos:Fazendo X=A, temos:
A + B = AB + AB = AB + AB = A + BA + B = AB + AB = AB + AB = A + B
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
4.4. Mostrar que AB + AC + BC = AB + ACMostrar que AB + AC + BC = AB + AC
AB+AC+BC = AB+AC+BC(A+A) =AB+AC+BC = AB+AC+BC(A+A) =
= AB + AC + ABC + ABC == AB + AC + ABC + ABC =
= AB(1+C)+AC(1+B) = AB + AC= AB(1+C)+AC(1+B) = AB + AC
11
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
5.5. Simplifique a expressão lógica de F:Simplifique a expressão lógica de F:
F(x,y,z) =F(x,y,z) = xyzxyz ++ xyzxyz ++ xyzxyz ++xyzxyz
== xyzxyz++xyzxyz++xyxy(z+z) =(z+z) = xyxy++xyzxyz++xyzxyz ==
= y(x+= y(x+xzxz)+)+xyzxyz = y(x+z)+= y(x+z)+xyzxyz ==
15b15b
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
5.5. (cont.)(cont.)
F =F = xyxy ++yzyz ++ xyzxyz == yzyz + x(y++ x(y+yzyz) =) =
== yzyz + x(y+z)+ x(y+z)
F(x,y,z) =F(x,y,z) = xyxy ++ xzxz ++ yzyz
15b15b
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
6.6. Determine a expressão lógica para a Determine a expressão lógica para a 
saída F no circuito abaixo:saída F no circuito abaixo:
CC
AA
BB FF
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
6.6. (cont.)(cont.)
F1 = AB , F2 = B + C = BC + BCF1 = AB , F2 = B + C = BC + BC
F = F1+F2 = AB + BC + BCF = F1+F2 = AB + BC + BC
FF
CC
AA
BB
F1F1
F2F2
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
7.7. Dado o circuito abaixo, obtenha a Dado o circuito abaixo, obtenha a 
expressão lógica mais simples que expressão lógica mais simples que 
você puder para a saída F:você puder para a saída F:
AA
BB
FF
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
7.7. (cont.)(cont.)
F1 = A + B = AB + AB , F2 = BF1 = A + B = AB + AB , F2 = B
F = F1+F2 = AB+AB+B = B(1+A)+AB =F = F1+F2 = AB+AB+B = B(1+A)+AB =
= B+AB = B+A = B.A = AB= B+AB = B+A = B.A = AB
FFA
A
BB
F1F1
F2F2
11
MM
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
7.7. (cont.)(cont.)
F(A,B) = AB
FFA
A
BB
AA
BB
FF
F(A,B) = AB
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
8.8. Desenhe o circuito correspondente a Desenhe o circuito correspondente a 
expressão abaixo:expressão abaixo:
F = ABC + BCF = ABC + BC
FF
AA
BB
CC
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
9.9. Simplifique a expressão de F do Simplifique a expressão de F do 
exemplo anterior:exemplo anterior:
F = ABC + BC = A+B+C + BC =F = ABC + BC = A+B+C + BC =
= A+B+C+B = A+1+C = 1= A+B+C+B = A+1+C = 1
11
MM
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
9.9. (cont.)(cont.)
AA
FF
BB
CC
“1”“1”
“0”(0volts)“0”(0volts)
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
10. No circuito abaixo, obtenha a expressão10. No circuito abaixo, obtenha a expressão
lógica mais simples que você puderlógica mais simples que você puder
para a saída F:para a saída F:
AA
BB
FF
CC
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
10.10.
F1 = A+B = A.BF1 = A+B = A.B
F2 = F1B C = ABBC = ABC = A+B+CF2 = F1B C = ABBC = ABC = A+B+C
F = F1F2 = F1+F2F = F1F2 = F1+F2
AA
BB
FF
CC
F1F1
F2F2
MM
MM
MM
Álgebra de Álgebra de BooleBoole
zz Exercícios:Exercícios: (cont.)(cont.)
10. (cont.)10. (cont.)
F1 = A+B = A.BF1 = A+B = A.B
F2 = F1B C = ABBC = ABC = A+B+CF2 = F1B C = ABBC = ABC = A+B+C
F = F1F2 = F1+F2F = F1F2 = F1+F2
F = F1+F2 = A+B + ABC = A+B+ABCF = F1+F2 = A+B + ABC = A+B+ABC
F = A+BC+B = A+B+C F = A+BC+B = A+B+C 
MM
MM
MM
Álgebra de Álgebra de BooleBoole
FF
AA
BB
CC
zz Exercícios:Exercícios: (cont.)(cont.)
10. (cont.)10. (cont.)
FFAABB
CC
CC
AA
BB
FF
CC
AA
BB
FF
	Introdução à Informática
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole
	Álgebra de Boole