Relacoes_Endorrelacoes

Prévia do material em texto

1 
 
UNIVERSIDADE FEDERAL DE PELOTAS 
CENTRO DESENVOLVIMENTO TECNOLÓGICO – CDTec 
CURSO DE CIÊNCIA DA COMPUTAÇÃO 
CURSO DE ENGENHARIA DE COMPUTAÇÃO 
 
 
Sistemas Discretos I 
Prof. Aline Brum LoretoProf. Aline Brum LoretoProf. Aline Brum LoretoProf. Aline Brum Loreto 
**************************************************************************************** 
RELAÇÕES 
1- Relações 
Entre as operações com conjuntos temos o produto cartesiano. 
 
Relação. Suponha A e B conjuntos. Uma Relação Binária R de A em B é um subconjunto de 
um produto cartesiano BA× , ou seja: 
BAR ×⊂ ou BAR →: 
onde A é denominado domínio, origem ou conjunto de partida de R; 
B é denominado contradomínio, codomínio ou conjunto de chegada de R. 
 Para indicar que Rba ∈),( pode-se usar a notação bRa . Se Rba ∉),( , escreveremos 
bRa . 
 Uma relação BAR ×⊂ é constituída de três partes: a origem A, o destino B e o 
conjunto de pares R. Qualquer alteração em uma destas três partes define uma outra relação. 
 
Exemplos: 
1) Se A = {1, 2, 3, 4} e B = {2, 3, 4, 5}, temos: 
 )}5,4( ),...,5,2( ),4,2( ),3,2( ),2,2( ),5,1( ),4,1( ),3,1( ),2,1{(=× BA 
 a) BAyxR ×∈= ),{(1 | }yx < 
 
 )}5,4( ),5,3( ),4,3( ),5,2( ),4,2( ),3,2( ),5,1( ),4,1( ),3,1( ),2,1{(1 =R 
b) BAyxR ×∈= ),{(2 | x = y} 
 )}4,4( ),3,3( ),2,2{(2 =R 
c) AxByxR ∈= ),{(3 | }10=+ yx 
 φ=3R 
 
2) Se ZBA == , então BA× é o conjunto formado por todos os pares ordenados de números 
inteiros. Um exemplo de relação em Z = ZZ × , é 
 ZZyxR ×∈= ),{(4 | }yx = 
 ),...},( ),...,1,1( ),0,0( ),1,1( ..., ),,{...(4 nnnnR −−−−= 
 
 2 
3) Se ℜ== BA , então BA× é o conjunto formado por todos os pares ordenados de números 
reais. Um exemplo de relação em R= ℜx ℜ, é 25 ),{( ℜ∈= yxR | }0≥y . 
 
4) Sejam A={a}, B={a, b} e C={0, 1, 2}. Então são relações: 
a) ∅ é uma relação de A em B, assim como de A em C, de B em C, etc. (O conjunto vazio é 
sempre subconjunto de qualquer conjunto). 
b) A x B = { 〉〈〉〈 baaa ,,, } é uma relação com origem em A e destino B (pois Ax B⊆AxB); 
c) Considerando o conjunto de partida A e o conjunto de chegada B, a relação de igualdade 
{ 〉〈 aa, }; 
d) }2,1,2,0,1,0{ 〉〈〉〈〉〈 é a relação “menor que” de C em C; 
e) },1,,0{ 〉〈〉〈 ba é uma relação de C em B. 
 
Notação 
Exemplo: Sejam A={a}, B={a,b} e C={0, 1, 2}. Então: 
a) Para a relação ⊂: P(B) → P(B), tem-se que {a} ⊂ {a,b} 
b) Para a relação ≤: C → C, tem-se que 0 ≤ 2 
c) Para a relação =: A →A, tem-se que a =a. 
 
Domínio e imagem. 
 Seja R uma relação de A em B. 
 Chama-se domínio de definição de R o subconjunto de A constituído pelos elementos x 
para cada um dos quais existe algum y em B tal que Ryx ∈),( . 
xRD {)( = ׀ }) ),()( ( RyxByyAx ∈∧∈∃∧∈ 
 
 Chama-se conjunto imagem ou domínio de valores de R o subconjunto de B constituído 
pelos elementos y para cada um dos quais existe algum x em A tal que R),( ∈yx . 
yR {)Im( = ׀ )} ),()( ( RyxAxxBy ∈∧∈∃∧∈ 
 
 Voltando aos exemplos anteriores temos: 
1) }4,3,2,1{)( 1 =RD e }5,4,3,2{)Im( 1 =R 
 }4,3,2{)( 2 =RD e }4,3,2{)Im( 2 =R 
 φ=)( 3RD e φ=)Im( 3R 
2) ZRD =)( 4 e ZR =)Im( 4 
3) IRRD =)( 5 e += IRR )Im( 5 
 
 Logo, D(R) é o conjunto formado pelos primeiros termos dos pares ordenados que 
constituam R e Im(R) é formado pelos segundos termos dos pares ordenados. 
 
 
 
 3 
Representações 
Diagrama de Venn 
 Quando A e B são conjuntos finitos com poucos elementos podemos representar uma 
relação BAR →: usando Diagrama de Venn, onde os dois elementos relacionados são 
ligados por uma seta. 
 
Exemplo: A A 
}2 ,1 ,0{=A 0 0 
2),{( AyxR ∈= }yx < 1 1 
 2 2 
 
Plano Cartesiano. Grande parte das relações em Matemática são relações em que A (conjunto 
de partida) e B (conjunto de chegada) são subconjuntos de ℜ. Nesses casos, o gráfico da 
relação é o conjunto de pontos de um plano dotado de um sistema de coordenadas cartesianas 
ortogonais, cujas abscissas são os primeiros termos e as ordenadas os segundos termos dos 
pares ordenados que constituem a relação. 
Exemplos: y 
 
1) )}1,1( ),1,1( )0,0{(1 −=R 
 0 x 
 
 
 
 
2) 22 ),{( ZyxR ∈= ׀ }yx = y 
 
 
 
 0 x 
 
 4 
 Endorrelação ou Auto-Relação 
Suponha A um conjunto. Então uma relação R: A→A (origem e destino no mesmo conjunto) 
é dita uma Endorrelação ou Auto-Relação. Nesse caso, afirma-se que R é uma relação em A. 
Uma endorrelação R: A→A é denotada por 〉〈 RA, . 
Exemplos: 
Seja A um conjunto. As seguintes relações são endorrelações: 
a) ≤〉〈 ,N 
b) <〉〈 ,Z 
c) =〉〈 ,Q 
d) ⊂〉〈 ),(AP 
 
Obs.: Uma relação não necesariamente relaciona entidades de um mesmo conjunto. 
Por exemplo, uma lista telefônica relaciona pessoas (os assinantes) com números (de 
telefone). 
 
Endorrelação como Grafo 
Toda endorrelação R: A→A pode ser representada como um grafo. 
A representação como grafo é como segue: 
- Cada elemento do conjunto A é representado como um ponto ou círculo, e é 
denominado de nodo; 
- Cada par 〉〈 ba, da relação é representado como uma seta, arco ou aresta, com origem 
em a e destino em b. 
 
Exemplo: 
Sejam A={a}, B={a,b} e C={0, 1, 2}. Então as seguintes relações são representadas como 
grafos: 
a) ∅: A→A (grafo sem arestas) 
b) =〉〈 ,B , dado que = é definida por { 〉〈〉〈 bbaa ,,, } 
c) <〉〈 ,C , dado que < é definida por { 〉〈〉〈〉〈 2,1,2,0,1,0 } 
d) R:C→C tal que R= { 〉〈〉〈〉〈 2,2,0,2,2,0 } 
 
