Aula_05

*
*
MATEMÁTICA DISCRETA \u2013 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 \u2013 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 \u2013 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 \u2013 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 \u2013 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 \u2286 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 \u2013 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 \u2013 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)} \u2286A×A.
A relação R pode, por exemplo, ser representada pelo diagrama a seguir: 
*
*
Aula 5 \u2013 Relações de ordem e conjuntos parcialmente ordenados
Relações Internas
R = {(1,1), (2,1), (3,3)} \u2286A×A.
*
*
Aula 5 \u2013 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 \u2013 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 \u2013 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) \uf0ce R, \uf022 x \uf0ce A
*
*
Aula 5 \u2013 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 \u2013 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 \u2013 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) \uf0ce R\uf0ae (y, x) \uf0ce R, para x, y \uf0ce A
*
*
Aula 5 \u2013 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 \u2013 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 \u2013 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) \uf0ceR e (y, z) \uf0ceR\uf0ae(x, z) \uf0ce R, para x, y, z \uf0ce A.
*
*
Aula 5 \u2013 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 \u2013 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)\uf0ceR e (y, x) \uf0ceR\uf0ae x = y, para x e y \uf0ce A
*
*
Aula 5 \u2013 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 \u2013 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 \u2013 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 \u2013 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 \u2013 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 \u2013 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 \u2013 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 \u2013 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 \u2013 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 \uf0ce A e y \uf0ce A, se identifica por x \uf0ae y. Considerando o diagrama abaixo, classifique R.
*
*
Aula 5 \u2013 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 \u2013 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 \u2013 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