Módulo 05a –Álgebra Booleana e Álgebra de Chaveamento

Prévia do material em texto

1
1
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 1
1
PCS 2215
Sistemas Digistais I
Módulo 05a – Álgebra Booleana e 
Álgebra de Chaveamento
Marco Túlio Carvalho de Andrade
Professor Responsável
Versão: 2.0 (Setembro de 2.013)
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 2
2
Conteúdo
Álgebra Booleana e Álgebra de 
Chaveamento
1. Álgebra Booleana;
2. Circuitos de Chaveamento;
3. Propriedades dos Circuitos de 
Chaveamento;
4. Álgebra de Chaveamento.
Bibliografia
2
2
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 3
1. Álgebra Booleana 
Análise de Circuitos Lógicos:
 Sempre pode ser feito por Tabelas da 
Verdade:
– Procedimento exaustivo - Requer tabelas 
que contenham todas as combinações 
possíveis das variáveis de entrada;
– Circuitos de n entradas e m saídas possuem 
Tabelas de 2n linhas e (n + m) colunas;
– Não é prático ter que manipular Tabelas 
para combinar e operar funções lógicas.
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 4
1. Álgebra Booleana 
 Por esta razão é conveniente definir um 
procedimento algébrico sistemático que:
1-) Represente funções lógicas de modo 
compacto;
2-) Permita manipulações convenientes 
destas funções;
3-) Defina operadores em um domínio 
especificado.
 A entidade matemática que dá suporte a 
estes objetivos é a Álgebra Booleana.
3
3
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 5
1. Álgebra Booleana 
Uma Álgebra Booleana é uma Estrutura 
Algébrica à qual pode-se atribuir várias 
interpretações:
1-) O Cálculo de Proposições pode ser visto 
como uma Álgebra de Proposições;
2-) A Teoria de Conjuntos pode ser vista 
como uma Álgebra de Conjuntos;
3-) Funções Lógicas como uma Álgebra de 
Chaveamento ... Sendo esta última a de 
maior interesse para o curso!
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 6
1. Álgebra Booleana 
 Definição 1.1.: Uma Álgebra Booleana
