Exercícios de Matemática Discreta sobre Diagramas de Hasse

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2017/2
Lista de Exerc´ıcios 6
1. Usando o diagrama de Hasse abaixo determine, caso exista:
a) seus elementos maximais,
b) seus elementos minimais,
c) seu maior elemento,
d) seu menor elemento,
e) cotas superiores para {a, b, c},
f) sup{a, b, c},
g) cotas inferiores para {f, g, h},
h) inf{f, g, h},
i) cotas superiores para {k, l},
j) sup{k, l},
k) cotas inferiores para {k, l},
l) inf{k, l}.
a b c
d e f
g h i
j k l
m n
o p
2. Determine conjuntos parcialmente ordenados que sejam descritos pelo diagrama
de Hasse abaixo.
a
b
c
d
e
f
g
a
d
g
k
i
e
h
j
f
b
l
c
3. Considere o conjunto POSET (S,≤ ) , cujo diagrama de Hasse e´ dado abaixo.
Determine, caso exista:
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
4. Determine quais dos conjuntos parcialmente ordenados abaixo, descritos pelo
diagrama de Hasse, sa˜o reticulados.
a
b
c
d
e
f
g
b
d
f
h
a
c
e
g
b
d
f
a
h
i
c
e
g
5. Complete o diagrama de Hasse para a relac¸a˜o de divisibilidade no conjunto
{1, 2, 3, 4, 5, 10, 15, 20, 30, 45, 60}, iniciando com os pontos dados abaixo.
1
2 5 3
6. Exiba 2 diagramas de Hasse diferentes obtidos transformando o diagrama de
Hasse da Questa˜o 1 em reticulado: um inserindo elementos e outro eliminando
elementos.
7. Fac¸a o diagrama de Hasse para a relac¸a˜o de divisibilidade ( | ) no conjunto dos
divisores de 60 iniciando com os pontos dados acima, no exerc´ıcio 5. Depois,
exiba 1 diagrama de Hasse (diferente) que ainda seja um reticulado, inserindo
3 elementos no diagrama de Hasse obtido anteriormente.
8. Podemos ordenar o conjunto das disciplinas obrigato´rias do curso de culina´ria
Computacional pelos seus pre´-requisitos. Dizemos que A � B se e so´ se A = B
ou se a disciplina A e´ um pre´-requisito para a disciplina B. Vamos considerar
C o conjunto das disciplinas matema´ticas desse curso dadas na tabela abaixo.
Fac¸a o diagrama de Hasse para C usando a ordem parcial descrita.
Disciplina Pre´-requisitos
MAT 101 Nenhum
MAT 201 MAT 101
MAT 250 MAT 101
MAT 251 MAT 250
MAT 340 MAT 201
MAT 341 MAT 340
MAT 450 MAT 201, MAT 250
MAT 500 MAT 450, MAT 251
9. Considere o conjunto C da questa˜o anterior e seu diagrama de Hasse.
a) Determine todos os elementos ma´ximos e mı´nimos de C.
b) O diagrama de Hasse e´ um reticulado?
c) Determine uma ordem total compat´ıvel com a ordem dada.
10. Seja H = {A,B,C,D,E, F,G} o conjunto formado pelos seguintes subconjun-
tos 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?