relacao de equivalencia

Prévia do material em texto

5) Relações5) Relações
5.1) Relações e Dígrafos5.1) Relações e Dígrafos
5.2) Propriedades de Relações5.2) Propriedades de Relações
5.3) Relações de Equivalência5.3) Relações de Equivalência
5.4) Manipulação de Relações 5.4) Manipulação de Relações 
5.5) Fecho de Relações5.5) Fecho de Relações
INE5403INE5403 -- Fundamentos de Matemática Fundamentos de Matemática 
Discreta para a ComputaçãoDiscreta para a Computação
Relações de equivalênciaRelações de equivalência
•• Suponha que a matrícula dos estudantes em uma dada Suponha que a matrícula dos estudantes em uma dada 
universidade siga o esquema:universidade siga o esquema:
Inicial do nome : Horário de matrícula :
A – G 8 :00 – 11 :00
H – N 11 :00 – 14 :00
O – Z 14 :00 – 17 :00
•• Seja R a relação que contém (x,y) se x e y são estudantes Seja R a relação que contém (x,y) se x e y são estudantes 
com nomes começando com letras do mesmo bloco.com nomes começando com letras do mesmo bloco.
•• Consequentemente, x e y podem se matricular na mesma Consequentemente, x e y podem se matricular na mesma 
hora se e somente se (x,y)hora se e somente se (x,y)∈∈ R.R.
•• PodePode--se notar que R é reflexiva, simétrica e transitiva.se notar que R é reflexiva, simétrica e transitiva.
•• Além disto, R divide os estudantes em 3 classes (Além disto, R divide os estudantes em 3 classes (equivalentesequivalentes).).
Relações de equivalênciaRelações de equivalência
•• Suponha dois horários (inteiros) a=20:00 e b=68:00. Estes Suponha dois horários (inteiros) a=20:00 e b=68:00. Estes 
horários estão relacionados pela relação “congruência módulo horários estão relacionados pela relação “congruência módulo 
24”, pois:24”, pois:
24 | (6824 | (68--20) ou 68=20 + k.2420) ou 68=20 + k.24
•• ““Um inteiro a está relacionado a um inteiro b se ambos Um inteiro a está relacionado a um inteiro b se ambos 
tiverem o mesmo resto quando divididos por 24”.tiverem o mesmo resto quando divididos por 24”.
–– podepode--se mostrar que esta relação é reflexiva, simétrica e se mostrar que esta relação é reflexiva, simétrica e 
transitiva. transitiva. 
•• ConcluiConclui--se que esta relação subdivide o conjunto dos inteiros se que esta relação subdivide o conjunto dos inteiros 
em 24 classes diferentes.em 24 classes diferentes.
•• Como o que nos interessa realmente é só o momento do dia, Como o que nos interessa realmente é só o momento do dia, 
só precisamos saber a que só precisamos saber a que classeclasse pertence um valor dado.pertence um valor dado.
Relações de equivalênciaRelações de equivalência
•• DefiniçãoDefinição: Uma relação R sobre um conjunto A é chamada : Uma relação R sobre um conjunto A é chamada 
uma uma relação de equivalênciarelação de equivalência se ela for uma relação se ela for uma relação 
reflexiva, simétrica e transitiva.reflexiva, simétrica e transitiva.
•• Dois elementos relacionados por uma relação de equivalência Dois elementos relacionados por uma relação de equivalência 
são ditos são ditos equivalentesequivalentes..
Relações de equivalênciaRelações de equivalência
•• Exemplo1Exemplo1: Sejam A={1,2,3,4} e: Sejam A={1,2,3,4} e
R={(1,1),(1,2),(2,1),(2,2),(3,4),(4,3),(3,3),(4,4)}.R={(1,1),(1,2),(2,1),(2,2),(3,4),(4,3),(3,3),(4,4)}.
R é uma relação de equivalência, pois satisfaz às 3 propriedadesR é uma relação de equivalência, pois satisfaz às 3 propriedades::
•• ReflexividadeReflexividade: R é reflexiva, pois {(1,1),(2,2),(3,3),(4,4)}: R é reflexiva, pois {(1,1),(2,2),(3,3),(4,4)}⊆⊆ RR
•• SimetriaSimetria: nota: nota--se que ase que a∈∈ R(b) R(b) ⇔⇔ bb∈∈ R(a)R(a)
•• TransitividadeTransitividade: nota: nota--se que: bse que: b∈∈ R(a) e cR(a) e c∈∈ R(b) R(b) ⇒⇒ cc∈∈ R(a)R(a)
•• Exemplo2Exemplo2: Seja A=Z o conjunto dos inteiros e seja R={(a,b): Seja A=Z o conjunto dos inteiros e seja R={(a,b)∈∈ AA××A|aA|a≤≤bb}.}.
R não é uma relação de equivalência, pois:R não é uma relação de equivalência, pois:
•• ReflexividadeReflexividade: R é reflexiva, pois : R é reflexiva, pois aa≤≤a, a, ∀∀ aa∈∈ AA
•• SimetriaSimetria: b: b≤≤a não segue de aa não segue de a≤≤b b ⇒⇒ R não R não éé simsiméétricatrica
•• TransitividadeTransitividade: se a: se a≤≤b e bb e b≤≤c c ⇒⇒ aa≤≤c, portanto se c, portanto se aRbaRb e e bRcbRc
então aRc. Assim, R então aRc. Assim, R éé transitiva.transitiva.
Relações de equivalênciaRelações de equivalência
•• Exemplo3Exemplo3: Seja m um inteiro positivo > 1. Mostre que a relação: Seja m um inteiro positivo > 1. Mostre que a relação
R={ (a,b) | aR={ (a,b) | a≡≡b (b (modmod m) }m) }
éé uma uma relarelaçção de equivalênciaão de equivalência sobre o conjunto dos inteiros.sobre o conjunto dos inteiros.
•• Lembre que: aLembre que: a≡≡b (b (modmod m) m) ⇔⇔ m|(am|(a--b) b) 
–– ReflexividadeReflexividade: a: a≡≡a (a (modmod m) pois am) pois a--a=0 e m|0 a=0 e m|0 ⇒⇒ aRaaRa
–– SimetriaSimetria: : se ase a≡≡b (b (modmod m), então am), então a--b=k.m b=k.m ⇒⇒ bb--a=(a=(--k).m k).m 
⇒⇒ bb≡≡a (a (modmod m)m)
assim: assim: aRbaRb ⇒⇒ bRabRa
–– TransitividadeTransitividade: suponha que a: suponha que a≡≡b (b (modmod m) e bm) e b≡≡c (c (modmod m)m)
⇒⇒ m divide tanto (bm divide tanto (b--a) como (ca) como (c--b)b)
⇒⇒ aa--b=k.m e bb=k.m e b--c=l.mc=l.m
⇒⇒ aa--c = (ac = (a--b)+(bb)+(b--c) = (k+l).mc) = (k+l).m
⇒⇒ aa≡≡c (c (modmod m)m)
portanto, portanto, aRbaRb e e bRcbRc ⇒⇒ aRc e R aRc e R éé transitiva.transitiva.
Relações de equivalência e partiçõesRelações de equivalência e partições
•• DefiniçãoDefinição::
Uma Uma partiçãopartição ou ou conjunto quociente conjunto quociente de um conjunto não de um conjunto não 
vazio A é uma coleção vazio A é uma coleção PP de subconjuntos não vazios de A tal de subconjuntos não vazios de A tal 
que:que:
1. Cada elemento de A pertence a algum dos conjuntos em 1. Cada elemento de A pertence a algum dos conjuntos em PP
2. Se A2. Se A11 e Ae A22 são elementos distintos em são elementos distintos em PP, então A, então A11∩∩AA22==∅∅ ..
–– Os conjuntos em P são chamados de Os conjuntos em P são chamados de blocosblocos ou ou células células 
da partição.da partição.
Relações de equivalência e partiçõesRelações de equivalência e partições
•• ExemploExemplo: A={1,2,3,5,7,9,11,13}: A={1,2,3,5,7,9,11,13}
1 2
3
A1
A2
A3
A4
5 
9
7
11 
13
•• AA11={1,2,3} A={1,2,3} A22={5,9} A={5,9} A33={7} A={7} A44={11,13}={11,13}
•• PP={A={A11, A, A22, A, A33, A, A44} é uma partição do conjunto A em 4 blocos.} é uma partição do conjunto A em 4 blocos.
Relações de equivalência e partiçõesRelações de equivalência e partições
•• Uma partição Uma partição PP pode ser usada para construir uma relação de pode ser usada para construir uma relação de 
equivalência sobre A.equivalência sobre A.
•• TeoremaTeorema: Seja : Seja PP uma partição sobre um conjunto A. Defina uma uma partição sobre um conjunto A. Defina uma 
relação R sobre A como:relação R sobre A como:
aRbaRb se e somente se a e b são membros do mesmo bloco.se e somente se a e b são membros do mesmo bloco.
Então R é uma Então R é uma relação de equivalênciarelação de equivalência sobre A (sobre A (determindetermin. por . por PP).).
ProvaProva::
(1) Se a(1) Se a∈∈ A, então a estA, então a estáá no mesmo bloco que ele mesmo,no mesmo bloco que ele mesmo,
de modo que aRa de modo que aRa ⇒⇒ R R éé reflexivareflexiva
(2) Se (2) Se aRbaRb então a e b estão no mesmo bloco, logo então a e b estão no mesmo bloco, logo bRabRa
⇒⇒ R R éé simsiméétricatrica
(3) Se (3) Se aRbaRb e e bRcbRc, então a, b e c estão no mesmo bloco , então a, b e c estão no mesmo bloco PP, logo aRc., logo aRc.
Portanto: Portanto: aRbaRb e e bRcbRc ⇒⇒ aRc (R aRc (R éé transitiva).transitiva).
Relações de equivalência e partiçõesRelações de equivalência e partições
•• ExemploExemplo: Seja A={1,2,3,4} e considere uma partição : Seja A={1,2,3,4} e considere uma partição 
PP={{1,2,3}, {4}}. Ache a relação de equivalência ={{1,2,3}, {4}}. Ache a relação de equivalência 
determinada por determinada porPP..
•• SoluçãoSolução: Os blocos de : Os blocos de PP são {1,2,3} e {4}. Para construir esta são {1,2,3} e {4}. Para construir esta 
relação, cada elemento do bloco deve estar relacionado com relação, cada elemento do bloco deve estar relacionado com 
todos os outros elementos no mesmo bloco e somente estes todos os outros elementos no mesmo bloco e somente estes 
elementos. Assim:elementos. Assim:
R={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,4)}R={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,4)}
Relações de equivalência e partiçõesRelações de equivalência e partições
•• TeoremaTeorema: Seja R uma relação : Seja R uma relação de equivalência sobre A e seja de equivalência sobre A e seja 
PP a coleção de todos os conjuntos relativos R(a), para todo a coleção de todos os conjuntos relativos R(a), para todo 
aa∈∈ A. EntãoA. Então PP é uma partição de A, e R é a relação de é uma partição de A, e R é a relação de 
equivalência determinada por equivalência determinada por PP..
–– Se R é uma relação de equivalência sobre A, então os Se R é uma relação de equivalência sobre A, então os 
conjuntos R(a) são chamados de conjuntos R(a) são chamados de classes de equivalênciaclasses de equivalência
de R. de R. 
–– A partição A partição PP construída no teorema acima consiste construída no teorema acima consiste 
portanto de todas as classes de equivalência de R e esta portanto de todas as classes de equivalência de R e esta 
partição é denotada por A/R. partição é denotada por A/R. 
–– Partições de um conjunto A também são chamadas de Partições de um conjunto A também são chamadas de 
“conjuntos quocientes” de A, e a notação A/R lembra que “conjuntos quocientes” de A, e a notação A/R lembra que 
PP é o conjunto quociente de A que é construído e é o conjunto quociente de A que é construído e 
determinado por R.determinado por R.
Relações de equivalência e partiçõesRelações de equivalência e partições
•• Exemplo1Exemplo1:: Seja Seja A={1,2,3,4} e seja a relação de equivalência A={1,2,3,4} e seja a relação de equivalência 
R sobre A definida porR sobre A definida por
R={(1,1), (1,2), (2,1), (2,2), (3,4), (4,3), (3,3), (4,4)}.R={(1,1), (1,2), (2,1), (2,2), (3,4), (4,3), (3,3), (4,4)}.
Determine A/R (todas as classes de equivalência de R).Determine A/R (todas as classes de equivalência de R).
•• SoluçãoSolução:: R(1) = {1,2}R(1) = {1,2}
R(2) = {1,2}R(2) = {1,2}
R(3) = {3,4}R(3) = {3,4}
R(4) = {3,4}R(4) = {3,4}
⇒⇒ A/R = {{1,2} , {3,4}}A/R = {{1,2} , {3,4}}
Relações de equivalência e partiçõesRelações de equivalência e partições
•• Exemplo2Exemplo2: Seja : Seja A=A=ZZ e seja R={(a,b)e seja R={(a,b)∈∈ AA××A | 2|(aA | 2|(a--b)} (como já b)} (como já 
visto, R é uma relação de equivalência). Determinar A/R. visto, R é uma relação de equivalência). Determinar A/R. 
•• SoluçãoSolução::
–– R(0)={R(0)={…… --6, 6, --4, 4, --2, 0, 2, 4, 6, 2, 0, 2, 4, 6, ……} (O conjunto dos inteiros } (O conjunto dos inteiros 
pares, pois 2 divide a diferença entre quaisquer dois inteiros pares, pois 2 divide a diferença entre quaisquer dois inteiros 
pares.)pares.)
–– R(1)={ R(1)={ …… --5, 5, --3, 3, --1, 0, 1, 3, 5, 1, 0, 1, 3, 5, ……} (O conjunto dos inteiros } (O conjunto dos inteiros 
ímpares, pois 2 divide a diferença entre quaisquer dois inteirosímpares, pois 2 divide a diferença entre quaisquer dois inteiros
ímpares.)ímpares.)
–– Assim, A/R consiste do conjunto dos inteiros pares e do Assim, A/R consiste do conjunto dos inteiros pares e do conjutoconjuto
dos inteiros ímpares, isto é, A/R={R(0), R(1)}.dos inteiros ímpares, isto é, A/R={R(0), R(1)}.
Procedimento geral para determinar partições A/RProcedimento geral para determinar partições A/R
•• Passo 1Passo 1.. Escolha um elemento qualquer de A, digamos a, e calcule Escolha um elemento qualquer de A, digamos a, e calcule 
a classe de equivalência R(a).a classe de equivalência R(a).
•• Passo 2Passo 2.. Se R(a)Se R(a)≠≠A, escolha um elemento b não incluído em R(a) e A, escolha um elemento b não incluído em R(a) e 
calcule a classe de equivalência R(b).calcule a classe de equivalência R(b).
•• Passo 3Passo 3.. Se A não é igual a união das classes de equivalência Se A não é igual a união das classes de equivalência 
previamente calculadas, então escolha um elemento x de A que nãopreviamente calculadas, então escolha um elemento x de A que não
esteja em nenhuma dessas classes de equivalência e calcule R(x).esteja em nenhuma dessas classes de equivalência e calcule R(x).
•• Passo 4Passo 4.. Repita o passo 3 até que todos os elementos de A estejam Repita o passo 3 até que todos os elementos de A estejam 
em classes de equivalência já calculadas. Se A é infinito este em classes de equivalência já calculadas. Se A é infinito este 
processo pode continuar indefinidamente. Neste caso, continue atprocesso pode continuar indefinidamente. Neste caso, continue até é 
que apareça um padrão que permita descrever ou dar uma fórmula que apareça um padrão que permita descrever ou dar uma fórmula 
para todas as classes de equivalênciapara todas as classes de equivalência
Relações de equivalência Relações de equivalência -- ExercíciosExercícios
•• Exercício 1Exercício 1: Seja A={a,b,c}. Determine se a relação R cuja : Seja A={a,b,c}. Determine se a relação R cuja 
matriz é dada abaixo é uma relação de equivalência.matriz é dada abaixo é uma relação de equivalência.
•• Resp.Resp.: SIM. (Por quê?): SIM. (Por quê?)










=
110
110
001
MR
Relações de equivalência Relações de equivalência -- ExercíciosExercícios
•• Exercício 2Exercício 2: Determine se a relação R cujo dígrafo é dado : Determine se a relação R cujo dígrafo é dado 
abaixo é uma relação de equivalência.abaixo é uma relação de equivalência.
•• Resp.Resp.: SIM. (Por quê?): SIM. (Por quê?)
1
4
6
3
2
5
Relações de equivalência Relações de equivalência -- ExercíciosExercícios
•• Exercício 3Exercício 3: Se {{1,3,5}, {2,4}} é uma partição do conjunto : Se {{1,3,5}, {2,4}} é uma partição do conjunto 
A={1,2,3,4,5}, determine a relação de equivalência R A={1,2,3,4,5}, determine a relação de equivalência R 
correspondente.correspondente.
•• Resp.Resp.: : 
R={(1,1),(1,3),(1,5),(3,1),(3,3),(3,5),(5,1),(5,3),(5,5),R={(1,1),(1,3),(1,5),(3,1),(3,3),(3,5),(5,1),(5,3),(5,5),
(2,2),(2,4),(4,2),(4,4)}(2,2),(2,4),(4,2),(4,4)}