é uma Estrutura Algébrica com a forma 
<{X≤}, +, . , ~, 0, 1>, na qual:
1-) X≤ é um conjunto parcialmente ordena-
do, onde: X é um conjunto tal que |X| > 1; 
≤ é uma relação de ordem parcial em X;
2-) “+” e “.” são operações sobre X:
– x + y = max(x,y),  x,y  X;
– x . y = min(x,y),  x,y  X.
4
4
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 7
1. Álgebra Booleana 
Definição 1.1.: Uma Álgebra Booleana é 
uma Estrutura Algébrica com a forma 
<{X≤}, +, . , ~, 0, 1> ... continuação:
3-) 0 e 1 são elementos especiais, tal que:
– 0 ≤ x e 1 ≥ x,  x  X.
4-) Sinal “~” é a operação de complemento 
e  x  X, | ~x  X, tal que:
– x + ~x = 1; x . ~x = 0; 0 ≤ ~x; 1 ≥ ~x.
5-) “+” e “.” são operações distributivas.
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 8
Exemplo 1.1. - Seja U o conjunto universo e 
seja S = P(U) o conjunto Potência de U.
– Se definimos as operações entre subconjuntos:
X + Y = X  Y, X . Y = X  Y, ~X = X
pertencentes a S então a sêxtupla (S,  ,  , , Ø, U) 
é uma Álgebra Booleana.
Alguns autores fazem a distinção entre:
– Uma Álgebra Booleana Funcional
(Z2, , , ~, 0, 1)
– Uma Álgebra Booleana Conjuntista
(S, ,  , , Ø, U)
1. Álgebra Booleana 
5
5
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 9
9
1. Álgebra Booleana 
Conjuntista (P(U), ,  , , Ø, U)
U = {1,2,3}
P(U)={Ø,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
(parcialmente ordenado) 
A  P(U), B  P(U) tal que A  B
Funcional (S, , , ~, 0, 1)
S = parcialmente ordenado
S = {1,2,3,5,6,10,15,30}
x divide y  xRy
Ø
{3}{1}
{2}
U= {1,2,3}
{1,2} {2,3}
{1,3}
52
3
30
6 15
10
1
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 10
Definição 1.2. - Duas ocorrências de uma 
estrutura são isomorfas se existir uma bijeção, 
chamada isomorfismo, que leva os elementos 
de uma ocorrência aos elementos da outra 
ocorrência, de modo que as propriedades 
relevantes sejam preservadas:
– Cada ocorrência é uma imagem da outra, 
com outra denominação dos elementos mas 
com o mesmo número de elementos.
– Pode-se usar esta idéia para classificar
exemplos de estruturas, associando-se as 
que são isomorfas.
1. Álgebra Booleana: Isomorfismo
6
6
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 11
11
Conjuntista (P(U), ,  , , Ø, U)
P(U)={Ø,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} 
Funcional (Z2, , , ~, 0, 1)
Z2 = {1,2,3,5,6,10,15,30}
4. Álgebras Booleanas: Isomorfismo
Ø
{3
}
{1}
{2}
U= {1,2,3}
{1,2} {2,3}
{1,3}
52
3
30
6 15
10
1
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 12
12
1. Álgebra Booleana 
Álgebra Booleana – Para pares de operan-
dos do tipo [(x, ~x) ou (X,X)], ocorre:
 Operadores de Conjunção (, ) – O 
elemento resultante da aplicação da 
operação é o Máximo dos Limitantes 
Inferiores (Ínfimo);
 Operadores de Disjunção (∨, ) – O 
elemento resultante da aplicação da 
operação é o Mínimo dos Limitantes 
Superiores (Supremo).
7
7
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 13
13
Conjuntista (P(U), ,  , , Ø, U)
P(U)={Ø,{1},{2},{3},{1,2},{1,3},{2,3}, 
{1,2,3}}
Propriedade: A  P(U), B  P(U) tal 
que A  B
I. Propriedade É satisfeita:
I.1. Operador  devolve: X
I.2. Operador  devolve: Y
II. Propriedade NÃO É satisfeita:
II.1. Operador  devolve: X Y
II.2. Operador  devolve: X Y
Funcional (S, , , ~, 0, 1)
S = {1,2,3,5,6,10,15,30}
Propriedade: x divide y
I. Propriedade É satisfeita:
I.1. Operador  devolve: x
I.2. Operador  devolve: y
II. Propried. NÃO satisfeita:
II.1. Operador  devolve: 
MDC(x,y)
II.2. Operador  devolve: 
mmc(x,y)
1. Álgebra Booleana 
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 14
2. Circuitos de Chaveamento 
 Chaves: Podem ser utilizadas como 
elementos de comutação (ou chaveamen-
to) para possibilitar a materialização 
(implementação física) de primitivas de 
lógica.
X
P1 P2
8
8
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 15
2. Circuitos de Chaveamento 
Chave Aberta (X = 0): Não há conexão 
física entre P1 e P2.
Chave Fechada (X = 1): Há conexão física 
entre P1 e P2.
X=0
P1 P2
X=1
P2
P1
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 16
2. Circuitos de Chaveamento 
Entradas - São as conexões que abrem ou 
fecham as chaves (exemplo: Entrada A).
Saídas - São o resultado da conectividade obtida 
no abrir e fechar de uma chave (ou associação 
de chaves), que por sua vez, irá abrir e/ou 
fechar outras chaves.
A=0
P1 P2
A=1
P1 P2
P1 não conectado a P2
Saída = 0
P1 conectado a P2
Saída = 1
9
9
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 17
2. Circuitos de Chaveamento 
Exemplo 2.1 - Circuito de Chaveamento 
- É uma rede elétrica, constituída de 
chaves abertas ou fechadas.1-) Chaves simbolizadas pela mesma letra 
estão todas abertas ou todas fechadas.
2-) Chave X aberta (fechada) implica em 
chave ~X fechada (aberta).
3-) Se uma corrente flui do terminal 
esquerdo para o direito diz-se que a saída 
do circuito é 1, em caso contrário é 0.
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 18
2. Circuitos de Chaveamento 
4-) Uma tabela de chaveamento proporcio-
na a saída do circuito para todos os valo-
res das chaves.
A
~A
B
C
Alguns exemplos 
de
possíveis valores 
de entrada
A B C Saída
1 1 1 1
1 0 1 0
1 1 0 1
0 0 1 1
1 0 0 0
10
10
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 19
3. Propriedades dos Circuitos de Chaveamento 
Podem ser definidos dois operadores 
binários,  e , sobre o conjunto 
Z2 = {0,1}.
A  B = 1, se A = B = 1
A  B = 0, em qualquer outro caso
A  B = 0, se A = B = 0
A  B = 1, em qualquer outro caso
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 20
3. Propriedades dos Circuitos de Chaveamento 
Pode ser definido um operador unário ~
sobre o conjunto Z2 = {0,1}:
~A = 0, se A = 1
~A = 1, se A = 0
Estes operadores podem ser implementa-
dos em circuitos de chaveamento.
Seguem algumas propriedades de um sis-
tema constituído por Z2 e os operadores 
,  e ~:
11
11
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 21
Teorema 3.1 - Se ,  e ~ são operadores 
como os definidos anteriormente, então 
exibem as seguintes propriedades (para 
todo a, b e c  Z2 = {0,1}):
Lei Associativa:
(a  b)  c = a  (b  c)
(a  b)  c = a  (b  c)
Lei Comutativa:
a  b = b  a
a  b = b  a
3. Propriedades dos Circuitos de Chaveamento 
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 22
Teorema 3.1 - Continuação:
Lei Distributiva:
a  (b  c) = (a  b)  (a  c)
a  (b  c) = (a  b)  (a  c)
Lei da Identidade:
a  0 = a
a  1 = a
Lei do Complemento:
a  ~a = 1
a  ~a = 0
3. Propriedades dos Circuitos de Chaveamento 
12
12
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 23
Exemplo 3.1 - Prova da primeira lei distri-
butiva. Deve-se mostrar que
a  (b  c) = (a  b)  (a  c)
a b c a  (b  c) (a  b)  (a  c) 
1 1 1 1 1 
1 1 0 1 1 
1 0 1 1 1 
1 0 0 0 0 
0 1 1 0 0 
0 1 0 0 0 
0 0 1 0 0 
0 0 0 0 0 
3. Propriedades dos Circuitos de Chaveamento 
Prova do Teorema 
3.1 - As provas das 
várias Leis (e/ou 
propriedades) con-
sistem em verifica-
ções diretas por 
meio de tabelas da 
verdade.
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 24
Definição 4.1 - Uma variável xi é dita uma 
Variável de Chaveamento se ela represen-
ta os estados de uma chave (aberta ou 
fechada) por meio dos valores 0 e 1, 
respectivamente.
Exemplo 4.1 - Existem 2n maneiras possí-
veis de se associar valores de verdade 
(dois valores - 0 e 1) a n variáveis.
4. Álgebra de Chaveamento
13
13
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 25
Definição 3.2 - Uma Função de Chaveamento 
de n variáveis (x0, x1, ..., xn-1) é uma associação 
particular de valores de verdade (zeros ou uns) 
para todas as 2n possíveis combinações de 
valores das n variáveis.
4. Álgebra de 
Chaveamento
222 1 n
2
x1 f
1 ?
0 ?
n=1
422 2 n
4
x2 x1 f
1 1 ?
1 0 ?
0 1 ?
0 0 ?
n=2
x3 x2 x1 f
1 1 1 ?
1 1 0 ?
1 0 1 ?
1 0 0 ?
0 1 1 ?
0 1 0 ?
0 0 1 ?
0 0 0 ?822 3 n
8
n=3
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 26
Exemplo 4.2: Com duas variáveis (n=2) há 
16 formas possíveis de se substituir os 
sinais de interrogação por zeros e uns (16 
funções de chaveamento possíveis).
4. Álgebra de Chaveamento
1622
222 
n
4
n=2
x2
0
0
1
1
x1
0
1
0
1
f2
0
0
1
0
f0
0
0
0
0
f1
0
0
0
1
f3
0
0
1
1
f4
0
1
0
0
f5
0
1
0
1
f6
0
1
1
0
f7
0
1
1
1
f10
1
0
1
0
f8
1
0
0
0
f9
1
0
0
1
f11
1
0
1
1
f12
1
1
0
0
f13
1
1
0
1
f14
1
1
1
0
f15
1
1
1
1
14
14
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 27
Definição 4.3 - Duas Funções de Chaveamento 
são iguais, ou equivalentes, se seus valores de 
verdade forem iguais para todas as combina-
ções possíveis dos valores de verdade de suas 
variáveis.
Nota 4.1 - A maioria dos problemas de Álgebra 
de Chaveamento deriva do fato de se desejar 
construir um bloco que implemente uma 
determinada função de chaveamento de “n” 
variáveis.
Nota 4.2 - Existem infinitas expressões equiva-
lentes a cada função possível.
4. Álgebra de Chaveamento
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 28
Nota 4.3 - A solução do problema passa pelo 
processo de determinar qual, dentre estas 
expressões equivalentes à função desejada, é a 
mais simples ou satisfaz alguns critérios de 
simplicidade.
Nota 4.4 - Se o problema se relaciona com a 
construção de um circuito eletrônico de 
chaveamento os critérios de simplicidade 
serão derivados da conveniencia de se utilizar 
o circuito o mais barato possível e que tenha o 
comportamento funcional desejado. 
4. Álgebra de Chaveamento
15
15
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 29
Definição 4.4 - Seja xi uma variável de 
Chaveamento, isto é, uma variável que 
representa os estados de uma chave 
(aberta ou fechada) por meio dos 
valores 0 e 1. Sejam n variáveis de 
chaveamento x1, x2, ..., xn, que definem 
funções de chaveamento (F.C.) distintas. 
A sêxtupla ({F.C.}, , , ~, 0t, 1t) é uma 
Álgebra de Chaveamento.
4. Álgebra de Chaveamento
n
m 221
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 30
30
A sêxtupla ({F.C.}, , , ~, 0t, 1t) é uma 
Álgebra de Chaveamento, onde:
– {F.C.} = {f0, f1, ... , fm} é o conjunto 
das funções de chaveamento possíveis 
para n variáveis lógicas.
– 0t = f0 = Função correspondente às 
chaves abertas.
– 1t = fm = Função correspondente às 
chaves fechadas.
4. Álgebra de Chaveamento
16
16
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 31
31
A sêxtupla “({F.C.}, , , ~, 0t, 1t)” é uma 
Álgebra de Chaveamento, onde:
–  é a operação lógica E (denotada por 
“.”).
–  é a operação lógica OU (denotada 
por “+”).
– ~ é a operação lógica NÃO.
– Valem as propriedades dos circuitosde 
chaveamento, enunciadas 
anteriormente.
4. Álgebra de Chaveamento
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 32
Para n = 2 variáveis de chaveamento podem 
ser obtidas as 16 funções de chaveamento 
possíveis e o Diagrama de Hasse corres-
pondente:
4. Álgebra de Chaveamento
x2
0
0
1
1
x1
0
1
0
1
f2
0
0
1
0
f0
0
0
0
0
f1
0
0
0
1
f3
0
0
1
1
f4
0
1
0
0
f5
0
1
0
1
f6
0
1
1
0
f7
0
1
1
1
f10
1
0
1
0
f8
1
0
0
0
f9
1
0
0
1
f11
1
0
1
1
f12
1
1
0
0
f13
1
1
0
1
f14
1
1
1
0
f15
1
1
1
1
 
