Conjunto Parciamente Ordenado

Prévia do material em texto

Relação de Ordem Parcial
• Além da relação de equivalência que acabamos de estudar, outro 
tipo de relação de particular importância é a relação de ordem parcial. 
Essa relação se diferencia da relação de equivalência pelas 
propriedades que deve satisfazer.
• Uma relação R em um conjunto A é dita um ordenamento parcial 
ou uma ordem parcial se R é reflexiva, antissimétrica e transitiva.
• Um conjunto A juntamente com uma ordem parcial R é dito 
parcialmente ordenado (poset – partially ordered set).
HAC ED2013 1
Exemplos
a) A relação de inclusão de conjuntos ⊆ é uma ordem parcial em 
qualquer coleção de conjuntos:
• A ⊆ A para todo conjunto A. (é reflexiva)
• Se A ⊆ B e B ⊆ A, então A = B. (é antissimétrica)• Se A ⊆ B e B ⊆ A, então A = B. (é antissimétrica)
• Se A ⊆ B e B ⊆ C, então A ⊆ C. (é transitiva)
HAC ED2013 2
b) A relação ≤ no conjunto R dos números reais é uma ordem 
parcial:
• x ≤ x, ∀ x ∈ R (é reflexiva)
• Se x ≤ y e y ≤ x, então x = y (é antissimétrica)• Se x ≤ y e y ≤ x, então x = y (é antissimétrica)
• Se x ≤ y e y ≤ z, então x ≤ z (é transitiva)
HAC ED2013 3
c) A relação a divide b é uma relação de ordem parcial no 
conjunto N+ de inteiros positivos.
• a | a, ∀ a ∈ N+ (é reflexiva)
• Se a|b e b|a, então a = b (é antissimétrica)• Se a|b e b|a, então a = b (é antissimétrica)
• Se a|b e b|c, então a|c (é transitiva)
HAC ED2013 4
Definição
Um conjunto parcialmente ordenado é um par P = (X,R) onde X é um conjunto 
e R é uma relação em X que satisfaz:
• R é reflexiva: ∀ x ∈ X, xRx,
• R é antissimétrica: ∀ x,y ∈ X, se xRy e yRx, então x=y,
• R é transitiva: ∀ x,y,z ∈ X, se xRy e yRz, então xRz.• R é transitiva: ∀ x,y,z ∈ X, se xRy e yRz, então xRz.
O conjunto X é chamado conjunto fundamental de P. O termo conjunto 
PO é uma abreviação de conjunto parcialmente ordenado.
HAC ED2013 5
Exemplo
Seja P=(X,R), com 
X = {1, 2, 3, 4} e
R = {(1,1), (1,2), (1,3), (1,4), (2,2), (3,3), (3,4), (4,4)}.
Pode-se verificar que R é reflexiva, antissimétrica e transitiva, 
portanto P é um conjunto PO.
HAC ED2013 6
Diagramas de Hasse
• Os conjuntos PO podem ser representados por diagramas chamados de 
diagramas de Hasse.
• Esses diagramas, apesar de serem bastante semelhantes aos grafos, tem 
um significado diferentes deles e são usados especificamente para ilustrar 
conjuntos parcialmente ordenados. conjuntos parcialmente ordenados. 
HAC ED2013 7
Diagramas de Hasse
• Cada elemento do conjunto fundamental é representado por um ponto no 
diagrama. 
• Se um par (x,y) está em R, ou seja, xRy, o ponto que representa x é 
desenhado abaixo do ponto que representa y e esses dois pontos são 
unidos por um segmento de reta – que não precisa estar exatamente na unidos por um segmento de reta – que não precisa estar exatamente na 
vertical. 
• Distinção importante entre diagramas de Hasse e grafos: nos grafos a 
localização em que os nós do grafo são desenhados não é importante.
HAC ED2013 8
• Nos diagramas de Hasse:
– A posição dos nós é importante;
– Não é necessário traçar uma ligação de um ponto com ele mesmo, – Não é necessário traçar uma ligação de um ponto com ele mesmo, 
pois está implícito que ela existe - sabemos que a relação é reflexiva;
– Não é necessário ligar todos os pares de pontos que estão 
relacionados por R. 
HAC ED2013 9
Exemplo
4
X = {1, 2, 3, 4} e
R = {(1,1), (1,2), (1,3), (1,4), (2,2), (3,3), (3,4), (4,4)}.
HAC ED2013 10
1
2 3
4
Diagrama de Hasse do conjunto PO do exemplo.
• Na figura anterior, desenhamos o ponto 1 abaixo do ponto 2 pois 1R2.
• Neste mesmo exemplo, vemos que (1,4) ∈R, mas não foi “desenhada” 
uma reta ligando 1 e 4. 
• A relação entre 1 e 4 está implícita na figura, uma vez que aparecem as 
ligações entre (1,3) e (3,4) e a relação R é transitiva.
HAC ED2013 11
Exemplos
P = ({1, 2, 3, 4, 5, 6}, |) (conjunto PO com a relação divide)
R = {(1,1,), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,4), (2,6), (3,3), (3,6), 
(4,4), (5,5), (6,6)}
HAC ED2013 12
1
2 3 5
4 6
• P = (2{1, 2, 3}, ⊆ ) (conjunto PO com conjunto fundamental sendo o 
conjunto das partes de {1,2,3} e a relação é-subconjunto-de)
{1,2,3}
HAC ED2013 13
∅
{1} {2} {3}
{1,2} {1,3} {2,3}
Refinamento
• O refinamento é uma relação entre partições de um conjunto. 
• A relação de refinamento é definida entre duas partições.
• Sejam P e Q partições de um conjunto A. 
– Dizemos que P refina Q se toda parte em P é subconjunto de alguma parte em Q. 
– Dizemos também que P é mais fina do que Q. 
HAC ED2013 14
Exemplo
• Seja A = {1, 2, 3, 4, 5, 6}, 
• P = {{1,2}, {3}, {4}, {5,6}} e 
• Q = {{1, 2, 3, 4}, {5, 6}}.
• É possível verificar que toda parte de P é um subconjunto de uma parte 
em Q. em Q. 
• Assim, P é um refinamento de Q.
HAC ED2013 15
• O refinamento é uma ordem parcial no conjunto de todas as partições 
de um dado conjunto.
• Exemplo: refinamento em todas as partições de {1, 2, 3, 4}. 
• Notação: Escrevemos os elementos de cada conjunto em sequência, 
sem separadores
1 / 2 / 34 em vez de {{1}, {2}, {3,4}},
1234 em vez de {1, 2, 3, 4},
12 / 34 em vez de {{1, 2,}, {3, 4}},
1 / 2 / 3 / 4 em vez de {{1}, {2}, {3}, {4}}
e assim por diante.
HAC ED2013 16
1234
123 / 4 124 / 3 134 / 2 234 / 1 12 / 34 13 / 24 14 / 23
HAC ED2013 17
12 / 3 / 4 13 / 2 / 4 14 / 2 / 3 23 / 1 / 4 24 / 1 / 3 34 / 1 / 2
1 / 2 / 3 / 4
Diagrama de Hasse da ordem parcial de refinamento em 
todas as partições de {1, 2, 3, 4}. 
Simbolos e Notações
• As relações de ordem parcial são usualmente representadas por um 
símbolo genérico, que denota qualquer relação. 
• Esse símbolo é o ≤, (que já é um símbolo muito conhecido, que 
representa também a relação de menor ou igual).
• Em P = (A, ≤), o símbolo pode estar representando uma ordem 
parcial genérica e é lido como “está abaixo de”.
HAC ED2013 18
• Dizemos que x está abaixo de y, quando escrevemos x≤y. 
• De forma semelhante lemos:
• o símbolo ≥ como “está acima de”, • o símbolo ≥ como “está acima de”, 
• o símbolo < como “está estritamente abaixo de” e 
• o símbolo > como “está estritamente acima de”. 
HAC ED2013 19
Observação
• A palavra “estritamente” no termo “está estritamente abaixo de” 
é usada para denominar essa relação no caso em que x<y e x ≠ y 
(x está estritamente abaixo de y e x é diferente de y). 
• A expressão “está abaixo de”, denotada por x ≤ y, pode incluir o 
caso em que x=y. 
HAC ED2013 20
Elementos comparáveis e não comparáveis
Seja P = (X, ≤) um conjunto PO. Sejam x, y ∈ X. 
• Dizemos que os elementos x e y são comparáveis se e somente se x 
≤ y ou y ≤ x. 
• Os elementos x e y são ditos não-comparáveis se não é verdade que 
x ≤ y ou y ≤ x. 
HAC ED2013 21
Exemplo
1
2 3
4
• Os pares de elementos 2 e 4, 2 e 3 são não-comparáveis;
• Os pares de elementos 1 e 4, 1 e 2, 1 e 3, 3 e 4, são comparáveis.
HAC ED2013 22
1
Cadeia e Anti-cadeia
Seja P = (X, ≤) um conjunto PO e seja C ⊆ X. 
Dizemos que C é uma cadeia de P se os elementos de todos os 
pares em C são comparáveis. 
Dizemos que C é uma anticadeia de P se, para todos os pares de 
elementos distintos em C, os elementos são não-comparáveis. 
HAC ED2013 23
Exemplo
1
2 3
4
• Os conjuntos {1,2} e {1,3,4} são algumas das cadeias de P.
• Os conjuntos {2,3} e {2,4} são exemplos de anticadeias de P. 
HAC ED2013 24
1
Altura e Largura
• Seja P = (X, ≤) um conjunto PO. 
• A altura de P é o tamanho máximo de uma cadeia de P. 
• A largura de P é o tamanho máximo de uma anticadeia de P.• A largura de P é o tamanho máximo de uma anticadeiade P.
HAC ED2013 25
Exemplo
1
2 3 4
5
HAC ED2013 26
1
Maior cadeia: {1, 3, 5}
Altura de P = 3
Maior anti-cadeia = {2, 3, 4}
Largura de P = 3
Máximo e Mínimo
• Seja P = (X, ≤) um conjunto PO. 
• Dizemos que x ∈ X é máximo se, para todo a ∈ X, temos a≤ x. 
• Dizemos que x ∈ X é mínimo se, para todo b ∈ X, temos x≤b.
Em outras palavras, 
• x é máximo se todos os outros elementos do conjunto PO estão 
abaixo de x.
• x é mínimo se todos os outros elementos do conjunto PO estão 
acima de x.
HAC ED2013 27
Exemplo
• Vamos considerar o conjunto PO que consiste dos divisores positivos 
de 36, ordenados por divisibilidade.
• Nesse conjunto PO, o elemento 1 é mínimo porque está abaixo de 
todos os outros elementos do conjunto PO. 
• O elementos 36 é máximo porque está acima de todos os outros 
elementos. elementos. 
HAC ED2013 28
1
2 3
4
6
9
12 18
36
• Consideremos agora o conjunto PO dos inteiros de 1 a 6 ordenados 
por divisibilidade. 
• Nesse conjunto o elemento 1 é mínimo, mas não há elemento 
máximo.
4 6
HAC ED2013 29
1
2 3 5
4 6
Elemento minimal e maximal
• Seja P = (X, ≤) um conjunto parcialmente ordenado. 
• Dizemos que um elemento x ∈ X é maximal se não existe qualquer b 
∈ X com x < b. 
• O elemento x é chamado minimal se não existe qualquer a ∈ X com 
a < x.
• Em outras palavras, x é maximal se não existe qualquer 
elemento estritamente acima de x, e minimal se não existe qualquer 
elemento estritamente abaixo dele.
HAC ED2013 30
• Consideremos novamente o conjunto PO dos inteiros de 1 a 6 
ordenados por divisibilidade. 
• Nesse conjunto os elementos 4, 5 e 6 são maximais e o elemento 1 é 
minimal (além de mínimo)minimal (além de mínimo)
HAC ED2013 31
1
2 3 5
4 6
Ordens Lineares
• Os conjuntos parcialmente ordenados tem uma 
subclasse, formada pelas ordens lineares, ou ordens 
totais. A característica das ordens totais é a não 
existência de elementos não-comparáveis.
• Seja P = (X, ≤) um conjunto parcialmente ordenado. 
Dizemos que P é uma ordem total ou linear quando P 
não contém elementos não-comparáveis. 
HAC ED2013 32
Exemplos
• O conjunto (Z, ≤) é uma ordem total.
• O conjunto parcialmente ordenado formado pelo conjunto Q 
= {1, 3, 9, 27, 81}, dos divisores de 81, ordenados por 
divisibilidade, é uma ordem total.divisibilidade, é uma ordem total.
• O conjunto parcialmente ordenado formado pelo conjunto X = 
{1, 2, 3, 4, 5}, e a relação “menor ou igual” é uma ordem total.
HAC ED2013 33
• As ordens totais satisfazem a regra da tricotomia: para todos 
os x e y no conjunto PO, exatamente uma das seguintes 
possibilidades é verdadeira:
• x < y,• x < y,
• x = y ou
• x > y.
HAC ED2013 34