Matematica Discreta - Relacoes - Produto Cartesiano e Tipos de Relacoes

Matematica Discreta Relações Def de produto cartesiano Sejam A e B dois conjuntos O produto cartesiano entre A e B denotado por A x B é o conjunto formado por todos os pares ordenados x y tal que x A e y B isto é A x B xy x A e y B Exemplo A a 5 3 B 7 6 A x B a a a7 a6 5 5 57 56 7 6 x 7 6 5 x x x x x x x x Def de relação Sejam A e B dois conjuntos Uma relação R de A a B é um subconjunto do produto cartesiano entre A e B isto é R A x B Exemplo R a 5 5 A x B Tipos de relações em um conjunto 1 Def de relação reflexiva Seja A um conjunto Uma relação R sobre A isto é R A x A é reflexiva se satisfaz a seguinte condição x A x x R 2 Def de relação simétrica Seja A um conjunto Uma relação R sobre A isto é R A x A é simétrica se satisfaz a seguinte condição x y A x y R y x R 3 Def de relação antissimétrica Seja A um conjunto Uma relação R sobre A isto é R A x A é antissimétrica se satisfaz a seguinte condição x y A x y R e y x R x y Note que uma relação antissimétrica pode ser simétrica 4 Def de relação transitiva Seja A um conjunto Uma relação R sobre A isto é R A x A é transitiva se satisfaz a seguinte condição x y z A x y R e y z R x z R 5 Def de préordem ou quaseordem Seja A um conjunto Uma relação R sobre A isto é R A x A é uma préordem ou quaseordem se é reflexiva e transitiva Exemplos de préordens ou quaseordens1 5 25 5 ℤ x ℤ ℕ x ℕ relação de divisibilidade 6 Def de ordem parcial Seja A um conjunto Uma relação R sobre A isto é R A x A é uma ordem parcial se é reflexiva transitiva e antissimétrica Exemplos de ordens parciais ℤ x ℤ ℕ x ℕ Exemplo de uma préordem que não é uma ordem parcial ℤ x ℤ A relação sobre ℤ não é antissimétrica 7 Def de relação de equivalência Seja A um conjunto Uma relação R sobre A isto é R A x A é uma relação de equivalência se é reflexiva transitiva e simétrica Exemplo de uma relação de equivalência ℤ x ℤ Representação de relações sobre um conjunto Toda relação R sobre um conjunto A pode ser representada por um grafo dirigido seguindo os seguintes passos 1º Desenhe todos os elementos de A junto a um ponto 2º Para cada x y R desenhe uma seta de x até y Exemplos 1 A a b c d e R₁ a a a e b d e d e a R₁ não é reflexiva pois b R₁ b bb R₁ R₁ não é simétrica pois b R₁ d mas d R₁ b R₁ não é transitiva pois e R₁ a e a R₁ e mas e R₁ e R₁ não é uma préordem nem ordem parcial nem uma relação de equivalência pois R₁ não é reflexiva 2 R₂ R₂ é reflexiva R₂ não é simétrica pois a R₂ d mas d R₂ a R₂ não é transitiva pois dR₂ b e bR₂ a mas dR₂ a R₂ não é antissimétrica pois a R₂ b e b R₂ a mas a b R₂ não é uma préordem nem ordem parcial nem uma relação de equivalência pois R₁ não é transitiva 3 R₃ R₃ é reflexiva R₃ é antissimétrica R₃ é transitiva R₃ não é simétrica pois a R₃ b mas b R₃ a R₃ é uma préordem e é uma ordem parcial R₃ não é uma relação de equivalência pois não é simétrica 4 R₄ R₄ é reflexiva R₄ é antissimétrica R₄ é transitiva R₄ é simétrica R₄ é uma préordem é uma ordem parcial e é uma relação de equivalência 5 R₅ R₅ é reflexiva R₅ não é antissimétrica pois a R₅ b e b R₅ a mas a b R₅ é transitiva R₅ é simétrica R₅ é uma préordem e é uma relação de equivalência R₅ não é uma ordem parcial pois não é antissimétrica