07/08/2013
2
Diagrama de Hasse
•
1, 2, 3, 4, 6, 8, 12 , |
RELAÇÕES:
DIAGRAMA DE HASSE, ELEMENTOS
MAXIMAIS E MINIMAIS, RETICULADOS
8
12
4
6
2
3
Matemática Discreta
Prof. João Paulo Lima
Universidade Federal Rural de Pernambuco
Departamento de Estatística e Informática
1
Copyright © 2006 by The McGraw-Hill Companies, Inc. All rights reserved.
3
Elementos Maximais
Elementos Maximais
• Dado o poset 𝑆, ≼
• Um elemento 𝑥 ∈ 𝑆 é maximal em 𝑆, ≼
4
2, 4, 5, 10, 12, 20, 25 , |
são maximais?
• 12, 20 e 25 são elementos maximais
• Ex: quais elementos do poset
se não existe
nenhum elemento maior que ele
• Não existe 𝑦 ∈ 𝑆 tal que 𝑥 ≺ 𝑦
12
20
4
10
2
5
25
5
Elementos Minimais
Elementos Minimais
• Dado o poset 𝑆, ≼
• Um elemento 𝑥 ∈ 𝑆 é minimal em 𝑆, ≼
nenhum elemento menor que ele
6
• Ex: quais elementos do poset
se não existe
2, 4, 5, 10, 12, 20, 25 , |
são minimais?
• 2 e 5 são elementos minimais
• Não existe 𝑦 ∈ 𝑆 tal que 𝑦 ≺ 𝑥
12
20
4
10
2
5
25
1
07/08/2013
7
8
Maior Elemento
Maior Elemento
• Dado o poset 𝑆, ≼
• Ex: quais dos posets abaixo possuem maior elemento?
• Um elemento 𝑥 ∈ 𝑆 é o maior elemento de 𝑆, ≼ se ele
• Resposta: 𝑐 e 𝑑
for maior que todos os outros elementos
• 𝑦 ≼ 𝑥 para todo 𝑦 ∈ 𝑆
• Quando existe, o maior elemento é único
9
10
Menor Elemento
Menor Elemento
• Dado o poset 𝑆, ≼
• Ex: quais dos posets abaixo possuem menor elemento?
• Um elemento 𝑥 ∈ 𝑆 é o menor elemento de 𝑆, ≼ se ele
• Resposta: 𝑎 e 𝑑
for menor que todos os outros elementos
• 𝑥 ≼ 𝑦 para todo 𝑦 ∈ 𝑆
• Quando existe, o menor elemento é único
11
12
Cotas Superiores
Cotas Superiores
• Upper Bounds
• Ex: quais são as cotas superiores dos subconjuntos
• Dado o poset 𝑆, ≼
𝑎, 𝑏, 𝑐 , 𝑗, 𝑕 e 𝑎, 𝑐, 𝑑, 𝑓 no poset a seguir?
• Dado um subconjunto 𝐴 de 𝑆
• Cotas superiores de 𝑎, 𝑏, 𝑐 : 𝑒, 𝑓, 𝑕, 𝑗
• Um elemento 𝑥 ∈ 𝑆 é cota superior (upper bound) de 𝐴 se
• Cotas superiores de 𝑗, 𝑕 : nenhuma
ele é maior ou igual a todos os elementos de 𝐴
• 𝑦 ≼ 𝑥 para todo 𝑦 ∈ 𝐴
• Cotas superiores de 𝑎, 𝑐, 𝑑, 𝑓 : 𝑓, 𝑕, 𝑗
2
07/08/2013
13
14
Cotas Inferiores
Cotas Inferiores
• Lower Bounds
• Ex: quais são as cotas inferiores dos subconjuntos
𝑎, 𝑏, 𝑐 , 𝑗, 𝑕 e 𝑎, 𝑐, 𝑑, 𝑓 no poset a seguir?
• Dado o poset 𝑆, ≼
• Dado um subconjunto 𝐴 de 𝑆
• Cotas inferiores de 𝑎, 𝑏, 𝑐 : 𝑎
• Um elemento 𝑥 ∈ 𝑆 é cota inferior (lower bound) de 𝐴 se
• Cotas inferiores de 𝑗, 𝑕 : 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓
ele é menor ou igual a todos os elementos de 𝐴
• 𝑥 ≼ 𝑦 para todo 𝑦 ∈ 𝐴
• Cotas inferiores de 𝑎, 𝑐, 𝑑, 𝑓 : 𝑎
15
16
Menor Cota Superior
Menor Cota Superior
• Dado o poset 𝑆, ≼
• Ex: qual a menor cota superior do subconjunto 𝑏, 𝑑, 𝑔 no
poset a seguir?
• Dado um subconjunto 𝐴 de 𝑆
• Um elemento 𝑥 ∈ 𝑆 é a menor cota superior de 𝐴 se ele é
• Cotas superiores de 𝑏, 𝑑, 𝑔 : 𝑔, 𝑕
uma cota superior de 𝐴 menor que todos as outras cotas
superiores de 𝐴
• 𝑦 ≼ 𝑥 para todo 𝑦 ∈ 𝐴
• 𝑥 ≼ 𝑧 para todo 𝑧 que é cota superior de 𝐴
• Quando existe, a menor cota superior é única
• Menor cota superior de 𝑏, 𝑑, 𝑔 : 𝑔
17
18
Maior Cota Inferior
Maior Cota Inferior
• Dado o poset 𝑆, ≼
• Ex: qual a maior cota inferior do subconjunto 𝑏, 𝑑, 𝑔 no
• Dado um subconjunto 𝐴 de 𝑆
poset a seguir?
• Um elemento 𝑥 ∈ 𝑆 é a maior cota inferior de 𝐴 se ele é
• Cotas inferiores de 𝑏, 𝑑, 𝑔 : 𝑎, 𝑏
uma cota inferior de 𝐴 maior que todos as outras cotas
inferiores de 𝐴
• 𝑥 ≼ 𝑦 para todo 𝑦 ∈ 𝐴
• 𝑧 ≼ 𝑥 para todo 𝑧 que é cota inferior de 𝐴
• Quando existe, a maior cota inferior é única
• Maior cota inferior de 𝑏, 𝑑, 𝑔 : 𝑏
3
07/08/2013
19
20
Reticulado
Reticulado
• Dado o poset 𝑆, ≼
• Ex: quais dos posets abaixo são reticulados?
• Se todo par de elementos de 𝑆 possui menor cota
• Resposta: 𝑎 e 𝑐
superior e maior cota inferior, então 𝑆, ≼ é um reticulado
4