A maior rede de estudos do Brasil

Grátis
49 pág.
07-relacoes

Pré-visualização | Página 2 de 2

Relações de Equivalência
• Uma relação binária em um conjunto S que 
é reflexiva, simétrica e transitiva é chamada 
uma relação de equivalência em S
• Exemplos:
‣ x ρ y ↔ x+y é par
‣ x ρ y ↔ x = y
Partição de um Conjunto
• Uma partição de um conjunto S é uma 
coleção de subconjuntos disjuntos não-
vazios de S, cuja união é igual a S.
• Exemplo
‣ S = {a, b, c, d, e, f, g}
‣ {{a, b}, {c, d}, {e, f, g}} é uma partição de S
Teorema
• Uma relação de equivalência ρ em um 
conjunto S determina uma partição de S.
• Uma partição de S determina uma relação 
de equivalência em S.
• Uma relação de equivalência divide o 
conjunto onde ela está definida em uma 
partição.
• Os subconjuntos que compõem a partição 
são formados agrupando-se os elementos 
relacionados.
• Exemplo
‣ S é o conjunto dos alunos em uma sala
‣ x ρ y ↔ “x senta na mesma fila que y”
Alunos 
na fila 1
Alunos 
na fila 2
...
Alunos 
na fila n
S
Classes de Equivalência
• Seja ρ é uma relação de equivalência em 
um conjunto S e x ∈ S
• Denota-se por [x] o conjunto de todos os 
elementos de S relacionados a x:
‣ [x] = {y | y ∈ S ∧ x ρ y} 
• Esse conjunto é chamado de classe de 
equivalência de x.
Exemplo
• Sabemos que x ρ y ↔ “x+y é par” é um 
relação de equivalência em ℕ. Quais são as 
classes de equivalência correspondentes?
Exemplo
• Sabemos que x ρ y ↔ “x+y é par” é um 
relação de equivalência em ℕ. Quais são as 
classes de equivalência correspondentes?
‣ [1] e [2]
Exemplo
• Sabemos que x ρ y ↔ “x+y é par” é um 
relação de equivalência em ℕ. Quais são as 
classes de equivalência correspondentes?
Ímpares Pares
ℕ
‣ [1] e [2]
Congruência Módulo n
• Sejam x e y inteiros e n um inteiro positivo
‣ x ≡ y (mod n) se x-y é um múltiplo inteiro de n
• Exemplos
‣ 9 ≡ 1(mod 4), pois 9-1 é múltiplo de 4
• A relação binária “congruência módulo n” é 
sempre uma relação de equivalência em ℤ
• Conceito importante no projeto de 
arquitetura de computadores.

Acesse esse e outros materiais grátis

Ao se conectar, você aceita os Termos de Uso e a Política de Privacidade.

Já tem cadastro?