Para Computação
Aula de Monitoria – Mini-prova 6
2013.1
Roteiro
• Relações de equivalência
• Ordens parciais
Relações de Equivalência
Questões:
1ª) Quais dessas relações sobre o conjunto de todas
as pessoas são relações de equivalência?
a)
b)
c)
d)
e)
{ (a,b) | a e b tem a mesma idade }
{ (a,b) | a e b tem os mesmos pais}
{ (a,b) | a e b compartilham um pai em comum}
{ (a,b) | a e b já saíram juntos}
{ (a,b) | a e b falam um idioma em comum }
Relações de Equivalência
2ª) Seja R a relação sobre pares ordenados de
inteiros positivos tal que ((a,b),(c,d)) ∈ R se e
somente se a + d = b + c. Mostre que R é uma
relação de equivalência.
Relações de Equivalência
3ª) Uma relação binária R em um conjunto A é uma
quase-ordem em A se R é reflexiva e transitiva. Seja
R uma quase-ordem em A. Mostre que 𝑅 ∩ 𝑅−1 é
uma relação de equivalência.
Ordens Parciais
Questões:
1ª) Determine quais dos itens a seguir são conjuntos
parcialmente ordenados:
a) (Z,=)
b) (Z,≠)
c) (Z,≥)
Ordens Parciais
2ª) Seja S = {1,2,3,4}. Considere a ordem
lexicográfica baseada na relação “menor que”.
a) Encontre todos os pares em SxS menores que
(2,3).
b) Encontre todos os pares em SxS maiores que
(3,1).
c) Desenhe o diagrama de Hasse para o conjunto
parcialmente ordenado (SxS, ≤)
Ordens Parciais
3ª) Seja P o conjunto de todos os subconjuntos de S
= {1,2,3}. Seja R a relação sobre P, onde xRy se e
somente se x é subconjunto próprio de y. O conjunto
(P,R) é parcialmente ordenado? Justifique sua
resposta.
Ordens Parciais
4ª) Desenhe o diagrama de Hasse para a relação de
divisibilidade no conjunto:
a) {1,2,3,4,5,6,7,8}
b) {1,2,3,5,7,11,13}
c) {1,2,4,16,32,64}
Dúvidas
?