6.4 Álgebras Booleanas Finitas

Prévia do material em texto

INE5403
FUNDAMENTOS DE
MATEMÁTICA DISCRETA
PARA A COMPUTAÇÃO
PROF. DANIEL S. FREITAS
UFSC - CTC - INE
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.1/51
6 - RELAÇÕES DE ORDENAMENTO
6.1) Conjuntos parcialmente ordenados (posets)
6.2) Extremos de posets
6.3) Reticulados
6.4) Álgebras Booleanas Finitas
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.2/51
RETICULADOS (P (S),⊆)
Vamos restringir nossa atenção aos reticulados do tipo (P (S),⊆),
onde S é um conjunto finito.
Muitas propriedades que não valem para reticulados em geral.
Por isto, são mais fáceis de trabalhar
Têm papel importante em muitas aplicações na Ciência da
Computação:
construção de representações lógicas para os circuitos do
computador
estudo de cifradores simétricos, na Criptografia
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.3/51
RETICULADOS (P (S),⊆)
Teorema: Sejam S1 = {x1, x2..., xn} e S2 = {y1, y2..., yn} dois
conjuntos finitos quaisquer com n elementos.
Então os reticulados (P (S1),⊆) e (P (S2),⊆) são isomórficos
ou seja, seus diagramas de Hasse são idênticos
Prova: arranjar os conjuntos e definir a seguinte f :
subconj. A
S1: x1 x2 . . . xn S1: x1
︷ ︸︸ ︷
x2 x3 x4 . . . xn
l l l
S2: y1 y2 . . . yn S2: y1 y2 y3 y4︸ ︷︷ ︸ . . . yn
subconj. f(A)
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.4/51
RETICULADOS (P (S),⊆)
Prova (cont.):
f(A): elementos de S2 que correspondem aos elementos de A
f : bijeção de subconjuntos de S1 para subconjuntos de S2
além disto, se A e B são subconjuntos quaisquer de S1:
A ⊆ B ⇔ f(A) ⊆ f(B)
Logo, os reticulados (P (S1),⊆) e (P (S2),⊆) são isomórficos.
�
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.5/51
RETICULADOS (P (S),⊆)
Logo: a condição de poset do reticulado (P (S),⊆) é determinada
pelo número |S| e não depende da natureza dos elementos de S.
Exemplo: Sejam os posets:
(P (S),⊆) , S = {a, b, c}: (P (T ),⊆) , T = {2, 3, 5}:
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.6/51
RETICULADOS (P (S),⊆)
Note que os 2 reticulados são isomórficos, sendo um possível
isomorfismo f : P (S)→ P (T ) dado por:
f({a}) = {2}
f({b}) = {3}
f({c}) = {5}
f({a, b}) = {2, 3}
f({b, c}) = {3, 5}
f({a, c}) = {2, 5}
f({a, b, c}) = {2, 3, 5}
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.7/51
RETICULADOS (P (S),⊆)
Conclusão: para cada n = 0, 1, 2, . . ., há apenas um tipo de
reticulado com a forma (P (S),⊆)
o qual depende apenas de n (e não de S)
e tem 2n elementos (= nro de possíveis subconjuntos de S).
Pode-se, portanto, tomar um diagrama de Hasse genérico para
(P (S),⊆) e rotulá-lo assim:
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.8/51
RETICULADOS (P (S),⊆)
Rotulando desta forma, este diagrama serve para descrever os 2
reticulados anteriores.
Melhor: para descrever um reticulado (P (S),⊆) originado de
qualquer conjunto S com 3 elementos.
Se o diagrama de Hasse do reticulado correspondente a um
conjunto com n elementos é rotulado desta forma (seqüências de 0s
e 1s de comprimento n), o reticulado resultante é chamado de Bn.
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.9/51
PROPRIEDADES DO ORDENAMENTO PARCIAL EM Bn
Sejam 2 elementos de Bn: x = a1a2 . . . an e y = b1b2 . . . bn.
Então:
x ≤ y se e somente se ak ≤ bk para k = 1, 2, . . . , n
x ∧ y = c1c2 . . . cn , onde ck = min{ak, bk}
x ∨ y = d1d2 . . . dn , onde dk = max{ak, bk}
o complemento de x é dado por x′ = z1z2 . . . zn , onde:

