Circuitos Digitais - Álgebra Booleana - Parte b

Prévia do material em texto

1
Circuitos DigitaisCircuitos Digitais
Capítulo 2 – Álgebra de Boole
Parte b
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Minitermos
„ Para facilitar a escrita de funções lógicas, pode-se 
representar os termos produto padrão como 
minitermos (ou mintermos)minitermos (ou mintermos).
 
 
 
Linha A B C Minitermo 
0 0 0 0 CBAm ..0 = 
1 0 0 1 CBAm ..1 = 
2 0 1 0 CBAm2 =
Variáveis 
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
2 0 1 0 CBAm .2
3 0 1 1 BCAm .3 = 
4 1 0 0 CBAm .4 = 
5 1 0 1 CBAm .5 = 
6 1 1 0 CABm =6 
7 1 1 1 ABCm =7 
2
Minitermos
„ Note que o minitermo mi assume o valor “1” na 
linha i da tabela, e o valor “0” para todas as outras 
linhaslinhas
 
 
 
Linha A B C m0 m1 m2 m3 m4 m5 m6 m7 
0 0 0 0 1 0 0 0 0 0 0 0 
1 0 0 1 0 1 0 0 0 0 0 0 
2 0 1 0 0 0 1 0 0 0 0 0
Variáveis 
Minitermos 
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
3 0 1 1 0 0 0 1 0 0 0 0 
4 1 0 0 0 0 0 0 1 0 0 0 
5 1 0 1 0 0 0 0 0 1 0 0 
6 1 1 0 0 0 0 0 0 0 1 0 
7 1 1 1 0 0 0 0 0 0 0 1 
 
Minitermos
„ Funções lógicas podem ser representadas como uma 
soma de minitermos. 
 