~


x2 x1. +

Λ

V
~x2~x1 
~
~Λ
~ 
~ V
~+
Absurdo (contradição) Tautologia
~  ~.
17
17
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 33
4. Álgebra de Chaveamento
[Contradições]
[Tautologias]
[Contingências]
f0(0000)
f1(0001)f8(1000)
f12(1100)
f14(1110)
f15(1111)
f7(0111)
f3(0011)
f13(1101) f11(1011)
f5(0101)f10(1010)
f4(0100) f2(0010)
f9(1001)
f6(0110)
[Contingências]
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 34
No Diagrama de Hasse da Álgebra de 
Chaveamento podem ser observadas algumas 
propriedades interessantes:
 1-) Dados fi e fj se os índices i e j somam quinze (i+j 
= 15) então fi = ~fj. Exemplo: f4 = 0100 e f11 = 1011.
 2-) Qualquer função de chaveamento pode ser 
expressa em termos da operação “+” sobre as 
funções:
f1 = 0001, f2 = 0010, f4 = 0100 e f8 = 1000
 3-) Qualquer função de chaveamento pode ser 
expressa em termos da operação “.” sobre as funções:
f7 = 0111, f11 = 1011, f13 = 1101 e f14 = 1110
4. Álgebra de Chaveamento
18
18
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 35
4. Álgebra de Chaveamento:Funções para duas variáveis
Se traduzimos esta tabela da verdade das 
funções de chaveamento para a linguagem das 
expressões das funções de chaveamento, em 
termos de suas variáveis, obtemos no Diagrama 
de Hasse uma representação mais fácil de ler.
 