Relação como Matriz 
Suponha A={a1, a2, …, an} e B={b1, b2, …, bn} dois conjuntos finitos. A representação de 
uma relação R:A→B na forma de matriz é como segue: 
- O número de linhas é n (número de elementos do dominio); 
- O número de colunas é m (número de elementos do codomínio); 
- A matriz resultante possui m*n posições ou células; 
- Cada uma das m*n posições da matriz contém um valor lógico (verdadeiro ou 
falso); 
 5 
- Se Rba ji ∈〉〈 , , a posição da matriz determinada pela linha i e coluna j contém o valor 
verdadeiro; caso contrario, contém o valor falso. São utilizados os dígitos 1 para 
representar o verdadeiro e 0 para o falso. 
 
Exemplo: Sejam A={a}, B={a,b} e C={0,1,2}. As seguintes endorrelações são representadas 
como matrizes: 
a) ∅: A→A (grafo sem arestas) 
∅ a 
a 0 
 
b) =〉〈 ,B , dado que = é definida por { 〉〈〉〈 bbaa ,,, } 
= a b 
a 
b 
 
c) <〉〈 ,C , dado que < é definida por { 〉〈〉〈〉〈 2,1,2,0,1,0 } 
< 0 1 2 
0 
1 
2 
 
d) R:C→C tal que R= { 〉〈〉〈〉〈 2,2,0,2,2,0 } 
R 0 1 2 
0 
1 
2 
 
 
Relação Inversa. Seja R uma relação de A em B. Chama-se relação inversa de R, denotada 
por 1−R , a relação de B em A: 
),{(1 xyR =− }),( Ryx ∈ | 
 A relação inversa 1−R é subconjunto de AB × , ao passo que BAR ×⊂ . 
 
Exemplos: 
1) Se }3,2 ,1 ,0{=A e }4,3 ,2 ,1{=B e 
 )4,3( ),3,2( ),2,1(),1,0{(=R }, então 
 )}3,4( ),2,3( ),1,2( ),0,1{(1 =−R . 
 6 
2) Se 2),{( e ℜ∈=ℜ== yxRBA ׀ }2xy = então 
 
21 ),{( ℜ∈=− xyR ׀ 2),{( }2 IRyxxy ∈== ׀ }2yx = 
3) Se 2),{( e ℜ∈=ℜ== yxRBA então }1)2( 22 ≤−+ yx 
 ׀
22221 ),{( }1)2(),{( ℜ∈=≤−+ℜ∈=− yxyxxyR }1)2( 22 ≤−+ xy 
 4) Se 2),{( e ℜ∈=ℜ== yxRBA então }2yx = 
 
21 ),{( ℜ∈=− xyR 22 ),{(} ℜ∈== yxyx }2xy = 
 Se a relação R admite um gráfico cartesiano, então o mesmo ocorre com 1−R . Como 
1),(),( −∈↔∈ RxyRyx , 
Observa-se que o gráfico cartesiano de 1−R é simétrico ao gráfico de R, em relação à reta de 
equação xy = . 
Observação: Representa-se 1−R pelo Diagrama de Venn simplesmente invertendo o sentido 
das setas. 
Exemplo: 
 Se }2 ,1 ,0{== BA e 
 }(1,2) ),2,0( ),1,0{(=R , 
 )}1,2( ),0,2( ),0,1{(1 =−R . 
 A B A B 
 0 0 0 0 
 1 1 1 1 
 2 2 2 2 
 
 
 :que se-Observa 
 )Im()( )1 1 RRD =− 
 Demonstração: 
 Se )()Im( Portanto ).( logo ,),(),( e )Im( 111 −−− ⊂∈∈→∈∈ RDRRDyRxyRyxRy . 
 Se )Im()( Portanto ).Im( logo ,),(),( e )( 111 RRDRzRzxRxzRDz ⊂∈∈→∈∈ −−− . 
 7 
 Então )Im()( 1 RRD =− . 
 )2 )()Im( 1 RDR =− 
 )3 RR =−− 11 )( 
Composição de Relações. Sejam CBSBAR →→ : e : relações. A composição de R e S, 
resultando na relação composta denotada por: 
CARS →:o 
é tal que: 
))(),(),(),)(()()(( RScaScbRbaCcBbAa o∈→∈∧∈∈∀∈∀∈∀ 
Exemplos: 
1) A composição das relações CBSBAR →→ : e : é CARS →:o sendo que: 
 )}5,( ),4,( ),3,( ),1,{( dbbaR = 
 )},5( ),,5( ),,2( ),,1{( zyyxS = 
 )},( ),,( ),,{( zdydxaRS =o 
 RS o 
 
 A R B S C 
 a 1 x 
 b 2 
 c 3 y 
 d 4 
 5 z 
 
2) Sejam ℜ=== CBA e as relações: 
 BAyxR ×∈= ),{( }8=+ yx 
 CBzyS ×∈= ),{( então },2 zy = 
 CAzxRS ×∈= ),{(o })8( 2 zx =− 
 
 8 
Exercícios: 
1) Sejam os conjuntos A = {1, 2, 3}, B = {2, 3, 4} e C = {3, 4, 6}. Considerando as relações: 
 R = {(1,3), (2,3), (3,4)} BA×⊂ 
 S = {(2,3), (3,3), (3,4), (4,4)} CB ×⊂ , determine .RS o 
 
2) Sejam IRCBA === e as relações: 
 
