Relações de Ordem: Reflexivas, Simétricas, Antissimétricas e Transitivas

Prévia do material em texto

Matemática Computacional / Aula 05 – Relações de Ordem: Reflexivas, Simétricas, Antissimétricas, Transitivas e Equivalentes
Objetivos desta aula
Nesta aula, você irá: 
1. Identificar algumas propriedades importantes em uma relação binária.
2. Entender que uma ordem parcial em um conjunto indica que alguns elementos deste conjunto são predecessores de outros elementos.
3. Representar graficamente uma Relação de Ordem por um diagrama.
4. Entender que Relação de Ordem e Diagrama de Hasse são formas naturais de se representar problemas de ordenação de tarefas para algum tipo de empreendimento.
Relações Binárias Reflexivas, Simétricas, Antissimétricas e Transitivas
Se A é um conjunto não vazio, uma relação binária R sobre A ou endorrelação ou autorrelação é qualquer subconjunto do produto cartesiano (A x A), isto é:
R ( A x A (leia-se: R é subconjunto de A x A).
Um par ordenado (a, b) ( R ou aRb.
Exemplo: Considere o conjunto A = {1,2 ,3} e a relação binária sobre A.
R = {(1, 1), (2, 1), (3, 3)} ( A x A. 
Diagrama de flechas para representar uma Relação R sobre um conjunto A
No estudo das relações sobre um conjunto A com poucos elementos, é útil fazer uma representação visual da relação através de um esquema de flechas, conforme indicamos a seguir:
Representar o conjunto A com seus elementos.
Indicar cada par ordenado (x, y) da relação através de uma flecha com origem x e extremidade y.
Se o par ordenado (x, x) está na relação, usa-se um laço envolvendo o elemento x.
Representação em diagrama de flechas da relação R.
Propriedades das relações binárias
Seja R uma relação sobre o conjunto A. A relação R é dita REFLEXIVA se todo elemento do conjunto A está relacionado consigo mesmo, ou seja:
Exemplo 1:
 
A relação R sobre o conjunto A={a, b, c} descrita por:
R = {(a, a), (b, b), (c, c)} é uma relação reflexiva.
O diagrama de flechas que representa a R é dado a seguir por:
(*) R é reflexiva, observe que todo elemento do conjunto A possui um laço.
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
Exemplo 2:
 
A relação R no conjunto A={a, b, c} descrita por:
R = {(a, a), (b, b), (a, b), (b, a), (b, c), (c, b)} é uma relação simétrica.
(*) R é simétrica, observe que toda flecha possui duas pontas.
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.
Exemplo 3:
 
A relação R no conjunto A={a, b, c}, descrita por:
R = {(a, a), (a, c), (c, b), (a, b)} é uma relação transitiva.
(*) R é transitiva, para um par de flechas consecutivas existe uma flecha cuja origem está na origem da primeira e a extremidade está na extremidade da segunda. 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
Exemplo 4:
Uma relação R no conjunto A={a, b, c}, descrita por:
 
R = {(a, a), (b, b), (a, b), (a, c)} é antissimétrica.
(*) R é antissimétrica, observe que não existem flechas com duas pontas.
Resumindo:
Uma relação R sobre o conjunto A pode ser classificada como:
( Reflexiva quando para todo x ∈ A, (x, x) ∈ R ou xRx.
( Simétrica quando para quaisquer x, y ∈ A , se xRy então yRx.
( Antissimétrica quando para quaisquer x, y ∈ A, se xRy e yRx então x = y.
( Transitiva quando para quaisquer x, y, z ∈ A, se xRy e yRz então xRz.
Exemplo 5:
Considere o conjunto Z dos números inteiros.
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.
R é reflexiva – todo elemento de A possui um laço;
R é simétrica – toda flecha possui duas pontas;
R é transitiva – para um par de flechas consecutivas existe uma flecha cuja origem está na origem da primeira e a extremidade está na extremidade da segunda.
Exercícios deste tópico no fim da apostila (ANEXO 1).
Relação de ordem parcial
Uma relação R sobre um conjunto A não vazio é chamada relação de ordem parcial sobre A se, e somente se, R é reflexiva, antissimétrica e transitiva.
Exemplos:
1) A relação no conjunto dos números reais x R y se e só se x ≤ y é uma relação de ordem parcial:
De fato, é reflexiva (xRx), antissimétrica (se aRb e bRa então a = b) e transitiva (se aRb e bRc então aRc).
2) A relação no conjunto dos números reais x R y se e só se x < y não é reflexiva, logo não é uma relação de ordem parcial.
3) Outra relação de ordem parcial no conjunto dos inteiros positivos é descrita por:
 
nRm se e somente se n divide m ou (n / m)
Reflexiva: n / n
Antissimétrica: se n / m e m / n, então n = m
Transitiva: se n / m e m / p então n / p
Notação
(S, ≤) - denota um conjunto parcialmente ordenado onde “  ≤   ”  pode indicar:
“menor ou igual” ou  “é um   subconjunto de” ou  “divide”,  etc..., dependendo da ordem estabelecida.
x  <  y - denota que  o elemento x é um predecessor de y ou que y é um sucessor de x na ordem parcial.
x  ≤  y - denota x = y  ou  x < y.
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. 
Por 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.
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.
É fácil ver que essa relação é reflexiva e antissimétrica. Além disso, x < y ↔ tarefa x é pré-requisito para a tarefa y.
Relação de ordem total
É uma relação de ordem parcial onde todo elemento do conjunto está relacionado a todos os outros elementos.
Exemplo 1
Exemplo 2
Exemplo 3
Diagrama de Hasse
Podemos representar visualmente um conjunto A parcialmente ordenado pelo diagrama de Hasse, esta representação pode ser obtida adotando-se os seguintes procedimentos:
Cada elemento do conjunto A será representado por um ponto, denominado nó ou vértice do diagrama.
Se x é um predecessor imediato de y, o nó que representa y é colocado acima do nó que representa x e os dois nós são conectados por um segmento de reta.
Atenção!
O diagrama de Hasse representa graficamente a propriedade a seguir:  “Um elemento em um nível superior cobre o de nível inferior”.
Exemplo 1:
Considere a relação de ordem “x divide y” no conjunto
A = {1, 2, 3, 6, 12, 18}
Então, em termos de pares ordenados, R é dada a seguir:
R= {(1, 1), (1, 2), (1, 3), (1, 6), (1, 12), (1, 18), (2, 2), (2, 6), (2, 12), (2, 18), (3,3), (3, 6), (3, 12), (3, 18), (6, 6), (6, 12), (6, 18), (12, 12), (18, 18)}
Observe que:
( R é reflexiva, todo elemento se relaciona com ele mesmo;
( R é antissimétrica, para todo (x, y) não existe (y, x);
( R é transitiva, temos, por exemplo, (3, 6), (6, 12) e (3, 12) pertencentes a R.
O diagrama de Hasse desta relação de ordem parcial pode ser dado na forma a seguir: 
Máximo e Mínimo:
Seja um conjunto parcialmente ordenado (PO). Dizemosque x é Máximo se todos 
os outros elementos do conjunto estiverem abaixo de x, e, x é mínimo se todos os outros elementos do conjunto estiverem acima de x.
No exemplo 1, o número 1 é um mínimo para o conjunto PO, mas este conjunto não possui máximo.
Exemplo 2:
Considere o conjunto parcialmente ordenado que consiste nos divisores positivos de 36, ordenados por divisibilidade. Neste conjunto, o elemento 1 é mínimo porque está estritamente abaixo de todos os outros elementos do conjunto. O elemento 36 é máximo porque está estritamente acima de todos os outros elementos.
Exemplo 3:
Considere o intervalo fechado [0, 1], por exemplo, há um elemento que é o maior de todos (máximo) e outro que é o menor de todos (mínimo). No caso, o máximo no intervalo é o número um e o mínimo é o número zero.
Elemento maximal e elemento minimal para um conjunto PO
O elemento x será maximal se não existir qualquer elemento estritamente acima de x, e minimal se não existir qualquer elemento estritamente abaixo dele.
Teorema
Num conjunto A parcialmente ordenado pela relação R, se houver elemento máximo de A então é elemento maximal e não há outros; se houver elemento mínimo de A então é elemento minimal e não há outros.
Exemplo:
Consideremos o conjunto PO que consiste nos números inteiros de 1 a 6 ordenados por divisibilidade.
 
Neste conjunto PO, o elemento 1 é mínimo, mas não há elemento máximo. Os elementos 4, 5 e 6 são maximais e o elemento 1 é minimal.
Atenção!
Não há elemento ‘maior’ que um elemento maximal nem há elemento ‘menor’ que um elemento minimal.
Mais Exemplos:
1) No conjunto de todos os subconjuntos próprios de {a, b, c} ordenado parcialmente pela relação {a, b}, {a, c}, {b, c}, são elementos maximais.
2) Seja o conjunto {1, 2, 3, 4, 5, 6} ordenado pela divisibilidade. Então, o diagrama de Hasse deste conjunto está apresentado a seguir:
3) Dada a relação R definida a seguir, observe o Diagrama de Hasse que a representa:
R = {(a, a), (b, b), (c, c), (p, p), (q, q), (x, x), (y, y), (a, p), (b, q), (c, q), (x, a), (x, b), (x, p), (x, q), (y, b), (y, c), (y, q)}
Os elementos x e y são minimais e os elementos p e q são maximais para o conjunto 
parcialmente ordenado.
4) O conjunto {x, y, z}, parcialmente ordenado pelos seus subconjuntos próprios, apresenta o seguinte diagrama de Hasse:
 
5) Seja o conjunto A = { 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 } com todos os divisores de 60, parcialmente ordenado pela divisibilidade, apresenta o seguinte diagrama de Hasse:
Síntese da aula
Nesta aula, você: 
Identificou algumas propriedades importantes em uma relação binária. 
Entendeu que uma ordem parcial em um conjunto indica que alguns elementos deste conjunto são predecessores de outros elementos. 
Representou visualmente uma Relação de Ordem por um diagrama. 
Percebeu que Relação de Ordem e Diagrama de Hasse são maneiras naturais de se representar problemas na ordenação de tarefas para algum tipo de empreendimento.
O que vem na próxima aula
Na próxima aula, abordaremos os seguintes assuntos:
 
Função de um conjunto S em um conjunto T. 
Domínio, contradomínio, imagem e Gráfico de uma função. 
Funções sobrejetoras, injetoras e bijetoras. 
Função composta. 
Conceito de inversa e Diagrama da definição de uma função inversa.
�PAGE �
�PAGE �10