Exercícios de Matemática Discreta sobre Reticulados

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2013/1
Lista de Exerc´ıcios 8
1. Seja (S,�) um reticulado. Mostre que:
(a) inf {x, y} = x⇐⇒ sup {x, y} = y
(b) inf {x, sup {x, y}} = x e sup {x, inf {x, y}} = x
2. Sejam (A,�) um reticulado e a, b, c ∈ A tais que a � b e a � c. Determine:
(a) sup {a, inf {b, c}} e inf {sup {a, b} , sup {a, c}}
(b) inf {a, sup {b, c}} e sup {inf {a, b} , inf {a, c}}
3. Usando o diagrama de Hasse abaixo determine, caso existam:
(a) seus elementos maximais e minimais,
(b) seu maior e seu menor elemento,
(c) cotas superiores para {a, b, c},
(d) sup{a, b, c},
(e) cotas inferiores para {f, g, h},
(f) inf{f, g, h},
(g) cotas superiores para {k, l},
(h) sup{k, l},
(i) cotas inferiores para {k, l},
(j) inf{k, l}.
a b c
d e f
g h i
j k l
m n
o p
4. Considere o conjunto POSET (S,� ) , cujo diagrama de Hasse e´ dado abaixo.
Determine, caso existam:
a) seus elementos maximais e minimais,
b) seu maior elemento e seu menor elemento,
c) cotas superiores e inferiores para {a, b, c},
d) sup{a, b, c}, e inf{a, b, c},
e) cotas superiores e inferiores para {f, g},
f) sup{f, g}, e inf{f, g},
b
b
b
b
b
b
b
b
b
b
b
b
ba b
c d
e f g
h i j
5. Seja S(R) o conjunto de todas as func¸o˜es f : [0, 1] → [0, 1]. A relac¸a˜o � e´
definida por f � g ⇐⇒ (∀x ∈ [0, 1])[f(x) ≤ g(x)]. Mostre que (S(R),�) e´
um reticulado.
6. Determine quais dos conjuntos parcialmente ordenados abaixo, descritos pelo
diagrama de Hasse, sa˜o reticulados.
a
b
c
d
e
f
g
a
b c
d e
f g
h
a
b c
d e
f g
h
i
7. Seja H = {A,B, C,D,E, F,G} o conjunto formado pelos seguintes subcon-
juntos de Z. A = {4}, B = {7}, C = {x ∈ Z; x > 5}, D = {x ∈
Z; x2 − 16 = 0}, E = {x ∈ Z; x2 > 25}, F = {x ∈ Z; x2 > 9},
G = {x ∈ Z; x > 3}. Sabemos que (H,⊆) e´ um POSET.
(a) Fac¸a o diagrama de Hasse para (H,⊆).
(b) Determine (caso existam) os elementos maximais e os elementos minimais
do Diagrama de Hasse acima.
(c) Determine (caso existam) seu maior elemento e seu menor elemento.
(d) O diagrama de Hasse acima (feito no item (a)) e´ um reticulado?
8. Seja S um conjunto parcialmente ordenado por � e seja T um subconjunto
na˜o-vazio de S.
(a) Prove que supT = maxT se, e somente se, T possui uma cota superior
x tal que x ∈ T .
(b) Seja I(T ) o conjunto das cotas inferiores de T . Prove que T possui ı´nfimo
se, e somente se, I(T ) possui elemento ma´ximo. Nesse caso, verifique que
inf T = max I(T ).