Aula_05

Prévia do material em texto

*
*
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 ordenadosA = {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 somente se, R é reflexiva, simétrica e transitiva.
Exemplo: Seja o conjunto A={a,b,c}, então a relação R sobre A descrita por:
 R = {(a,a), (b,b),(c,c),(a,c),(c,a)} é de equivalência.
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
- RELAÇÃO DE EQUIVALÊNCIA
Exemplo: Suponha que a matrícula dos estudantes em uma dada Universidade siga o esquema:
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
Seja R a relação que contém (x,y) e x e y são estudantes com nomes começando com letras do mesmo bloco:
	– Consequentemente, x e y podem se matricular na mesma hora se e somente se (x,y)  R.
	– Pode-se notar que R é reflexiva, simétrica e transitiva.
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM
Intuitivamente, podemos pensar numa relação de ordem quando lembramos de uma fila no banco, de uma fila de alunos dispostos numa sala de aula, na relação "menor ou igual" no conjunto dos números naturais, etc
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM
Relações são usadas frequentemente para alguns ou todos os elementos de um conjunto.
→ Ordenamos palavras usando xRy, onde x vem antes do y no dicionário!
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM
A relação de ordem é uma generalização do conceito de menor ou igual (≤) ou de maior ou igual (≥). 
A relação de ordem é interna e só existe se comparar elementos do mesmo conjunto.
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM
Uma relação R sobre um conjunto A não vazio é chamada relação de ordem sobre A se, e somente se, R é reflexiva, antissimétrica e transitiva.
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM
Parcial
Total
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM PARCIAL
Uma Relação de ordem parcial é uma relação que é ao mesmo tempo reflexiva, antissimétrica e transitiva.
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM PARCIAL
Exemplo: A relação no conjunto dos números reais:
 x R y se e só se x ≤ y é uma relação de ordem parcial.
→ É reflexiva (aRa), antissimétrica (se aRb e bRa, então a=b) e transitiva (se aRb e bRc, então aRc).
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM PARCIAL
Quando temos uma ordem parcial em um conjunto, alguns elementos deste conjunto irão preceder outros, isto é, conseguiremos estabelecer uma ordenação para os elementos do conjunto. 
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM PARCIAL
De forma equivalente, se um conjunto de tarefas deve ser executado na realização de um empreendimento, a idéia de que a tarefa x precede a tarefa y (x < y) significa que a tarefa x deve ser executada antes da tarefa y. 
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM PARCIAL
Exemplo: Deseja-se construir uma casa de madeira. O processo pode ser dividido em uma série de tarefas, algumas delas tendo outras tarefas como pré-requisitos. A tabela abaixo mostra as tarefas para construir a casa e os respectivos pré-requisitos.
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
Podemos definir uma ordem parcial no conjunto de tarefas por  x ≤ y ↔ tarefa x = tarefa y ou tarefa x é pré-requisito para a tarefa y.
Relação é reflexiva e antissimétrica.  
A relação ≤ é uma relação de ordem parcial em qualquer subconjunto do conjunto dos números reais.
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
Grafo representativo das tarefas:
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
Relação de ordem total
É uma relação de ordem onde todo elemento do conjunto está relacionado a todos os outros elementos.
Exemplo: S = {a, b, c}
 
R = { (a,a), (b,b), (c,c), (a,b), (b,c),(a,c)}
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
Relação de ordem total
Exemplo: A relação no conjunto A={2,4,8,16,...,2n,...) definida por “x é múltiplo de y” é uma relação de ordem total em A.
A ordem natural “x ≤ y” no conjunto dos números reais é uma relação de ordem total.
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
Diagramas de Hasse de Conjuntos munidos de uma Relação de Ordem
– Conjuntos munidos de uma relação de ordem são uma relação e portanto pode-se desenhar seu grafo.
– No entanto, muitas arestas não precisam estar presentes em virtude das propriedades da relação de ordem (reflexiva e transitiva).
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
Diagramas de Hasse de Conjuntos munidos de uma Relação de Ordem
– Para simplificar a representação, retira-se de seus grafos as arestas que sempre devem estar presentes.
– As estruturas obtidas desta forma são chamadas de DIAGRAMAS DE HASSE da relação de ordem.
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Regras:
Se A é um conjunto finito, então podemos representar visualmente um conjunto parcialmente ordenado em A por um diagrama de Hasse. 
Cada elemento de A é representado por um ponto (vértice) do diagrama. 
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
O diagrama de Hasse pode ser construído com base num grafo, onde as arestas que representam as relações reflexivas e transitivas ficam implícitas no diagrama. 
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Exemplo: Considere o grafo da relação de ordem “≤”sobre o conjunto A={1,2,3,4}:
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Exemplo: Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", monte o diagrama de Hasse:
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Exemplo: Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", monte o diagrama de Hasse:
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Exemplo: Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", monte o diagrama de Hasse:
*
*
Aula 5 – Relações de ordem e conjuntos parcialmente ordenados
Exemplo: Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", monte o diagrama de Hasse:
*