Aula_05

Aula_05


DisciplinaMatemática Discreta6.432 materiais85.771 seguidores
Pré-visualização2 páginas
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 \u2013 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 \u2013 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:
	\u2013 Consequentemente, x e y podem se matricular na mesma hora se e somente se (x,y) \uf0ce R.
	\u2013 Pode-se notar que R é reflexiva, simétrica e transitiva.
*
*
Aula 5 \u2013 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 \u2013 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.
\u2192 Ordenamos palavras usando xRy, onde x vem antes do y no dicionário!
*
*
Aula 5 \u2013 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 (\u2264) ou de maior ou igual (\u2265). 
A relação de ordem é interna e só existe se comparar elementos do mesmo conjunto.
*
*
Aula 5 \u2013 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 \u2013 Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM
Parcial
Total
*
*
Aula 5 \u2013 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 \u2013 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 \u2264 y é uma relação de ordem parcial.
\u2192 É reflexiva (aRa), antissimétrica (se aRb e bRa, então a=b) e transitiva (se aRb e bRc, então aRc).
*
*
Aula 5 \u2013 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 \u2013 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 \u2013 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 \u2013 Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
*
*
Aula 5 \u2013 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 \u2264 y \u2194 tarefa x = tarefa y ou tarefa x é pré-requisito para a tarefa y.
Relação é reflexiva e antissimétrica.  
A relação \u2264 é uma relação de ordem parcial em qualquer subconjunto do conjunto dos números reais.
*
*
Aula 5 \u2013 Relações de ordem e conjuntos parcialmente ordenados
Propriedades das Relações Binárias
Grafo representativo das tarefas:
*
*
Aula 5 \u2013 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 \u2013 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 \u201cx é múltiplo de y\u201d é uma relação de ordem total em A.
A ordem natural \u201cx \u2264 y\u201d no conjunto dos números reais é uma relação de ordem total.
*
*
Aula 5 \u2013 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
\u2013 Conjuntos munidos de uma relação de ordem são uma relação e portanto pode-se desenhar seu grafo.
\u2013 No entanto, muitas arestas não precisam estar presentes em virtude das propriedades da relação de ordem (reflexiva e transitiva).
*
*
Aula 5 \u2013 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
\u2013 Para simplificar a representação, retira-se de seus grafos as arestas que sempre devem estar presentes.
\u2013 As estruturas obtidas desta forma são chamadas de DIAGRAMAS DE HASSE da relação de ordem.
*
*
Aula 5 \u2013 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 \u2013 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 \u2013 Relações de ordem e conjuntos parcialmente ordenados
Exemplo: Considere o grafo da relação de ordem \u201c\u2264\u201dsobre o conjunto A={1,2,3,4}:
*
*
Aula 5 \u2013 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 &quot;x divide y&quot;, monte o diagrama de Hasse:
*
*
Aula 5 \u2013 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 &quot;x divide y&quot;, monte o diagrama de Hasse:
*
*
Aula 5 \u2013 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 &quot;x divide y&quot;, monte o diagrama de Hasse:
*
*
Aula 5 \u2013 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 &quot;x divide y&quot;, monte o diagrama de Hasse:
*