5) Relaes5) Relaes

5.1) Relaes e Dgrafos5.1) Relaes e Dgrafos

5.2) Propriedades de Relaes5.2) Propriedades de Relaes

5.3) Relaes de Equivalncia5.3) Relaes de Equivalncia

5.4) Manipulao de Relaes 5.4) Manipulao de Relaes

5.5) Fecho de Relaes5.5) Fecho de Relaes

INE5403INE5403 -- Fundamentos de Matemtica Fundamentos de Matemtica Discreta para a ComputaoDiscreta para a Computao

Propriedades de relaesPropriedades de relaes

Em muitas aplicaes da computao aparecem relaes Em muitas aplicaes da computao aparecem relaes sobre um conjunto A em vez de relaes de A em B.sobre um conjunto A em vez de relaes de A em B.

DefinioDefinio: (Reflexividade): (Reflexividade)

Uma relao R sobre um conjunto A dita Uma relao R sobre um conjunto A dita reflexivareflexiva se se (a,a)(a,a)R para todo aR para todo aA, ou seja, se aRa para todo aA, ou seja, se aRa para todo aA.A.

Uma relaUma relao R sobre A o R sobre A dita dita irreflexivairreflexiva se (a,a)se (a,a)R para R para todo atodo aA.A.

Ou seja: R Ou seja: R reflexiva reflexiva se todo elemento ase todo elemento aA estA est relacionado relacionado consigo mesmo e consigo mesmo e irreflexiva irreflexiva se nenhum elemento estse nenhum elemento estrelacionado consigo mesmo.relacionado consigo mesmo.

Propriedades de relaes (reflexividade)Propriedades de relaes (reflexividade)

ExemplosExemplos: :

a) a) = { (a,a) | a = { (a,a) | a A}: a relaA}: a relao de igualdade no conjunto A.o de igualdade no conjunto A.Por definiPor definio, (a,a)o, (a,a), , aaA.A.

b) b) R = { (a,b) R = { (a,b) AAA | aA | ab} b} Irreflexiva pois (a,a)Irreflexiva pois (a,a)R, R, aaA.A.

c) c) Seja A = {1,2,3} e R={(1,1),(1,2)}. Ento:Seja A = {1,2,3} e R={(1,1),(1,2)}. Ento:R no R no reflexiva pois (2,2)reflexiva pois (2,2)RRR no R no irreflexiva pois (1,1)irreflexiva pois (1,1)RR

Propriedades de relaes (reflexividade)Propriedades de relaes (reflexividade)

ExemploExemplo: Quais das relaes a seguir so reflexivas?: Quais das relaes a seguir so reflexivas?

RR11 = { (a,b) | a = { (a,b) | a b }b }RR22 = { (a,b) | a = { (a,b) | a >> b }b }RR33 = { (a,b) | a = { (a,b) | a == b ou a b ou a == --b }b }RR44 = { (a,b) | a = { (a,b) | a == b }b }RR55 = { (a,b) | a = { (a,b) | a == b+1 }b+1 }RR66 = { (a,b) | a+b = { (a,b) | a+b 3 }3 }

RespostaResposta: : RR11: pois a : pois a a a para todo inteiro apara todo inteiro a RR33 e Re R44 Para cada um dos outros casos, podePara cada um dos outros casos, pode--se encontrar um par da se encontrar um par da

forma (a,a) que no est na relao.forma (a,a) que no est na relao.

Propriedades de relaes (reflexividade)Propriedades de relaes (reflexividade)

Caracterizao de reflexividade e Caracterizao de reflexividade e irreflexividadeirreflexividade em termos de em termos de matrizes e dgrafos:matrizes e dgrafos:

1. Matrizes:1. Matrizes:

relao R reflexiva relao R reflexiva a matriz Ma matriz MRR possui todos os possui todos os elementos da diagonal principal iguais a 1elementos da diagonal principal iguais a 1

relao R irreflexiva relao R irreflexiva a matriz Ma matriz MRR possui todos os possui todos os elementos da diagonal principal iguais a 0elementos da diagonal principal iguais a 0

2. Dgrafos:2. Dgrafos:

relao R reflexiva relao R reflexiva para todos os vpara todos os vrtices do drtices do dgrafo grafo existem arestas que ligam o vexistem arestas que ligam o vrtice a ele mesmo.rtice a ele mesmo.

relao R irreflexiva relao R irreflexiva para todos os vpara todos os vrtices do drtices do dgrafo grafo no existem arestas que ligam o vno existem arestas que ligam o vrtice a ele mesmo.rtice a ele mesmo.

Observe tambm que se R sobre A reflexiva, ento:Observe tambm que se R sobre A reflexiva, ento:Dom(R) = Dom(R) = RanRan(R) = A(R) = A

