Circuitos Digitais - Álgebra Booleana - Parte a

Prévia do material em texto

4/26/2011
1
Circuitos Digitais
Capítulo 2 - Álgebra de Boole
Parte a
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Cálculo Verdade
„ Funções verdade
… Retorna dois valores, um dos quais é interpretado como 
verdadeiro e o outro como falsoverdadeiro, e o outro como falso.
… Valores
„ “T” ou “F”
„ “1” ou “0”
„ “on” ou “off”
… Uma função verdade f é definida como um mapeamento de 
n valores verdadeiro/falso em um único valor que pode
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
n valores verdadeiro/falso em um único valor, que pode 
ser verdadeiro ou falso
},{},{: TFTFf n →
4/26/2011
2
Tabela verdade
„ Representa uma função verdade. 
„ É necessário que ela apresente todas as combinações 
í i d l d iá i d t dpossíveis de valores das variáveis de entrada, e o 
valor produzido pela função para cada uma dessas 
combinações
„ Ex: BABAf ∧=),(
Norma ANSI
Símbolo (porta AND):
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Norma ANSI
Norma IEC
Tabela verdade
„ Operação lógica “OU” (OR):
Norma ANSI
Símbolo (porta OR):
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Norma IEC
4/26/2011
3
Tabela verdade
„ Operação lógica “OU-exclusivo” (Exclusive-
OR, ou XOR):
Norma ANSI
Símbolo (porta XOR):
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Norma IEC
Conectivos Binários
„ Um conectivo binário corresponde a uma 
atribuição única de valores “T” ou “F” para as 
li h d b l d d d dquatro linhas da tabela verdade de duas 
variáveis
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
4/26/2011
4
Conectivos binários
„ Uma tabela verdade para n variáveis apresenta 
2n linhas
n„ Existem 22n funções verdade para n variáveis
„ Ex: n=2
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Cálculo Verdade
„ Expressões podem ser verificadas equivalentes 
através da construção de suas respectivas tabelas 
verdadeverdade
)()( BABA ⊃≡∨
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
4/26/2011
5
Cálculo verdade
„ Expressões compostas também podem ser 
manipuladas através de suas funções verdade 
componentescomponentes
( ) ( )[ ]ABBAAB ⊃∧⊃≡≡ )(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Cálculo Verdade
„ A utilização correta dos parênteses é extremamente 
importante:
( ) ( )BABAA ⊃≡⊃∨ ( ) BBAA ≡⊃∨
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
( ) ( ) BAABAA ⊃∨≠⊃∨
4/26/2011
6
Cálculo Verdade
„ Os conectivos NAND (Not AND) e NOR (Not OR) 
podem ser expressos como no Teorema de DeMorgan
BABABA ∨≡∧≡↑ BABABA ∧≡∨≡↓
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Cálculo Verdade
„ Conjunto de conectivos funcionalmente 
completo
É…É qualquer subconjunto dos conectivos suficiente 
para a realização de todos os outros conectivos:
„ AND, OR e NOT
„ AND e NOT
„ OR e NOT
NAND
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
„ NAND
„ NOR
„ Etc...
4/26/2011
7
Cálculo Verdade
„ Os conectivos AND, OR e NOT formam um 
conjunto de conectivos funcionalmente completo: 
AAf ∧=0 BAf ∧=4 BAf ∨=8 Af =12
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
BAf ∧=2
BAf ∧=1
Af =3
Bf =5
( ) ( )BABAf ∧∨∧=6
BAf ∨=7
( ) ( )BABAf ∧∨∧=9
Bf =10
BAf ∨=11
BAf ∨=13
BAf ∧=14
AAf ∨=15
Cálculo Verdade
„ O conectivo NAND é funcionalmente completo:
XXXXX ↑≡∧≡
( ) ( )YYXXYXYXYXYX ↑↑↑≡↑≡∧≡∨≡∨
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
( ) ( )YXYXYXYX ↑↑↑≡↑≡∧
4/26/2011
8
Cálculo Verdade
„ O conectivo NOR é funcionalmente completo
XXXXX ↓≡∨≡
( ) ( )YYXXYXYXYXYX ↓↓↓≡↓≡∨≡∧≡∧
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
( ) ( )YXYXYXYX ↓↓↓≡↓≡∨
Teoria dos Conjuntos
„ Equivalências entre conectivos binários e 
operações da Teoria de Conjuntos
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
4/26/2011
9
Teoria dos Conjuntos
„ Os diagramas de Venn utilizados na Teoria dos 
Conjuntos são úteis na visualização geométrica das 
funções verdade Exemplo: conectivo ANDfunções verdade. Exemplo: conectivo AND.
BA∧
Cálculo Verdade:
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Teoria dos Conjuntos
„ Diagrama de Venn para o conectivo OR
BA∨
Cálculo Verdade:
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
4/26/2011
10
Teoria dos Conjuntos
„ Visualização geométrica do Postulado da Distributividade 
(apresentado adiante) da operação OR com relação à operação 
AND
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
( ) ( ) ( )CABACBA ∨∧∨≡∧∨
Álgebra de Boole
„ Álgebra Booleana ou Álgebra de Boole consiste em 
um conjunto K de elementos, juntamente com duas 
operações binárias {+} e { } e uma operação unáriaoperações binárias {+} e {.} e uma operação unária 
{’}, tais que atendam aos Postulados ou Axiomas
(pressuposições aceitas como verdadeiras) 
apresentados a seguir.
„ Os Postulados ou Axiomas estabelecidos em 1904 por 
Edward Huntington podem ser demonstrados como
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Edward Huntington podem ser demonstrados como 
sendo consistentes (nenhum dos axiomas contradiz 
outro) e independentes (nenhum dos axiomas pode 
ser demonstrado a partir de outro) 
4/26/2011
11
Álgebra de Boole - Axiomas
1. Existe um conjunto de elementos K, sujeitos 
a uma relação de equivalência “=” que 
i f i í i d b i i ãsatisfaz ao princípio da substituição.
2. Fechamento
a) Uma regra de combinação “+” é definida de tal 
forma que a+b está em K contanto que a e b
estejam em K.
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
j
b) Uma regra de combinação “.” é definida de tal 
forma que a.b está em K contanto que a e b
estejam em K.
Álgebra de Boole - Axiomas
3. Identidade
a) Existe um elemento 0 em K tal que, para todo a
K 0em K, a+0=a
b) Existe um elemento 1 em K tal que, para todo a
em K, a.1=a
4. Leis comutativas
a) Para todo a e b em K, a+b=b+a
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
) ,
b) Para todo a e b em K, a.b=b.a
4/26/2011
12
Álgebra de Boole - Axiomas
5. Leis distributivas
a) Para todo a e b em K, a+(b.c) =(a+b).(a+c)
b) Para todo a e b em K a (b+c) =(a b)+(a c)b) Para todo a e b em K, a.(b+c) =(a.b)+(a.c)
6. Para todo elemento a em K, existe o elemento a’
tal que: 
0. =aa
1=+ aa
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
7. Existem pelo menos dois elementos x e y em K, 
tais que x≠y
Álgebra de Boole
„ No caso em que K apresenta somente dois 
elementos 0 e 1, eles devem satisfazer a:
01= 10 =
11001111.1 =+=+=+=
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
01.00.10.000 ====+
4/26/2011
13
Álgebra de Boole
„ Dualidade
…Note que os axiomas são apresentados em pares, e 
d d d i dque pode ser demonstrado que um axioma do par 
pode ser obtido do outro a partir das seguintes 
substituições:
„ “0” por “1”
„ “1” por “0”
„ “ ” por “+”
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
„ . por +
„ “+” por “.”
Álgebra de Boole
„ Dualidade
…Exemplo: axioma 3
…Exemplo: axioma 5
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
…Exemplo: axioma 5
4/26/2011
14
Álgebra de Boole - Teoremas1. Os elementos 0 e 1 são únicos.
2. Para todo elemento a em K
a+a=a
a.a=a
3. Para todo elemento a em K
a+1=1
0 0
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
a.0=0
4. Os elementos 0 e 1 são distintos, e 1´=0
Álgebra de Boole - Teoremas
5. Para todo par de elementos a e b em K
a+ab=a
a.(a+b)=a
6. O elemento a’ definido pelo Axioma 6 é 
único
7. Para todo elemento a em K, a = a’’
P i ê l b K
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
8. Para quaisquer três elementos a, b e c em K
a[(a+b)+c]=[(a+b)+c].a=a
4/26/2011
15
Álgebra de Boole - Teoremas
9. Para quaisquer três elementos a, b e c em K
a+(b+c)=(a+b)+c
a.(b.c)= (a.b).c
10. Para todo par de elementos a e b em K
11. Para todo par de elementos a e b em K
babaa .).( =+
babaa +=+ .
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
p
baba +=.
baba .=+
Álgebra de Boole - Teoremas
12. Para quaisquer três elementos a, b e c em K
cabacbcaba +=++ ....
)).(()).().(( cabacbcaba ++=+++
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
4/26/2011
16
Demonstração dos Teoremas
„ Os teoremas podem ser demonstrados a partir dos 
axiomas e dos outros teoremas.
„ T 1 O l t 0 1 ã ú i„ Teorema 1. Os elementos 0 e 1 são únicos.
… Assumindo que existem dois elementos zero (01 e 02)
… Seja
111 0 aa =+
21 0=a
(Axioma 3a)222 0 aa =+
12 0=a
e
e
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
… Pelo Axioma 4a:
21 00 =
212 000 =+ 121 000 =+ePortanto
Demonstração dos Teoremas
… (demonstração por contradição) Assumindo que existem 
dois elementos um (11 e 12)
… Seja
… Pelo Axioma 4b:
111 1. aa =
21 1=a
(Axioma 3b)222 1. aa =
12 1=a
212 11.1 = 121 11.1 =
e
e
ePortanto
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
… Pelo Axioma 4b:
… Note que essa parte da demonstração pode ser obtida por 
dualidade a partir da demonstração anterior!
21 11 =
4/26/2011
17
Demonstração dos Teoremas
„ Teorema 2 
Para todo elemento a em K
aaa =
aaa =+
)).(( aaaaaa ++=+
1).( aaaa +=+
aaaaa .+=+
(Axioma 3b)
(Axioma 6)
(Axioma 5a)
aaa =.
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
0+=+ aaa
aaa =.
aaa =+ (Axioma 3a)
(Axioma 6)
(Teorema da Dualidade)
Demonstração dos Teoremas
„ Teorema 3
Para todo elemento a em K
00 =a
11=+a
)1)((1 ++=+ aaaa
)1.(11 +=+ aa
1.1 aaa +=+
(Axioma 3b)
(Axioma 6)
(Axioma 5a)
00. =a
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
aaa +=+1
00. =a
11=+a
(Axioma 3b)
(Axioma 6)
(Teorema da Dualidade)
4/26/2011
18
Demonstração dos Teoremas
„ Teorema 4
Os elementos 0 e 1 são distintos, e 1´=0
… Seja a um elemento em K. 
… Assumindo que 1=0, as expressões acima são 
satisfeitas somente para a=0. O axioma 7, no 
entanto, afirma que existem pelo menos dois 
00. =a aa =1.
(Axioma 3b)
(Teorema 3)
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
, q p
elementos em K. Essa contradição pode ser 
resolvida concluindo que 1≠ 0
01=
1.11= (Axioma 3b)
(Axioma 6)
Demonstração dos Teoremas
„ Teorema 5 aaba =+
abaa =+ )(
)1( baaba +=+
abaaba +=+ 1.
(Axioma 3b)
(Axioma 5b)
1.aaba =+ (Teorema 3)
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
abaa =+ . (Postulado 3b)
abaa =+ )(. (Teorema da Dualidade)
4/26/2011
19
Demonstração dos Teoremas
„ Teorema 6 (por contradição)
O definido no axioma 6, para cada a em Ka
é único
… Assumindo dois valores distintos e que 
satisfaçam o Axioma 6:
1a
0. 1 =aa
(Axioma 3b)
11 =+ aa
2a
1 aa =
0. 2 =aa12 =+ aa
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
(Suposição)
(Axioma 3b)
(Axioma 5b)
212 )( aaaa +=
22 .1 aa =
2122 aaaaa +=
Demonstração dos Teoremas
„ Teorema 6 (continuação)
(Suposição)
2122 aaaaa +=
212 0 aaa +=
2112 aaaaa +=
)( aaaa +=
(Suposição)
(Axioma 5b)
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
(Suposição)
(Axioma 3b)
12 .1 aa =
12 aa =
122 )( aaaa += (Axioma 5b)
4/26/2011
20
Demonstração dos Teoremas
„ Teorema 7
Para cada elemento a em K, aa =
… Seja . Portanto: 
… Mas
… Como x e a satisfazem ao Axioma 6 como o
1=+ xa0=xa
xa =
1=+ aa0. =aa
(Axioma 6)
(Axioma 6)
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
… Como x e a satisfazem ao Axioma 6 como o 
complemento de 
(Teorema 6)ax =
a
Demonstração dos Teoremas
„ Teorema 8
aacbacbaa =++=++ ])[(])[(
(Axioma 5b)
(Teorema 5)
acbaacbaa ++=++ )(])[(
acacbaa +=++ ])[(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
(A 4b, T 5)acbaacbaa ])[(])[( ++==++
4/26/2011
21
Demonstração dos Teoremas
„ Teorema 9 cbacba ++=++ )()(
cabbca )()( =
)](].[)[( cbacbaZ ++++=
(Teorema 8)
)].()[(])[( cbcbaacbaZ ++++++=
)].()[( cbcbaaZ ++++=
}])[(]){[( bbbZ
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
}].)[(]){[( ccbabcbaaZ ++++++=
(Teorema 8, Axioma 4b)}].)[({ ccbabaZ ++++=
(Teorema 5)cbaZ ++= )(
(Axioma 5b)
Demonstração dos Teoremas
„ Teorema 10 babaa +=+
abbaa =+ )(
).(1. babaa +=+
)).((. baaabaa ++=+
babaa +=+ .
(Axioma 5a)
(Axioma 6)
(Axioma 3)
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
babaa .)(. =+ (Teorema da Dualidade)
4/26/2011
22
Demonstração dos Teoremas
„ Teorema 11 baba .=+
baba +=.
])].[()[(.)( bbaabababa ++++=++
(Axioma 4a)
(Teorema 9, Axioma 3)
)]()].[([.)( abbbaababa ++++=++
11.1.)( ==++ baba
(Axioma 5a)
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
).().().).(( abbbaababa +=+
000).).(( =+=+ baba
(Axioma 5b, Axioma 4b)
(Teorema 9, Axioma 3)
Demonstração dos Teoremas
„ Teorema 11 baba .=+
baba +=.
… Ambas as partes do Axioma 6 são atendidas, de 
modo que a+b é o único complemento de
… Portanto
ba.
baba .=+ baba .=+ou
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
bababa .. ==+ (Teoremas 6 e 7)baba .=+ou
4/26/2011
23
Demonstração dos Teoremas
„ Teorema 12 caabbccaab +=++
))(())()(( cabacbcaba ++=+++
)1()1( bcacabbccaab +++=++
)( aabccaabbccaab +++=++
bcacaabcabbccaab +++=++
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
)1()1( bcacabbccaab +++=++
caabbccaab +=++
Simplificação de funções - exemplo
„ Exemplo 1:
Os senhores A, B e C colecionam livros. O Sr. 
A coleciona trabalhos políticos brasileiros e 
romances estrangeiros. O Sr. B coleciona 
trabalhos políticos exceto romances 
brasileiros, e trabalhos brasileiros que não são 
romances. O Sr. C coleciona itens não fictícios
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
romances. O Sr. C coleciona itens não fictícios 
que são trabalhos brasileiros ou trabalhos 
políticos estrangeiros. Determinar os livros que 
são desejados por dois ou mais colecionadores.
4/26/2011
24
Simplificação de funções - exemplo
„ Inicialmente, temos que determinar as funções lógicas 
dos conjuntos de livros desejados por cada 
colecionadorcolecionador
„ As variáveis utilizadas foram:
A – conjunto de livros colecionados pelo Sr. A
B – conjunto de livros colecionados pelo Sr. B
C – conjunto de livros colecionados pelo Sr. C
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
N – conjunto de livros nacionais (brasileiros)
R – conjunto de romances
P – conjunto de trabalhos políticosSimplificação de funções - exemplo
„ O Sr. A coleciona trabalhos políticos 
brasileiros e romances estrangeiros.
„ O Sr. B coleciona trabalhos políticos exceto 
romances brasileiros, e trabalhos brasileiros 
que não são romances.
RNPNA .. +=
RNNRPB +)( RNNNRPNPB +++ )(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
RNNRPB += )(
RNRPNPB ++=
RNRNPB ++= )(
RNNNRPNPB +++= )(
RNNPB +=
)1()1( PRNRNPB +++=
4/26/2011
25
Simplificação de funções - exemplo
„ O Sr. C coleciona itens não fictícios que são 
trabalhos brasileiros ou trabalhos políticos 
iestrangeiros.
RPNNC )( +=
RPRNC +=
RPNC )( +=
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
„ Os livros desejados por dois ou mais 
colecionadores são:
BCACABZ ++=
Simplificação de funções - exemplo
))(())(())(( RPRNRNNPRPRNRNNPRNNPRNNPZ ++++++++=
))(())(( RPRNRNNPRPRNNPRNNPZ ++++++= ))(())(( RPRNRNNPRPRNNPRNNPZ ++++++=
))(())(( RPRNRNNPRNNPRNNPZ +++++=
))(( RPRNRNNPRNNPZ ++++=
)()( RPRNRNNPRNRPRNRNNPNPZ +++++++=
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
)()(
RNRRNPZ ++= )(
RNNPZ +=
4/26/2011
26
Simplificação de funções - exemplo
RNNPA += RNNPA +
RNNPB +=
RNNP +=Z
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
RPRNC +=
Simplificação de circuitos
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
CABABCCBABCACBACBAf ++++=),,(
4/26/2011
27
Simplificação de circuitos
CABABCCBABCACBACBAf ++++=),,(
)()()( AACBAABCCBACBAf ++++= )()(),,( AACBAABCCBACBAf ++++=
CBBCCBACBAf ++=),,(
)(),,( CCBCBACBAf ++=
BCBACBAf +=),,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
f ),,(
BCACBAf +=),,(
Simplificação de circuitos
CABCBABCACBACBACBAf ++++)(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
CABCBABCACBACBACBAf ++++=),,(
4/26/2011
28
Simplificação de circuitos
CABCBABCACBACBACBAf ++++=),,(
)()()( BBCACCBACBACBAf ++++= )()(),,( BBCACCBACBACBAf ++++=
CABACBACBAf ++=),,(
CACBBACBAf ++= )(),,(
CACBACBAf ++= )(),,(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
CACABACBAf ++=),,(
)(),,( AACBACBAf ++=
CBACBAf +=),,(
Função chaveamento
„ Uma função chaveamento (switching function) 
de n variáveis é qualquer designação particular 
d l f i i (“1” 0”) dde valores funcionais (“1” ou 0”) para todas as 
combinações possíveis de valores das variáveis
„ Note que existem 22n funções chaveamento de 
n variáveis.
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
4/26/2011
29
Função chaveamento
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
ABCDDABCDCABDCBADCBABCDADBCADCBADCBADCBADCBADCBAf ++++++++++=),,,(
Função chaveamento
ABCDCCDABCCDBADDBCADDCBACCDBADCBAf ++++++++++= )()()()()(),,,(
ABCDDABCDCABDCBADCBABCDADBCADCBADCBADCBADCBADCBAf ++++++++++=),,,(
ABCDDABDBABCACBADBADCBAf +++++=),,,(
)()(),,,( CDDABDBACCBADBADCBAf +++++=
)(),,,( CDABDBABADBADCBAf ++++=
ABCDABDBADBBADCBAf ++++= )(),,,(
ABCBBDADBADCBAf ++++ )()()(
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
ABCBBDADBADCBAf ++++= )()(),,,(
ABCDADABADCBAf +++=),,,(
)()(),,,( ACABAADDCBAf +++=
BCBADDCBAf ++=),,,(
4/26/2011
30
Definições
„ Literal
…Variável ou seu complemento
„ Termo Produto
…Série de literais relacionados por AND
„ Termo Soma
…Série de literais relacionados por OR
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
„ Termo Normal
…Termo soma ou termo produto no qual nenhum 
literal aparece mais de uma vez
Soma-de-produtos
„ Encontre a forma soma de termos produto para 
a expressão abaixo:
))((),,,,( BEDBCAEDCBAf ++=
])[)((),,,,( BEDCBAEDCBAf ++=
])[)((),,,,( EBDCBAEDCBAf +++=
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
))((),,,,( EDDBCBAEDCBAf +++=
EDCDCBEDBDBEDADBAEDCBAf +++++=),,,,(
Soma de produtos normais
4/26/2011
31
Soma-de-produtos
„ Encontre a forma soma-de-produtos para a 
expressão abaixo na qual todos os literais 
d daparecem em cada termo produto.
CBACBAf +=),,(
CBAACCBBACBAf )())((),,( ++++=
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
CBACBACBACBACABABCCBAf +++++=),,(
CBACBACBACABABCCBAf ++++=),,(
Soma padrão de produtos
minitermo
Definições (continuação)
„ Termo Padrão
…Termo soma ou termo produto no qual todos os 
li i ãliterais estão presentes
„ Minitermo
…Termo soma padrão
„ Maxitermo
…Termo produto padrão
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
…Termo produto padrão
4/26/2011
32
Teoremas
„ Qualquer função chaveamento de n variáveis 
f(x1,x2,.., xn) pode ser expressa como uma soma 
d ã d d ( d dpadrão de produtos (soma de termos produto 
padrão)
„ Qualquer função chaveamento de n variáveis 
f(x1,x2,.., xn) pode ser expressa como um 
produto padrão de somas (produto de termos
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
produto padrão de somas (produto de termos 
soma padrão)
Produto-de-somas
„ Encontre a forma produto padrão de somas
para a função abaixo:
CBACBAf +=),,(
))((),,( CABACBAf ++=
))((),,( BBCACCBACBAf ++++=
))()()((),,( CBACBACBACBACBAf ++++++++=
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
Produto padrão de somas
))()()((),,( CBACBACBACBACBAf ++++++++
))()((),,( CBACBACBACBAf ++++++=
Maxitermo
4/26/2011
33
Minitermos e Maxitermos
„ Para facilitar a escrita de funções lógicas, pode-se
… representar termos produto padrão por minitermos quando 
se utilizar a forma soma padrão de produtos; ouse utilizar a forma soma padrão de produtos; ou
… representar termos soma padrão por Maxitermos quando se 
utilizar a forma produto padrão de somas.
 
 
 
Linha A B C Minitermo Maxitermo 
0 0 0 0 CBAm ..0 = )(0 CBAM ++= 
1 0 0 1 CBAm ..1 = )(1 CBAM ++=
Variáveis 
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
1 )(1
2 0 1 0 CBAm .2 = )(2 CBAM ++= 
3 0 1 1 BCAm .3 = )(3 CBAM ++= 
4 1 0 0 CBAm .4 = ).(4 CBAM ++=
5 1 0 1 CBAm .5 = )(5 CBAM ++= 
6 1 1 0 CABm =6 )(6 CBAM ++= 
7 1 1 1 ABCm =7 )(7 CBAM ++= 
 
Minitermos
Linha A B C Minitermo
0 0 0 0 CBAm ..0 =
1 0 0 1 CBAm ..1 =
2 0 1 0 CBAm .2 =
3 0 1 1 BCAm .3 =
4 1 0 0 CBAm .4 =
5 1 0 1 CBAm =
Variáveis
Capítulo 2 – Álgebra de BooleMárcio Brandão – CIC/UnB – Circuitos Digitais
5 1 0 1 CBAm .5 =
6 1 1 0 CABm =6
7 1 1 1 ABCm =7