Exercícios de Reticulados

Prévia do material em texto

QUINTA LISTA DE EXERCI´CIOS – RETICULADOS E ETC
MATEMA´TICA DISCRETA II
Exerc´ıcio 1. Sejam (A,≤) um conjunto parcialmente ordenado e ≥= (≤)−1. Mostre que (A,≥) e´
conjunto parcialmente ordenado.
Exerc´ıcio 2. Seja (A,≤) um conjunto parcialmente ordenado. Em B = A×A, definimos
(a, x) � (b, y)⇔
{
a ≤ b e
(a = b ⇒ x ≤ y)
Esta e´ a chamada ordem lexicogra´fica. Mostre que � e´ ordem sobre B.
Exerc´ıcio 3. Tome a ordem usual em X = 0, 1, 2. Determine o digrama de Hasse da ordem lexi-
cogra´fica em X ×X.
Exerc´ıcio 4. Tome a ordem do “divide” em D(10). Determine o diagrama de Hasse da ordem lexi-
cogra´fica em D(10)×D(10).
Exerc´ıcio 5. Seja (A,≤) um conjunto parcialmente ordenado. Seja S = {x ∈ L : x ≤ a} para a ∈ L
fixado. Mostre que, se b e´ minimal de S, enta˜o b e´ minimal de A.
Exerc´ıcio 6. Seja (A,≤) um conjunto parcialmente ordenado. Mostre que todo subconjunto na˜o vazio
e finito de A admite minimal.
Exerc´ıcio 7. Seja (A,≤) um conjunto parcialmente ordenado. Suponha que S e T sa˜o subconjuntos
na˜o vazios de A tais que s = supS e t = supT . Mostre que x = sup {s, t} se, e somente se, x =
supS ∪ T .
Exerc´ıcio 8. Seja (L,∨,∧) um reticulado, mostre que x ∨ (y ∨ z) = sup {x, y, z}.
Exerc´ıcio 9. Seja (L,∨,∧) um reticulado. Mostre que todo finito na˜o vazio admite supremo e ı´nfimo.
Exerc´ıcio 10. Desenhe o diagrama de Hasse para as seguintes ordens parciais:
(1) S = {a, b, c} e ρ = {(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)}
(2) S = {a, b, c, d} e ρ = {(a, a), (b, b), (c, c), (d, d), (a, b), (a, c)}
(3) S = {∅, {a} , {a, b} , {c} , {a, c} , {b}} com o “⊆”.
Exerc´ıcio 11. Para o exerc´ıcio anterior, apresente os elementos mı´nimo, ma´ximo, minimais e maxi-
mais, se existirem.
Exerc´ıcio 12. Desenhe o diagrama de Hasse para {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17} com
a ordem do divide.
Exerc´ıcio 13. Considere o conjunto parcialmente ordenado (D(90), |) e determine seu diagrama de
Hasse. Calcule sup {6, 10}, inf {6, 10}, sup {30, 9} e inf {18, 45, 15}, justificando suas respostas.
Exerc´ıcio 14. Para cada um dos diagramas de Hasse abaixo, apresente todos os pares ordenados que
pertencem a` relac¸a˜o de ordem correspondente.
(1)
5
>>
>>
>>
>
��
��
��
�
3 4
1 2
(2)
d e f
a b c
(3)
5
4
��
��
��
�
>>
>>
>>
>
2
>>
>>
>>
> 3
��
��
��
�
1
(4)
g
��
��
��
��
e f
d
��
��
��
��
a b c
Exerc´ıcio 15. Determine as ta´buas para ∨ e ∧ dos itens do exerc´ıcio anterior, quando existir.
Date: Marc¸o de 2013.
1
QUINTA LISTA DE EXERCI´CIOS – RETICULADOS E ETC MATEMA´TICA DISCRETA II
Exerc´ıcio 16. Seja (S,�) um reticulado. Suponha que x � y. Mostre que
x ∨ (y ∧ z) � (x ∨ z) ∧ y .
Exerc´ıcio 17. A ta´bua abaixo foi deixada incompleta. A mesma da´ os valores de sup {x, y}, para x e
y em um conjunto S, onde (S,≤) e´ conjunto parcialmente ordenado.
sup a b c d e f
a e a e e a
b d d e b
c d e c
d e d
e e
f
(1) Preencha o resto da tabela.
(2) Qual e´ o mı´nimo e o ma´ximo de S?
(3) Mostre que f ≤ c ≤ d ≤ e.
(4) Desenhe o diagrama de Hasse para (S,≤).
Exerc´ıcio 18. Seja n ∈ N \ {0, 1}. Mostre que sa˜o equivalentes:
(1) D(n) e´ a´lgebra booleana com a ordem do divide,
(2) na˜o existe p ∈ N, primo, tal que p2|n, e
(3) existem p1, . . . , pk ∈ N, primos e distintos 2 a 2, tal que n = p1 · · · pk.
Exerc´ıcio 19. Considere D(36) o conjunto de todos os divisores positivos de 36 com a ordem do
“divide”.
(1) Desenhe o Diagrama de Hasse para (D(36), |).
(2) Determine quais elementos tem complemento e determine quem sa˜o os complementos destes.
Exerc´ıcio 20. Considere o reticulado L cujo diagrama de Hasse esteja representado na figura abaixo.
1




??
??
??
??
s t
~~
~~
~~
~~
@@
@@
@@
@@
u
v
@@
@@
@@
@@
w x
~~
~~
~~
~~
0
(1) Encontre v ∨ x, s ∨ w, u ∨ v, s ∧ t e w ∧ u.
(2) Todo elemento tem complemento? Quais tem e quem sa˜o?
(3) Ha´ elemento com mais de um complemento?
(4) L e´ distributivo?
Exerc´ıcio 21. Seja (B,∨,∧,0,1,c) uma a´lgebra de Boole. Em B, definimos a seguinte operac¸a˜o:
x⊕ y = (x ∧ yc) ∨ (xc ∧ y), para x, y ∈ B.
Determine, para x ∈ B:
(1) x⊕ x (2) 0⊕ x (3) 1⊕ x (4) x⊕ xc
Exerc´ıcio 22. Nas condic¸o˜es do exerc´ıcio anterior, mostre que, para x, y ∈ B:
(1) x⊕ y = (x ∨ y) ∧ (x ∧ y)c (2) x⊕ y = 0⇔ x = y. (3) x⊕ y = y ⊕ x
Exerc´ıcio 23. Mostre que, num reticulado, sa˜o equivalentes:
(1) a ≥ c⇒ a ∧ (b ∨ c) = (a ∧ b) ∨ c, para quaisquer a, b, c ∈ L, e
(2) a ≥ c⇒ a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c), para quaisquer a, b, c ∈ L, e
Exerc´ıcio 24. Seja (L,∨,∧,0,1) um reticulado limitado. Um elemento a ∈ L e´ chamado irredut´ıvel
se, e somente se, a 6= 0 e sempre que a = x ∨ y, para x, y ∈ L, enta˜o a = x ou a = y.
(1) Mostre que todo a´tomo e´ irredut´ıvel.
(2) Se L e´ a´lgebra booleana, mostre que todo irredut´ıvel e´ a´tomo
(3) Se L e´ distributivo, a e´ irredut´ıvel e a = x1 ∨ · · · ∨ xn, enta˜o a = xi, para algum i ∈ {1, . . . , k}.
(4) Determine os a´tomos e os irredut´ıveis em todos os diagramas de Hasse desta lista de exerc´ıcios,
quando a definic¸a˜o for poss´ıvel.
2