Propriedades de relaes Propriedades de relaes -- simetriasimetria

DefinioDefinio (Simetria)(Simetria): Uma relao R sobre um conjunto A dita : Uma relao R sobre um conjunto A dita simtricasimtrica se se sempresempre que (a,b)que (a,b)R, ento tambR, ento tambm (b,a)m (b,a)R.R.

-- segue que R sobre A segue que R sobre A uma relauma relao o nono--simsimtricatrica se para algumse para alguma,ba,bA for verificado que (a,b)A for verificado que (a,b)R e (b,a)R e (b,a)R.R.

DefinioDefinio (Assimetria)(Assimetria): Uma relao R sobre um conjunto A dita : Uma relao R sobre um conjunto A dita assimtricaassimtrica se se sempresempre que (a,b)que (a,b)R, ento (b,a)R, ento (b,a)R.R.

-- uma relauma relao R sobre A o R sobre A nono--assimassimtricatrica se para se para algumalguma,ba,bA for verificado que (a,b)A for verificado que (a,b)R e (b,a)R e (b,a)R.R.

DefinioDefinio ((AntissimetriaAntissimetria)): Uma relao R sobre um conjunto A dita : Uma relao R sobre um conjunto A dita antissimtricaantissimtrica se se sempresempre que (a,b)que (a,b)R e R e (b,a)(b,a)R, ento a=b.R, ento a=b.

-- equivalentemente, se a equivalentemente, se a b, ento (a,b)b, ento (a,b)R ou (b,a)R ou (b,a)RR

-- uma relauma relao R sobre A o R sobre A nono--antissimantissimtricatrica se existir a,bse existir a,bA comA comaab e tanto (a,b)b e tanto (a,b)R como (b,a)R como (b,a)R.R.

Propriedades de relaesPropriedades de relaes

LembreteLembrete: escrever (a,b) : escrever (a,b) R R equivalente a escrever equivalente a escrever aRbaRb, , que significa dizer que a estque significa dizer que a est relacionado com b por R.relacionado com b por R.

ObservaoObservao: para verificar se estas propriedades so : para verificar se estas propriedades so vlidas vlidas ou noou no para uma certa relao R, devepara uma certa relao R, deve--se notar que:se notar que:

1. Uma propriedade 1. Uma propriedade no vlidano vlida em geral se puder ser em geral se puder ser encontrada uma situao onde ela no pode ser verificada.encontrada uma situao onde ela no pode ser verificada.

2. Se no houver situao em que a propriedade 2. Se no houver situao em que a propriedade falhafalha, deve, deve--se concluir que propriedade sempre vlida.se concluir que propriedade sempre vlida.

Propriedades de relaes Propriedades de relaes -- exemplosexemplos

Exemplo 1Exemplo 1: Seja A=Z (o conjunto dos inteiros) e seja R a : Seja A=Z (o conjunto dos inteiros) e seja R a relao R={(a,b)relao R={(a,b)AAA | a A | a b}. Determine se R b}. Determine se R simsimtrica, trica, assimassimtrica ou antissimtrica ou antissimtrica.trica.

SoluoSoluo::

simetriasimetria: se a: se ab, ento no b, ento no sempre verdade que bsempre verdade que ba a (exemplo: 2 (exemplo: 2 1 mas 1 < 2) 1 mas 1 < 2) R R nono--simsimtrica.trica.

assimetriaassimetria: R no: R no--assimtrica pois se a=2 e b=2 temos assimtrica pois se a=2 e b=2 temos aRbaRbe e bRabRa..

antissimetriaantissimetria: R antissimtrica pois a: R antissimtrica pois abb e be ba a a=b.a=b.

Propriedades de relaes Propriedades de relaes -- exemplosexemplos

Exemplo 2Exemplo 2: Seja A={1,2,3,4} e seja a relao:: Seja A={1,2,3,4} e seja a relao:R={(1,2),(2,2),(3,4),(4,1)}R={(1,2),(2,2),(3,4),(4,1)}

Determine se R simtrica, assimtrica ou antissimtrica.Determine se R simtrica, assimtrica ou antissimtrica.

/

assimetriaassimetria: R no: R no--assimtrica pois (2,2) assimtrica pois (2,2) RR

antissimetriaantissimetria: R antissimtrica pois se a: R antissimtrica pois se ab, ento ou b, ento ou (a,b)(a,b)R ou (b,a)R ou (b,a)R.R.

SoluoSoluo::

simetriasimetria: R no: R no--simtrica, pois, por exemplo, 1R2 e 2R1simtrica, pois, por exemplo, 1R2 e 2R1

Propriedades de relaes Propriedades de relaes -- exemplosexemplos

