Universidade Federal de Pernambuco
Anjolina Grisi de Oliveira
Definições
• Ordem Parcial
– Uma relação R em um conjunto S com as
seguintes propriedades
• Reflexiva
• Anti-simétrica
• Transitiva
• Conjunto Parcialmente Ordenado (poset)
- Um conjunto S juntamente com uma ordem
parcial R: (S,R)
Matemática Discreta – if670
Centro de Informática / UFPE
2
Exemplos
• Mostre que (Z,) é um poset
– Temos que a  a para todo inteiro a: reflexiva
– Se a  b e b  a então a = b: anti-simétrica
– Se a  b e b  c então a  c: transitiva
– Logo  é uma ordem parcial no conjunto dos
inteiros e (Z,  ) é um conjunto parcialmente
ordendo.
Matemática Discreta – if670
Centro de Informática / UFPE
3
Exemplos
• Mostre que a relação de inclusão  é uma
ordem parcial no conjunto das partes de
um conjunto S. Ou seja, (P(S),  ) é um
poset.
• Mostre que a relação de divisibilidade no
conjunto dos inteiros positivos é uma
ordem parcial. Ou seja, (Z+,|) é um poset.
Matemática Discreta – if670
Centro de Informática / UFPE
4
• Em um poset a notação a  b denota que (a,b)
pertence a R
• A relação “menor ou igual” é um paradigma para
ordens parciais
• A notação a  b denota que a  b, mas a  b.
Dizemos que “a é menor que b” ou “b é maior que
a”.
Matemática Discreta – if670
Centro de Informática / UFPE
5
• Por quê o nome ordem parcial?
– Em (P(Z),), {1,4} não se relaciona com {1,2} e
nem vice-versa
– Em (Z+,|), 2 não se relaciona com 5 e nem viceversa
• Os elementos a e b em um poset (S,) são
chamados de comparáveis se ou a  b ou b  a.
Caso contrário, eles são ditos incomparáveis.
Matemática Discreta – if670
Centro de Informática / UFPE
6
• Se (S,) é um poset e cada par de elementos de S
são comparáveis, dizemos que S é um conjunto
totalmente ordenado ou linearmente ordenado, e 
é chamada de ordem total ou linear.
• Um conjunto totalmente ordenado é chamado de
cadeia
• O poset (Z,  ) é uma cadeia
• O poset (Z+,|) não é totalmente ordenado
Matemática Discreta – if670
Centro de Informática / UFPE
7
Ordem Lexicográfica
As palavras em um dicionário são listadas em
ordem alfabética ou ordem lexicográfica, que é
baseada na ordem das letras do alfabeto.
Esse exemplo é um caso especial onde é
possível ordenar cadeias a partir de uma ordem
parcial sobre o alfabeto em que as cadeias são
construídas.
Matemática Discreta – if670
Centro de Informática / UFPE
8
• Como construir uma ordem parcial no produto
cartesiano de dois posets (A,1) e (B, 2)
• A ordem lexicográfica  em A  B é definida da
seguinte forma:
(a1,b1)  (a2,b2) se
ou a1 <1 a2
ou a1 = a2 e b1 <2 b2
A ordem parcial é obtida adicionando a igualdade à ordem <
em A  B
Matemática Discreta – if670
Centro de Informática / UFPE
9
• Exemplo
Seja o poset (ZZ, ), onde  é a ordem
lexicográfica construída a partir da ordem
usual  no conjunto dos inteiros. Determine
se
(3,5) < (4,8);
(3,9) < (3,10);
(6,8) < (6,9)
Matemática Discreta – if670
Centro de Informática / UFPE
10
Uma ordem lexicográfica pode ser definida no
produto cartesiano de n posets:
(A1, 1), (A2, 2)...,(An, n).
Defina a ordem parcial em A1A2...An por:
(a1,a2,...,an) < (b1,b2,...,bn)
Se a1<1b1ou se existe um inteiro i>0 t.q.
a1=b1...ai=bi e ai+1<i+1 bi+1.
Matemática Discreta – if670
Centro de Informática / UFPE
11
• Ordem lexicográfica de cadeias
– Considere as cadeias distintas a1a2...am e b1b2...bn sobre
um conjunto parcialmente ordenado S;
– Seja t o menor dentre m e n
– a1a2...am < b1b2...bn se e somente se
– (a1,a2...,at ) < (b1,b2...,bt ) ou
– (a1,a2...,at) = (b1,b2...,bt) e m<n
Matemática Discreta – if670
Centro de Informática / UFPE
12
Diagrama de Hasse
• Seja o poset ({1,2,3,4,6},|). Qual é a
representação da relação | usando grafos?
Matemática Discreta – if670
Centro de Informática / UFPE
13
Diagrama de Hasse
• Seja o poset ({1,2,3,4,6},|). Qual é a
representação da relação | usando grafos?
6
4
3
2
1
Matemática Discreta – if670
Centro de Informática / UFPE
14
Diagrama de Hasse
• A relação é reflexiva: possui laços em todos os nós
• Não é preciso colocar os laços
• Transitiva: não precisamos colocar as arestas que
ilustram a transitividade
• Desenhamos o diagrama de forma que não é preciso
colocar setas
4
66
3
2
1
Matemática Discreta – if670
Centro de Informática / UFPE
15
Diagrama de Hasse
• Desenhe o diagrama de Hasse para os seguintes
posets
• (P({a,b,c},)
• ({2,4,5,10,12,20,25},|)
Matemática Discreta – if670
Centro de Informática / UFPE
16
Elementos Maximais e Minimais
20
12
10
4
2
25
5
• Seja um poset (S,).
• O elemento a é maximal nesse poset se não
existe b  S de forma que a < b.
• O elemento a é minimal nesse poset se não
existe b  S de forma que b < a.
Matemática Discreta – if670
Centro de Informática / UFPE
17
Maior elemento/ Menor elemento
• a é o maior elemento no poset (S, ) se b  a
para todo b  S
• a é o menor elemento no poset (S, ) se a  b
para todo b  S
• Quando existem, o maior e o menor elementos
são únicos
Matemática Discreta – if670
Centro de Informática / UFPE
18
Limitante superior/inferior
• Seja A um subconjunto do poset (S, ).
• Se u  S e a  u para todo a  A, então u é
chamado de limitante superior de A.
• Se i  S e i  a para todo a  A, então i é
chamado de limitante inferior de A.
Matemática Discreta – if670
Centro de Informática / UFPE
19
Limitante superior/inferior
• Limitantes superior e inferior dos subconjuntos
{a,b,c}, {j.h} e {a,c,d,f} do seguinte poset.
h
j
g
f
d
e
b
c
a
• De {a,b,c}: sup= {e,f,h,j}; inf={a}
• De {j,h}: sup=; inf={f,d,e,b,c,a}
• De {a,c,d,f}: sup={f,j,h}; inf={a}
Matemática Discreta – if670
Centro de Informática / UFPE
20
Supremo e ínfimo
• Supremo: o menor dos limitantes superiores
• Ínfimo: o maior dos limitantes inferiores
• Quando existem são únicos
• Qual o supremo e o ínfimo de {b,d,g} do poset do
exemplo anterior?
Matemática Discreta – if670
Centro de Informática / UFPE
21
Exemplo
• Seja P o conjunto das cadeias de 0´s e 1´s (incluindo a
cadeia vazia). Defina a ordenação  sobre P da seguinte
forma: u  v se e somente se v é prefixo de u. (Considere
que a cadeia vazia é prefixo de qualquer cadeia).
• Mostre que (P,  ) é um poset
• Desenhe o diagrama de Hasse para as cadeias cujo
tamanho é menor ou igual a 3
• Encontre os elementos maximais e minimais
• Existe o menor/maior elemento? Qual?
• Encontre os limitantes superiores/inferiores de {01,10}
• Encontre o supremo e ínfimo de {0} (caso existam)
Matemática Discreta – if670
Centro de Informática / UFPE
22
Reticulados
• Um poset onde cada par de elementos possui um
supremo e um ínfimo é chamado de reticulado
f
d
e
c
b
a
O segundo diagrama não é um reticulado. Os
elementos b e c não têm supremo. Os elementos d,e
e f são limitantes superior de b e c, no entanto não
existe o menor entre eles.
Matemática Discreta – if670
Centro de Informática / UFPE
23
Exemplo
• Em muitos sistemas o fluxo de informação
entre pessoas e programas é gerenciado
por políticas de segurança.
• O seguinte reticulado modela uma
determinada política de segurança.
• Cada pedaço de uma informação é
associado a uma classe de segurança,
representada por um par (A,C).
Matemática Discreta – if670
Centro de Informática / UFPE
24
Exemplo
• No par (A,C), A significa o nível de autoridade,
que pode ser: 0 – não classificado; 1 –
confidencial; 2 – secreto; e 3 – altamente secreto
• C são categorias representadas por subconjuntos
de todos os cargos ou compartimentos relevantes
de uma determinada área.
• Se o conjunto de cargos é {agentes, espiões,
agentes duplos}, então temos 8 categorias.
Matemática Discreta – if670
Centro de Informática / UFPE
25
Exemplo
• As classes de segurança podem ser
ordenadas especificando que (A1,C1) 
(A2,C2) se e somente se A1  A2 e C1  C2
• As informações podem ser passadas de
uma classe de segurança (A1,C1) para
(A2,C2) se e somente se (A1,C1)  (A2,C2) .
• Que classe de segurança seria o supremo
e ínfimo de cada par de classe?
• Supremo: (maior(A1, A2), C1C2)
• Ínfimo: (menor(A1, A2), C1C2)
Matemática Discreta – if670
Centro de Informática / UFPE
26