Grátis
Denunciar
Pré-visualização | Página 1 de 2
* * MATEMÁTICA DISCRETA – AULA 5 PROFESSORA HELGA BODSTEIN, D.Sc. Aula 5 RELAÇÕES DE ORDEM E CONJUNTOS PARCIALMENTE ORDENADOS * * Conteúdo Propriedades em uma relação binária Ordem parcial em um conjunto Representação gráfica de uma Relação de Ordem por um diagrama Problemas de ordenação de tarefas por meio da Relação de Ordem e Diagrama de Hasse * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Introdução O estudo das relações binárias é a base para a compreensão da construção de um banco de dados relacional para um empreendimento e também para o estudo de funções. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Relações Binárias Sejam dois conjuntos A e B, qualquer subconjunto do produto cartesiano A x B é dito Relação Binária de A em B. Exemplo: Seja A ={a, b} e B = {a, b, c}, então o conjunto R = {(a,a), (b,a), (b,c)} é uma Relação Binária de A em B. R é um subconjunto de A x B * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Relações Binárias Se o número de elementos do conjunto A é igual a m e o número de elementos do conjunto B é igual a p, então: O número de relações binárias possíveis entre os conjuntos A e B é igual a 2m.p * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Relações Binárias Endorrelação ou auto-relação Considere um conjunto A não vazio. Uma relação binária R sobre A ou endorrelação ou auto-relação é qualquer subconjunto do produto cartesiano A×A, isto é, R ⊆ A ×A (leia-se: R é subconjunto de A x A) Podemos chamar relação de A em A de Relação Interna sobre o conjunto A. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Relações Internas Grafo da relação As relações em A podem ser representadas por grafos dirigidos os quais são constituídos por um conjunto de vértices (que representam os elementos de A) e um conjunto de ramos (que correspondem aos pares ordenados que pertencem à relação). * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Relações Internas Exemplo: Considere o conjunto A = {1, 2, 3} e a relação binária sobre A: R = {(1,1), (2,1), (3,3)} ⊆A×A. A relação R pode, por exemplo, ser representada pelo diagrama a seguir: * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Relações Internas R = {(1,1), (2,1), (3,3)} ⊆A×A. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Relações Internas Exemplo: Sejam A={1,2,3,4} e R={(1,1),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)}. O grafo de R é: * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Relações Internas Exemplo: Explicite a relação determinada pelo grafo abaixo: R = {(1,1), (1,3), (2,3), (3,2), (3,3), (4,3)} * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Reflexiva Seja R uma relação sobre o conjunto A. A relação R é dita REFLEXIVA se todo elemento de um conjunto A está relacionado consigo mesmo, ou seja: (x,x) R, x A * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Reflexiva Exemplo: É uma relação reflexiva a relação R sobre o conjunto A={a,b,c} descrita por: R = {(a,a), (b,b),(c,c)} * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Reflexiva - Grafo Para todos os vértices do grafo, existem arestas que ligam o vértice a ele mesmo. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Simética A relação R é dita SIMÉTRICA se quando x está relacionado com y, implicar em y estar relacionado com x, ou seja: (x, y) R (y, x) R, para x, y A * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Simética Exemplo: É simétrica a relação R no conjunto A={a,b,c} descrita por: R = {(a, a), (b, b),(a, b),(b, a)} * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Simética - Grafo Se de algum vértice do grafo partir uma aresta para um outro vértice, deve obrigatoriamente existir uma aresta no sentido oposto. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Transitiva A relação R é dita TRANSITIVA se quando x está relacionado com y e y está relacionado com z, implicar em x estar relacionado com z, ou seja: (x, y) R e (y, z) R(x, z) R, para x, y, z A. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Transitiva Exemplo: É transitiva a relação R no conjunto A={a,b,c}, é descrita por: R = {(a, a),(a, c),(c, b),(a, b)} * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Antiassimétrica A relação R é dita ANTISSIMÉTRICA se quando x está relacionado com y e y está relacionado com x somente quando x = y. (x, y)R e (y, x) R x = y, para x e y A * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Antiassimétrica Exemplo: É antissimétrica uma relação R no conjunto A={a, b, c}, descrita por: R = {(a, a), (b, b),(a, b),(a, c)} * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Relação Antiassimétrica - Grafo Se de algum vértice do grafo partir uma aresta para um outro vértice, não pode existir uma aresta no sentido contrário. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Exemplo: Seja S= {a, b, c}, classifique a relação R = {(a,a), (b,b), (c,c), (a,b), (a,c)} * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias R é reflexiva, todo elemento tem um laço R é antissimétrica, existem flechas sem duas pontas * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Exemplo: Seja R = {(a,a), (c,c), (a,b), (b,c), (a,c)}. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados R não é reflexiva, nem todo elemento tem um laço R é antissimétrica, existem flechas sem duas pontas R é transitiva, para todo par de flechas consecutivas existe uma flecha cuja origem está na origem da primeira e a extremidade está na extremidade da segunda * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Exemplo: Seja R = {(a,a), (b,b), (b,c), (c,b), (b,d), (d,b), (c,d), (d,c)} * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados R não é reflexiva, nem todo elemento tem um laço. R é simétrica, toda flecha tem duas pontas. R é transitiva, para todo par de flechas consecutivas existe uma flecha cuja origem está na origem da primeira e a extremidade está na extremidade da segunda. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias Exemplo: Seja o conjunto A = {a, b, c, d} e R uma relação em A, onde: x R y, x A e y A, se identifica por x y. Considerando o diagrama abaixo, classifique R. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados A = {a, b, c, d} Como nenhum elemento de A se relaciona com ele mesmo, então R não é Reflexiva. Como o elemento a se relaciona com o elemento b e o elemento b não se relaciona com o elemento a, então R não é simétrica. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados A = {a, b, c, d} Quando, por exemplo, a se relaciona com b e b se relaciona com c ou com d tem-se que a se relaciona com c ou com d, nesse caso R é transitiva. * * Aula 5 – Relações de ordem e conjuntos parcialmente ordenados Propriedades das Relações Binárias - RELAÇÃO DE EQUIVALÊNCIA Uma relação R sobre um conjunto A não vazio é chamada relação de equivalência sobre A se, e