Exemplo 3Exemplo 3: Seja A= Z: Seja A= Z++ (inteiros positivos) e seja(inteiros positivos) e sejaR = { (a,b)R = { (a,b)AAA | a|b} (a divide b).A | a|b} (a divide b).

Determine se R Determine se R simsimtrica, assimtrica, assimtrica ou antissimtrica ou antissimtrica.trica.

SoluoSoluo::

simetriasimetria: a|b no implica que b|a, ento R no: a|b no implica que b|a, ento R no--simtrica.simtrica.

assimetriaassimetria: se a=b=5, por exemplo, ento : se a=b=5, por exemplo, ento aRbaRb e e bRabRa. Assim, . Assim, R noR no--assimtrica.assimtrica.

antissimetriaantissimetria: se : se a|b e b|a, ento a=b, de modo que R a|b e b|a, ento a=b, de modo que R antissimantissimtrica.trica.

Propriedades de relaes Propriedades de relaes -- exemplosexemplos

Exemplo 4Exemplo 4: Quais das relaes a seguir so simtricas e quais : Quais das relaes a seguir so simtricas e quais so antissimtricas?so antissimtricas?

RR11 = { (a,b) | a = { (a,b) | a b }b }RR22 = { (a,b) | a = { (a,b) | a >> b }b }RR33 = { (a,b) | a = { (a,b) | a == b ou a b ou a == --b }b }RR44 = { (a,b) | a = { (a,b) | a == b }b }RR55 = { (a,b) | a = { (a,b) | a == b+1 }b+1 }RR66 = { (a,b) | a+b = { (a,b) | a+b 3 }3 }

RR33 simtrica: se a=b ou a= simtrica: se a=b ou a=--b, ento b=a ou b=b, ento b=a ou b=--a. a. RR44 simtrica: a=b simtrica: a=b b=a.b=a. RR66 simtrica: a+b simtrica: a+b33 b+ab+a3.3. RR11 antissimtrica: a antissimtrica: a bb e e b b a a b=a.b=a. RR22 antissimtrica: impossvel a>b e b>a. antissimtrica: impossvel a>b e b>a. RR44 antissimtrica pela definio. antissimtrica pela definio. RR55 antissimtrica: impossvel acontecer a=b+1 e b=a+1. antissimtrica: impossvel acontecer a=b+1 e b=a+1.

Caracterizao de simetria, assimetria e Caracterizao de simetria, assimetria e antissimetriaantissimetria atravs da matriz de relaoatravs da matriz de relao

SimetriaSimetria: A matriz M: A matriz MRR=[=[mmijij] de uma relao simtrica satisfaz ] de uma relao simtrica satisfaz propriedade:propriedade:

mmijij=1=1 mmjiji=1=1mmijij=0=0 mmjiji=0=0

Portanto, neste caso temPortanto, neste caso tem--se que se que mmijij=m=mjiji, o que significa que R , o que significa que R simtrica se e somente se Msimtrica se e somente se MRR=(M=(MRR))tt..

AssimetriaAssimetria: A matriz M: A matriz MRR=[=[mmijij] de uma relao assimtrica satisfaz:] de uma relao assimtrica satisfaz:

mmijij=1=1 mmjiji=0=0

Logo, se R assimtrica, segue que Logo, se R assimtrica, segue que mmiiii=0=0 para todo i.para todo i.

AntissimetriaAntissimetria: A matriz M: A matriz MRR=[=[mmijij] de uma relao antissimtrica ] de uma relao antissimtrica satisfaz:satisfaz:

se ise ij ento j ento mmijij=0=0 ou ou mmjiji=0=0

Propriedades de relaes com matrizesPropriedades de relaes com matrizes

Exemplo1Exemplo1: :

=

111100101

M 1R

=

1100110100110110

M 2R

=

000010111

M 3R

=

0001100001001100

M 4R

=

1000010011101001

M 5R

=

1000010011001010

M 6R

Propriedades de relaes com matrizesPropriedades de relaes com matrizes

Exemplo1 (cont.)Exemplo1 (cont.): :

R1 e R2 so simtricas, pois MR1 e R2 so simtricas, pois MR1R1 e Me MR2R2 so matrizes simtricas.so matrizes simtricas.

R3 antissimtrica, pois no existe nenhuma simetria fora da R3 antissimtrica, pois no existe nenhuma simetria fora da diagonal.diagonal.

R3 no assimtrica, pois contm 1s na diagonal principal.R3 no assimtrica, pois contm 1s na diagonal principal.

R4 no simtrica, nem assimtrica e nem antissimtrica pois:R4 no simtrica, nem assimtrica e nem antissimtrica pois:1. M1. MR4R4 no simtrica;no simtrica;2. A presena do 2. A presena do nronro. 1 no elemento m. 1 no elemento m4141 viola tanto aviola tanto a

