Relações em Conjuntos - Matemática Discreta

MATEMÁTICA DISCRETA Tópico 07 Relações em um Conjunto Consulta indicada MENEZES P B Matemática discreta para computação e informática Porto Alegre Instituto de Informática da UFRGS Editora Sagra Luzzato 2004 Série Livros Didáticos nº16 RELAÇÕES EM UM CONJUNTO A ENDORRELAÇÃO Seja A um conjunto qualquer Então uma relação R onde associamos um elemento de A com outros elementos do próprio conjunto A é dita uma endorrelação ou autorrelação Nesse caso dizemos que R é uma relação de A em A também chamada de relação em A Definição Seja A um conjunto Uma relação R de A em A ou simplesmente uma relação em A é qualquer subconjunto do produto cartesiano A A R é uma relação em A R A A Exemplos Seja A 123 Então a R A A xRy x y A A 11 22 33 R A A R b S A A xSy x y A A 21 31 32 S A A S PROPRIEDADES DAS RELAÇÕES EM A Seja R uma relação definida em um conjunto A qualquer Então Reflexiva R é reflexiva x A xRx x A x x R Informalmente uma relação é reflexiva quando todo elemento está relacionado consigo mesmo 2 Exemplos 1 Seja A 123 Então a R A A xRy x y A A 11 22 33 R A A R R é reflexiva b S A A xSy x y A A 11 21 22 31 32 33 S A A S S é reflexiva c T A A xTy x y A A 21 31 32 T A A T T não é reflexiva d 11 21 P A A P 11 21 A A P não é reflexiva 2 2 R N xRy x y N N R é reflexiva 3 2 R xRy x y R não é reflexiva 3 Irreflexiva R é irreflexiva x A xRx x A x x R Informalmente uma relação é irreflexiva quando todo elemento não está relacionado consigo mesmo Exemplos 1 Seja A 123 Então a R A A xRy x y A A 11 22 33 R A A R R não é irreflexiva b S A A xSy x y A A 11 21 22 31 32 33 S A A S S não é irreflexiva c T A A xTy x y A A 21 31 32 T A A T T é irreflexiva d 11 21 P A A P 11 21 A A P não é irreflexiva 2 2 R N xRy x y N N R não é irreflexiva 3 2 R xRy x y R é irreflexiva 4 Transitiva R é transitiva x y z A xRy yRz xRz x y z A x y R y z R x z R Exemplos 1 Seja A 123 Então a R A A xRy x y A A 11 22 33 R A A R R é transitiva b S A A xSy x y A A 11 21 22 31 32 33 S A A S S é transitiva c T A A xTy x y A A 21 31 32 T A A T T é transitiva d 12 23 J A A P 12 23 A A J não é transitiva 2 2 R N xRy x y N N R é transitiva 3 2 R xRy x y R não é transitiva 5 Simétrica R é simétrica x y A xRx yRx x y A x y R y x R Exemplos 1 Seja A 123 Então a R A A xRy x y A A 11 22 33 R A A R R é simétrica b S A A xSy x y A A 11 21 22 31 32 33 S A A S S não é simétrica c T A A xTy x y A A 21 31 32 T A A T T não é simétrica d 12 21 33 K A A K 12 21 33 A A K é simétrica 2 2 R N xRy x y N N R não é simétrica 3 2 R xRy x y R é simétrica 6 Antissimétrica R é antissimétrica x y A xRy yRx x y x y A x y R y x R x y Exemplos 1 Seja A 123 Então a R A A xRy x y A A 11 22 33 R A A R R é antissimétrica b S A A xSy x y A A 11 21 22 31 32 33 S A A S S é antissimétrica c T A A xTy x y A A 21 31 32 T A A T T é antissimétrica d 12 21 33 K A A K 12 21 33 A A K não é antissimétrica 2 2 R N xRy x y N N R é antissimétrica 3 2 R xRy x y R não é antissimétrica 7 RELAÇÕES DE EQUIVALÊNCIA EM A Seja R A A Então R é uma relação de equivalência em A se e somente se R é reflexiva transitiva e simétrica Definição R é uma relação de equivalência em A R é reflexiva transitiva e simétrica Exemplos 1 R xRy x y é uma relação de equivalência De fato É reflexiva pois x x x É transitiva pois x y z x y y z x z É simétrica pois x y x y y x Classes de Equivalência Seja R uma relação de equivalência em A Seja a A Então a classe de equivalência de a denotada por a ou R a ou R a é o subconjunto de A formado por todos os elementos que estão relacionados com a Ou seja a x A xRa a x A x a R Exemplos 1 Seja A 0123 Seja a relação de equivalência definida por R A A 00 11 22 33 02 13 20 31 R Então classe de equivalência do elemento 0 0 0 02 x A xR classe de equivalência do elemento 1 1 1 13 x A xR classe de equivalência do elemento 2 2 2 02 x A xR classe de equivalência do elemento 3 3 3 13 x A xR Assim 0 2 1 3 Isto significa que segundo esta relação 0 é equivalente a 2 e 1 é equivalente a 3 0 2 1 3 8 RELAÇÕES DE ORDEM EM A Seja R A A Então R é uma relação de ordem em A se e somente se R é reflexiva transitiva e antissimétrica Definição R é uma relação de ordem em A R é reflexiva transitiva e antissimétrica Exemplo Seja A um subconjunto qualquer de A relação em A definida por x y é uma relação de ordem em A De fato É reflexiva pois x x x É transitiva pois x y z x y y z x z É antissimétrica pois x y x y y x x y Ordem Total e Ordem Parcial Seja R uma relação de ordem em A Então R é uma relação de ordem total x y A x y R y x R R é uma relação de ordem parcial x y A x y R y x R Diagrama de Hasse É uma representação gráfica de relações de ordem em conjuntos discretos Seja R uma relação de ordem em A onde A é um conjunto discreto não necessariamente finito Essa relação pode ser representada na forma de um diagrama Assim xRy é representado por y x A representação usual é sempre de baixo para cima pois o diagrama de Hasse não usa arestas orientadas 9 Exemplos 1 Sejam A 0135 e R A A xRy x y É uma relação de ordem total Já que x y A x y R y x R 5 3 1 0 2 Sejam A 123689 e R A A xRy x y É uma relação de ordem parcial Já que 23 23 32 A R R