Lista2b-Relações de equivalência e congruência -2013

Prévia do material em texto

Universidade Federal de São Carlos – Departamento de Computação 
Estruturas Discretas – Lista de Exercícios – Relações de Equivalência 
 
1) Quais dos conjuntos a seguir são relações de equivalência? Justifique suas respostas. 
a) R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)} no conjunto {1, 2, 3} 
b) R = {(1, 2), (2, 3), (3, 1)} no conjunto {1, 2, 3} 
c) | (relação divide) em Z 
d) {1, 2, 3}  {1, 2, 3} no conjunto {1, 2, 3} 
 
2) Para cada relação de equivalência ache a classe de equivalência pedida. 
a) R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} em {1, 2, 3, 4}. Ache [1]. 
b) R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} em {1, 2, 3, 4}. Ache [4]. 
c) R é tem-o-mesmo-tamanho-que em 2{1, 2, 3, 4, 5}. Ache [{1, 3}]. 
 
3) Considere o conjunto A = {1, 2, 3, 4, 5, 6} e a relação de equivalência R sobre esse conjunto: 
R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4), (4, 5), (4, 6), (5, 4), (5, 5), (5, 6), (6, 4), (6, 
5), (6, 6)}. 
Encontre as classes de equivalência dessa relação e faça o diagrama de Venn dessas classes. 
 
4) Seja R a seguinte relação de equivalência no conjunto A = {1, 2, 3, 4, 5, 6}: 
R = {(1, 1), (1, 5), (2, 2), (2, 3), (2, 6), (3, 2), (3, 3), (3, 6), (4, 4), (5, 1), (5, 5), (6, 2), (6, 
3), (6, 6)} 
Ache a partição de A induzida por R, isto é, ache todas as classes de equivalência de R. 
 
5) Considere o conjunto de palavras W = {saúde, luva, sal, pato, peso, som}. Ache a relação de 
equivalência R em W definida por 
a) “tem o mesmo número de letras que” 
b) “começa com a mesma letra que”. 
 
6) Seja R uma relação de equivalência em um conjunto A e sejam a, b A. Prove que Se (a, b) 
R, então [a][b] = . 
 
7) Seja R uma relação de equivalência em um conjunto A e seja aA. Prove que a  [a]. 
 
8) Seja R uma relação de equivalência em um conjunto A. Prove ou refute: Se [a][b], então 
[a] = [b]. 
 
9) Há apenas uma relação de equivalência possível em um conjunto de um elemento: se A = {1}, 
então R = {(1,1)} é a única relação de equivalência possível. Há exatamente duas relações de 
equivalência possíveis em um conjunto de dois elementos. Quais são elas? Quantas e quais 
relações de equivalência diferentes são possíveis em um conjunto com três elementos? 
 
10) Mostre que a relação R = {(x,y) | x  y mod 4}, definida em Z, é uma relação de 
equivalência. 
 
11) Encontre as classes de equivalência da seguinte relação de equivalência: 
R = {(x,y) | x  y mod 3} em {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. 
(OBS:- x  y mod 3 se 3|(x-y)). 
 
12) Prove que se x e y são ambos ímpares, então xy (mod 2).