Lista11 Relacoes Equivalencia

Prévia do material em texto

Lista 11 de Matemática Discreta I
Relações de equivalência
1. Quais das seguintes relações em {0, 1, 2, 3} são relações de equivalência? Caso não
seja, indique a propriedade que falha.
(a) {(0, 0), (1, 1), (2, 2), (3, 3)}.
(b) {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}.
(c) {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}.
(d) {(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}.
(e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 2), (3, 3)}
2. Seja A o conjunto de todas as funções f : Z→ Z. Verifique se as seguintes relações
são relações de equivalência em A. Caso não seja, indique a propriedade que falha.
(a) R = {( f , g) : f (1) = g(1)};
(b) R = {( f , g) : f (0) = g(0) ∨ f (1) = g(1)};
(c) R = {( f , g) : f (x) − g(x) = 1, ∀x ∈ Z};
(d) R = {( f , g) : f (1) = g(0) ∧ f (0) = g(1)};
3. Seja A = {(a, b) : a, b ∈ Z∗+}. Verifique se as relações abaixo são relações de
equivalência:
(a) R = {((a, b), (c, d)) : a + d = b + c};
(b) R = {((a, b), (c, d)) : ad = bc};
4. Verifique se as relações representadas pelas matrizes abaixo são relações de equiv-
alência:
a)
1 0 10 1 11 1 1
, b)

1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
, c)

1 1 1 0
1 1 1 0
1 1 1 0
0 0 0 1
.
5. Enumere todos os pares ordenados nas relações de equivalência produzidas pelas
seguintes partições do conjunto {0, 1, 2, 3, 4, 5}.
1
2
(a) {0}, {1, 2}, {3, 4, 5};
(b) {0, 1}, {2, 3}, {4, 5};
(c) {0, 1, 2}, {3, 4, 5};
(d) {0}, {1}, {2}, {3}, {4}, {5}.
6. Seja a relação de equivalência em N dada por {(a, b) : a + b é par}. Descreva a
partição dos naturais determinada por esta relação.
7. Descreva as classes de equivalência de cada uma das relações a seguir:
(a) EmN, xRy se, e só se, x = y;
(b) No conjunto {1, 2, 3}, R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}.
8. Definiremos a relação de congruência módulo m, no conjunto Z dos inteiros: um
inteiro x é congruente a ymódulom, simbolizado por x ≡ y(mod m) se x e ydeixam
restos iguais quando divididos por m. Mostre que isso equivale a dizer que x − y
é um múltiplo exato de m. Já vimos na aula que esta relação é uma relação de
equivalência. Considere agora m = 4 e ache todas as classes de equivalência desta
relação. Repita o exercício para m = 2.