Relações2-2013_b

Prévia do material em texto

Estruturas Discretas
Relações de equivalência
2º. Sem.2013
HAC ED 2013 1
Relação de Equivalência
• Seja R uma relação em um conjunto A. 
• Dizemos que R é uma relação de equivalência se R é reflexiva, 
simétrica e transitiva.
• Relações de equivalência são relações que apresentam forte 
semelhança com a relação de igualdade. Objetos relacionados 
por uma relação de equivalência são objetos parecidos.
HAC ED 2013 2
Exemplo
• Considere o conjunto dos subconjuntos (conjunto das partes) de X = 
{1, 2, 3, 4, 5}
2X = {∅, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, ....}.
• Vamos definir a relação R “tem o mesmo tamanho que” sobre o 
conjunto 2X. conjunto 2X. 
• Essa relação estabelece uma ligação entre conjuntos, que são os 
elementos de 2X. 
• Assim, para dois conjuntos A e B ∈ 2X, 
ARB se e somente se |A| = |B|.
HAC ED 2013 3
• Por exemplo,
– ({2},{3}) ∈ R
– ({1,2},{4,5}) ∈ R 
– ({1},{4,5}) ∉ R.
• A relação “tem o mesmo tamanho que” assim definida é 
relação de equivalência, pois é 
• reflexiva, 
• simétrica e 
• transitiva. 
HAC ED 2013 4
Verificação:
• Vamos verificar que a relação “tem o mesmo tamanho 
que”, definida sobre o conjunto 2X é relação de 
equivalência.
• Observações:
• A verificação de que um resultado é verdadeiro não é a 
mesma coisa que prova. 
• Verificação é uma discussão informal que apresenta 
evidências de que a afirmação é verdadeira.
HAC ED 2013 5
• Reflexiva: Um elemento de 2X, seja qual for, tem o mesmo 
número de elementos que ele mesmo, logo, para todo A ∈ 2X, 
ARA.
• Simétrica: Se um elemento A de 2X tem o mesmo tamanho • Simétrica: Se um elemento A de 2X tem o mesmo tamanho 
que um elemento B de 2X, obviamente B tem o mesmo 
tamanho que A. Assim, 
Se ARB então BRA.
HAC ED 2013 6
• Transitiva: Se um elemento A de 2X tem o mesmo 
tamanho que um elemento B de 2X,que por sua 
vez tem o mesmo tamanho que um elemento C vez tem o mesmo tamanho que um elemento C 
de 2X, é fácil concluir que A tem o mesmo 
tamanho que C, logo, 
se ARB e BRC, então ARC.
HAC ED 2013 7
• A relação de inclusão definida sobre um conjunto 
de conjuntos é relação de equivalência?
• é reflexiva 
• é transitiva.• é transitiva.
• Não é simétrica, 
já que A ⊆ B não implica B ⊆ A.
• Logo, NÃO é relação de equivalência.
HAC ED 2013 8
Classes de equivalência
• Classes de equivalência são conjuntos de 
elementos relacionados uns com os outros. 
• Uma relação de equivalência sempre determina 
classes de equivalência sobre o conjunto em que 
está definida.
HAC ED 2013 9
• Seja R uma relação de equivalência em um conjunto A e seja a 
∈ A. 
• A classe de equivalência de a, denotada por [a], é o conjunto 
de todos os elementos de A, relacionados com a (pela R), isto 
é,é,
[a] = {x ∈ A | x R a}
• Qualquer b ∈ [a] é dito representante da classe de 
equivalência.
HAC ED 2013 10
Exemplo
• A = {1, 2, 3, 4, 5, 6, 7}
• R = {(1,1), (1,2), (1,3), (2,2), (2,1), (2,3), (3,3), (3,1), (3,2), 
(4,4), (4,5), (4,6), (5,5), (5,4), (5,6), (6,6), (6,4), (6,5), (7,7)}
[1] = {1, 2, 3}
[4] = {4, 5, 6}
[7] = {7}
HAC ED 2013 11
Relação “tem o mesmo tamanho que”
• Considere a relação R tem o mesmo tamanho que nos 
subconjuntos finitos de Z. 
• Já verificamos que essa relação é de equivalência. 
• R permite categorizar os subconjuntos finitos de Z de 
acordo com sua cardinalidade. 
As categorias de conjuntos ficam:• As categorias de conjuntos ficam:
conjuntos com cardinalidade 0: ∅
conjuntos com cardinalidade 1: ....{-2}, {-1}, {0}, {1}, {2}, ... 
conjuntos com cardinalidade 2: ..... {-2,-1}, {0,1}, {-1,0}, {2,3},.....
HAC ED 2013 12
• Os conjuntos de cada uma dessas categorias estão 
relacionados com todos os conjuntos da mesma categoria 
e não estão relacionados com nenhum de uma categoria 
diferente.
• Cada categoria é uma classe de equivalência:• Cada categoria é uma classe de equivalência:
[∅] = {A ⊆ Z | |A| = 0}= {∅}
• (A classe de equivalência de ∅ é formada pelos conjuntos 
que tem zero elementos. Nesse caso, a classe tem só um 
elemento que é o conjunto vazio.)
HAC ED 2013 13
[{0}] = {A ⊆ Z | |A| = 1}
• A classe de equivalência de {0} é formada pelos 
conjuntos que tem um elemento. 
• Note que qualquer conjunto de um elemento pode 
ser usado como o representante da classe: 
[{0}] = [{-2}] = [{1}] = .....
HAC ED 2013 14
[{0,1}] = {A ⊆ Z | |A| = 2}
• A classe de equivalência de {0,1} é formada pelos 
conjuntos que tem dois elementos. 
• Note que qualquer conjunto de dois elementos pode 
ser usado como o representante da classe: 
[{0,1}] = [{-2,-1}] = [{-1,1}] = .....
HAC ED 2013 15
Relações de equivalência e partições
• As relações de equivalência têm uma forte ligação 
com as partições de conjuntos.
• Lembre que, dado um conjunto não vazio A, uma 
partição de A é uma subdivisão de A em conjuntos partição de A é uma subdivisão de A em conjuntos 
não vazios, disjuntos. 
• Qualquer relação de equivalência determina uma 
partição no conjunto em que está definida.
HAC ED 2013 16
Exemplo
• A = {1, 2, 3, 4, 5, 6, 7}
• R = {(1,1), (1,2), (1,3), (2,2), (2,1), (2,3), (3,3), (3,1), (3,2), (4,4), (4,5), 
(4,6), (5,5), (5,4), (5,6), (6,6), (6,4), (6,5), (7,7)}
[1] = {1, 2, 3}
[4] = {4, 5, 6}
[7] = {7}
• Qual a partição induzida por R em A?
P = {{1, 2, 3}, {4, 5, 6}, {7}}
HAC ED 2013 17
Teorema
Seja R uma relação de equivalência em um conjunto A. O 
conjunto das classes de equivalência de A pela R é uma 
partição de A. Especificamente:
• para cada a ∈ A, temos a ∈ [a].• para cada a ∈ A, temos a ∈ [a].
• [a] = [b] se e somente se (a,b) ∈ R.
• Se [a] ≠ [b], então [a] e [b] são disjuntos.
• Por outro lado, dada uma partição {Ai} do conjunto A, 
existe uma relação de equivalência R em A tal que os 
conjuntos Ai são as classes de equivalência de R.
HAC ED 2013 18
Corolário
• Seja R uma relação de equivalência em um 
conjunto A. 
• As classes de equivalência de R são 
subconjuntos de A não-vazios, disjuntos dois a subconjuntos de A não-vazios, disjuntos dois a 
dois, cuja união é A.
HAC ED 2013 19
Congruência Módulo n
• Seja n um inteiro positivo. Dizemos que os inteiros x e y são 
congruentes módulo n se n|(x-y) (lê-se n divide x-y) e escrevemos 
x ≡ y (mod n)
• (lê-se x é congruente a y módulo n).
• Em outras palavras, x ≡ y (mod n) se e somente se x e y diferem 
por um múltiplo de n. Em geral abreviamos para mod a palavra 
módulo. 
• Vamos usar a expressão /≡ para indicar que dois números inteiros 
não são congruentes. 
HAC ED 2013 20
Exemplos
• 3 ≡ 13 (mod 5) porque 3 – 13 = -10 é múltiplo de 5.
• 4 ≡ 4 (mod 2) porque 4 – 4 = 0 é múltiplo de 2.• 4 ≡ 4 (mod 2) porque 4 – 4 = 0 é múltiplo de 2.
• 10 ≡ 4 (mod 3) porque 10 – 4 = 6 é múltiplo de 3.
• 16 /≡ 3 (mod 5) porque 16 – 3 = 13 não é múltiplo de 5.
HAC ED 2013 21
Congruência mod 2
• 3 ≡ 115 (mod 2) porque 3 – 115 = -112 é divisível por 2.
• 0 ≡ 14 (mod 2) porque 0 – 14 = -14 é divisível por 2.
• 19 ≡ 5 (mod 2) porque 19 – 5 = 14 é divisível por 2.
• 3 ≡ 3 (mod 2) porque 3 – 3 = 0 é divisível por 2.• 3 ≡ 3 (mod 2) porque 3 – 3 = 0 é divisível por 2.
• 3 /≡ 12 (mod 2) porque 3-12 = -9 não é divisível por 2.
• -1 /≡ 0 (mod 2) porque -1-0 = -1 não é divisível por 2.
• Observação: Dois números são congruentes módulo 2 se e somente 
se ambos são pares ou ambos são ímpares (têm a mesma 
paridade).
HAC ED 2013 22
Observação
• A relação de congruência módulo 2 é uma relação de equivalência.
• Podemos verificar as propriedades: 
≡– Reflexiva: x ≡ x (mod 2) 
– Simétrica: x ≡ y (mod 2) => y ≡ x (mod 2) 
– Transitiva: (x ≡ y (mod 2) e y ≡ z (mod 2)) => x ≡z (mod 2) 
(Fazer as verificações como exercício)
HAC ED 2013 23
Observação
• Dois números são congruentes módulo 2 se e somente se ambos são 
pares ou ambos são ímpares (têm a mesma paridade).
• Estão definidas duas classes de números pela relação congruentes 
mod 2: a classe dos números pares e a dos números ímpares. 
• Números pares relacionam-se apenas com números pares e números 
ímpares relacionam-se apenas com números ímpares, pela relação 
de congruência módulo 2. 
• Assim, essas duas classes são classes de equivalência dos inteiros, 
pela relação R.
HAC ED 2013 24
vamos considerar a classe de equivalência do número 1, denotada por 
[1]:
[1] = {x ∈ Z | x ≡ 1 (mod 2)}
Dessa forma, esse é o conjunto de todos os inteiros x tais que 2 | (x-Dessa forma, esse é o conjunto de todos os inteiros x tais que 2 | (x-
1), isto é, 
x-1 = 2k para algum k,
de modo que
x = 2k+1 isto é, x é ímpar.
Assim, a classe de equivalência [1] é formada por todos os números 
ímpares.
HAC ED 2013 25
Vamos considerar agora a classe de equivalência do zero, denotada por 
[0]:
[0] = {x ∈ Z | x ≡ 0 (mod 2)}
Esse é o conjunto de todos os inteiros x tais que 2 | x, ou seja, Esse é o conjunto de todos os inteiros x tais que 2 | x, ou seja, 
x = 2k para algum k, isto é, x é par.
Assim, a classe de equivalência [0] é formada por todos os números 
pares.
HAC ED 2013 26
Calculando a classe de equivalência do número 3, [3] podemos constatar que 
[1] = [3].
De forma semelhante, verificamos também que [0] = [2].
Com isso verificamos que a relação de equivalência congruência módulo 2 Com isso verificamos que a relação de equivalência congruência módulo 2 
tem apenas duas classes de equivalência: 
– o conjunto dos inteiros ímpares [1] e 
– o conjunto dos inteiros pares [0]. 
HAC ED 2013 27
• Verificamos que a relação de congruência módulo 2 é de 
equivalência. Além disso, é possível provar que, para 
qualquer valor de n a relação de congruência módulo n é 
de equivalência.
• Teorema:
Seja n um número inteiro positivo. A relação é congruente 
com mod n é uma relação de equivalência no conjunto 
dos inteiros.
HAC ED 2013 28