2),{( IRyxR ∈= }12 =− yx 
 
2),{( IRzyS ∈= . determine },32 RSyz o+= 
 
Propriedades das Relações em um Conjunto A. Uma relação R em A, isto é, de A em A 
pode apresentar as principais propriedades que seguem. 
 
Reflexiva. R é reflexiva se todo elemento de A se relaciona consigo mesmo. 
)),()(( RxxAxx ∈→∈∀ 
Exemplos: 
1) A relação a)}(b, ),,( ),,( ),,( ),,{( caccbbaaR = em },,{ cbaA = é reflexiva pois 
 ),( e ),( ,),( RccRbbRaa ∈∈∈ . 
2) A relação }),{( 2 yxyxR =ℜ∈= é reflexiva pois, para todo x real, x=x. 
 
Contra-exemplo: 
Uma relação R em A não é reflexiva quando existir um elemento x em A tal que .),( Rxx ∉ 
Por exemplo, )},( ),,( ),,( ),,( ),,( ),,{( bccbaccabbaaR = sobre },,{ cbaA = , pois .),( Rcc ∉ 
 
Simétrica. R é simétrica quando, estando x relacionado com y, temos também y relacionado 
com x. 
)),(),)(( , ( RxyRyxAyx ∈→∈∈∀ 
 
 
 9 
Exemplos: 
1) A relação )},( ),,( ),,( ),,{( bbabbaaaR = é uma relação simétrica em },,{ cbaA = 
2) A relação R de perpendicularismo definida sobre o conjunto A das retas do espaço: 
yxRyx ⊥↔∈),( 
 é simétrica pois, para duas retas x e y quaisquer , .xyyx ⊥↔⊥ 
Contra-exemplo: 
Uma relação R em A não é simétrica se existirem AyAx ∈∈ e tais que 
.),( e ),( RxyRyx ∉∈ Por exemplo, )},( ),,( ),,( ),,{( baccbbaaR = sobre },,{ cbaA = , pois 
.),( e ),( RabRba ∉∈ 
 
Transitiva. R é transitiva se x está relacionado com y e y está relacionado com z então, x está 
relacionado com z. 
)),(),( e ),)((,, ( RzxRzyRyxAzyx ∈→∈∈∈∀ 
Exemplos: 
1) A relação )},( ),,( ),,( ),,{( cacbbaaaR = sobre },,{ cbaA = é transitiva. 
2) A relação R sobre IN (conjunto dos números naturais) definida por yxIRyx ≤↔∈),( 
é transitiva pois, dados três naturais x, y e z, se . então e zxzyyx ≤≤≤ 
Contra-exemplo: 
Uma relação R em A não é transitiva se existirem x, y, z ∈ A tais que ),( ,),( RzyRyx ∈∈ 
e .),( Rzx ∉ Por exemplo, a relação )},( ),,( ),,( ),,{( cccbbaaaR = sobre },,{ cbaA = não é 
transitiva pois R.c)(a, e ),( ,),( ∉∈∈ RcbRba 
 
Anti-simétrica. R é anti-simétrica se x e y são elementos distintos, então x não se relaciona 
com y ou y não se relaciona com x. 
)),(ou ),()(, ( RxyRyxyxAyx ∉∉→≠∈∀ 
Exemplos: 
1) A relação )},( ),,( ),,( ),,{( cababbaaR = sobre },,{ cbaA = é anti-simétrica. 
2) A relação R de divisibilidade sobre IN, xRyx ↔∈),( ׀ y (x é divisor de y) é anti-simétrica 
pois, dados dois números naturais x e y, se x ׀ y e y ׀ x então x = y . 
 10
Contra-exemplo: 
Uma relação R sobre A não é anti-simétrica se existirem Ayx ∈ , tais que ),( , Ryxyx ∈≠ 
e .),( Rxy ∈ Por exemplo, a relação )},( ),,( ),,( ),,( ),,{( ccbbabbaaaR = sobre },,{ cbaA = 
não é anti-simétrica pois .),( e ),( , RabRbaba ∈∈≠ 
 
 No estudo das relações sobre um conjunto A finito e com “poucos” elementos, é útil a 
representação através de um grafos: representamos o conjunto A com seus elementos e 
indicamos cada par ),( ba da relação através de uma flecha com “origem a e “extremidade” 
b. Se ),( aa está na relação, usa-se um “laço” envolvendo a. 
Exemplo: 
)},( ),,( ),,( ),,( ),,{( bccbbabbaaR = 
sobre }.,,{ cbaA = 
 
Através da representação em grafos é possível visualizar se as propriedades definidas se 
verificam ou não para uma relação R. 
 Reflexiva. Em cada ponto do diagrama deva haver um laço. 
 Exemplo Contra-exemplo 
 1R 2R 
 
 
 
 
 
 
 Simétrica. Toda flecha deve ter duas “pontas”. 
 Exemplo Contra-exemplo 
 3R 4R 
 
 
 
 a • • b 
 
 c • A 
 
 a • • b 
 
 • c 
 
A 
 
 a • • b 
 • c 
 
A 
 
 a • • b 
 
 c • • d 
A 
 
 a • • b 
 
 c • • dA 
 11
 Transitiva. Para todo par de flechas consecutivas existe uma flecha cuja origem é a da 
primeira e a extremidade, a da segunda. 
 Exemplo Contra-exemplo 
 5R 6R 
 
 
 
 
 
 Anti-simétrica. Não há flechas de duas pontas. 
 Exemplo Contra-exemplo 
 7R 8R 
 
 
 
 
 
Endorrelações – ordem e equivalência 
 
Endorrelações, Ordenação e Equivalência 
 
a) Propriedades: principais propriedades das endorrelações; 
b) Fecho: extensão de uma endorrelação de forma a satisfazer determinadas propriedades; 
c) Ordem: endorrelações as quais refletem uma noção intuitiva de ordem; 
d) Equivalência: endorrelações as quais refletem uma noção de igualdade semântica. 
 
 
a) Propriedades: 
- Reflexiva, Irreflexiva: Para um conjunto finito A, uma forma simples de entender e verificar se uma 
endorrelação R:A→A é reflexiva ou irreflexiva, é analisar a sua representação como matriz ou como 
grafo: 
a) Matriz 
 - Reflexiva: a diagonal da matriz contém somente o valor verdadeiro; 
 - Irreflexiva: a diagonal da matriz contém somente o valor falso; 
 
 a • • b 
 
 c • • d 
A 
 
 a • • b 
 
 • • d 
A 
 
 a • • b 
 
 c • • d 
A 
 
 a • • b 
 
 c • • d 
A 
 12
b) Grafo 
 - Reflexiva: qualquer nodo tem um arco com origem e destino nele mesmo; 
 - Irreflexiva: qualquer nodo não tem um arco com origem e destino nele mesmo. 
 
Exemplos; 
Seja A= {0,1,2}. As seguintes relações são: 
a) Reflexivas, mas não irreflexivas 
A2:A→A 
<A,=>, dado que = é definida por {<0,0>,<1,1>,<2,2>}. 
 
b) Irreflexivas, mas não reflexivas 
∅: A→A 
R={<0,1>,<1,2>,<2,1>}. 
 
 
- Simétrica, Anti-Simétrica: Para um conjunto finito A, uma forma simples de entender e verificar se 
uma endorrelação R:A→A é simétrica ou anti-simétrica, é analisar a sua representação como matriz ou 
como grafo: 
 
a) Matriz 
 - Simétrica: a metade acima da diagonal da matriz é a imagem espelhada da metade abaixo; 
 - Anti-simétrica: para qualquer célula verdadeira em uma das metades da matriz (com 
relação à diagonal), a correspondente célula na outra metade é falsa; 
b) Grafo 
 - Simétrica: entre dois nodos quaisquer, ou não existe seta, ou existem duas seta, uma em 
cada sentido; 
 - Anti-simétrica: entre dois nodos quaisquer, existe no máximo uma seta. 
 
Exemplos; 
Seja A= {0,1,2}. As seguintes relações são: 
a) Simétrica, mas não anti-simétrica: A2 
b) Simétrica e Anti-Simétrica: <A,=> 
c) Anti-Simétrica, mas não simétrica: R:A→A tal que R= {<0,0>,<1,1>,<1,2>}. 
d) Nem simétrica, nem anti-simétrica: S:A→A tal que S= {<0,1>,<1,0>,<1,2>}. 
 
 
- Transitiva: Para o entendimento e visualização de uma endorrelação transitiva (sobre um conjunto 
finito) como matriz não é vantajoso, porém como grafo, a transitividade possui uma importante 
interpretação: o grafo explicita todos os caminhos possíveis entre dois nodos. Informalmente, um 
caminho em um grafo é determinado por uma seta ou por uma sequência de setas encadeadas. Se 
existe uma forma de ligar dois nodos via setas encadeadas, então existe um caminho entre estes nodos. 
 
Exemplos: Seja A={0,1,2}, as seguintes endorrelações são transitivas: 
A2:A→A 
<A,=> 
<A,≤ > 
<A,< > 
 
 
 13
b)Fecho de uma Endorrelação 
Definição: Sejam R:A→A uma endorrelação e P um conjunto de propriedades. Então o fecho de R 
em Relação a P, é a menor endorrelação em A que contém R e que satisfaz as propriedades de P e é 
denotado por: 
FECHO-P(R) 
Portanto, para qualquer conjunto de propriedades considerado, a relação sempre será subconjunto de 
seu fecho, ou seja: 
R⊆FECHO-P(R). 
 
Suponha uma endorrelação R:A→A. A construção do fecho de R para as propriedades reflexiva, 
simétrica e transitiva é como segue; 
a) Fecho Reflexivo. 
FECHO-{reflexiva}(R) = R∪{(a,a)a∈A} 
b) Fecho Simétrico. 
 FECHO-{simétrica}(R) = R∪{(b,a)(a,b)∈R} 
c) Fecho Transitivo. O FECHO-{transitiva}(R) é construído como segue; 
c.1) Se (a,b)∈R, então (a,b)∈FECHO-{transitiva}(R) 
c.2) Se (a,b)∈FECHO-{transitiva}(R) e (b,c)∈FECHO-{transitiva}(R), então (a,c)∈FECHO-
{transitiva}(R) 
c.3) Os únicos elementos de FECHO-{transitiva}(R) são os constituídos como acima. 
 
A definição acima é um tipo especial de definição denominada de definição indutiva ou definição 
recursiva. 
Dois tipos de fecho de uma relação são especialmente importantes para Computação e Informática e 
possuem notação própria. Suponha uma endorrelação R:A→A. Então: 
a) Fecho Transitivo de R denotado por R+, ou seja: 
R+ = FECHO-{transitiva}(R) 
b) Fecho Reflexivo e Transitivo de R denotado por R*, ou seja: 
R* = FECHO-{reflexiva, transitiva}(R) 
 
 
Exemplos: Fecho de uma Relação 
Sejam A={1,2,3,4,5} um conjunto e R:A→A uma endorrelação tal que: 
R= {<1,2>,<1,5>,<2,3>,<3,4>}. 
Alguns fechos de R é como segue: 
a) Fecho Reflexivo. 
FECHO-{reflexiva}(R)= {<1,1>, <1,2>,<1,5>,<2,2>,<2,3>,<3,3>,<3,4>,<4,4>,<5,5>}. 
b) Fecho Simétrico. 
FECHO-{simétrica}(R)= {<1,2>,<1,5>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>,<5,1>}. 
c) Fecho Transitivo. 
R+= {<1,2>,<1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<3,4>}. 
d) Fecho Reflexivo e Transitivo. 
R* = {<1,1>, <1,2>,<1,3>,<1,4>,<1,5>,<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>,<5,5>}. 
 
 
c) Ordenação 
Relação de Ordem reflete a noção intuitiva de ordem. 
 
 
 14
Definição: Relação Conexa 
Seja R:A→A uma endorrelação. Então R é uma Relação Conexa, se: 
(∀a∈A)( ∀b∈A)(aRb ∨ bRa ∨ a=b}. 
 
Exemplo: 
Sejam A={a}, B={a,b} e C={0,1,2}. Então: 
a) A endorrelação ∅:B→B é não-conexa; 
b) A endorrelação (C, < ), dado que < é definida por {(0,1),(0,2),(1,2)}, é conexa; 
c) A endorrelação =:A→A é conexa. 
 
As propriedades de uma endorrelação de ordem, são exemplificadas: considere as filas de clientes 
para os diversos caixas de um banco. Então: 
a) Transitiva. Importante propriedade da noção intuitiva de ordem. Em uma fila, se João 
antecede José, e José antecede Maria, então João antecede Maria; 
 
b) Anti-Simétrica. O princípio mais fundamental deste exemplo (e que melhor caracteriza 
qualquer ordem) é a propriedade anti-simétrica. Considere a seguinte situação: a ordenado em 
relação à b e vice-versa (b ordenado em relação à a) só faz sentido se a for igual a b (no 
exemplo do banco, a antecede b e b antecede a só se a e b forem o mesmo cliente); 
 
c) Parcial/Conexa. Nem todos os clientes estão relacionados entre si. De fato, em qualquer banco, 
sempre existe um caixa especial (e consequentemente, uma fila em separado) para idosos, 
gestantes e outros casos especiais. Entretanto, parcialidade não é uma propriedade fundamental 
para caracterizar formalmente a noção de ordem. 
 
d) Reflexiva/Irreflexiva. Relações de ordem podem ser reflexivas (como, por exemplo, no caso da 
relação <N, ≤ > ) ou irreflexivas (como, por exemplo, no caso da relação <Z, < >). No exemplo 
das filas em um banco, o mais natural seria considerar como uma relação de ordem irreflexiva. 
Entretanto, uma interpretação reflexiva (todo cliente antecede a si próprio na fila) faria sentido. 
 
Relação de Ordem 
Definição- Relação de Ordem Parcial/Conexa, Ampla/Estrita 
Seja R: A→A uma endorrelação. Então R é uma: 
a) Relaçãode Ordem Parcial Ampla ou simplesmente Relação de Ordem Parcial, se R é uma 
relação: 
- reflexiva; 
- anti-simétrica; 
- transitiva; 
b) Relação de Ordem Parcial Estrita, se R é uma relação: 
- irreflexiva; 
- anti-simétrica; 
- transitiva; 
c) Relação de Ordem Conexa Ampla, Relação de Ordem Conexa ou Cadeia se R é uma relação: 
- de ordem parcial ampla; 
- conexa; 
d) Relação de Ordem Conexa Estrita ou Cadeia Estrita se R é uma relação: 
- de ordem parcial estrita; 
- conexa. 
 15
 
Exemplos: Relação de Ordem Parcial/Conexa, Ampla/Estrita 
Considere um conjunto não vazio A. Então, as seguintes relações são de: 
a) Ordem parcial (ampla): 
<N, ≤ > 
<P(A), ⊆> 
b) Ordem parcial estrita: 
<N, < > 
<P(A), ⊂> 
c) Ordem conexa (ampla): 
<N, ≤ > 
d) Ordem conexa estrita: 
<N, < > 
 
Exemplo – Ordem Lexicográfica 
Ordem Lexicográfica estabelece uma relação de ordem conexa. Dado um alfabeto Σ={a,b}, o conjunto 
Σ* (todas as palavras sobre Σ), é como segue: 
Σ*={ε, a, b, aa, ab, ba, bb, aaa,...} 
Observa-se que as palavras, no conjunto Σ*, foram listadas em ordem lexicográfica, ou seja, por 
tamanho da palavra (número de símbolos) e, para palavras do mesmo tamanho, por ordem “alfabética” 
(supondo a menor do que b). Dessa forma, qualquer alfabeto ordenado Σ induz o conjunto ordenado 
(lexicograficamente) Σ*. 
 
 
Obs.: Quando R é uma relação de ordem parcial sobre A, para exprimirmos que: 
 Rba ∈),( usaremos )( Rba ≤ (“a precede b na relação R”). 
 baRba ≠∈ e ),( usaremos )( Rba < (“a precede estritamente b na relação R”). 
 
 Um conjunto parcialmente ordenado é um conjunto sobre o qual se definiu uma certa relação de 
ordem parcial. 
 
 Seja R uma relação de ordem parcial sobre A. Os elementos a, b A∈ se dizem comparáveis 
mediante R se .ou abba ≤≤ 
 
Relação de Ordem Total. Se dois elementos quaisquer de A forem comparáveis mediante R, então R 
será chamada relação de ordem total sobre A. O conjunto A, neste caso, é chamado conjunto 
totalmente ordenado. 
 
Exemplos: 
1) A relação )},(),,(),,(),,(),,(),,{( cbcabaccbbaaR = 
é uma relação de ordem total sobre },,{ cbaA = . 
 Observe no diagrama ao lado que o fato de não haver 
dois pontos que não estejam ligados por uma flecha indicam 
que a ordem é total. 
 
 
2) A relação R sobre ℜ definida por yxRyx ≤↔∈),( é uma relação de ordem total, pois: 
 ))( ( xxIRxx ≤→∈∀ 
 ) e )(, ( yxxyyxIRyx =∈→≤≤∈∀ 
 
 a • • b 
 • 
 c 
 16
 ) e )(,, ( zxzyRyxIRzyx ≤→≤∈≤∈∀ 
 ( )( )xyyxIRyxyx ≤≤→∈∀ ou ,, 
3) A relação R de divisibilidade sobre xRyxIN ↔∈),(: ׀ y é :pois parcial ordem de 
 xINxx →∈∀ )( ( ׀ )x 
 xINyx )(, ( ∈∀ ׀ yy e ׀ )yxx =→ 
 xINzyx )(,, ( ∈∀ ׀ yy e ׀ xz → ׀ )z 
 
Limites Superiores e Inferiores. Seja A um conjunto parcialmente ordenado mediante a relação ≤ . 
Seja B um subconjunto de A, com .φ≠B 
 Um elemento L A∈ é um limite superior de B se for verdadeira a proposição: 
( )( )LxBxx ≤→∈∀ 
isto é, quando qualquer elemento de B precede L. 
 
 Um elemento l A∈ é um limite inferior de B se for verdadeira a proposição: 
( )( )xlBxx ≤→∈∀ 
isto é, quando l precede qualquer elemento de B. 
 
Máximo e Mínimo. Seja B um subconjunto não vazio do conjunto A parcialmente ordenado pela 
relação ≤ . 
 Um elemento BM ∈ é um máximo de B quando se verifica a propriedade: 
( )( )MxBxx ≤→∈∀ 
isto é, quando M é um limite superior de B e pertence a B. 
 Um elemento Bm ∈ é um mínimo de B quando se verifica a propriedade: 
( )( )xmBxx ≤→∈∀ , isto é, quando m é um limite inferior de B e pertence a B. 
Proposição. Se B é um subconjunto do conjunto parcialmente ordenado A e existe um máximo 
(mínimo) de B, então ele é único. 
Demonstração: 
 Admitamos que 2 1 e MM sejam máximos de B. Temos: 
 1221 e de máximo é MMBMBM ≤→∈ 
 2112 e de máximo é MMBMBM ≤→∈ , então 21 MM = . 
 
 Admitamos que 2 1 e mm sejam mínimos de B. Temos: 
 2121 m e de mínimo é mmBBm ≤→∈ 
 1212 m e de mínimo é mmBBm ≤→∈ , então 21 mm = . 
 
Supremo e Ínfimo. Seja B um subconjunto não vazio do conjunto parcialmente ordenado A. Chama-
se supremo de B o mínimo (caso exista) do conjunto dos limites superiores de B. Chama-se ínfimo de 
B o máximo (caso exista) do conjunto dos limites inferiores de B. 
 
d)Relações de Equivalência. Uma relação R sobre um conjunto A não vazio é chamada relação de 
equivalência sobre A se, e somente se, R é reflexiva, simétrica e transitiva, isto é, se são verdadeiras as 
sentenças: 
 i) )),,()( ( RxxAxx ∈→∈∀ 
 ii) )),(),)((, ( RxyRyxAyx ∈→∈∈∀ 
 iii) )),(),( e ),)((,, ( RzxRzyRyxAzyx ∈→∈∈∈∀ 
 
 17
 Quando R é uma relação de equivalência sobre A, se Rba ∈),( usa-se a notação ),(Rba ≡ que 
se lê: “a é equivalente a b módulo R”. 
 
Exemplos: 
1) A relação )},(),,(),,(),,(),,{( accaccbbaaR = é 
uma relação de equivalência sobre },,{ cbaA = 
 
 
2) A relação de igualdade sobre IR: yxRyx =↔∈),( é uma relação de equivalência pois: 
 i) ))( ( xxIRxx =→∈∀ 
 ii) ))(, ( xyyxyx =→=∀ 
 iii) ) e )(,, ( zxzyyxzyx =→==∀ 
 
Classes de Equivalência. Seja R uma relação de equivalência sobre A. Dado ,Aa ∈ chama-se classe 
de equivalência determinada por a, módulo R, o subconjunto a de A constituídos pelos elementos x 
tais que Rax ∈),( . Simbolicamente: 
Axa ∈= { ׀ }),( Rax ∈ 
 O conjunto das classes de equivalência determinado por R é indicado por RA / e chamado 
conjunto quociente de A por R. 
 
 
 
Exemplo: 
Na relação de equivalência 
)},(),,(),,(),,(),,{( accaccbbaaR = temos: 
},{ caa = 
}{bb = 
},{ acc = , }}{},,{{/ bcaRA = 
 
 
 
Observação: Cada classe de equivalência é um elemento do conjunto das partes de A, P(A). Além 
disso, nota-se que o conjunto quociente de A por R é subconjunto do conjunto das partes de A, ou seja, 
)(/ APRA ⊂ . 
Partição de um Conjunto. Seja A um conjunto não vazio. Diz-se que uma classe F de subconjuntos 
não vazios de A é uma partição de A se, e somente se: 
a) dois membros quaisquer de F ou são iguais ou são disjuntos; 
b) a união dos membros de F é igual a A. 
Exemplos: A 
1) }}4{},3,2{},1{{=F é ima partição 
do conjunto }.4,3,2,1{=A 
 
 a • • c 
 • 
 b 
A 
 
 a • • c 
 • 
 b 
A 
1 2 
 
 3 4 
 18
 
 
2) Sejam 
ZxP ∈= { ׀ e }par é xZxI ∈= {׀}ímpar é x Z 
então },{ IPF = é uma partição de Z. 
 
3) ] [ [ ] ] [{ } ,1, 1,1, 1, +∞−−∞−=F é 
uma partição de IR. 
 
 
Relação Dual x Composição de Relações 
Relação Dual é a inversão (troca) das componentes de cada par ordenado. 
Composição de Relações é a aplicação de uma relação sobre o resultado de outra. 
A dualidade e a composição de relações são operações (unária e binária, respectivamente) 
sobre as relações, as quais, juntamente com as operações sobre conjuntos como, por exemplo, 
união e intersecção, constituem uma álgebra de relações. 
 
Relação Dual 
Definição- Relação Dual, Relação Oposta, Relação Inversa 
Seja R: A→B uma relação. Então a relação Dual¸Relação Oposta ou RelaçãoInversa de R, 
denotado por 
R-1: B→A ou Rop: B→A 
 
é como segue: R-1 = {<b,a> | <a,b> ∈ R}. 
 
Obs.: O termo relação dual ou oposta será usado preferencialmente aos termos relação 
inversa. Embora referenciar relação inversa seja mais comum nas bibliografias em geral, o 
termo causa confusão com a idéia de uma relação que possui inversa, conceito fundamental 
nos estudos das relações. 
 
Exemplo: 
Sejam A={a}, B={a,b} e C={0,1,2}. São relações e suas correspondentes relações opostas 
(dual): 
 
Relação Relação Dual 
=: A→B dada por {<a,a>} =op: B →A dada por {<a,a>} 
{<0,a>, <1,b>}: C→B {<0,a>, <1,b>}-1= {<a,0>, <b,1>}: B→C 
A x B:A→B (A x B)-1=BxA:B→A 
∅:A→B ∅op=∅:B→A 
<:C→C <op = >:C→C 
 
 
 P I 
 
] [1,−∞− [ ]1,1− ] [+∞,1 
 19
Representação de Relação Dual no Plano Cartesiano: 
Exemplo: 
Seja R = {<x, y>| x = y2} 
Rop = {<y,x>| x = y2} 
 
 
Representação de Relação Dual como matriz e como grafo: 
Para uma dada relação, a correspondente relação dual como matriz ou como grafo (no caso de 
um endorrelação) é como segue: 
- matriz: a matriz da relação dual é a matriz transposta da matriz da relação, ou seja, é a 
matriz resultante da troca das linhas pelas colunas; 
- grafo: o grafo da endorrelação dual é o grafo dual da endorrelação, ou seja, é o grafo 
resultante da inversão do sentido das arestas. 
 
Exemplo: 
Sejam A={a}, B={a,b} e C={0,1,2}. Suponha a seguinte endorrelação <C, < >: 
a) Grafos: a endorrelação dual é <C, <op >, correspondente à relação >. 
 
 
 
 
 
 
 
 
 
b) Matriz: a endorrelação dual é <C, <op >, correspondente à relação > dada por 
{ <2,1 >, <2,0>,<1,0>}. 
 
 
 
 
 
 
Tipos de Relações 
Uma relação pode ser classificada nos seguintes tipos os quais não são mutuamente 
exclusivos: 
- funcional; 
- injetora; 
- total; 
- sobrejetora; 
- monomorfismo; 
- epimorfismo; 
- isomorfismo. 
 
 .... 0 < 
 
 .1 .2 
 .... 0 > 
 
 .1 .2 
< 0 1 2 
0 
1 
2 
 
> 0 1 2 
0 
1 
2 
 
 20
A dualidade dos tipos de relação é: 
- funcional é o dual de injetora e vice-versa; 
- total é o dual de sobrejetora e vice-versa. 
 
Considerando que: 
- monomorfismo significa simultaneamente total e injetora; 
- epimorfismo significa simultaneamente sobrejetora e funcional; 
vale, como conseqüência, a seguinte dualidade: 
- monomorfismo é o dual de epimorfismo e vice-versa. 
Como isomorfismo estabelece uma noção semântica de igualdade, portanto: 
- isomorfirmo é o dual de si mesmo. 
 
Funcional e Injetora 
Uma relação funcional permite definir função. 
Definição – Relação Funcional: Seja R:A→B uma relação. Então R é uma Relação 
Funcional se e somente se: 
))()()(( 212121 bbaRbaRbBbBbAa =→∧∈∀∈∀∈∀ 
 
Portanto, em uma relação funcional R:A→B, cada elemento de A está relacionado com, no 
máximo, um elemento de B. 
 
Exemplos: 
Sejam A={a}, B={a,b} e C={0,1,2}. 
a) São relações funcionais: 
∅:A→B 
{<0,a>, <1,b>}: C→B 
=: A→B 
x
2:Z→Z onde x2 = {(x,y) ∈Z2| y = x2} 
 
b) Não são relações funcionais: 
A x B:A→B 
<:C→C 
 
Obs.: 
1) A relação funcional em termos da notação com matriz ou como grafo, no caso de 
uma endorrelação: 
- matriz: existe no máximo um valor verdadeiro em cada linha da matriz; 
- grafo: existe no máximo uma aresta partindo de cada nodo. 
 
2) Considerando que injetora é o conceito dual, o seguinte pode ser inferido em 
termos da notação como matriz ou como grafo ( no caso de uma endorrelação): 
- matriz: existe no máximo um valor verdadeiro em cada coluna da matriz; 
- grafo: existe no máximo uma aresta chegando a cada nodo. 
 
 21
Definição – Relação Injetora: Seja R:A→B uma relação. Então R é uma Relação Injetora se 
e somente se: 
))()()(( 212121 aaRbaRbaAaAaBb =→∧∈∀∈∀∈∀ 
Portanto, em uma relação injetora R:A→B, cada elemento de B está relacionado com, no 
máximo, um elemento de A. 
 
Exemplos: 
Sejam A={a}, B={a,b} e c={0,1,2}. 
a) São relações injetoras: 
∅:A→B 
{<0,a>, <1,b>}: C→B 
=: A→B 
A x B:A→B 
 
 
b) Não são relações injetoras: 
B x A:B→A 
x
2:Z→Z onde x2 = {(x,y) ∈Z2| y = x2} 
<:C→C 
 
Obs.: 
1) Os conceitos funcional e injetora não são complementares; 
2) As relações podem ser (ou não) simultaneamente funcional e injetora. 
 
 
Total e Sobrejetora 
Definição – Relação Total: Seja R:A→B uma relação. Então R é uma Relação Total se e 
somente se: 
))()(( aRbBbAa ∈∃∈∀ 
 
Portanto, em uma relação total R:A→B, o domínio de definição é a origem A. 
 
Exemplos: 
Sejam A={a}, B={a,b} e c={0,1,2}. 
a) São relações totais: 
=: A→B 
A x B:A→B 
x
2:Z→Z onde x2 = {(x,y) ∈Z2| y = x2} 
 
b) Não são relações totais: 
∅:A→B 
{<0,a>, <1,b>}: C→B 
<:C→C 
 
 22
Obs.: 
1) A relação total em termos da notação com matriz ou como grafo, no caso de uma 
endorrelação: 
- matriz: existe pelo menos um valor verdadeiro em cada linha da matriz; 
- grafo: existe pelo menos uma aresta partindo de cada nodo. 
 
2) Considerando que sobrejetora é o conceito dual, o seguinte pode ser inferido em 
termos da notação como matriz ou como grafo ( no caso de uma endorrelação): 
- matriz: existe pelo menos um valor verdadeiro em cada coluna da matriz; 
- grafo: existe pelo menos uma aresta chegando a cada nodo. 
 
Definição – Relação Sobrejetora: Seja R:A→B uma relação. Então R é uma Relação 
Sobrejetora se e somente se: 
))()(( aRbAaBb ∈∃∈∀ 
Portanto, em uma relação sobrejetora R:A→B, o conjunto imagem é B. 
 
Exemplos: 
Sejam A={a}, B={a,b} e c={0,1,2}. 
a) São relações sobrejetoras: 
{<0,a>, <1,b>}: C→B 
=: A→A 
A x B:A→B 
 
b) Não são relações sobrejetoras: 
∅:A→B 
=: A→B 
<:C→C 
x
2:Z→Z onde x2 = {(x,y) ∈Z2| y = x2} 
 
 
Obs.: 
3) Os conceitos total e sobrejetora não são complementares; 
4) As relações podem ser (ou não) simultaneamente total e sobrejetora. 
 
Monomorfismo e Epimorfismo 
Definição – Monomorfismo ou Monorrelação: Seja R:A→B. Então R é um Monomorfismo 
ou uma Monorrelação se e somente se for simultaneamente: 
- total; 
- injetora. 
 
Portanto, em uma monorrelação R:A→B, o domínio de definição é A, e cada elemento de B 
está relacionado com, no máximo, um elemento de A. Para enfatizar que R:A→B é uma 
monorrelação, denota-se: 
R:A >→ B 
 23
 
Exemplos: 
Sejam A={a}, B={a,b} e c={0,1,2}. 
a)São monorrelações: 
=: A→B 
A x B:A→B 
 
b)Não são monorrelações: 
∅:A→B 
B x C:B→C 
{<0,a>, <1,b>}: C→B 
<:C→C 
x
2:Z→Z onde x2 = {(x,y) ∈Z2| y = x2} 
 
Obs.: 
1) Uma monorrelação em termos da notação com matriz ou como grafo, no caso de 
uma endorrelação: 
- matriz: existe pelo menos um valor verdadeiro em cada linha (total) e no máximo um 
valor verdadeiro em cada coluna (injetora) da matriz; 
- grafo: existe pelo menos uma aresta partindo (total) e no máximo uma aresta 
chegando (injetora) a cada nodo. 
 
2) Considerando que epirrelação é o conceito dual, ou seja, é uma relação funcional e 
sobrejetora, então o seguinte pode ser inferido em termos da notação como matriz ou como 
grafo ( no caso de uma endorrelação): 
- matriz: existe pelo menos um valor verdadeiro em cada coluna (sobrejetora) e no 
máximo um valor verdadeiro em cada linha (funcional) da matriz; 
- grafo: existe pelo menos uma aresta chegando (sobrejetora) e no máximo uma aresta 
partindo (funcional) de cada nodo. 
 
Definição – Epimorfismo ou Epirrelação: Seja R:A→B uma relação. Então R é um 
Epimorfismoou uma Epirrelação se e somente se for simultaneamente : 
- funcional; 
- sobrejetora. 
Portanto, em uma epirrelação R:A→B, o conjunto imagem é B e cada elemento de A está 
relacionado com, no máximo, um elemento de B. Para enfatizar que R:A→B é uma 
epirrelação, denota-se: 
 
R: A →> B. 
Exemplos: 
Sejam A={a}, B={a,b} e c={0,1,2}. 
a)São epirrelações: 
{<0,a>, <1,b>}: C→B 
=: A→A 
 24
 
b)Não são epirrelações: 
∅:A→B 
=: A→B 
A x B:A→B 
<:C→C 
x
2:Z→Z onde x2 = {(x,y) ∈Z2| y = x2} 
 
 
Isomorfismo 
O conceito de isomorfismo está associado a uma noção de igualdade semântica, no sentido 
em que se pode definir uma relação tal que, quando composta com a sua inversa, resulta em 
uma igualdade. Assim, intuitivamente, um isomorfismo possibilita “ir” (via relação) e “voltar’ 
(via sua inversa), “sem alterar”. 
Para introduzir o conceito de isomorfismo, a seguinte notação é desejável: 
- em diversos momentos, foram introduzidas relações de igualdade como, por exemplo: 
=:{a} → {a,b} definida por {<a,a>} 
<{a,b},=> definida por {<a,a>, <a,b>} 
- quando a relação de igualdade é uma endorrelação <A, =>, é usual denominar essa relação 
de relação identidade e denotá-la por <A, idA> tal que: 
 
