Matematica Discreta Aula 5

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 
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 é chamadarelaçã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
Tarefa Pré-requisitos
1- Limpeza do terreno Nenhum
2- Produção e colocação da fundação Tarefa 1
3- Produção da estrutura Tarefa 2
4- Colocação do telhado Tarefa 3
5- Colocação das tábuas externas Tarefa 3
6-Instalação do encanamento e da fiação Tarefas 4 e 5
7- Colocação das janela e portas Tarefa 3
8- Instalação as paredes internas Tarefa 6
9- Pintura do interior Tarefas 7 e 8
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:
Tarefa Pré-requisitos
1- Limpeza do terreno Nenhum
2- Produção e colocação da
fundação
Tarefa 1
3- Produção da estrutura Tarefa 2
4- Colocação do telhado Tarefa 3
5- Colocação das tábuas
externas
Tarefa 3
6-Instalação do encanamento
e da fiação
Tarefas 4 e 5
7- Colocação das janela e
portas
Tarefa 3
8- Instalação as paredes
internas
Tarefa 6
9- Pintura do interior Tarefas 7 e 8
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:
1
32
6
1812
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:
1
32
6
1812
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:
1
32
6
1812
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: