Módulo 05b – Complementos de Álgebra Booleana

Prévia do material em texto

1
1
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 1
Módulo 05b – Complementos de Álgebra
Booleana
Marco Túlio Carvalho de Andrade
Professor Responsável
Versão: 2.0 (Setembro de 2.013)
PCS 2215
Sistemas Digitais I
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 2
Conteúdo
Álgebra de Chaveamento
1. Circuitos Combinatórios.
2. Propriedades dos Circuitos Combinatórios.
3. Álgebras Booleanas.
4. Álgebras Booleanas: Outras Definições.
4.1  Reticulados  (“Lattices”).
4.2 Subálgebras.
5. Álgebra de Chaveamento.
2
2
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 3
1. Circuitos Combinatórios 
Circuito Combinatório
Qualquer circuito, desde que sua saída seja unicamente definida 
para cada combinação possível de valores de suas entradas.
1-) Uma mesma combinação de valores de entrada não pode dar margem a 
dois possíveis valores de saída.
2-) O valor da saída depende apenas e tão somente dos valores das entradas 
em um determinado instante e não tem qualquer vínculo com valores 
anteriores  (“realimentações”)  ou  estados  internos  do  circuito.
Nota 1.1: Circuitos combinatórios individuais (ou elementares) 
podem ser interconectados, ou combinados, de maneira a 
propiciar a obtenção de circuitos mais complexos.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 4
1. Circuitos Combinatórios 
Definição 1.1
Uma porta E (“And”  em  inglês)  recebe  duas  entradas,  x1 e x2, que 
são  “bits”,  e  produz  uma  saída  representada  por  x1  x2 (que 
também  é  um  “bit”),  de  tal  modo  que:
x1  x2 = 1, se x1 = x2 = 1
x1  x2 = 0, em qualquer outro caso
O símbolo usual (e tabela da verdade) para representar a porta E é:
AND
Entrada Saída
0 0
0 1
1 0
1 1
0
0
0
1
3
3
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 5
1. Circuitos Combinatórios 
Definição 1.2
Uma porta OU (“Or”  em  inglês)  recebe  duas  entradas,  x1 e x2, que 
são  “bits”,  e  produz  uma  saída  representada  por  x1  x2 (que 
também  é  um  “bit”),  de  tal  modo  que:
x1  x2 = 0, se x1 = x2 = 0
x1  x2 = 1, em qualquer outro caso
O símbolo usual (e tabela da verdade) que representa a porta OU é:
OR
Entrada Saída
0 0
0 1
1 0
1 1
0
1
1
1
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 6
1. Circuitos Combinatórios 
Definição 1.3
Uma porta NÃO (“Not”  em  inglês,  mais  comumente  denominada  
como porta inversora em português) recebe uma entrada x, onde 
x  é  um  “bit”,  e  produz  uma  saída  representada  por  ~x  (que  
também  é  um  “bit”),  de  tal  modo  que:
~x = 0, se x = 1
~x = 1, se x = 0
O símbolo usual (e tabela da verdade) para representar a porta 
inversora é:
Inversora
Entrada Saída
0
1
1
0
4
4
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 7
1. Circuitos Combinatórios 
Exercício 1.1 - O circuito abaixo é um circuito combinatório?
b
a e
fc
d
g
ENTRADAS SINAIS INTERMEDIÁRIOS SAÍDA FINAL
a b c d e f g
0
0
1
1
0
1
0
1
1
0
1
0
1
1
0
0
0
0
0
1
1
0
0
0
1
0
0
1
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 8
1. Circuitos Combinatórios 
Exercício 1.2 - Os circuitos abaixo são circuitos combinatórios? 
x1
x2
y
x1
x2
y
5
5
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 9
1. Circuitos Combinatórios 
Exercício 1.3 - O circuito abaixo é um circuito combinatório? 
x1
x2
y
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 10
1. Circuitos Combinatórios 
Exemplo 1.1 - Os circuitos C1 e C2 dos exercícios anteriores 
podem ser combinados por meio de um circuito C3 (uma porta 
OU, por exemplo) para gerar o circuito C:
x1
x2
x3
x4
y
C1
C2
C3
C
6
6
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 11
1. Circuitos Combinatórios 
Exemplo 1.2 - Um circuito combinatório pode ser representado por 
uma expressão usando-se os símbolos ,  e ~.
x1
x2
y
~x1 ~x1  x2
x2
x2
(~x1  x2)x2 ~((~x1  x2)x2)
y=~((~x1 x2)x2)
Tais expressões são ditas
Expressões Booleanas.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 12
1. Circuitos Combinatórios 
Definição 1.4 - Expressões Booleanas geradas sobre os 
símbolos x1, x2, ..., xn são definidas recursivamente:
1-) 0, 1, x1, x2, ..., xn são expressões Booleanas.
2-) Se X1 e X2 são expressões Booleanas então:
(a) (X1) (b) ~X1 (c) X1  X2 (d) X1  X2
também são expressões Booleanas.
3-) Se X é uma expressão Booleana gerada sobre os símbolos 
x1, x2, ..., xn então podemos escrever
X = X(x1, x2, ..., xn)
onde cada símbolo xi (ou ~xi) é chamado de um Literal.
7
7
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 13
1. Circuitos Combinatórios 
Exercício 1.4
a) Usar a definição 1.4 para mostrar que o lado direito da expressão 
y=~((~x1  x2)x2) é uma expressão Booleana.
b) Encontre o circuito combinatório correspondente às expressões 
Booleanas:
b.1) y=~((x1  x2)x1).
b.2) y=(~x1  x2)(x1  ~x2).
b.3) y=~((~x1  x2)(x1  ~x2)).
c) Encontre o valor de verdade das expressões Booleanas do item 
b) considerando-se que:
c.1) x1 = 1 e x2 = 0.
c.2) x1 = 1 e x2 = 1.
c.3) x1 = 0 e x2 = 0.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 14
1. Circuitos Combinatórios 
Exemplo 1.3 - Circuito de Chaveamento - É uma rede 
elétrica,  constituída  de  chaves  “abertas”  ou  “fechadas”.
1-) Se a chave X está aberta (fechada) então X = 0 (X = 1).
2-) Chaves simbolizadas pela mesma letra estão todas abertas ou 
todas fechadas.
3-) Chave X aberta implica em chave ~X fechada.
4-) Se a corrente flui do terminal esquerdo para o direito diz-se que a 
saída do circuito é 1, em caso contrário é 0.
5-) Uma tabela de chaveamento proporciona a saída do circuito para 
todos os valores das chaves.
A
~A
B
C
A B C Saída
1 1 1 1
1 0 1 0
1 1 0 1
Alguns exemplos de
possíveis valores 
de entrada
8
8
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 15
2. Propriedades dos Circuitos Combinatórios 
Propriedades dos Circuitos Combinatórios
Anteriormente definimos dois operadores binários,  e , 
e um operador unário ~ sobre o conjunto Z2 = {0,1}.
– Vimos que estes operadores podiam ser implementa-
dos  em  circuitos,  como  sendo  as  “portas  lógicas”  bá-
sicas de circuitos combinatórios.
– Agora serão mostradas algumas propriedades de um 
sistema constituído por Z2 e os operadores ,  e ~:
– Associativa
– Comutativa
– Distributiva
– Identidade
– Complemento
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 16
2. Propriedades dos Circuitos Combinatórios
Propriedades dos Circuitos Combinatórios
Teorema 2.1 - Se ,  e ~ são operadorescomo os definidos 
em 1.1, 1.2 e 1.3, então exibem as seguintes propriedades:
– Lei Associativa: (a b)  c = a (b c)
(a b) c = a (b c)
– Lei Comutativa: a b = b a; a b = b a
– 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
para todo a, b e c  Z2 = {0,1}
9
9
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 17
2. Propriedades dos Circuitos Combinatórios
Prova do Teorema 2.1 - As provas das várias Leis (e/ou proprie-
dades) consistem em verificações diretas por meio de tabelas da 
verdade.
Exemplo 2.1 - Prova da primeira lei distributiva. 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 
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 18
2. Propriedades dos Circuitos Combinatórios
Exemplo 2.2 - Usando o teorema 2.1 mostre que os circuitos 
abaixo são equivalentes (tem saídas iguais para entradas iguais):
x1
x2
x3
x2
x3
x1
Pelo Teorema 2.1: a  (b  c) = (a  b)  (a  c)
x1  (x2  x3)
(x1  x2)  (x1  x3)
10
10
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 19
2. Propriedades dos Circuitos Combinatórios
Definição 2.1 - Sejam X1 = X1(x1, x2, ... , xn) e X2 = X2(x1, x2, ... , 
xn) expressões Booleanas. Diz-se que X1 é igual a X2 e denota-se 
por X1 = X2 se
X1(a1, a2, ... , an) = X2(a1, a2, ... , an) para todo ai  Z2 = {0,1}
Nota 2.1 - Se definirmos uma relação R sobre um conjunto de 
expressões Booleanas baseada na propriedade X1 = X2 , ou seja,
X1RX2 se X1 = X2
então R é uma relação de equivalência.
Nota 2.2 - Cada Classe de Equivalência que resulta desta relação 
consiste em um conjunto de expressões Booleanas cujos valores 
são iguais para os mesmos valores dos literais(ou entradas), isto 
é, expressões Booleanas equivalentes entre si.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 20
2. Propriedades dos Circuitos Combinatórios
Definição 2.2 - Diz-se que dois circuitos combinatórios, 
cada um dos quais tendo as entradas x1, x2, ..., xn e uma 
saída única, são equivalentes, se para os mesmos valo-
res de entrada suas saídas produzem o mesmo valor.
Nota 2.3 - Se definirmos uma relação R sobre um con-
junto de circuitos combinatórios por meio da regra 
C1RC2 se C1 e C2 são equivalentes (no sentido da 
definição 2.2) R é uma relação de equivalência:
Nota 2.4 Cada classe de equivalência consiste de um con-
junto de circuitos combinatórios mutuamente equiva-
lentes. 
11
11
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 21
2. Propriedades dos Circuitos Combinatórios
Nota 2.5 - Circuitos equivalentes podem não ter o mesmo número 
de portas (para efeitos práticos é desejável o mínimo possível).
Nota 2.6 - Segue que circuitos combinatórios são equivalentes se 
as expressões Booleanas que os representam são iguais (ou 
podem ser transformadas para ficarem iguais).
a
b
~(a  b)
= ~a  ~b = ~(a  b)
~a  ~ba
b
a
b
a
b
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 22
2. Propriedades dos Circuitos Combinatórios
Teorema 2.2 - Sejam C1 e C2 circuitos combinatórios re-
presentados, respectivamente, pelas expressões Booleanas 
X1 = X1(x1, x2, ... , xn) e X2 = X2(x1, x2, ... , xn). Então C1 e C2
são equivalentes se e somente se X1 = X2.
– O valor X1(a1, a2, ... , an) [ou X2(a1, a2, ... , an)] para ai  Z2 é 
a saída para o circuito C1 [ou C2] para entradas a1, a2,..., an.
– De acordo com a definição 2.2:
» Os circuitos C1 e C2 são equivalentes se e somente se eles 
tem as mesmas saídas X1(a1, a2, ... , an) e X2(a1, a2, ... , an) 
para todas as possíveis entradas a1, a2, ... , an. 
» Assim C1 e C2 são equivalentes se e somente se:
X1(a1, a2, ... , an) = X2(a1, a2, ... , an) para todo ai  Z2
12
12
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 23
3. Álgebras Booleanas
Definição 3.1 - Uma Álgebra Booleana B consiste em um 
conjunto S contendo pelo menos dois elementos distin-
tos (denotados por 0 e 1),  dois  operadores  binários,  “+”
e  “.”,  e  um  operador  unário  “~”,  constituindo  uma  sêx-
tupla B = <S, + , . , ~ , 0 , 1> sobre S que satisfaz:
a) Lei Associativa (para todo x, y, z  S)
(x + y) + z = x + (y + z) e (x . y) . z = x . (y . z)
b) Lei Comutativa (para todo x, y, z  S)
x + y = y + x e x . y = y . x
c) Lei Distributiva (para todo x, y, z  S)
x.(y+z) = (x.y)+(x.z) e x+(y.z) = (x+y).(x+z)
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 24
3. Álgebras Booleanas
d) Lei da Identidade ( x  S): x + 0=x e x . 1=x
e) Complemento ( x  S): x+~x=1 e x.~x=0
Exemplo 3.1 - A  sêxtupla  “(Z2, , , ~, 0, 1)”  pelo  
Teorema 2.1 é uma Álgebra Booleana, onde:
– Z2 = {0,1}, sendo que são meros símbolos que não 
guardam relação com os números 0 e 1.
– As triplas de operadores (+,.,~) e (,,~) são equiva-
lentes.
– “a  .  b”  denota-se  usualmente  por  “ab”.  O  operador  
“.”  tem  precedência  sobre  “+”.
13
13
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 25
3. Álgebras Booleanas
Exemplo 3.2 - Seja U o conjunto universo e seja S = 
P(U) o conjunto Potência de U.
» Se definimos as seguintes 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)
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 26
3. Álgebras Booleanas
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
14
14
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 27
3. Álgebras Booleanas
Ainda Exemplo 3.2 - Sejam X, Y e Z subconjuntos de 
S. As propriedades (a) a (e) da definição 3.1 passam 
a ser as seguintes propriedades de conjuntos:
a) Lei Associativa [para todo X, Y, Z  S, onde S = P(U)]
(X  Y)  Z = X  (Y  Z)
(X  Y)  Z = X  (Y  Z)
b) Lei Comutativa (para todo X, Y, Z  S)
X  Y = Y  X e X  Y = Y  X
c) Lei Distributiva (para todo X, Y, Z  S)
X  (Y  Z) = (X  Y)  (X  Z)
X  (Y  Z) = (X  Y)  (X  Z)
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 28
3. Álgebras Booleanas
d) Lei da Identidade (para todo X  S)
X Ø = X e X  U = X
e) Lei do Complemento (para todo X  S)
X  X = U e X  X = Ø
Teorema 3.1 - Em uma Álgebra Booleana, o 
elemento ~x da definição 3.1 é único.
– Especificamente se x + y = 1 e xy = 0, então y = ~x.
Definição 3.2 - Em uma Álgebra Booleana o 
elemento ~x é denominado complemento de x.
15
15
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 29
3. Álgebras Booleanas
Estamos agora em condições de derivar outras propriedades 
importantes das Álgebras Booleanas.
Teorema 3.2 - Seja B = (S, +, ., ~, 0, 1) uma 
Álgebra Booleana. Então valem as seguintes 
propriedades:
a) Lei Idempotente (para todo x  S)
x + x = x e x . x = x
b) Lei das Fronteiras Superiores e Inferiores (para todo x  S)
x + 1 = 1 e x . 0 = 0
c) Lei da Absorção (para todo x, y  S)
x + x . y = x e x . (x + y) = x
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 30
3. Álgebras Booleanas
d) Lei da Involução (para todo x  S)
~(~x) = x
e) Lei do 0 e do 1
~0 = 1 e ~1 = 0
f) Lei de De Morgan (para todo x, y  S)
~(x + y) = ~x . ~y e ~(x . y) = ~x + ~y
Exemplo 3.3 - Conforme mostrado no exemplo 3.2, se 
U é um conjunto, P(U) associado a alguns operado-
res é uma Álgebra Booleana, para a qual:
(X  Y) = X  Y e (X  Y) = X  Y
O teorema 3.2 mostra que estas equações são consequências de 
outras Leis já demonstradas.
16
16
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 31
3. Álgebras Booleanas
Definição 3.3 - É provável que já se tenha notado que 
as equações envolvendo elementos da Álgebra 
Booleana aparecem aos pares. Estes pares são ditos 
duais. Exemplo, Lei da identidade:
x + 0 = x e x . 1 = x
– O dual de expressões da Álgebra Booleana é obtido 
substituindo 0 por 1 , 1 por 0, + por . e . por +.
Exemplo: o dual de ~(x + y) = ~x . ~y é ~(x . y) = ~x + ~y
Teorema 3.3 - O dual de um teorema sobre uma 
Álgebra Booleana também é um teorema.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 32
4. Álgebras Booleanas: Outras Definições
Definição 4.1 Consideremos as proposições vistas em 
Lógica Proposicional. Seja uma expressão de duas 
variáveis proposicionais. Então sua tabela da verdade 
define  uma  função  “f”  tal  que:  f:{V,F}2  {V,F}
Exemplo 4.1:
Note que: 1-)  Neste  exemplo  “f(a,b)  =  a”.
2-) Podemos generalizar este conceito para n variáveis 
proposicionais: f:{V,F}n  {V,F}
a b f 
V V V 
V F V 
F V F 
F F F 
17
17
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 33
4. Álgebras Booleanas: Outras Definições
3-) A função associada a uma tautologia é uma aplicação:
f:{V,F}n  {V}
4-) A função associada a uma contradição (absurdo) é 
uma aplicação:
f:{V,F}n  {F}
5-) Sabe-se que é possível construir a Tabela da Verdade 
para  quaisquer  sentenças  proposicionais  “p”  ou  “q”,  
compostas  de  “n”  variáveis  proposicionais.  A  função  
associada a estas sentenças está definida por sua Tabela 
da Verdade. Se  “p”e  “q”  têm  a  mesma  Tabela  da  
Verdade elas definem a mesma função. Então podemos 
escrever: “p  =  q”      em  vez  de        “p            q”
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 34
4. Álgebras Booleanas: Outras Definições
6-)  A  propriedade  da  “igualdade”  entre  sentenças  propo-
sicionais estabelece uma relação de equivalência entre 
as sentenças que possuem a mesma Tabela da Verdade 
(ver Teorema 2.2.):
É  imediato  verificar  que  a  “igualdade”obedece  às  proprie-
dades reflexiva, simétrica e transitiva, portanto é uma 
relação de equivalência.
Esta relação de equivalência particiona o conjunto (infini-
to)  de  sentenças  de  “n”  variáveis  em  um  conjunto  de  
Classes de Equivalência (CE={Ci}).
18
18
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 35
4. Álgebras Booleanas: Outras Definições
7-) Se n = 2 há 16 classes de equivalência:
C. E. = {C0, C1, ... , C15}
p
F
F
V
V
q
F
V
F
V
C2
F
F
V
F
C0
F
F
F
F
C1
F
F
F
V
C3
F
F
V
V
C4
F
V
F
F
C5
F
V
F
V
C6
F
V
V
F
C7
F
V
V
V
C10
V
F
V
F
C8
V
F
F
F
C9
V
F
F
V
C11
V
F
V
V
C12
V
V
F
F
C13
V
V
F
V
C14
V
V
V
F
C15
V
V
V
V
122:  nmObs
TautologiaAbsurdo (contradição)
p q. + ~p~q~+~ ~.
 

© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 36
4. Álgebras Booleanas: Outras Definições
8-) Até agora estamos utilizando apenas dois operadores 
(conectivos)  binários  “ e ”, e um operador unário 
“~”: Podemos definir novos operadores? Quantos?
Para duas variáveis o número de operadores é igual a 16, 
que é o número de Classes de Equivalência.
Por  exemplo:  a  “disjunção  exclusiva”  (“ou  exclusivo”  -
) é uma nova operação (que até o momento não 
havia aparecido).
Pode-se resumir estes conceitos na definição de um outro 
tipo de estrutura Booleana (definição 4.2 - a seguir).
19
19
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 37
4. Álgebras Booleanas: Outras Definições
Definição 4.2- A sêxtupla ({C.E.}, , , ~, Ft, Vt) 
é uma Álgebra Booleana, onde:
– {C. E.} = {C0, C1, ... , Cm} é o conjunto das classes 
de  equivalência  possíveis  para  “n”  variáveis  lógicas.
– Ft = C0 = Classe de Equivalência correspondente às 
Contradições.
– Vt = Cm = Classe de Equivalência correspondente às 
Tautologias.
– A estrutura da Álgebra de Boole da lógica de propo-
sições permite que suas transformações sejam apli-
cadas aos circuitos lógicos.
122  nm
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 38
4. Álgebras Booleanas: Outras Definições
(Duas Variáveis Proposicionais - 16 Classes de Equivalência)
C0(FFFF)
C1(FFFV)C8(VFFF)
C12(VVFF)
C14(VVVF)
C15(VVVV)
C7(FVVV)
C3(FFVV)
C13(VVFV) C11(VFVV)
C5(FVFV)C10(VFVF)
C4(FVFF) C2(FFVF)
C9(VFFV)
C6(FVVF)
[Contradições]
[Tautologias]
[Contingências][Contingências]
20
20
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 39
4. Álgebras Booleanas: Outras Definições
Definição 4.2.a - Átomo ou Elemento Atômico -
Dada a Álgebra de Boole B = (S, , , ~, 0t, 1t) 
chama-se Átomo a  sk  S (sk  0t) tal que para 
si S ocorre: si  sk = 0t ou si  sk = sk 
Ex: Átomos da definição 4.2: {C1, C2, C4, C8}
Teorema 4.1 - Dada uma Álgebra Booleana B = (S, 
, , ~, 0t, 1t) cujos átomos são {si, sj, ..., sk}  sm 
 S pode expressar-se de maneira única como uma 
soma de átomos:
sm  S {si, sj, ..., sk} (0  i, j, ..., k  n)
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 40
4. Álgebras Booleanas: Isomorfismo
Definição 4.3 - 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 são 
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éiapara  “classificar”  exemplos  
de estruturas, associando-se as que são isomorfas.
21
21
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 41
4. Álgebras Booleanas: Isomorfismo
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}
Ø
{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 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 42
4.1.  Reticulados  (“Lattices”)
Sabe-se da teoria de Relações que:
– Sendo S um conjunto e R uma relação de ordem 
parcial ao par (S, ) chama-se conjunto parcialmente
ordenado, onde  é o símbolo de ordenação parcial.
– O grafo de um conjunto parcialmente ordenado, 
denomina-se Diagrama de Hasse, sendo uma 
representação simplificada para este.
sk
sjsi
sn
(S, )
22
22
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 43
4.1.  Reticulados  (“Lattices”)
Dado o par (S,  ) - Definições:
4.4.1. Limite Máximo (LM) - Dado sn
 S, sn = LM se  si  S  si  sn.
4.4.2. limite mínimo (lm) - Dado s1 
S, s1 = lm se  si  S  s1  si.
=LM
= lm
sn
si
s1
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 44
4.1. Reticulados
Dado P = {pi,pj,pk} e P  S - Definições:
4.4.3. Fronteira Superior (FS) - Um 
dado sn  S é FS de P se e somente se 
para  pk  P houver pksn. Onde sn 
obrigatoriamente a P (pode pertencer).
4.4.4. Fronteira Superior mínima 
(FSm) - Um dado sn  S é FSm de P 
se e somente se sn é FS de P e para 
si = FS de P houver snsi. Onde sn 
obrigatoriamente a P (pode pertencer).
=FS
= fi
sn
pj
s1
pi
pk
=fiM
=FSm
23
23
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 45
4.1. Reticulados
Exemplo 4.2.a - Dado S ao lado:
1) Limite Máximo (LM) - Não existe sn 
S de modo que para  si  S  sisn
(os elementos 5 e 6 não se comparam).
2) Para P1 = {5,6}  S:
– Fronteira Superior (FS) - Não existe, dado 
que não há sn  S de modo que para  pk 
 P ocorra pksn.
– Fronteira Superior mínima (FSm) - Não 
existe dado que não existe nenhum 
elemento de S que seja FS de P.
4
1
3
5
2
6
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 46
4.1. Reticulados
Exemplo 4.2.a - Dado S ao lado:
3) Para P1 = {1,2}  S:
– Fronteira Superior (FS) - Existem 4. São 5 
para cada elemento {1} e {2}:
– 11; 13; 14; 15 e 16
– 22; 23; 24; 25 e 26
– Comuns: 3, 4, 5 e 6.
– Fronteira Superior mínima (FSm) = 3 = sn. 
O único elemento que satisfaz a condição 
de FSm ( sn, snsi) é o 3.
4
1
3
5
2
6
24
24
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 47
4.1. Reticulados
Exemplo 4.2.a - Dado S ao lado:
4) Para P1 = {2,6}  S:
– Fronteira Superior (FS) - São 5 para o ele-
mento {2} e uma para o elemento {6}:
– 22; 23; 24; 25 e 26
– 66
– Comum: apenas o elemento 6.
– Fronteira Superior mínima (FSm) = 6 = sn. 
Já que á a única Fronteira Superior si
candidata a FSm, e vale snsi.
4
1
3
5
2
6
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 48
4.1. Reticulados
Dado P = {pi,pj,pk} e P  S - Definições:
4.4.5. fronteira inferior (fi) - Um dado 
s1  S é fi de P se e somente se para 
pi  P houver s1pi. Onde s1 obriga-
toriamente a P (pode pertencer).
4.4.6. fronteira inferior Máxima (fiM)
- Um dado s1  S é fiM de P se e so-
mente se s1 é fi de P e para  si = fi de 
P houver s1si. Onde s1 obrigatoria-
mente a P (pode pertencer).
=FS
= fi
sn
pj
s1
pi
pk
=fiM
=FSm
25
25
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 49
4.1. Reticulados
Exemplo 4.2.b - Dado S ao lado:
1) Limite Mínimo (lm) - Não existe s1 
S de modo que para  si  S  s1si
(os elementos 1 e 2 não se comparam).
2) Para P1 = {1,2}  S:
– fronteira inferior (fi) - Não existe, dado 
que não há s1  S de modo que para  pi 
P ocorra s1pi.
– fronteira inferior Máxima (fiM) - Não 
existe dado que não existe nenhum 
elemento de S que seja fi de P.
4
1
3
5
2
6
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 50
4.1. Reticulados
Exemplo 4.2.b - Dado S ao lado:
3) Para P1 = {5,6}  S:
– fronteira inferior (fi) - São 5 para {5} e 
{6} mas apenas 4 comuns:
– 15; 25; 35; 45 e 55
– 16; 26; 36; 46 e 66
– Comuns: 1, 2, 3 e 4.
– fronteira inferior Máxima (fiM) = 4 = s1. O 
único elemento que satisfaz a condição de 
fiM ( si, s1si) é o 4.
4
1
3
5
2
6
26
26
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 51
4.1. Reticulados
Exemplo 4.2.b - Dado S ao lado:
4) Para P1 = {2,6}  S:
– fronteira inferior (fi) - São 5 para o ele-
mento {6} e uma para o elemento {2}:
– 66; 46; 36; 26 e 16
– 22
– Comum: apenas o elemento 2.
– fronteira inferior Máxima (fiM) = 2 = s1. 
Já que á a única fronteira inferior si
candidata a fiM, e vale sis1.
4
1
3
5
2
6
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 52
4.1. Reticulados
Decorrência das Definições 4.4.1 e 4.4.2 - Dado
um conjunto parcialmente ordenado (S, ), o li-
mite mínimo (lm) e o Limite Máximo (LM), se 
existirem, são únicos.
Decorrência das Definições 4.4.4 e 4.4.6 - Dado 
o subconjunto P  S, sendo S um conjunto par-
cialmente ordenado (S, ), a fronteira inferior 
Máxima (fiM) e a Fronteira Superior mínima 
(FSm) se existirem, são únicas.
27
27
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 53
4.1. Reticulados
Definição 4.1 - Reticulado - É um conjunto par-
cialmente ordenado (S, ), de modo que, para 
 si  S e  sk  S o subconjunto P = {si, sk} 
possui uma fronteira inferior Máxima (fiM) e 
uma Fronteira Superior mínima (FSm).
Definição 4.2 - Reticulado Distributivo - É um 
reticulado que obedece às propriedades:
si  (sj  sk) = (si  sj)  (si  sk)
si (sj  sk) = (si  sj)  (si  sk)
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 54
4.1. Reticulados
Definição 4.3 - Reticulado Complementado - É 
um reticulado onde  si  S existe ~si tal que:
si  ~ si = lm e si  ~ si = LM
Teorema 4.2 - Se um reticulado é distributivo e 
complementado ao mesmo tempo, então ~si é 
único.
Operação que calcula
a fiM do subconjunto
dos dois elementos.
Operação que calcula
a FSm do subconjunto
dos dois elementos.
28
28
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 55
4.1. Reticulados
Exemplo 4.3 - Um reticulado é uma estrutura com uma 
ordem parcial envolvida. Portanto pode-se representar 
por um Diagrama de Hasse.
S = {1,2,5,7,10,14,35,70} e R = MDC (s1,s2) = s1
[R vai implicar em que mmc(s1,s2) = s2] 
72
5
70
10 35
10
1
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 56
4.1. Reticulados
Definição 4.4 - Um reticuladoque é distributivo e 
complementado define uma Álgebra Booleana:
B = (S, , , ~, , )
onde:  = LM (as vezes denotado por: {S},S,)
 = lm (as vezes denotado por: ,�,I,0
 e  são únicos e   
De modo que para  si  P  S e  sk  P  S:
 = fiM(si, sk)
 = FSm(si, sk)
dado si  ~ si é único
29
29
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 57
4.1. Reticulados
Álgebra Booleana como da def. 4.4- Propriedades:
P1 - Limite Máximo e limite mínimo:
a) si  lm = lm e si  LM = si
b) si  LM = LM e si  lm = si
P2 - Complemento: si si = lm e si  si = LM
P3 - Distributiva:
a) si  (sl  sk) = (si  sl)  (si  sk)
b) si (sl  sk) = (si  sl)  (si  sk)
P4- Comutativa: si sk = sk si e si  sk = sk  si
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 58
4.1. Reticulados
Teorema 4.3 - Seja uma Álgebra Booleana como 
a da definição 4.4. Para esta vale:
Se si  sk = lm E si  sk = LM Então sk = ~si
Prova: sk  lm = sk (P1b)  sk = sk  lm
sk = sk si si(P2a) 
sk = (sk si) sk si(P3b)
sk = (si sk) sk si(P4b)
sk = LM sk si(pelas hipóteses)
sk = sk si LM (P4a)
sk = sk si(P1a) [1]
30
30
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 59
4.1. Reticulados
Prova (continuação):
~si  lm = ~si (P1b)  ~si = si  lm
~si = ~si si sk(pelas hipóteses) 
~si = (~si si) si sk(P3b)
~si = LM si sk(P2b)
~si = si sk LM (P4a)
~si = si sk (P1a)
~si = sk si(P4b) [2]
Portanto de [1] e de [2] vem:
[1] = sk sisk = ~si = sk si [2] C.Q.D.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 60
4.1. Reticulados
Teorema 4.4 - Seja uma Álgebra Booleana como 
a da definição 4.4. Para esta valem:
1-) Se si  sk = si Então si  sk = sk
2-) Se si  sk = sk Então si  sk = si
3-) Se si  sk = sk Então ~si  sk = LM
4-) Se ~si  sk = LM Então si  sk = sk
5-) Se ~si  sk = LM Então si  ~sk = lm
6-) Se si  ~sk = lm Então ~si  sk = LM
31
31
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 61
4.2. Subálgebras
Definição 4.5 - Uma  operação  “fechada”  sobre  
elementos de um conjunto S é uma operação 
que devolve apenas valores que pertencem a S. 
Definição 4.6 - A Álgebra Booleana B1 = (P, , , 
~, , ) é uma subálgebra de B = (S, , , ~, , 
) se ocorrer:
P  S e  = LM  P e  = lm  P
Para  si  P e  sk  P as operações:
si  sk e si  sk e ~si são fechadas em P
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 62
4.2. Subálgebras
Exemplo 4.4 - Juntando ao exemplo 4.3 as 
definições: (s1  s2) = MDC (s1,s2); (s1  s2) = 
mmc(s1,s2); ~si = 70/si; = lm = 1;  = LM = 70. 
Tem-se que a Álgebra Booleana B = (S, , , ~, 
, ) pode ter as seguintes subálgebras:
Bi = ({1,70} , , , ~, 1, 70)
Bj = ({1,2,35,70} , , , ~, 1, 70)
Bk = ({1,5,14,70} , , , ~, 1, 70)
Bl = ({1,7,10,70} , , , ~, 1, 70)
32
32
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 63
4.2. Subálgebras
Teorema 4.5 - Toda subálgebra de uma Álgebra 
Booleana é também uma Álgebra Booleana.
Teorema 4.6 - A partir das propriedades LM e lm, 
complemento, distributiva e comutativa (P1,P2,P3
e P4) pode-se demonstrar as seguintes:
P5 - Idempotência - si  si = si e si  si = si
P6 - Associativa - si  (sj  sk) = (si  sj)  sk
P7 - Absorção - si  (si  sk) = si ; si  (si  sk) = si
P8 - Involução - ~(~si) = si
P9 - De Morgan - ~(sjsk) = ~sj~sk ; ~(sjsk) = ~sj~sk
P10 - Modularidade - si[sj(sisk)] = si; (sisj) (sisk) 
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 64
4.2. Subálgebras
Teorema 4.7 - Se as operações ,  e ~ de uma 
Álgebra Booleana satisfazem as propriedades de 
P1 a P10 estas operações serão fechadas em P 
S, para  = LM  P e  = lm  P se:
 e ~ são fechadas em P 
ou
 e ~ são fechadas em P
Resultado útil: Para provar que Bi é uma subálge-
bra de B basta provar que duas das três opera-
ções são fechadas.
33
33
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 65
5. Álgebra de Chaveamento
Definição 5.1 - 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 Booleana, 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 a chaves abertas.
– 1t = fm = Função correspondente a chaves fechadas.
n
m 221
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 66
5. Álgebra de Chaveamento
A sêxtupla  “({F.C.}, , , ~, 0t, 1t)”  é  uma  Álgebra 
Booleana, onde (continuação):
–  é  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 P1 a P10 enunciadas 
anteriormente.
Em vista disto pode-se encontrar o reticulado 
distributivo e complementado que a representa, 
onde fi + fj = FSm(fi, fj) e fi . fj = fiM(fi, fj).
34
34
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 67
5. Á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 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 68
5. Álgebra de Chaveamento
No diagrama de Hasse do reticulado 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  “+”  (FSm) 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  “.”  (fiM) sobre as funções:
f7 = 0111, f11 = 1011, f13 = 1101 e f14 = 1110
35
35
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 69
5. Álgebra de Chaveamento: Funções para duas variáveis
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
~  ~.
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 nodiagrama de Hasse uma representação mais fácil de ler.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 70
5. Á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
36
36
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 71
5. Álgebra de Chaveamento
Sob esta nova representação do diagrama de Hasse:
[1] f1 = x1.x2, f2 = ~x1.x2, f4 = x1.~x2 e f8 = ~x1.~x2
Da definição de á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 {f1, f2, f4, f8} não 
podem ser obtidos pela operação de FSm sobre 
nenhuma outra função e denominam-se mintermos.
[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 fiM sobre nenhuma 
outra função e denominam-se maxtermos.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 72
5. Á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)
37
37
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de Álgebra Booleana > PCS 2215 Sistemas Digitais I 73
Bibliografia
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.
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.
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.