Avaliando o Aprendizado - Matemática Discreta V-193

Prévia do material em texto

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. 
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. 
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. 
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. 
 
 
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)} 
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. 
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). 
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. 
Regras: 
SeA é 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. 
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. 
Exemplo: Considere o grafo da relação de ordem “≤”sobre o conjunto A={1,2,3,4}: 
 
 
Exemplo: Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", monte odiagrama de Hasse: