Aula_05

*
*
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