Exercícios Resolvidos sobre Relações de Equivalência e Operações Binárias

1 Determine se cada uma das relações definidas abaixo é uma relação de equivalência Caso seja descreva a classe de equivalência determinada pela relação a nRm em Z se nm 0 b xRy em R se x y c xRy em R se x y d xRy em R se x y 3 e Seja f R R dada por fx x² 5x 6 xRy em R se fx fy 2 Determine se cada uma das operações binárias abaixo é comutativa e se é associativa a em Z definida por a b a b b em Q definida por a b ab 1 c em Q definida por a b ab2 d em Z definida por a b 2ab e em Z definida por a b ab 3 Seja S um conjunto unitário Quantas operações binárias podem ser definidas em S Responda a pergunta para um conjunto S com 2 elementos Responda a pergunta para um conjunto com 3 elementos Para um conjunto com n elementos 4 Decida se cada uma das afirmações abaixo é correta aceitável para publicação a Uma operação binária é comutativa se e somente se a b b a b Uma operação binária é associativa se e somente se para todos a b c S temse b c a b c a c Um subconjunto H de um conjunto S é fechado para a operação binária definida em S se e somente se a b H para todos a b S 5 Prove que se é uma operação binária comutativa e associativa em S então a b c d d c a b para todos a b c d S 1 a nRm em Z se nm 0 Solução Vejamos se a relação é de equivalência i seja n Z Se n 0 então nn 0 e portanto nRn Agora se n 0 então nn 0 e logo nRn Logo R é reflexiva ii sejam m n Z tais que nRm Então nm 0 implicando mn 0 Z é comutativo logo mRn Portanto R é simétrica iii suponha nRm e mRk Então nm 0 e mk 0 Observe que se nm 0 então ou n m 0 ou n m 0 Analogamente se mk 0 então mk 0 ou mk 0 Logo nk 0 e portanto nRk Logo R é transitiva Portanto R é uma relação de equivalência A classe de equivalência de n Z é n m Z nm 0 b x R y em IR se x y Solução R não é uma relação de equivalência pois R não é simétrica Considere x 2 y 1 Temos x R y pois 2 1 Mas y R x pois 1 2 c x R y em IR se 1x1 1y1 Solução Sejam x y z IR i Como 1x1 1x1 então x R x Logo R é reflexiva ii Se x R y então 1x1 1y1 Logo 1y1 1x1 implicando y R x Portanto R é simétrica iii Se x R y e y R z Então 1x1 1y1 e 1y1 1z1 Logo 1x1 1z1 e portanto x R z ou seja R é transitiva Portanto R é uma relação de equivalência A classe de equivalência de x IR é x x x d x R y em IR se x y 3 Solução R não é uma relação de equivalência Suponha que x R y e y R z Logo x y 3 e y z 3 Temos x z x y y z x y y z desigualdade triangular 3 3 6 Logo x z 6 Portanto R não é transitiva 1e f IR IR dada por fx x² 5x 6 x R y se fx fy Solução Sejam x y z IR i Como fx fx então x R x Logo R é reflexiva ii Se x R y então fx fy logo fy fx implicando y R x Portanto R é simétrica iii Se x R y e y R z então fx fy e fy fx implicando fx fz logo x R z Portanto R é transitiva Contudo concluímos que R é uma relação de equivalência A classe de x é dada por x y IR fx fy y y é a solução de x² 5x 6 a a IR 2 a Considere a operação em Z dada por a b a b a b Z não é comutativa Considere a 2 b 1 Z temos a b 2 1 1 e b a 1 2 1 Logo a b b a Vejamos se é associativa Sejam a b c Z a b c a b c a b c a b c Por outro lado abc abc abc abc Logo abc abc e portanto não é associativa b Considere a operação em Q dada por ab ab 1 a b Q Vejamos se é comutativa Sejam ab Q ab ab 1 ba 1 pois ab Q e vale comutatividade em Q em relação a operação usual ba Logo ab ba ou seja é comutativa Vejamos se é associativa Sejam abc Q abc abc 1 abc 1 1 abc a 1 Por outro lado abc ab 1c ab 1c 1 abc c 1 Logo abc abc e portanto não é associativa c Considere a operação em Q dada por a b ab2 ab Q é comutativa Dados ab Q temos a b ab2 ba2 pois Q é comutativo com a operação usual b a Portanto a b b a é associativa sejam abc Q a b c a bc2 abc22 abc2 21 abc Por outro lado a b c ab2 c ab2 c2 abc2 21 abc Logo a b c a b c e portanto é associativa d Considere a operação em Z dada por a b 2ab é comutativa sejam ab Z a b 2ab 2ba b a ou seja a b b a Vejamos se é associativa Dados abc Z a b c a 2bc 2a2bc Por outro lado abc 2abc 2abc Logo a bc abc e portanto não é associativa e Considere a operação em Z dada por a b ab não é comutativa Pois a b ab e b a ba Logo a b b a Por exemplo tome a 2 b 3 a b 23 8 e b a 32 9 não é associativa Tome a 2 b 3 e c 4 a b c a 34 2 81 281 Por outro lado a b c 23 4 8 4 84 4096 Logo a b c a b c 3 Seja S um conjunto unitário Supomos S a então uma operação binária em S é dada por S x S S a a a Logo só temos uma possibilidade de operação binária em S Agora suponha S um conjunto com dois elementos S a b Temos a seguinte operação S x S S onde podemos ter a b a ou a b b logo temos 222 possibilidades b a a ou b a b logo temos 222 possibilidades Assim obtemos 222222 24 16 possibilidades de operações binárias Agora suponha S com três elementos S a b c Observe que a b a ou b ou c a c a ou b ou c b a a ou b ou c b c a ou b ou c c a a ou b ou c c b a ou b ou c Ou seja para cada par de elementos de S temos 3 possibilidades de resultado Logo temos 333333333 39 19683 possibilidades Agora se S tem n elementos indutivamente temos nn2 n2n possibilidades 4 As alternativas a e b estão corretas Pois essas são as definições de comutativa e associatividade c A afirmação está errada Pois um subconjunto H de um conjunto S é fechado para operação binária definida em S se e somente se ab H para todos ab H 5 Temos abcd cdab pois é comutativa dcab pois é comutativa dcab pois é associativa Portanto abcd dcab