Universidade Federal de Pernambuco
Centro de Informática
Anjolina Grisi de Oliveira
Relações
• O que é uma relação em um conjunto?
– Uma relação R em um conjunto S é uma relação
de S para S
– Em outras palavras, é um subconjunto de S  S
• O que é uma relação reflexiva?
- Uma relação R em um conjunto S é
chamada de reflexiva se (s,s)  S para todo
elemento s  S.
Matemática Discreta – if670
Centro de Informática / UFPE
2
Relações
• O que é uma relação simétrica?
– Uma relação R em um conjunto S é chamada
simétrica se (b,a)  R toda vez que (a,b)  R,
para a,b  S.
– Em outras palavras: Se (a,b)  R → (b,a)  R.
• O que é uma relação anti-simétrica?
- Uma relação R em um conjunto S é chamada
anti-simétrica se quando (a,b)  R e (b,a)  R
então a = b, para a,b  S.
- Se (a,b)  R Λ (b,a)  R → a = b.
Matemática Discreta – if670
Centro de Informática / UFPE
3
Relações
• O que é uma relação transitiva?
– Uma relação R em um conjunto S é chamada
transitiva se toda vez que (a,b)  R e (b,c) 
R, então (a,c)  R, para a,b,c  S.
– Se (a,b)  R Λ (b,c)  R → (a,c)  R.
Matemática Discreta – if670
Centro de Informática / UFPE
4
Exemplos
Defina uma relação no conjunto {1,2,3,4} que seja:
a) reflexiva, simétrica e não seja transitiva.
R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(2,1),(3,2)}
b) simétrica, transitiva, e não reflexiva
R={(1,1)}
c) reflexiva, anti-simétrica e não transitiva.
R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,3)}
d) reflexiva, simétrica e transitiva
R={(1,1),(2,2),(3,3),(4,4)}
e) reflexiva, anti-simétrica e transitiva
R={(1,1),(2,2),(3,3),(4,4)}
Matemática Discreta – if670
Centro de Informática / UFPE
5
Relações
• Explique como uma matriz de bits pode ser usada para
representar uma relação em um conjunto finito S.
– Liste os elementos de S em uma ordem arbitrária:
{s1,s2,...,sn}
– A relação R pode ser representada pela matriz MR =
[mij] onde:
– [mij] = 1, se (si,sj)  R
– [mij] = 0, se (si,sj)  R
S={1,2,3} e R={(1,2),(2,2),(3,1)}
0
1
0
Ordem: {1,2,3}
0
1
0
1
0
0
Matemática Discreta – if670
Centro de Informática / UFPE
6
Relações
• Explique como uma matriz de bits que representa uma
relação em um conjunto finito S pode ser usada para
determinar se a relação é reflexiva, simétrica, e antisimétrica.
– Reflexiva: se todos os elementos da diagonal principal
forem iguais a 1
– Simétrica: se a matriz for igual a sua transposta
– Anti-simétrica: para i  j, se [mij] = 1 então [mji] = 0. Ou
em outras palavras, quando i  j, ou [mij] = 0 ou [mji] = 0
1
1
0
0
1
0
1
0
1
Matemática Discreta – if670
Reflexiva e anti-simétrica
Centro de Informática / UFPE
7
Relações de Equivalência
• O que é uma relação de equivalência em um conjunto?
– É uma relação que é reflexiva, simétrica e transitiva
• Que relações no conjunto {a,b,c,d} são relações de
equivalência e contêm os pares (a,b) e (b,d) ?
– R1={(a,a),(b,b),(c,c),(d,d),(a,b),(b,d),(a,d),(b,a),(d,b),(d,a)
}
– R2={(a,a),(b,b),(c,c),(d,d),(a,b),(b,d),(a,d),(b,a),(d,b),(d,a)
(a,c),(c,a),(b,c),(d,c),(c,b),(c,d),}
Matemática Discreta – if670
Centro de Informática / UFPE
8
Relações de Equivalência
• O que acontece com um conjunto onde é definida uma
relação de equivalência ?
– É criada uma partição no conjunto
• Dê um exemplo de uma relação de equivalência em um
conjunto e identifique o conceito de classes de
equivalência, relacionando-o com a noção de partição.
– Seja S o conjunto dos inteiros positivos
– R = { (x,y) | x  y (mod 4) }
– Existem quatro classes de equivalência: quando o resto
da divisão for 0, 1, 2 ou 3
– Cada classe de equivalência é um subconjunto da
partição de S.
Matemática Discreta – if670
Centro de Informática / UFPE
9
Ordens Parciais
• O que é uma ordem parcial
– É uma relação em um conjunto que tem as seguintes
propriedades: reflexiva, anti-simétrica e transitiva
• Mostre que a relação de divisibilidade no conjunto dos
inteiros positivos é uma ordem parcial.
– Reflexiva: z  Z+, z|z
– Anti-simétrica: Sejam, a,b,m e n  Z+, se a|b e b|a →
a.m = b e b.n = a → a.m.n = a → m=n=1 → a=b
– Transitiva: Sejam, a,b,c,m e n  Z+, se a|b e b|c → a.m
= b e b.n = c → a.m.n = c → a|c, pois a operação de
multiplicação é fechada em Z+.
Matemática Discreta – if670
Centro de Informática / UFPE
10
Ordens Parciais
• O que é conjunto parcialmente ordenado?
– É um conjunto S juntamente com uma ordem parcial R:
(S,R)
– Também chamamos de poset (do inglês: partially
ordered set)
– Usamos a notação (S,) para falarmos de um poset
arbitrário
Matemática Discreta – if670
Centro de Informática / UFPE
11
• 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
12
• 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
13
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
14
• 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
15
• 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
16
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
17
• 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
18
• Exemplo
Suponha que (S,1) e (T, 2) são conjuntos parcialmente
ordenados. Mostre que (S  T, ) é um conjunto
parcialmente ordenado onde (s,t)  (u,v) se e somente
se s 1 u e t 2 v.
• Reflexiva: (s,t)  S  T, (s,t)  (s,t) pois s 1 s e t 2 t
• Anti-simétrica: se ((s,t),(u,v))   e ((u,v),(s,t))   → s 1 u ,
t 2 v, u 1 s e v 2 t → s = u e t = v → (s,t) = (u,v)
• Transitiva: se ((s,t),(u,v))   e ((u,v),(w,z))   → s 1 u , t
2 v, u 1 w e v 2 z → s 1 w e t 2 z → ((s,t),(w,z))  
Matemática Discreta – if670
Centro de Informática / UFPE
19
Diagrama de Hasse
Desenhe o diagrama de Hasse para ({2,3,5,9,12,15,18},|)
18
Elementos maximais?
15
9
12
2
12,15 e 18
Elementos minimais ?
3
2,3,5
5
Menor elemento?
Maior elemento?
Não
Não
Matemática Discreta – if670
Centro de Informática / UFPE
20
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
21
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
22
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
23
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
24
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
25
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
26