Variáveis 
Linha A B C f(A,B,C) 
0 0 0 0 1 
1 0 0 1 0 
2 0 1 0 0 
3 0 1 1 1 
4 1 0 0 0 
5 1 0 1 0 
6 1 1 0 1 
7 1 1 1 1 
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
7630),,( mmmmCBAf +++=
ABCCABBCACBACBAf +++=),,(
∑= )7,6,3,0(),,( mCBAf
3
Minitermos
„ A partir da representação soma padrão de 
produtos, a obtenção da representação na 
f d i i é i diforma soma de minitermos é imediata:
0000
ABCDDCBADBCADCBADCBAf +++=),,,(
0110 1010 1111Designação binária
(minitermos)
0 6 10 15Designação decimal
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
∏= )14,13,12,11,9,8,7,5,4,3,2,1(),,,( MDCBAf
∑= )15,10,6,0(),,,( mDCBAf
Maxitermos
„ Para facilitar a escrita de funções lógicas, pode-se 
representar termos soma padrão por maxitermos (ou 
maxtermos) quando se utilizar a forma produto padrãomaxtermos) quando se utilizar a forma produto padrão 
de somas 
 
 
Linha A B C Maxitermo 
0 0 0 0 )(0 CBAM ++= 
1 0 0 1 )(1 CBAM ++= 
2 0 1 0 )(2 CBAM ++= 
Variáveis 
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
3 0 1 1 )(3 CBAM ++= 
4 1 0 0 ).(4 CBAM ++=
5 1 0 1 )(5 CBAM ++= 
6 1 1 0 )(6 CBAM ++= 
7 1 1 1 )(7 CBAM ++= 
 
4
Maxitermos
„ Note que um Maxitermo Mi assume o valor “0” na 
linha i da tabela, e o valor “1” para todas as outras 
linhaslinhas
 
 
 
Linha A B C M0 M1 M2 M3 M4 M5 M6 M7
0 0 0 0 0 1 1 1 1 1 1 1 
1 0 0 1 1 0 1 1 1 1 1 1 
2 0 1 0 1 1 0 1 1 1 1 1 
Variáveis 
Maxitermos 
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
3 0 1 1 1 1 1 0 1 1 1 1 
4 1 0 0 1 1 1 1 0 1 1 1 
5 1 0 1 1 1 1 1 1 0 1 1 
6 1 1 0 1 1 1 1 1 1 0 1 
7 1 1 1 1 1 1 1 1 1 1 0 
 
Maxitermos
„ Funções lógicas podem ser representadas como um 
produto de maxitermos. 
 
Variáveis 
Linha A B C f(A,B,C) 
0 0 0 0 1 
1 0 0 1 0 
2 0 1 0 0 
3 0 1 1 1 
4 1 0 0 0 
5 1 0 1 0 
6 1 1 0 1 
7 1 1 1 1 
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
5421),,( MMMMCBAf =
))()()((),,( CBACBACBACBACBAf ++++++++=
∏= )5,4,2,1(),,( MCBAf
5
Maxitermos
„ A partir da representação produto padrão de 
somas, a obtenção do produto de maxitermos é 
i diimediata:
0000
))()()((),,,( DCBADCBADCBADCBADCBAf ++++++++++++=
0100 1011 1111Designação binária
(maxitermos)
0 4 11 15Designação decimal
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
∑= )14,13,12,10,9,8,7,6,5,3,2,1(),,,( mDCBAf
∏= )15,11,4,0(),,,( MDCBAf
Maxitermos
„ A partir da representação soma de minitermos, 
a obtenção do produto de maxitermos é 
i diimediata:
0000
ABCDDCBADBCADCBADCBAf +++=),,,(
0110 1010 1111Designação binária
(minitermos)
0 6 10 15Designação decimal
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
0 6 10 15g ç
∏= )14,13,12,11,9,8,7,5,4,3,2,1(),,,( MDCBAf
∑= )15,10,6,0(),,,( mDCBAf
6
Mapa de Karnaugh
„ Como numa tabela verdade, um mapa de 
Karnaugh (ou k-map) possibilita a 
ã d f õ ló irepresentação de funções lógicas.
„ Um mapa de Karnaugh para uma função 
booleana de n variáveis apresenta 2n posições 
organizadas em 2 ou 3 dimensões, indexada 
pelos valores das variáveis.
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
pelos valores das variáveis.
„ A organização dos índices é feita segundo o 
código de Gray, o que faz com que índices 
adjacentes difiram em apenas uma variável 
Mapa de Karnaugh de 2 variáveis
„ Equivalência entre os compartimentos de 
mapa de Karnaugh e as linhas da tabela 
d dverdade:
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
7
Mapa de Karnaugh de 2 variáveis
BABABAf ⊕=≡= )(),(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Mapa de Karnaugh de 2 variáveis
BABAf ⊕=),(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
8
Mapa de Karnaugh de 2 variáveis
BABAf ⊕=),(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Mapa de Karnaugh de 3 variáveis
„ Um minitermo preenche com “1” a menor 
área possível de um mapa de Karnaugh:
7),,( mABCCBAf ==
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
9
Mapa de Karnaugh de 3 variáveis
„ Um maxitermo preenche com “1” a maior área 
possível (que não seja a totalidade) de um 
mapa de Karnaugh:
0),,( MCBACBAf =++=
mapa de Karnaugh:
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Mapa de Karnaugh de 3 variáveis
)( MCBACBAf
„ Operações lógicas podem ser feitas entre 
mapas de Karnaugh:
0),,( MCBACBAf =++=
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
10
Teoremas de DeMorgan no k-mapa
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Mapa de Karnaugh de 4 variáveis
„ A versão da direita enfatiza as regiões nas 
quais as variáveis assumem o valor “1”
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
11
Mapa de Karnaugh de 4 variáveis
„ Podemos ser redundantes:
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Mapa de Karnaugh de 4 variáveis
„ Com a variável mais significativa numerando 
as linhas:
Variável mais significativa
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
12
Mapa de Karnaugh – adjacências
„ As adjacências horizontais e as adjacências 
verticais correspondem a termos padrão com 
l ã iá lalteração em apenas uma variável
DCBAm = DCABm =
DCBAm =4
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
DCBAm =5 DCABm =13
BCDAm =7
DCBAm =1
Mapa de Karnaugh – adjacências
„ As adjacências também ocorrem nas 
extremidades do mapa de Karnaugh:
DCBAm =8
DCBAm = DCBAm =
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
DCBAm =9
DCABm =13
CDBAm =11
DCBAm =1
13
Mapa de Karnaugh – adjacências
„ As adjacências também ocorrem nas 
extremidades do mapa de Karnaugh:
DBCAm =6
DCABm =DCBAm =
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
DCABm =12
DCBAm =5
DCBAm =0
DCBAm =4
Pares de minitermos adjacentes
„ Por Álgebra de Boole:
∑ )1298()( DCBAf
DCABDCBADCBADCBAf ++=),,,(
DCABDDCBADCBAf ++= )(),,,(
DCABCBADCBAf +=),,,(
∑= )12,9,8(),,,( mDCBAf
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
)(),,,( DBBCADCBAf +=
)(),,,( DBCADCBAf+=
DCACBADCBAf +=),,,(
14
Pares de minitermos adjacentes
„ Por álgebra de boole (outra versão) :
∑ )1298()( DCBAf
DCABDCBADCBADCBAf ++=),,,(
∑= )12,9,8(),,,( mDCBAf
DCABDCBADCBADCBADCBAf +++=),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
)()(),,,( BBDCADDCBADCBAf +++=
DCACBADCBAf +=),,,(
Pares de minitermos adjacentes
„ Um par de minitermos adjacentes 
(horizontalmente ou verticalmente) no mapa 
d K h d dde Karnaugh pode ser representado por um 
termo produto contendo um literal a menos 
que um minitermo.
DCACBADCBAf +=),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
DCACBADCBAf +),,,(
15
Pares de minitermos adjacentes
„ Equivalência de um agrupamento de par de 
minitermos com a simplificação por álgebra de 
B lBoole
)(),,,( BBDCADCBAf +=
DCABDCBADCBAf +=),,,(
DCADCBAf =),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Pares de minitermos adjacentes
„ Equivalência de um agrupamento de par de 
minitermos com a simplificação por álgebra de 
B lBoole
)(),,,( DDCBADCBAf +=
CBADCBAf =),,,(
DCBADCBADCBAf +=),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
16
Pares de minitermos adjacentes
„ Qualquer par de minitermos de n variáveis que 
sejam adjacentes (horizontalmente ou 
verticalmente) no mapa de Karnaugh pode ser 
combinado em um único termo produto 
contendo (n 1) literais
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
contendo (n-1) literais
2k minitermos adjacentes
„ Qualquer conjunto de 2k minitermos de n 
variáveis que sejam adjacentes no mapa de 
Karnaugh pode ser combinado em um único 
termo produto contendo (n-k) literais
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
17
2k minitermos adjacentes
„ Simplificação por álgebra de boole
∑ )10820()( DCBAf
DCBADCBADCBADCBADCBAf +++=),,,(
∑= )10,8,2,0(),,,( mDCBAf
)()(),,,( CCDBACCDBADCBAf +++=
DBADBADCBAf +=),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
)(),,,( AADBDCBAf +=
DBDCBAf =),,,(
2k minitermos adjacentes
„ Simplificação no mapa de Karnaugh
∑ )10820()( DCBAf ∑= )10,8,2,0(),,,( mDCBAf
DBDCBAf =),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
18
2k minitermos adjacentes
„ Simplificação por álgebra de boole
∑ )7531()( DCBAf
BCDADCBACDBADCBADCBAf +++=),,,(
∑= )7,5,3,1(),,,( mDCBAf
)()(),,,( CCBDACCDBADCBAf +++=
BDADBADCBAf +=),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
)(),,,( BBDADCBAf +=
DADCBAf =),,,(
2k minitermos adjacentes
„ Simplificação no mapa de Karnaugh
∑= )7,5,3,1(),,,( mDCBAf
DADCBAf =),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
19
2k minitermos adjacentes
„ Simplificação por álgebra de Boole
∑ )12840()( DCBAf
DCABDCBADCBADCBADCBAf +++=),,,(
∑= )12,8,4,0(),,,( mDCBAf
)()(),,,( BBDCABBDCADCBAf +++=
DCADCADCBAf +=),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
)(),,,( AADCDCBAf +=
DCDCBAf =),,,(
2k minitermos adjacentes
„ Simplificação no mapa de Karnaugh
∑= )12,8,4,0(),,,( mDCBAf
DCDCBAf =),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
20
Simplificação de funções
„ Definição
…Uma expressão soma de produtos de segunda 
ordem é MÍNIMA se não existe:
„ nenhuma expressão equivalente envolvendo menos 
produtos;
„ Nenhuma expressão equivalente envolvendo o mesmo 
ú d d t ú d lit i
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
número de produtos mas um número menor de literais
Simplificação de funções
„ Uma expressão soma de produtos de segunda 
ordem corresponde a um circuito lógico de 
d i í idois níveis:
…O primeiro nível com portas AND
…O segundo nível com uma porta OR
DCACBADCBAf +=),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
21
Simplificação de funções
„ Regra na utilização de mapas de Karnaugh
…Começar agrupando termos para os quais só existe 
ibilid d d bi ãuma possibilidade de combinação
„ No exemplo abaixo o agrupamento pontilhado 
não faz parte da expressão mínima!
∑= )14,12,11,10,2,0(),,,( mDCBAf
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
CBADABDBADCBAf ++=),,,(
Simplificação de funções
„ Os minitermos que constituem o agrupamento 
pontilhado (m10 e m14) já fazem parte de 
i iagrupamentos essenciais
„ Portanto o agrupamento pontilhado não deve 
ser considerado.
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
CBADABDBADCBAf ++=),,,(
22
Simplificação de funções
„ O circuito lógico de dois níveis associado à 
expressão mínima de segunda ordem, está 
d b iapresentado abaixo:
CBADABDBADCBAf ++=),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Simplificação de funções
„ Não devem ser considerados agrupamentos em 
que todos os seus minitermos já façam parte de 
i iagrupamentos essenciais:
∑= )15,13,12,11,7,6,5,1(),,,( mDCBAf
ACDCABBCADCADCBAf +++=),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
23
Simplificação de funções
„ Não devem ser considerados agrupamentos em 
que todos os seus minitermos já façam parte de 
i iagrupamentos essenciais:
∑= )15,14,13,12,7,6,5,1(),,,( mDCBAf
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
ABDADCBAf +=),,,(
Simplificação x Circuito
„ A expressão soma de produtos de segunda 
ordem mínima não está necessariamente 
i d i iassociada a um circuito que apresente o menor 
número de portas lógicas
„ Exemplo ∑= )14,13,10,9,6,5(),,,( mDCBAf
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
DCBDBCDCADACDCBAf +++=),,,(
24
Simplificação x Circuito
„ Circuito mínimo de segunda ordem na forma 
soma-de-produtos
É…É o circuito associado à expressão soma-de-
produtos mínima de segunda ordem
DCBDBCDCADACDCBAf +++=),,,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Simplificação x Circuito
∑= )14,13,10,9,6,5(),,,( mDCBAf
DCBDBCDCADACDCBAf +++=),,,(
„ Outras alternativas (obtidas por simplificação 
booleana a partir da expressão acima) que não 
atendem à definição da expressão soma-de-
produtos mínima de segunda ordem:
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
DCBADCBADCBAf )()(),,,( +++=
))((),,,( DCDCBADCBAf ++=
25
Simplificação x Circuito
„ A expressão obtida pela simplificação 
booleana não está nem no formato soma-de-
d !produtos!
„ O circuito lógico equivalente tem menos portas 
lógicas que o circuito mínimo, mas apresenta 
três níveis de portas lógicas
DCBADCBADCBAf )()(),,,( +++=
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
três níveis de portas lógicas
Simplificação x Circuito
„ Outra expressão obtida:
))((),,,( DCDCBADCBAf ++=
„ O circuito lógico equivalente tem menos portas 
lógicas que o circuito mínimo e apresenta dois 
níveis de portas lógicas. No entanto, como o 1º 
nível apresenta portas OR e XOR, os retardos 
na saída serão diferenciados
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
na saída serão diferenciados.
26
Simplificação x Circuito
„ A adoção de uma das soluções alternativas 
pode ser feita quando
…atrasos no sinal na saída maiores do que aqueles 
existentes no circuito mínimo de segunda ordem 
na forma soma-de-produtos são tolerados
…A exigência de um circuito contendo o menor 
número possível de portas for preponderante sobre 
i ê id i i d
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
a exigência de um circuito com tempo de resposta 
mínimo
Decomposição de K-mapas
„ A decomposição de mapas de Karnaugh exige 
uma visualização geométrica de sub-mapas e 
õ b l á i bas operações booleanas necessárias sobre os 
mesmos, de tal forma a produzir uma função 
lógica específica.
„ Essa técnica pode eventualmente ser utilizada 
para se tentar obter circuitos com menos portas
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
para se tentar obter circuitos com menos portas 
do que os circuitos mínimos de segunda ordem 
na forma soma-de-produtos
27
Decomposição de K-mapas
„ O último resultado do exemplo anterior 
poderia ser obtido por essa técnica:
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
),,,( DCBAf = )( BA+ • )( DCDC +
Mapa de Karnaugh de 5 variáveis
∑= )31,30,26,25,23,22,18,17,15,7(),,,,( mEDCBAf
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
28
Mapa de Karnaugh de 5 variáveis
∑= )31,30,26,25,23,22,18,17,15,7(),,,,( mEDCBAf
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
CDEEADEDCADCBAf ++=),,,(
Mapa de Karnaugh de 6 variáveis
CD CD
B = 0 B = 1
∑= )61,58,53,50,45,42,37,34,26,24,18,10,8,2(),,,,,( mFEDCBAf
EF 01 11 1000
00
01
11
10
EF 01 11 1000
00
01
11
10
CD CD
A = 0
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
CD
EF 01 11 1000
00
01
11
10
CD
EF 01 11 1000
00
01
11
10
A = 1
29
Mapa de Karnaugh de 6 variáveis
CD CD
B = 0 B = 1
∑= )61,58,53,50,45,42,37,34,26,24,18,10,8,2(),,,,,( mFEDCBAf
1
1 1
EF 01 11 1000
00
01
11
10
1
1 1
EF 01 11 1000
00
01
11
10
CD CD
A = 0
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
1 1
1 1
CD
EF 01 11 1000
00
01
11
10
1 1
1 1
CD
EF 01 11 1000
00
01
11
10
A = 1
Mapa de Karnaugh de 6 variáveis
CD CD
B = 0 B = 1
FDCAFEADFEDFEDCBAf ++=),,,,,(
1
1 1
EF 01 11 1000
00
01
11
10
1
1 1
EF 01 11 1000
00
01
11
10
CD CD
A = 0
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
1 1
1 1
CD
EF 01 11 1000
00
01
11
10
1 1
1 1
CD
EF 01 11 1000
00
01
11
10
A = 1