zk = 1 se xk = 0
zk = 0 se xk = 1
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.10/51
PROPRIEDADES DO ORDENAMENTO PARCIAL EM Bn
Estas afirmações podem ser confirmadas pela observação de que
(Bn,≤) é isomórfico a (P (S),⊆):
x, y ∈ Bn correspondem a subconjuntos A e B de S
então:
x ≤ y corresponde a A ⊆ B
x ∧ y corresponde a A ∩B
x ∨ y corresponde a A ∪B
x′ corresponde a A
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.11/51
RETICULADOS Bn
Diagramas de Hasse dos reticulados B0, B1, B2 e B3:
n=0: •
n=1: n=2: n=3:
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.12/51
RETICULADOS Bn
Todo reticulado (P (S),⊆) é isomórfico com Bn, onde n =| S |.
Outros reticulados também podem ser isomórficos com algum Bn.
Possuindo todas as propriedades especiais que o Bn possui.
Exemplo: D6 (divisores de 6, ordem parcial de divisibilidade).
Isomorfismo f : D6 → B2 dado por:
f(1) = 00 f(2) = 10 f(3) = 01 f(6) = 11
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.13/51
ÁLGEBRAS BOOLEANAS
Em geral: um reticulado finito é chamado de Álgebra Booleana se
ele for isomórfico com algum Bn.
Portanto:
todo Bn é uma Álgebra Booleana
assim como todo reticulado (P (S),⊆).
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.14/51
ÁLGEBRAS BOOLEANAS
Exemplo: reticulados D20 e D30 (divisores de 20 e 30, ordem parcial
de divisibilidade):
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.15/51
ÁLGEBRAS BOOLEANAS
Exemplo (cont.):
D20 tem 6 elementos:
6 6= 2n
D20 não é uma Álgebra Booleana
Já o poset D30 tem 8 elementos:
8 = 23 ⇒ chance de ser Álgebra Booleana
note que D30 é isómórfico com B3
· com isomorfismo f : D30 → B3 dado por:
f(1) = 000 f(2) = 100 f(3) = 010 f(5) = 001
f(6) = 110 f(10) = 101 f(15) = 011 f(30) = 111
portanto, D30 é uma Álgebra Booleana. �
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.16/51
ÁLGEBRAS BOOLEANAS
CONCLUSÃO:
Se um reticulado L não contém 2n elementos, sabemos que L
não pode ser uma Álgebra Booleana.
Se | L |= 2n, então L pode ou não ser uma Álgebra Booleana.
Se L for pequeno, pode-se tentar comparar o seu diagrama de
Hasse com o de Bn
no entanto, esta técnica pode não ser prática se L for grande
· aí tenta-se construir diretamente um isomorfismo com Bn
ou com (P (S),⊆)
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.17/51
ÁLGEBRAS BOOLEANAS GRANDES
Para ver se um dado reticulado Dn (n grande) é Álgebra Booleana:
Teorema: Seja n = p1p2 . . . pk onde os pi são primos distintos.
Então Dn é uma Álgebra booleana.
Prova:
Seja S = {p1, p2, . . . , pk}.
Todo divisor de n deve ser da forma aT , onde:
aT é o produto dos primos em algum subconjunto T de S (nota: a∅ = 1)
Aí, se V e T são subconjuntos de S:
V ⊆ T se e somente se aV | aT
aV ∩T = aV ∧ aT (=MDC(aV , aT ))
aV ∪T = aV ∨ aT (=MMC(aV , aT ))
Logo, f : P (S)→ Dn, dada por f(T ) = aT , é um isomorfismo de P (S) para Dn
Então, como (P (S),⊆) é uma Álgebra Booleana, Dn também o é. �
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.18/51
ÁLGEBRAS BOOLEANAS GRANDES
Exemplo:
210 = 2.3.5.7 ⇒ D210 é Álgebra Booleana
66 = 2.3.11 ⇒ D66 é Álgebra Booleana
646 = 2.17.19 ⇒ D646 é Álgebra Booleana
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.19/51
ÁLGEBRAS BOOLEANAS GRANDES
Outros casos de reticulados L grandes:
tentar mostrar que L não é uma Álgebra Booleana
mostrando que o ordenamento parcial de L não apresenta as
propriedades necessárias.
Exemplo: uma Álg. Booleana é sempre isomórfica com algum Bn e,
portanto, com algum reticulado (P (S),⊆).
Logo, se o reticulado L for uma Álgebra Booleana:
ele deverá ser limitado (deverá possuir LUB e GLB)
cada um dos seus elementos deverá possuir um complemento
Ou seja, para que L seja reticulado:
L deverá ter um maior elemento I (⇔ S) e um menor
elemento O (⇔ ∅)
todo elemento x de L deverá ter um complemento x′
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.20/51
ÁLGEBRAS BOOLEANAS
O Princípio da Correspondência entre posets ajuda a estabelecer
propriedades das Álgebras Booleanas.
Teorema (REGRA DA SUBSTITUIÇÃO):
Toda fórmula que envolve ∪ e ∩, ou que vale para subconjuntos
arbitrários de um conjunto S, continuará a valer para elementos
arbitrários de uma Álgebra Booleana L se:
∩ for substituído por ∧
∪ for substituído por ∨Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.21/51
ÁLGEBRAS BOOLEANAS
Exemplo: Se x, y e z são elementos de uma Álgebra Booleana
qualquer L, valem:
(a) (x′)′ = x −→ involução
(b) (x ∧ y)′ = x′ ∨ y′ −→ 1a. lei de De Morgan
(c) (x ∨ y)′ = x′ ∧ y′ −→ 2a. lei de De Morgan
Isto vale para Álgebras booleanas, pois sabemos que as fórmulas:
(a’) (A) = A
(b’) (A ∩B) = A ∪B
(c’) (A ∪B) = A ∩B
valem para subconjuntos arbitrários A e B de um conjunto S.
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.22/51
PROPRIEDADES DAS ÁLGEBRAS BOOLEANAS (L,≤)
De maneira similar, podemos listar outras propriedades que devem
valer em qualquer Álgebra Booleana em conseqüência da regra de
substituição.
Na tabela a seguir:
x, y e z são elementos arbitrários em L
A, B e C são subconjuntos arbitrários de S
I e O denotam o maior e o menor elemento de L,
respectivamente.
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.23/51
PROPRIEDADES DAS ÁLGEBRAS BOOLEANAS (L,≤) (1/2)
Algumas propriedades básicas Propriedade correspondente para
de uma Álgebra Booleana (L,≤) subconjuntos de um conjunto S
1) x ≤ y se e somente se x ∨ y = y 1’) A ⊆ B se e somente se A ∪B = B
2) x ≤ y se e somente se x ∧ y = x 2’) A ⊆ B se e somente se A ∩B = A
3) (a) x ∨ x = x 3’) (a) A ∪A = A
(b) x ∧ x = x (b) A ∩A = A
4) (a) x ∨ y = y ∨ x 4’) (a) A ∪B = B ∪A
(b) x ∧ y = y ∧ x (b) A ∩B = B ∩A
5) (a) x ∨ (y ∨ z) = (x ∨ y) ∨ z 5’) (a) A ∪ (B ∪ C) = (A ∪B) ∪ C
(b) x ∧ (y ∧ z) = (x ∧ y) ∧ z (b) A ∩ (B ∩ C) = (A ∩B) ∩ C
6) (a) x ∨ (x ∧ y) = x 6’) (a) A ∪ (A ∩B) = A
(b) x ∧ (x ∨ y) = x (b) A ∩ (A ∪B) = A
7) O ≤ x ≤ I, ∀x ∈ L 7’) ∅ ⊆ A ⊆ S, ∀A ∈ P (S)
8) (a) x ∨ O = x 8’) (a) A ∪ ∅ = A
(b) x ∧ O = O (b) A ∩ ∅ = ∅
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.24/51
PROPRIEDADES DAS ÁLGEBRAS BOOLEANAS (L,≤) (2/2)
Algumas propriedades básicas Propriedade correspondente para
de uma Álgebra Booleana (L,≤) subconjuntos de um conjunto S
9) (a) x ∨ I = I 9’) (a) A ∪ S = S
(b) x ∧ I = x (b) A ∩ S = A
10) (a) x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) 10’) (a) A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C)
(b) x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) (b) A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C)
11) Todo elemento x tem um único 11’) Todo elemento A tem um único
(a) x ∨ x′ = I (a) A ∪A = S
(b) x ∧ x′ = O (b) A ∩A = ∅
12) (a) O′ = I 12’) (a) ∅ = S
(b) I′ = O (b) S = ∅
13) (x′)′ = x 13’) A = A
14) (a) (x ∧ y)′ = x′ ∨ y′ 14’) (a) A ∩B = A ∪B
(b) (x ∨ y)′ = x′ ∧ y′ (b) A ∪B = A ∩B
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.25/51
PROPRIEDADES DAS ÁLGEBRAS BOOLEANAS (L,≤)
Talvez seja possível mostrar que um reticulado L não é Álgebra
Booleana mostrando que ele não possui alguma propriedade básica.
Exemplo: Mostre que o reticulado abaixo não é Álgebra Booleana:
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.26/51
PROPRIEDADES DAS ÁLGEBRAS BOOLEANAS (L,≤)
Exemplo (cont.):
Os elementos a e g são ambos complementos de c
ou seja, ambos satisfazem as propriedades 11(a) e 11(b) com
respeito ao elemento c.
Mas a propriedade estabelece que tal elemento deve ser único
em qualquer Álgebra booleana.
Logo, o reticulado dado não é uma Álgebra booleana. �
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.27/51
PROPRIEDADES DAS ÁLGEBRAS BOOLEANAS (L,≤)
Exemplo: Mostre que se p2 | n, onde p é um primo, então Dn não é
uma Álgebra Booleana.
suponha que p2 | n
então n = p2.q
mas p também é divisor de n, de modo que p ∈ Dn
se Dn é uma Álg. Booleana, p deve ter um complemento p′
de modo que MDC(p, p′) = 1 e MMC(p, p′) = n
daí temos que p.p′ = n
de modo que p′ = n/p = p.q
mas isto significa que MDC(p, p.q) teria que ser 1 (!!)
Logo, Dn não pode ser uma Álg. Booleana. �
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.28/51
PROPRIEDADES DAS ÁLGEBRAS BOOLEANAS (L,≤)
Na verdade, de acordo com um teorema já visto,
“Seja n = p1p2 . . . pk onde os pi são primos distintos. Então Dn
é uma Álgebra booleana”.
concluímos que:
Dn é uma Álgebra Booleana se e somente se nenhum primo
divide n mais do que uma vez.
Exemplo: 40 = 23.5 e 125 = 3.52
Então: nem D40 nem D125 podem ser Álgebras Booleanas.
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.29/51
ÁLGEBRAS BOOLEANAS
Final deste item.
Dica: fazer exercícios sobre Álgebras Booleanas...
Prof. Daniel S. Freitas - UFSC/CTC/INE/2008 – p.30/51
	large nullextsc {6 - Relações de ordenamento}
	large nullextsc {Reticulados $(P(S),subseteqnull)$}
	large nullextsc {Reticulados $(P(S),subseteqnull)$}
	large nullextsc {Reticulados $(P(S),subseteqnull)$}
	large nullextsc {Reticulados $(P(S),subseteqnull)$}
	large nullextsc {Reticulados $(P(S),subseteqnull)$}
	large nullextsc {Reticulados $(P(S),subseteqnull)$}
	large nullextsc {Reticulados $(P(S),subseteqnull)$}
	nullormalsize nullextsc {Propriedades do ordenamento parcial em $B_n$}
	nullormalsize nullextsc {Propriedades do ordenamento parcial em $B_n$}
	large nullextsc {Reticulados $B_n$}
	large nullextsc {Reticulados $B_n$}
	large nullextsc {Álgebras Booleanas}
	large nullextsc {Álgebras Booleanas}
	large nullextsc {Álgebras Booleanas}
	large nullextsc {Álgebras Booleanas}
	large nullextsc {Álgebras Booleanas grandes}
	large nullextsc {Álgebras Booleanas grandes}
	large nullextsc {Álgebras Booleanas grandes}
	large nullextsc {Álgebras Booleanas}
	large nullextsc {Álgebras Booleanas}
	nullormalsize nullextsc {Propriedades das Álgebras Booleanas $(L,leq )$}
	small nullextsc {Propriedades das Álgebras Booleanas $(L,leq )$null(1/2)}
	small nullextsc {Propriedades das Álgebras Booleanas $(L,leq )$null(2/2)}
	nullormalsize nullextsc {Propriedades das Álgebras Booleanas $(L,leq )$}
	nullormalsize nullextsc {Propriedades das Álgebras Booleanas $(L,leq )$}
	nullormalsize nullextsc {Propriedades das Álgebras Booleanas $(L,leq )$}
	nullormalsize nullextsc {Propriedades das Álgebras Booleanas $(L,leq )$}
	nullextsc {Álgebras Booleanas}