Introdução à Informática_TSC-CEDERJ_08

Prévia do material em texto

Introdução à InformáticaIntrodução à Informática
Funções LógicasFunções Lógicas
Ageu Pacheco e Alexandre Ageu Pacheco e Alexandre MeslinMeslin
Funções LógicasFunções Lógicas
zzObjetivoObjetivo dada AulaAula::
zz Estudar os principais métodos Estudar os principais métodos 
empregados na simplificação/minimização empregados na simplificação/minimização 
de funções lógicas (de funções lógicas (booleanasbooleanas).).
Funções LógicasFunções Lógicas
zzConceito de Conceito de mintermosmintermos e e maxtermosmaxtermos::
Considere a tabela verdade a seguir Considere a tabela verdade a seguir 
que expressa a função que expressa a função votadorvotador
majoritário para 3 votantes:majoritário para 3 votantes:
Funções LógicasFunções Lógicas
11111111
11001111
11110011
00000011
11111100
00001100
00110000
00000000
FFCCBBAA Por inspeção na tabela Por inspeção na tabela 
podemos escrever:podemos escrever:
F = ABC+ABC+ABC+ABCF = ABC+ABC+ABC+ABC
Funções LógicasFunções Lógicas
F(A,B,C) = ABC + ABC + ABC + ABCF(A,B,C) = ABC + ABC + ABC + ABC
zzRepare que a expressão de F é Repare que a expressão de F é 
constituída por uma soma de produtos constituída por uma soma de produtos 
lógicos, cada um composto pelas 3 lógicos, cada um composto pelas 3 
variáveis de que F depende. variáveis de que F depende. 
zzCada um destes produtos “completos” Cada um destes produtos “completos” 
é denominado é denominado mintermomintermo..
Funções LógicasFunções Lógicas
zzA descrição de uma função por meio A descrição de uma função por meio 
de soma de produtos (de soma de produtos (mintermosmintermos) ) 
representa a função implementada representa a função implementada 
nos pontos em que ela é “1”nos pontos em que ela é “1”
zzNotação compacta:Notação compacta:
F = ABC + ABC + ABC + ABCF = ABC + ABC + ABC + ABC
F = mF = m33 + m+ m55 + m+ m66 + m+ m77
F = F = ∑∑(3,5,6,7) (3,5,6,7) (nota(notaçãção compacta)o compacta)
Funções LógicasFunções Lógicas
11111111
11001111
11110011
00000011
11111100
00001100
00110000
00000000
FFCCBBAA Função Função votadorvotador majoritário:majoritário:
F = ABC+ABC+ABC+ABCF = ABC+ABC+ABC+ABC
F = mF = m33+m+m55+m+m66+m+m77
F = F = ∑∑(3,5,6,7)(3,5,6,7)
Funções Lógicas Funções Lógicas 
zz Invertendo F e aplicando a Lei deInvertendo F e aplicando a Lei de
Morgan à equação resultante temos:Morgan à equação resultante temos:
F = ABC + ABC + ABC + ABC =F = ABC + ABC + ABC + ABC =
F = (ABC).(ABC).(ABC).(ABC) =F = (ABC).(ABC).(ABC).(ABC) =
F = (A+B+C)(A+B+C)(A+B+C)(A+B+C)F = (A+B+C)(A+B+C)(A+B+C)(A+B+C)
MM
MMMM
MM
Funções LógicasFunções Lógicas
F = (A+B+C)(A+B+C)(A+B+C)(A+B+C)F = (A+B+C)(A+B+C)(A+B+C)(A+B+C)
zz F achaF acha--se representada por um produto se representada por um produto 
de somas onde cada soma contém as de somas onde cada soma contém as 
3 variáveis de que F depende. 3 variáveis de que F depende. 
zzCada um destas somas “completas” é Cada um destas somas “completas” é 
denominada denominada maxtermomaxtermo..
Funções LógicasFunções Lógicas
zzA descrição de uma função por meio de A descrição de uma função por meio de 
produtos de somas (produtos de somas (maxtermosmaxtermos) ) 
representa a função implementada nos representa a função implementada nos 
pontos em que ela é “0”pontos em que ela é “0”
zzNotação compacta:Notação compacta:
F = (A+B+C)(A+B+C)(A+B+C)(A+B+C)F = (A+B+C)(A+B+C)(A+B+C)(A+B+C)
F = MF = M33 .. MM55 .. MM66 .. MM77
F = F = ¶¶ (3,5,6,7) (3,5,6,7) (nota(notaçãção compacta)o compacta)
Funções LógicasFunções Lógicas
0011111111
0011001111
0011110011
1100000011
0011111100
1100001100
1100110000
1100000000
FFFFCCBBA A F = (A+B+C).(A+B+C).F = (A+B+C).(A+B+C).
.(A+B+C).(A+B+C).(A+B+C).(A+B+C)
F = MF = M33.M.M55.M.M66.M.M77
F = F = ¶¶ (3,5,6,7)(3,5,6,7)
00
11
22
33
44
55
66
77
Funções LógicasFunções Lógicas
zzPara achar F representada por Para achar F representada por 
maxtermosmaxtermos aplicamos Morgan à aplicamos Morgan à 
expressão de F descrita por expressão de F descrita por mintermosmintermos::
F = ABC+ABC+ABC+ABCF = ABC+ABC+ABC+ABC
F = mF = m00+m+m11+m+m22+m+m44
Funções LógicasFunções Lógicas
F =ABC+ABC+ABC+ABCF =ABC+ABC+ABC+ABC
F = mF = m00+m+m11+m+m22+m+m44
Pela tabela já dá para Pela tabela já dá para 
perceber que F por perceber que F por 
maxtermosmaxtermos será:será:
F = MF = M00.M.M11.M.M22.M.M440011111111
0011001111
0011110011
1100000011
0011111100
1100001100
1100110000
1100000000
FFFFCCBBA A 
Funções LógicasFunções Lógicas
zzAplicando Morgan a F:Aplicando Morgan a F:
F = ABC+ABC+ABC+ABC =F = ABC+ABC+ABC+ABC =
F = (ABC).(ABC).(ABC).(ABC) =F = (ABC).(ABC).(ABC).(ABC) =MM
MM
MM
Funções LógicasFunções Lógicas
zzAplicando Morgan a F (cont.):Aplicando Morgan a F (cont.):
F=(A+B+C)(A+B+C)(A+B+C)(A+B+C)F=(A+B+C)(A+B+C)(A+B+C)(A+B+C)
F=(A+B+C)(A+B+C)(A+B+C)(A+B+C)F=(A+B+C)(A+B+C)(A+B+C)(A+B+C)
F = MF = M00.M.M11.M.M22.M.M44 = ¶= ¶ (0,1,2,4)(0,1,2,4)
Funções LógicasFunções Lógicas
0011111111
0011001111
0011110011
1100000011
0011111100
1100001100
1100110000
1100000000
FFFFCCBBA A F = mF = m33+m+m55+m+m66+m+m77
F = MF = M00.M.M11.M.M22.M.M44
F = mF = m00+m+m11+m+m22+m+m44
F = MF = M33.M.M55.M.M66.M.M77
00
11
22
33
44
55
66
77
Funções LógicasFunções Lógicas
MM77 = x + y + z= x + y + zmm77 = x y z= x y z
MM66 = x + y + z= x + y + zmm66 = x y z= x y z
MM55 = x + y + z= x + y + zmm55 = x y z= x y z
MM44 = x + y + z= x + y + zmm44 = x y z= x y z
MM33 = x + y + z= x + y + zmm33 = x y z = x y z 
MM22 = x + y + z= x + y + zmm22 = x y z = x y z 
MM11 = x + y + z= x + y + zmm11 = x y z= x y z
mm00 = x y z= x y z
11111177
00111166
11001155
00001144
11110033
00110022
11000011
MM00 = x + y + z= x + y + z00000000
MaxtermoMaxtermoMintermoMintermozzyyx x LinhaLinha
Funções LógicasFunções Lógicas
zz Exercícios: (Exercícios: (mintermosmintermos e e maxtermosmaxtermos))
1)Represente1)Represente F(A,B,C)=F(A,B,C)=∑∑1,3,5,71,3,5,7
por meio de produtos de por meio de produtos de maxtermosmaxtermos..
F(A,B,C) = ¶ 0,2,4,6 = MF(A,B,C) = ¶ 0,2,4,6 = M00.M.M22.M.M44.M.M66
F = (A+B+C)(A+B+C)(A+B+C)(A+B+C)F = (A+B+C)(A+B+C)(A+B+C)(A+B+C)
Funções LógicasFunções Lógicas
2)2) RepresenteRepresente aa funçãofunção
FF da tabela por meio da tabela por meio 
de soma de mintermosde soma de mintermos
ee produtosprodutos dede
maxtermosmaxtermos.
00111111
00001111
00110011
11000011
00111100
11001100
11110000
00000000
FFCCBBAA
.
Funções LógicasFunções Lógicas
2)
00111111
00001111
00110011
11000011
00111100
11001100
11110000
00000000
FFCCBBAA2) F = F = ∑∑1,2,4 = m1,2,4 = m11+m+m22+m+m44
F = F = ¶ 0,3,5,6,7¶ 0,3,5,6,7
F = MF = M00.M.M33.M.M55.M.M66.M.M77
Funções LógicasFunções Lógicas
2)2) F = mF = m11+m+m2 2 +m+m44
F = ABC + ABC + ABCF = ABC + ABC + ABC
F = MF = M00.M.M33.M.M55.M.M66.M.M77
F = (A+B+C).(A+B+C).(A+B+C).F = (A+B+C).(A+B+C).(A+B+C).
(A+B+C).(A+B+C)(A+B+C).(A+B+C)
Funções LógicasFunções Lógicas
zzSimplificação de expressões lógicas:Simplificação de expressões lógicas:
Métodos:Métodos:
Por manipulações algébricasPor manipulações algébricas
Por mapas de Por mapas de KarnaughKarnaugh
Pelo método de Pelo método de QuineQuine--McCluskey McCluskey 
Funções LógicasFunções Lógicas
zzManipulações algébricas (exemplos):Manipulações algébricas (exemplos):
1)1) Simplificar a funçãoSimplificar a função
F(A,B,C) = F(A,B,C) = ∑∑ 3,5,6,73,5,6,7
((votadorvotador majoritário de 3 votantes)majoritário de 3 votantes)
F = ABC+ABC+ABC+ABCF = ABC+ABC+ABC+ABC
Funções LógicasFunções Lógicas
1) (cont.)1) (cont.)
F = ABC+ABC+ABC+ABCF= ABC+ABC+ABC+ABC
F = ABC+ABC+AB(C+C)F = ABC+ABC+AB(C+C)
F = B(A+AC)+ABC = B(A+C)+ABCF = B(A+AC)+ABC = B(A+C)+ABC
11
Funções LógicasFunções Lógicas
1) (cont.)1) (cont.)
F = B(A+C)+ABCF = B(A+C)+ABC
F = AB+BC+ABC = AB+C(B+BA)F = AB+BC+ABC = AB+C(B+BA)
F = AB+C(B+A) F = AB+AC+BCF = AB+C(B+A) F = AB+AC+BC
Funções LógicasFunções Lógicas
2) F(A,B,C) = 2) F(A,B,C) = ∑∑ 3,73,7
F = ABC+ABC = BC(A+A) = BCF = ABC+ABC = BC(A+A) = BC
Funções LógicasFunções Lógicas
2) F(A,B,C) = 2) F(A,B,C) = ∑∑ 3,73,7
F = ABC+ABC = BC(A+A) = BCF = ABC+ABC = BC(A+A) = BC
3) F(A,B,C) = ABC+ABC+ABC+ABC3) F(A,B,C) = ABC+ABC+ABC+ABC
F = AB(C+C)+AB(C+C) = AB+ABF = AB(C+C)+AB(C+C) = AB+AB
F = A(B+B) F = AF = A(B+B) F = A
Funções LógicasFunções Lógicas
3) (cont.) 3) (cont.) 
F=ABC+ABC+ABC+ABCF=ABC+ABC+ABC+ABC
F = F = ∑∑ 4,5,6,74,5,6,7
((mintermosmintermos adjacentes)adjacentes)
11111111
11001111
11110011
11000011
00111100
00001100
00110000
00000000
FFCCBBAA
Funções LógicasFunções Lógicas
4) F(A,B,C) = ABC+ABC+ABC+ABC 4) F(A,B,C) = ABC+ABC+ABC+ABC 
F = AC(B+B)+AC(B+B) F = AC(B+B)+AC(B+B) 
F = AC+AC = C(A+A) = CF = AC+AC = C(A+A) = C
Funções LógicasFunções Lógicas
4) 4) 
F=ABC+ABC+ABC+ABCF=ABC+ABC+ABC+ABC
F = F = ∑∑ 0,2,4,60,2,4,6
((mintermosmintermos adjacentes)adjacentes)
00111111
11001111
00110011
11000011
00111100
11001100
00110000
11000000
FFCCBBAA
Funções LógicasFunções Lógicas
5) 5) 
0011111100
0000111100
0011001100
1100001100
0011110000
1100110000
1111000000
1100000000
FFDDCCBBA A 
0011111111
1100111111
0011001111
1100001111
0011110011
1100110011
1111000011
1100000011
FFDDCCBBA A 
Funções LógicasFunções Lógicas
5) F(A,B,C,D) = 5) F(A,B,C,D) = ∑∑ 0,1,2,4,8,9,10,12,140,1,2,4,8,9,10,12,14
F = ABCD+ABCD+ABCD+ABCD+F = ABCD+ABCD+ABCD+ABCD+
++ABCD+ABCD+ABCD+ABCD+ABCDABCD+ABCD+ABCD+ABCD+ABCD
(a simplificação será feita mais adiante por (a simplificação será feita mais adiante por 
meio do mapa de meio do mapa de KarnaughKarnaugh))
00 11 22 44
88 99 1010 1212 1414
Funções LógicasFunções Lógicas
zzMapas de Mapas de KarnaughKarnaugh (Maurice (Maurice KarnaughKarnaugh ~~1950)~~1950)
O mapa de O mapa de KarnaughKarnaugh é uma é uma 
representação gráfica espacial da representação gráfica espacial da 
tabela verdade onde cada quadrado tabela verdade onde cada quadrado 
representa um representa um mintermomintermo de tal maneira de tal maneira 
que quadrados adjacentes contêm que quadrados adjacentes contêm 
mintermosmintermos adjacentes.adjacentes.
Funções LógicasFunções Lógicas
001111
110011
111100
000000
FFBBA A 
zzExemplos de mapas:Exemplos de mapas:
1)1)
0011
1100
AA
BB 00
00
11
11
00
mm33mm22
mm11mm00
AA
BB 00
00
11
11
11
22
33
Funções LógicasFunções Lógicas
2) Mapa de 3 variáveis:Mapa de 3 variáveis:
mm66mm77mm55mm44
mm22mm33mm11mm00
BCBC
0000
00
11
AA 0101 1111 1010
AA
BB
CC
inversão na sequência
11111111
00001111
00110011
11000011
11111100
00001100
00110000
11000000
FFCCBBAA
m0m0
m1m1
m2m2
m3m3
m4m4
m5m5
m6m6
m7m7
Funções LógicasFunções Lógicas
00110011
00110011
BCBC
0000AA
BCBC
BCBC
BB
AA
CCCC
2) Mapa de 3 variáveis:Mapa de 3 variáveis:
11111111
00001111
00110011
11000011
11111100
00001100
00110000
11000000
FFCCBBAA
m0m0
m1m1
m2m2
m3m3
m4m4
m5m5
m6m6
m7m7
BB
00
11
0101 1111 1010
AA
CC
Funções LógicasFunções Lógicas
11111111
00001111
00110011
11000011
11111100
00001100
00110000
11000000
FFCCBBAA
m0m0
m1m1
m2m2
m3m3
m4m4
m5m5
m6m6
m7m7
2) cont:
Pela tabela temos:Pela tabela temos:
F(A,B,C) = F(A,B,C) = ∑∑ 0,3,4,7 0,3,4,7 
F = mF = m00+m+m33+m+m44+m+m77
Funções LógicasFunções Lógicas
2) cont:cont:
F = mF = m00+m+m33+m+m44+m+m77
F = ABC+ABC+ABC+ABCF = ABC+ABC+ABC+ABC
F = BC(A+A)+BC(A+A) = BC+BCF = BC(A+A)+BC(A+A) = BC+BC
11 11
Funções LógicasFunções Lógicas
1111111100
1100111100
0011001100
0000001100
1111110000
1100110000
1111000000
0000000000
FFDDCCBBA A 
0011111111
0000111111
0011001111
1100001111
0011110011
0000110011
1111000011
0000000011
FFDDCCBBA A 
3) Mapa de 4 variáveis:
Funções LógicasFunções Lógicas
3) F(A,B,C,D) = ∑ m1,m2,m3,m6,m7,m9,m12
mm1010mm1111mm99mm88
mm1414mm1515mm1313mm1212
mm66mm77mm55mm44
mm22mm33mm11mm00
0101
1111
1111 10100000
0000
0101
1010
ABAB
CDCD
00001100
00000011
11110000
11111100
0101
1111
1111 10100000
0000
0101
1010
ABAB
CDCD
FF
Funções LógicasFunções Lógicas
00001100
00000011
11110000
11111100
0101
1111
1111 10100000
0000
0101
1010
ABAB
CDCD
FF CC
AA
AABBCCDD
BBCCDD
ACAC
3) F(A,B,C,D) = ∑ m1,m2,m3,m6,m7,m9,m12
BB
DD
Funções LógicasFunções Lógicas
3) F(A,B,C,DD) = ∑ m1,m2,m3,m6,m7,m9,m12
F = ABCD + ABCD + ABCD + ABCD +
ABCD + ABCD + ABCD
F = AC + BCD +ABCD
Funções LógicasFunções Lógicas
zz Regras para simplificação com oRegras para simplificação com o
mapa de mapa de KarnaughKarnaugh::
1. Começar pelos quadrados isolados, isto1. Começar pelos quadrados isolados, isto
é, que não tenham adjacentes. Elesé, que não tenham adjacentes. Eles
representam representam mintermosmintermos que não podemque não podem
ser simplificados mas que fazem parteser simplificados mas que fazem parte
da função.da função.
Funções LógicasFunções Lógicas
zz Regras (cont.):Regras (cont.):
2. Procurar por quadrados que só tenham2. Procurar por quadrados que só tenham
uma possibilidade de combinação.uma possibilidade de combinação.
3.3. Daí em diante procurar visualizarDaí em diante procurar visualizar
combinações envolvendo o máximo decombinações envolvendo o máximo de
quadrados.quadrados.
Funções LógicasFunções Lógicas
zz Observação importante:Observação importante:
Combinações onde Combinações onde todostodos quadrados quadrados 
participantes já tenham sido utilizados emparticipantes já tenham sido utilizados em
combinações prévias, não geramcombinações prévias, não geram
simplificações adicionais. Na verdade taissimplificações adicionais. Na verdade tais
combinações geram termos redundantes.combinações geram termos redundantes.
Funções LógicasFunções Lógicas
zz “Sentidos” de mapas:“Sentidos” de mapas:
101011119988
1414151513131212
66775544
22331100
ABAB
CDCD
CDCD
ABAB
101014146622
111115157733
9913135511
8812124400
Funções LógicasFunções Lógicas
zzExercícios:Exercícios:
1. F(A,B,C) = ∑ 0,2,4,5,6
11
11 2
2
66
CC
001111
0011
BCBC
0000
00
11
AA 0101
AA
ABAB 00 11
44 55
00
1111 1010
BB
33
77
CC
Funções LógicasFunções Lógicas
1a. F(A,B,C) = ∑ 0,2,4,5,6
11
11111111
ABAB
0000
00
CC 0101
ABAB00 22 4466
11 3 77 55
CC
F = AB + CF = AB + C
000
300011
1111 1010
AA
CC
BB
Funções LógicasFunções Lógicas
00
2. F(A,B,C,D) = ∑ 3,4,5,7,9,13,14,15
001100
11111100
00111111
00110000
ABAB
CDCD
22331100
88
77 665544
101099 1111
14141313 15151212
AA
BB
CC
DD
ACDACD
ABCABC
ACDACD
ABCABC
Funções LógicasFunções Lógicas
3. F(A,B,C,D) = ∑ 0,2,5,7,8,10,13,15
11
00 110011
00111100
00111100
110000
ABAB
CDCD
223311
88
77 665544
101099 1111
14141313 15151212 BB
CC
DD
001 1
11
BDBD
BDBD
AA
Funções LógicasFunções Lógicas
4. F(A,B,C,D) = ∑ 0,2,3,4,6,9,10,11,12,14
11111100
1111
1111
111111
ABAB
CDCD
22331100
88
77 665544
101099 1111
14141212
AA
CC
DD
ABDABDBDBD
ADAD
BCBC
00
01500 130
0000
BB13 15
Funções LógicasFunções Lógicas
4. F(A,B,C,D) = ∑ 0,2,3,4,6,9,10,11,12,14
F = ABCD + ABCD + ABCD + ABCD +
ABCD + ABCD + ABCD + ABCD +
ABCD + ABCD
F = AD + BC + BD + ABD
5.F(A,B,C,D) =ABCD+ABCD+ABCD+ABCD+
+ACD+ACD+BCD
11001111
11000011
00000011
11001111
ABAB
CDCD
22331100
88
77 665544
101099 1111
14141313 15151212
AA
BB
CC
DD
ADAD
1 1
1
BDBD
BCBC
CDCD
1
Funções LógicasFunções Lógicas
Funções LógicasFunções Lógicas
5) F(A,B,C,D) = 5) F(A,B,C,D) = ∑∑ 0,1,2,4,8,9,10,12,140,1,2,4,8,9,10,12,14
F = ABCD+ABCD+ABCD+ABCD+F = ABCD+ABCD+ABCD+ABCD+
++ABCD+ABCD+ABCD+ABCD+ABCDABCD+ABCD+ABCD+ABCD+ABCD
(a simplificação será feita mais adiante por (a simplificação será feita mais adiante por 
meio do mapa de meio do mapa de KarnaughKarnaugh))
00 11 22 44
88 99 1010 1212 1414
Funções LógicasFunções Lógicas
5) F(A,B,C,D) = 5) F(A,B,C,D) = ∑∑ 0,1,2,4,8,9,10,12,140,1,2,4,8,9,10,12,14
F = ABCD+ABCD+ABCD+ABCD+F = ABCD+ABCD+ABCD+ABCD+
++ABCD+ABCD+ABCD+ABCD+ABCDABCD+ABCD+ABCD+ABCD+ABCD
F(A,B,C,D) = AD + BC + BD + CD
00 11 22 44
88 99 1010 1212 1414
Álgebra de Álgebra de BooleBoole
z F(A,B,C,D) = AD + BC + BD + CD
CC
AA
BB
FF
DD
ADAD
BDBD
BCBC
CDCD
	Introdução à Informática
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Funções Lógicas
	Álgebra de Boole