propriedade de assimetria quanto a de propriedade de assimetria quanto a de antissimetriaantissimetria..

R5 antissimtrica mas no assimtrica.R5 antissimtrica mas no assimtrica.

R6 antissimtrica e no assimtrica.R6 antissimtrica e no assimtrica.

Propriedades de relaes Propriedades de relaes -- transitividadetransitividade

DefinioDefinio: Uma relao R sobre um conjunto A dita : Uma relao R sobre um conjunto A dita transitiva transitiva se, sempre que a R b e b R c, ento a R c.se, sempre que a R b e b R c, ento a R c.

/ Por outro lado, R sobre A uma relao Por outro lado, R sobre A uma relao nono--transitivatransitiva se se

existir a, b e c em A tais que a R b e b R c, mas a R c.existir a, b e c em A tais que a R b e b R c, mas a R c. se tais a, b e c no existirem, ento R se tais a, b e c no existirem, ento R transitivatransitiva..

Propriedades de relaes Propriedades de relaes -- transitividadetransitividade

Exemplo2Exemplo2: A relao R={(1,2),(1,3),(4,2)} sobre A={1,2,3,4} : A relao R={(1,2),(1,3),(4,2)} sobre A={1,2,3,4} transitiva? transitiva?

SoluoSoluo: como no possvel encontrar elementos a, b e c : como no possvel encontrar elementos a, b e c tais que (a,b)tais que (a,b)R, (b,c)R, (b,c)R, mas (a,c)R, mas (a,c)R, R, R R transitivatransitiva..

Exemplo1Exemplo1: Seja A=Z: Seja A=Z++ e R={ (a,b) e R={ (a,b) AAA | a|b } (A | a|b } (a divide ba divide b). ). A relao R transitiva?A relao R transitiva?

SoluoSoluo: suponha que a R b e que b R c, de modo que a|b e : suponha que a R b e que b R c, de modo que a|b e b|c. Ento a|c, o que significa que a R c. Logo, R transitivab|c. Ento a|c, o que significa que a R c. Logo, R transitiva. .

Caracterizao de relaes transitivas por Caracterizao de relaes transitivas por matrizesmatrizes

Se MSe MRR=[=[mmijij] a matriz de uma relao transitiva R, ento M] a matriz de uma relao transitiva R, ento MRRsatisfaz propriedade:satisfaz propriedade:

se se mmijij=1=1 e e mmjkjk=1=1, ento , ento mmikik=1=1

ou seja, a transitividade de R significa que se (Mou seja, a transitividade de R significa que se (MRRMMRR) tem ) tem um 1 em qualquer posium 1 em qualquer posio, ento Mo, ento MRR deve ter um 1 na deve ter um 1 na mesma posimesma posio (o converso pode ser falso), ou seja:o (o converso pode ser falso), ou seja:

MMRRMMRR MMR R

Caracterizao de relaes transitivas por Caracterizao de relaes transitivas por matrizesmatrizes

ExemploExemplo: Mostre que a relao R sobre A={1,2,3} dada : Mostre que a relao R sobre A={1,2,3} dada abaixo transitiva:abaixo transitiva:

SoluoSoluo: Por clculo direto, M: Por clculo direto, MRRMMRR=M=MRR, de modo que R , de modo que R transitiva.transitiva.

=

100100111

MR

Propriedades de relaes Propriedades de relaes -- ExercciosExerccios

Exerccio1Exerccio1: Determine se as relaes abaixo so reflexivas, : Determine se as relaes abaixo so reflexivas, irreflexivas, simtricas, assimtricas, antissimtricas ou transirreflexivas, simtricas, assimtricas, antissimtricas ou transitivas:itivas:

a) R={(1,3),(1,1),(3,1),(1,2),(3,3),(4,4)}a) R={(1,3),(1,1),(3,1),(1,2),(3,3),(4,4)}

b) R={(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4)}b) R={(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4)}

RespostasRespostas: :

a) N, N, N, N, N, Na) N, N, N, N, N, N

b) S, N, S, N, N, Sb) S, N, S, N, N, S

Propriedades de relaes Propriedades de relaes -- ExercciosExerccios

Exerccio2Exerccio2: Seja A={1,2,3,4,5}. Determine se as relaes definidas : Seja A={1,2,3,4,5}. Determine se as relaes definidas pelos dgrafos abaixo so reflexivas, irreflexivas, simtricas, pelos dgrafos abaixo so reflexivas, irreflexivas, simtricas, assimtricas, antissimtricas ou transitivas.assimtricas, antissimtricas ou transitivas.

3

21

4

55

21

3

4

Resp. (a): N, N, N, N, S, S Resp. (b): ?