Sistemas Digitais - Simplificação de expressão Booleana

Prévia do material em texto

Sistemas Digitais I
Introduc¸a˜o
Myle`ne Christine Queiroz de Farias
Departamento de Engenharia Ele´trica
Universidade de Bras´ılia (UnB)
Bras´ılia, DF 70910-900
mylene@unb.br
March 10, 2018
Aula 03: S´ıntese e Simplificac¸a˜o de Expresso˜es Boleanas
Suma´rio
Mintermos
Maxtermos
Minimizac¸a˜o
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 2 / 29
Suma´rio
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 3 / 29
Obtenc¸a˜o da expressa˜o alge´brica de uma func¸a˜o
Considere um alarme que soe
quando:
As luzes estejam E
A porta esteja aberta E
A chave na˜o esteja na
ignic¸a˜o
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 4 / 29
Obtenc¸a˜o da expressa˜o alge´brica de uma func¸a˜o
Pergunta
Como obter uma func¸a˜o m´ınima? O ideal seria termos um procedimento
padra˜o!
Termos
Literal: Varia´vel ou seu complemento (A,A,B,B)
Termo de produto: Se´rie de literais relacionados por AND (produto)
ex: A · B · C
Termo de soma: Se´rie de literais relacionados por OR (soma)
ex: A + B + C
Termo normal: Termo de produto ou soma no qual nenhuma varia´vel
esta´ sobrando ou aparece mais de uma vez.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 5 / 29
Obtenc¸a˜o da expressa˜o alge´brica de uma func¸a˜o
Pergunta
Como obter uma func¸a˜o m´ınima? O ideal seria termos um procedimento
padra˜o!
Termos
Literal: Varia´vel ou seu complemento (A,A,B,B)
Termo de produto: Se´rie de literais relacionados por AND (produto)
ex: A · B · C
Termo de soma: Se´rie de literais relacionados por OR (soma)
ex: A + B + C
Termo normal: Termo de produto ou soma no qual nenhuma varia´vel
esta´ sobrando ou aparece mais de uma vez.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 5 / 29
Sintese
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 6 / 29
S´ıntese
Considere uma
tabela-verdade qualquer
A func¸a˜o F pode ser
implementada tomando-se
um OU de todas as
combinac¸o˜es de sa´ıda que
resultem em 1
F = X · Y · Z + X · Y · Z + X · Y · Z + X · Y · Z + X · Y · Z
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 7 / 29
S´ıntese
Na˜o e´ necessariamente a forma mais simples de F
Forma mecaˆnica de extrair a func¸a˜o alge´brica da tabela-verdade
Definic¸o˜es:
Termos-produto E – ex: ABZ
Termos-soma OU – ex: X + A
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 8 / 29
Mintermo
Mintermo = Termo-produto em que todas as varia´veis aparecem uma vez
(invertidas ou na˜o)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 9 / 29
Mintermo
Para n varia´veis existira˜o 2n mintermos (Como nu´mero bina´rios, de 0
a 2n−1)
Quando codificados, numerados em ordem
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 10 / 29
Maxtermo
Maxtermo = Termo-soma em que todas as varia´veis aparecem uma vez
(invertidas ou na˜o)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 11 / 29
MaxtermoxMintermos
Mintermos e maxtermos com o mesmo ı´ndice sa˜o complementares
mj = Mj
Exemplo:
m3 = X · Y · Z = X + Y + Z = M3
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 12 / 29
Soma de Mintermos
OU de todos os mintermos
da tabela-verdade que a
sa´ıda seja 1
F = m0 + m2 + m5 + m7
F = X · Y · Z + X · Y · Z + X · Y · Z + X · Y · Z
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 13 / 29
Soma de Mintermos
Complementos de F
Soma dos mintermos
restantes
Neste caso:
F = m1 + m3 + m4 + m6
F = X · Y · Z + X · Y · Z + X · Y · Z + X · Y · Z
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 14 / 29
Produto de Maxtermos
O maxtermo e´ 1 exceto para seu pro´prio caso
Enta˜o, M1 somente e´ falso para 001
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 15 / 29
Produto de Maxtermos
E de todos os maxtermos da
tabela-verdade que a sa´ıda
seja 0
F = M1 · M3 · M4 · M6
F = (X + Y + Z ) · (X + Y + Z ) · (X + Y + Z ) · (X + Y + Z )
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 16 / 29
S´ıntese
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 17 / 29
Exemplo 1
P = A · B + A · B
P = A
⊕
B
OU Exclusivo
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 18 / 29
Exemplo 2
Considere que o alarme do carro soe quando as luzes estiverem acesas OU
o carro estiver engrenado E as chaves na˜o estiverem na ignic¸a˜o
P = A · B · C + A · B · C + A · B · C
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 19 / 29
Exemplo 2
soma de mintermos:
P = m2 + m4 + m6
P = A · B · C + A · B · C + A · B · C
produto de maxtermos:
P = M0 · M1 · M3 · M5 · M7
P = (A+B +C ) · (A+B +C ) · (A+B +C ) · (A+B +C ) · (A+B +C )
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 20 / 29
Mapeamento entre as formas canoˆnicas
Conversa˜o de mintermo para maxtermo: Usar maxtermos cujos
ı´ndices na˜o aparec¸am na expansa˜o de mintermos.
F (A,B,C ) =
∑
m(1, 3, 5, 6, 7) =
∏
M(0, 2, 4)
Conversa˜o de maxtermo para mintermo: Usar mintermos cujos ı´ndices
na˜o aparec¸am na expansa˜o de maxtermos.
F (A,B,C ) =
∏
M(0, 2, 4) =
∑
m(1, 3, 5, 6, 7)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 21 / 29
Mapeamento entre as formas canoˆnicas
Conversa˜o da expansa˜o de mintermos de F para a expansa˜o de
mintermos de F: usar mintermos cujos ı´ndices na˜o aparec¸am.
F (A,B,C ) =
∑
m(1, 3, 5, 6, 7)
F (A,B,C ) =
∑
m(0, 2, 4)
Conversa˜o da expansa˜o de maxtermos de F para a expansa˜o de
maxtermos de F : usar maxtermos cujos ı´ndices na˜o aparec¸am.
F (A,B,C ) =
∏
M(0, 2, 4)
F (A,B,C ) =
∏
M(1, 3, 5, 6, 7)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 22 / 29
Manipulac¸a˜o de func¸o˜es
Somente portas E, OU e INVERSORAS foram utilizadas ate´ aqui.
Por que na˜o continuar utilizando-as ?
Por que se preocupar com as portas NA˜O-E e NA˜O-OU ?
A a´rea que o circuito ocupara´ e´ uma varia´vel importante!
Deve-se fazer uso otimizado da a´rea.
A porta NA˜O-E usa menor a´rea que a porta E (e e´ mais ra´pida).
Usando DeMorgan, a porta NA˜O-E pode implementar portas E e OU.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 23 / 29
Manipulac¸a˜o de func¸o˜es
Somente portas E, OU e INVERSORAS foram utilizadas ate´ aqui.
Por que na˜o continuar utilizando-as ?
Por que se preocupar com as portas NA˜O-E e NA˜O-OU ?
A a´rea que o circuito ocupara´ e´ uma varia´vel importante!
Deve-se fazer uso otimizado da a´rea.
A porta NA˜O-E usa menor a´rea que a porta E (e e´ mais ra´pida).
Usando DeMorgan, a porta NA˜O-E pode implementar portas E e OU.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 23 / 29
Lo´gica de 2 n´ıveis:
Soma de produtos
Portas E formam
termos-produto (mintermos)
Porta OU para a soma
Produto das somas:
Portas OU formam
termos-soma (maxtermos)
Porta E para o produto
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 24 / 29
Lo´gica de 2 n´ıveis usando portas NA˜O–E
Porta OU com entradas invertidas: porta NA˜O-E
De Morgan’s: A + B = A · B
Lo´gica de 2 n´ıveis NA˜O-E/NA˜O-E:
Entradas invertidas na˜o sa˜o contadas;
Em um circuito padra˜o, a inversa˜o e´ executada uma vez e distribu´ıda
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 25 / 29
Lo´gica de 2 n´ıveis usando portas NA˜O–OU
Porta E com entradas invertidas: porta NA˜O-OU
De Morgan’s: A · B = A + B
Lo´gica de 2 n´ıveis NA˜O-OU/NA˜O-OU:
Entradas invertidas na˜o sa˜o contadas;
Em um circuito padra˜o, a inversa˜o e´ executada uma vez e distribu´ıda
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 26 / 29
Minimizac¸a˜o
Encontrar a realizac¸a˜o m´ınima da soma de produtos ou do produto
das somas
Simplificac¸a˜o alge´brica
Na˜o e´ um procedimento sistema´tico
Como saber que a implementac¸a˜o m´ınima foi alcanc¸ada?
Ferramentas de aux´ılio computacional:
Soluc¸es precisas requerem um tempo computacional longo (> 10
entradas)
Me´todos manuais ainda sa˜o relevantes
Entender as ferramentas automa´ticas (vantagens e desvantagens)Habilidade de checar os resultados
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 27 / 29
Minimizac¸a˜o
Encontrar a realizac¸a˜o m´ınima da soma de produtos ou do produto
das somas
Simplificac¸a˜o alge´brica
Na˜o e´ um procedimento sistema´tico
Como saber que a implementac¸a˜o m´ınima foi alcanc¸ada?
Ferramentas de aux´ılio computacional:
Soluc¸es precisas requerem um tempo computacional longo (> 10
entradas)
Me´todos manuais ainda sa˜o relevantes
Entender as ferramentas automa´ticas (vantagens e desvantagens)
Habilidade de checar os resultados
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 27 / 29
Minimizac¸a˜o
Encontrar a realizac¸a˜o m´ınima da soma de produtos ou do produto
das somas
Simplificac¸a˜o alge´brica
Na˜o e´ um procedimento sistema´tico
Como saber que a implementac¸a˜o m´ınima foi alcanc¸ada?
Ferramentas de aux´ılio computacional:
Soluc¸es precisas requerem um tempo computacional longo (> 10
entradas)
Me´todos manuais ainda sa˜o relevantes
Entender as ferramentas automa´ticas (vantagens e desvantagens)
Habilidade de checar os resultados
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 27 / 29
Minimizac¸a˜o
Encontrar a realizac¸a˜o m´ınima da soma de produtos ou do produto
das somas
Simplificac¸a˜o alge´brica
Na˜o e´ um procedimento sistema´tico
Como saber que a implementac¸a˜o m´ınima foi alcanc¸ada?
Ferramentas de aux´ılio computacional:
Soluc¸es precisas requerem um tempo computacional longo (> 10
entradas)
Me´todos manuais ainda sa˜o relevantes
Entender as ferramentas automa´ticas (vantagens e desvantagens)
Habilidade de checar os resultados
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 27 / 29