idA:A→A 
 
Definição – Isomorfismo ou Isorrelação: Uma relação R:A→B é dita um Isomorfismo ou 
uma Isorrelação se e somente se existe uma relação S:B→A tal que: 
 
S ° R = idA e R° S = idB 
Para enfatizar que R:A→B é uma isorrelação, denota-se: 
 
R: A ↔ B 
 
Adicionalmente, vale que: 
- quando S ° R = idA, afirma-se que R possui inversa à esquerda; 
- quando R° S = idB, afirma-se que R possui inversa à direita; 
- quando S ° R = idA e R° S = idB, afirma-se que R (respectivamente S) possui inversa, a qual 
é S (respectivamente, R). 
 
Definição – Conjuntos Isomorfos: 
Dois conjuntos A e B são ditos Conjuntos Isomorfos se existe uma isorrelação R: A ↔ B. 
 
 
 
 25
Exemplos: 
1) Para qualquer conjunto A, a relação identidade idA:A→A é um isomorfismo. De fato, a 
identidade composta com ela mesma resulta na própria identidade, ou seja: 
idA ° idA = A 
 
portanto, qualquer conjunto é isomorfo a si mesmo. 
 
2) Sejam A={a, b,c}, C={1,2,3} e a relação R:A→C tal que: 
R={<a,1>, <b,2>, <c,3>} 
R é um isomorfismo. 
De fato, considere a relação dual R-1:C→A tal que: 
R-1={<1,a>, <2,b>, <3,c>} 
Logo: 
R-1 ° R = {<a,a>, <b,b>, <c,c>}= idA e R ° R-1 = {<1,1>, <2,2>, <3,3>}= idC. 
Portanto, A e C são conjuntos isomorfos. 
 
Obs.: Para provar que uma relação é um isomorfismo, basta mostrar que ela possui inversa. 
Observe que, se possui inversa, então esta é a relação dual. Entretanto, mostrar que uma 
relação não é um isomorfismo pode ser um pouco mais difícil (a dual nem sempre é a 
inversa). 
Frequentemente, tal prova é por absurdo, como exemplo abaixo: 
 
Exemplo: Não é Isomorfismo 
Sejam A={0,1,2}, B={a, b} e a relação R:A→B tal que: 
R = {<0,a>, <1,b>} 
R não é um isomorfismo. 
A prova que segue é por absurdo. Assim, suponha que R é um isomorfismo. Portanto, R 
possui uma relação inversa S:B→A tal que: 
S ° R = idA e R° S = idB 
Então: 
S ° R = idA ⇒ definição de relação identidade 
<2,2> ∈ S ° R ⇒ definição de composição 
(∃x∈A)( <2,x> ∈ R ∧ <x,2> ∈ S) 
o que é um absurdo, pois não existe um par do tipo <2,x> em R. Logo, é absurdo supor que R 
é um isomorfismo. 
Portanto, R não é um isomorfismo. 
 
Exemplo: Isorrelação 
Sejam A={a}, B={a,b} e c={0,1,2}. 
a)São isorrelações: 
∅:∅→∅ 
{<0,1>, <1,2>,<2,0>}: C→C 
 26
ad_1:N→N-{0} onde ad_1={<x,y> ∈ N xN –{0}| y=x+1} 
R:Z →Z onde R={<x,y> ∈ ZxN |y=2x se x≥0 e y=|2x|-1 se x<0}, sendo que |2x| 
denota o módulo (valor absoluto) de 2x. 
 
b)Não são isorrelações: 
∅:A→B 
A x B:A→B 
<:C→C 
x
2:Z→Z onde x2 = {(x,y) ∈Z2| y = x2}. 
 
O seguinte teorema apresenta um importante resultado relativamente às isorrelações. 
A prova é omitida. 
 
Teorema – Isorrelação ↔↔↔↔ Monorrelação e Epirrelação 
Seja R:A→B uma relação. Então R é uma isorrelação se e somente se, simultaneamente: 
- R é uma monorrelação; 
- R é uma epirrelação. 
 
Portanto, uma relação é uma isorrelação se e somente se for, simultaneamente; 
- total; 
- injetora; 
- funcional; 
- sobrejetora. 
 
Exemplo: Não é isomorfismo 
Sejam A={0,1,2}, B={a,b} e a relação R:A→B tal que: 
R={<0,a>, <1,b>} 
R não é um isomorfismo. De fato, R não é total. 
 
Obs.: Outro importante resultado que pode ser deduzido de um isomorfismo é que os 
conjuntos origem e destino possuem o mesmo número de elementos. Tal fato é explorado 
detalhadamente quando do estudo da cardinalidade (número de elementos) de um conjunto. 
Conjuntos que possuem o mesmo cardinal são ditos “iguais” (semanticamente) a menos de 
uma relação de troca de nomes dos elementos, ou seja, a menos de uma isorrelação. Tal fato 
induz a seguinte afirmação, usual em muitas teorias, para um dado isomorfismo, para 
enfatizar que nomes de elementos não são importantes e que podem ser trocados: 
Iguais a menos de isomorfismo 
 
Exemplo- Igualdade a Menos de Isomorfismo: Produto Cartesiano 
Comutatividade. O produto cartesiano é uma operação não-comutativa. Por exemplo, para os 
conjuntos A={a,b} e B={0,1}, os seguintes conjuntos resultantes do produto cartesiano são 
claramente distintos: 
A x B = {<a,0>, <a,1>, <b,0>, <b,1>} 
B x A = {<0,a>, <1,a>, <0,b>, <1,b>}. 
 27
Entretanto, são conjuntos isomorfos. De fato: 
- considere a relação troca:AxB →BxA a qual troca a primeira componente de cada 
par pela segunda, ou seja: 
troca = {<<a,0>, <0,a>>,<<a,1>,<1,a>> , <<b,0>, <0,b>>,<<b,1>,<1,b>> } 
- a relação troca possui como inversa a relação dual troca-1:BxA →AxB a qual 
simplesmente destroca as componentes, ou seja: 
troca
-1
 = {<<0,a>, <a,0>>,<<1,a>,<a,1>> , <<0,b>, <b,0>>,<<1,b>,<b,1>> } 
- o seguinte resultado ocorre: 
troca
-1
 ° troca = idAxB e troca ° troca-1 = idBxA 
a generalização deste raciocínio mostra que, para quaisquer dois conjuntos A e B, o conjunto 
AxB é isomorfo ao BxA e, portanto, esses conjuntos são iguais a menos de isomorfismo.