ordem parcial

Prévia do material em texto

Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Fundamentos de Matemática para Computação
FMC
{erikamorais, jullianonascimento}@inf.ufg.br
Instituto de Informática
Universidade Federal de Goiás
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Relação de ordem parcial
Com frequência, usamos relações para ordenar alguns ou
todos os elementos de conjuntos.
Exemplo: se vestir.
Tarefas para construção de uma casa: fundação, estrutura,
telhado, laterais externas, encanamento, fiação, piso,
revestimento das paredes, pintura externa, pintura interna,
carpete, acessórios internos e externos, acabamento.
Lexicográfica: x vem antes de y no dicionário.
Projeto: a tarefa a deve ser completada antes do início da
tarefa b.
Inteiros: x é menor que y.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Relação de ordem parcial
Definição 1 (Relação de ordem parcial)
Seja R uma relação sobre A.
Dizemos que R é uma relação de ordem parcial se R é
reflexiva, antissimétrica e transitiva.
Definição 2 (Conjunto parcialmente ordenado)
O par (A,R) é chamado de conjunto parcialmente ordenado
(ou poset de partially ordered set). Os membros de A são
chamados de elementos do poset.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Ordens Parciais
Exemplo 1
Mostre que a relação R = {(a, b) ∈ Z×Z|a ≥ b}, é uma ordem
parcial.
Solução
Temos que mostrar que R é reflexiva, antissimétrica e
transitiva.
Como a ≥ a, para todo inteiro a, então (a, a) ∈ R e R é
reflexiva.
Se a ≥ b e b ≥ a, então a = b. Logo, R é antissimétrica.
Finalmente, se a ≥ b e b ≥ c, então a ≥ c.
Portanto, R é transitiva.
Segue que R é uma ordem parcial e (Z,≥) é um poset.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Ordens Parciais
Exercício 1
Mostre que a relação R = {(a, b) ∈ Z+ × Z+ tal que a|b}, é
uma ordem parcial.
Solução
Temos que mostrar que R é reflexiva, antissimétrica e
transitiva.
Como a|a, para todo inteiro positivo a, então (a, a) ∈ R e
R é reflexiva.
Se a|b e b|a, então a = b. Logo, R é antissimétrica.
Finalmente, se a|b e b|c, então a|c.
Portanto, R é transitiva.
Segue que R é uma ordem parcial e (Z+, |) é um poset.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Ordens Parciais
Exercício 2
Mostre que a relação de inclusão ⊆ é uma ordem parcial no
conjunto das partes de um conjunto S.
Solução
Temos que mostrar que R é reflexiva, antissimétrica e
transitiva.
Como A ⊆ A, sempre que A for um subconjunto de S,
então ⊆ é reflexiva.
Sabemos que se A ⊆ B e B ⊆ A, então A = B. Logo, R
é antissimétrica.
Se A ⊆ B e B ⊆ C, então A ⊆ C e ⊆ é transitiva.
Portanto, ⊆ é uma ordem parcial em P (S) e (P (S),⊆) é
um poset.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Ordens Parciais
Exercício 3
Seja R a relação no conjunto das pessoas tal que (x, y) ∈ R se
x e y forem pessoas e x for mais velha do que y. Mostre que R
não é uma ordem parcial.
Solução
Como nenhuma pessoa é mais velha do que si mesma, então
(x, x) /∈ R e R não é reflexiva.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Ordens Parciais
Exercício 4
Seja A = {(x, y)|x, y ∈ Z}. Defina a relação R através da
seguinte regra:
(a, b)R(c, d) ↔ a ≤ c ou b ≤ d.
Mostre que R não é uma ordem parcial sobre A.
Solução
Veja que (a, b)R(a, b), pois a ≤ a ou b ≤ b é sempre verdade.
Logo, R é reflexiva. Observe que, pela regra, (1, 4)R(3, 2) pois
1 ≤ 3 e (3, 2)R(1, 4) pois 2 ≤ 4. Mas, (1, 4) 6= (0, 3) e
((1, 4), (0, 3)) /∈ R. Logo, R não é antissimétrica.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Relação de ordem parcial
Exemplo 2
São exemplos de relações de ordem parcial:
idA.
≤.
Consideramos A = {1, 2, 3, 4, 5, 6} e R =
idA ∪ {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 4), (3, 4), (3, 5)}.
(Z+, |).
(P(A),⊆).
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Comparação entre elementos de A
Definição 3 (Elementos comparáveis)
A indicação a � b é usada para denotar que (a, b) ∈ R em
um poset arbitrário (S,R).
Seja (A,�) um poset. Sejam a, b ∈ A.
Dizemos que a e b são comparáveis se a � b ou b � a.
Se (a, b) /∈ R, dizemos que a � b.
Notação
Seja (A,�) um poset. Sejam a, b ∈ A.
Quando (a, b) 6∈ �, denotamos por a � b.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Comparação entre elementos de A
Exemplo 3
1 Seja o poset (Z+,≤). Quaisquer dois elementos de Z+ são
comparáveis pois
∀x, y ∈ Z+ | x ≤ y ou y ≤ x.
2 Sejam A = {1, 2, 3}, B = {1, 2}, C = {3},X = {A,B,C}
e o poset (X,⊆):
1 A e B são comparáveis, pois B ⊆ A.
2 A e C são comparáveis, pois C ⊆ A.
3 B e C não são comparáveis, pois B * C e C * B.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Visualização de uma relação de ordem parcial
Diagrama de Hasse
Seja (A,�) um poset. O diagrama de Hasse é obtido da
seguinte forma:
Os pontos correpondem aos elementos de A.
Tem uma aresta subindo de a para b se:
a ≺ b (ou seja, a � b e a 6= b);
se a � c e c � b, então a = c ou c = b.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Visualização de uma relação de ordem parcial
Diagrama de Hasse a partir do grafo
A partir do grafo da relação de ordem parcial �.
1 Remover os laços.
2 Posicionar os arcos para cima e remover as orientações.
3 Remover os arcos paralelos do caminho (transitividade).
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Comparação entre elementos de A
Exemplo 4
Sejam A = {a, b, c, d} e a relação R sobre A. R =
{(a, a), (a, b), (a, c), (a, d), (b, d), (c, d), (b, b), (c, c), (d, d))}. O
Diagrama de Hasse de (A,R) é:
a
b
d
c
a e b são comparáveis.
a e c são comparáveis.
a e d são comparáveis.
b e c não são comparáveis.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Diagrama de Hasse
Exercício 5
Sejam A = {1, 2, 3, 6, 12, 18} e a relação “x divide y” sobre A.
O Diagrama de Hasse de (A, |) é:
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Diagrama de Hasse
Exercício 5
Sejam A = {1, 2, 3, 6, 12, 18} e a relação “x divide y” sobre A.
O Diagrama de Hasse de (A, |) é:
1
2
6
3
12 18
Fundamentos
de
Matemática
para
ComputaçãoOrdem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Diagrama de Hasse
Exercício 6
Sejam A = {1, 2, 3, 4} e a relação ≤ sobre A, ou seja, ≤=
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}.
O Diagrama de Hasse de (A,≤) é:
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Diagrama de Hasse
Exercício 6
Sejam A = {1, 2, 3, 4} e a relação ≤ sobre A, ou seja, ≤=
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}.
O Diagrama de Hasse de (A,≤) é:
1
2
3
4
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Elementos especias
Definição 4
Seja (A,�) um poset e a ∈ A.
Dizemos que a é minimal se ∄b ∈ A tal que b ≺ a.
(ou seja, se b � a, então a = b.)
Dizemos que a é mínimo se ∀b ∈ A, temos que a � b.
Dizemos que a é maximal se ∄b ∈ A tal que a ≺ b.
(ou seja, se a � b, então a = b.)
Dizemos que a é máximo se ∀b ∈ A, temos que b � a.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Elementos especiais
Exemplo 5
No poset (A,=), ∀a ∈ A, a é minimal e maximal.
No poset (Z,≤) não tem elemento minimal nem maximal.
No poset (N, |), 1 é mínimo e 0 é máximo.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Elementos especiais
Exemplo 6
d
c
a
b
b e c são maximais.
a e d são minimais.
Não existe elemento máximo.
Não existe elemento mínimo.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Elementos especiais
Exemplo 7
a
b
d
c
a é mínimo e minimal.
d é máximo e maximal.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Elementos especias no Diagrama de Hasse
Elemento Descrição no Diagrama de Hasse
minimal Nenhum elemento abaixo dele.
mínimo Todos os elementos acima dele.
maximal Nenhum elemento acima dele.
máximo Todos os elementos abaixo dele.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Próxima aula
Funções: ordem de grandeza.
Fundamentos
de
Matemática
para
Computação
Ordem
Parcial
Elementos
Diagrama de
Hasse
Elementos
Especiais
Próxima aula
Referências Bibliográficas
Referências
Gersting, J. L.
Fundamentos Matemáticos para a Ciência da Computação.
5a. edição, Editora LTC, 2004.
Rosen, K. H.,
Matemática Discreta e suas aplicações.
6a. edição, Editora McGraw Hill, 2009.
Scheinerman, Edward R.
Matemática Discreta, Uma introdução.
Thomson Pioneira, 2003.
	Ordem Parcial
	Elementos
	Diagrama de Hasse
	Elementos Especiais
	Próxima aula