~


x2 x1. +

Λ

V
~x2~x1 
~Λ
~ 
~ V
~+
Absurdo (contradição) Tautologia
~  ~.
x2
0
0
1
1
x1
0
1
0
1
f2
0
0
1
0
f0
0
0
0
0
f1
0
0
0
1
f3
0
0
1
1
f4
0
1
0
0
f5
0
1
0
1
f6
0
1
1
0
f7
0
1
1
1
f10
1
0
1
0
f8
1
0
0
0
f9
1
0
0
1
f11
1
0
1
1
f12
1
1
0
0
f13
1
1
0
1
f14
1
1
1
0
f15
1
1
1
1
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 36
4. Álgebra de Chaveamento
0
x1x2~x1 ~ x2
~x2 x2 
~x1+~x2 x1+ x2
1
x1x2
x1+ ~x2 ~x1+ x2
~x1 x1
x1.~x2 ~x1.x2
x1x2
0
x1x2~x1 ~ x2
~x2 x2 
~x1+~x2 x1+ x2
1
x1x2
x1+ ~x2 ~x1+ x2
~x1 x1
x1.~x2 ~x1.x2
x1x2
19
19
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 37
Desta nova representação do Diagrama de 
Hasse pode-se deduzir que [1/2]:
[1] f1 = x1.x2, f2 = ~x1.x2, f4 = x1.~x2 e f8 = ~x1.~x2
Definição 4.5- Átomo:  fk  {F.C.} (fk 
f0) tal que para  fi  {F.C.} ocorre fi . fk
= f0 ou fi . fk = fk.
Os átomos do diagrama anterior, que são
{f1, f2, f4, f8}, não podem ser obtidos pela 
operação de “+” sobre nenhuma outra 
função e denominam-se mintermos.
4. Álgebra de Chaveamento
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 38
Desta nova representação do Diagrama de 
Hasse pode-se deduzir que [2/2]:
[2] f7= x1+x2, f11= ~x1+x2, f13= x1+~x2 e 
f14= ~x1+~x2
Por outro lado, as funções {f7, f11, f13, f14} 
não podem ser obtidos pela operação de 
“.” sobre nenhuma outra função e 
denominam-se maxtermos.
4. Álgebra de Chaveamento
20
20
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 39
4. Álgebra de Chaveamento
0
x1.x2
~x1 ~ x2
~x1+~x2 x1 + x2
1
x1+~x2 ~x1 + x2
x1.~x2 ~x1 . x2
f14 = M3 = = f7 = M0
= f11 = M1
= f2 = m2
= f1 = m3
f13 = M2 =
f4 = m1 =
f8 = m0 =
f1(0001)
f8(1000)
f14(1110)
f7(0111)
f13(1101) f11(1011)
f4(0100)
f2(0010)
0
x1.x2
~x1 ~ x2
~x1+~x2 x1 + x2
1
x1+~x2 ~x1 + x2
x1.~x2 ~x1 . x2
f14 = M3 = = f7 = M0
= f11 = M1
= f2 = m2
= f1 = m3
f13 = M2 =
f4 = m1 =
f8 = m0 =
f1(0001)
f8(1000)
f14(1110)
f7(0111)
f13(1101) f11(1011)
f4(0100)
f2(0010)
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 40
40
Lição de Casa
 Leitura Obrigatória:
– Capítulo 4, seção 4.1 do Livro 
Texto.
 Exercícios Obrigatórios:
– Capítulo 4 do Livro Texto;
– Lista de Exercícios do Módulo 5.
21
21
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 41
41
Lição de Casa
 Leitura Complementar:
– Transparências sobre Complementos de 
Álgebra Booleana.
– Fregni, Edson; Ranzini, Edith. Teoria da 
Comutação: Introdução aos Circuitos 
Digitais (Partes 1 e 2). Apostila 
PCS/EPUSP, Outubro de 1.999. (capítulo 
1).
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 42
42
Lição de Casa
 Exercícios Complementares:
– Dias, Francisco José de Oliveira; “Introdução 
aos circuitos de Chaveamento”; Apostila, 
PEL/EPUSP, 1.989. (capítulo 4)
– Mendelson, Elliott; “Álgebra Booleana e 
Circuitos de Chaveamento”, Coleção Schaum, 
Editora McGraw-Hill, 1.977. 
– Fregni, Edson; Ranzini, Edith. Teoria da 
Comutação: Introdução aos Circuitos Digitais 
(Partes 1 e 2). Apostila PCS/EPUSP, Outubro 
de 1.999. (capítulo 1).
22
22
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 43
Bibliografia
Dias, Francisco José de Oliveira; “Introdução 
aos circuitos de Chaveamento”; Apostila, 
PEL/EPUSP, 1.989.
Fernández, Gregório; Saez Vacas, Fernando; 
“Fundamentos de Informática”, Alianza 
Editorial, Colección Alianza Informática, 
1.987.
Gersting, Judith L.; “Fundamentos Matemáticos 
Para a Ciência da Computação”, LTC - Livros 
Técnicos e Científicos Editora S. A., 1.995.
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 44
Bibliografia
Harrison, Michael A.; “Introduction To 
Switching and Automata Theory”, McGraw-
Hill Book Company, 1.965.
Hill, Frederic and Peterson, Gerald; 
“Introduction To Switching Theory and 
Logical Design”, John Wiley Sons, 1.974.
Johnsonbaugh, Richard; “Discrete 
Mathematics”, 3ª Edição, Macmillan 
Publishing Company, 1.993.
23
23
© Andrade, Corrêa, Gomi e Margi 2.013 Álgebra Booleana e de Chaveamento PCS 2215 - Fund. Eng. Comp. II 45
Bibliografia
Mendelson, Elliott; “Álgebra Booleana e 
Circuitos de Chaveamento”, Coleção Schaum, 
Editora McGraw-Hill, 1.977.
Ranzini, Edith; “Notas de Aula de PEL 213”, 
Apostila, EPUSP, 1.985.
Tremblay, J. P. and Monohar, R.; “Discrete 
Mathematical Structures With Applications to 
Computer Science”, McGraw-Hill, 1.975.