Se descobrimos que duas pessoas, Tales e Julia estão relacionados, entenderemos que existe alguma conexão entre elas. Ou seja o par (Tales, Julia) se diferencia de outros pares ordenados de pessoas porque existe uma relação que essas duas pessoas satisfazem (eles podem ser irmãos, primos, namorados, etc.).

Matematicamente podemos definir relações de forma análoga.

Dados dois conjuntos S e T, uma relação binária de S para T é um subconjunto de S x T (um conjunto de pares ordenados de elementos de S com elementos de T, respectivamente) .

Exemplo: S = {1,2,3} e T={2,4,7}. O conjunto R={(1,2),(2,4),(2,7)} é formado por elementos de SxT e, por tanto, é uma relação binária de S em T.

Dado um conjunto S, uma relação binária R em S é um subconjunto de S x S.x R y se e somente se (x,y) per tencer a

R.

ExemploExemplo: S = {1,2,3} e x R y se e somente se

x = y ou x > y. Então S x S ={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),

(3,2),(3,3)} e R = {(1,1),(2,2),(3,3),(2,1),(3,1)

(3,2)}.

Considere a relação R definida sobre o conjunto IN e verif ique quais pares ordenados per tencem a R.

a) xRy se só se x=y+1: (2,2), (2,3),(3,3),(3,2).b) xRy se e só se x divide y : (2,4),(2,5),(2,1),

(2,26).c) xRy se e só se x é ímpar : (2,3),(3,4),

(13,18),(23,0), (107,13).d) xRy se e só se x > y 2: (2,1),(1,2),(7,5),

(5,13),(4,3).e) xRy se e só se x + y é par: (2,3),(5,7),(1,0),

(103,48),(65,77).Ver exercícios 1, 2, 3 das pág. 209 e 210.

S={1,2} e x R y se e somente se x + y é par, então

S x S = {(1,1),(1,2),(2,1),(2,2)} e R = {(1,1),(2,2)}. Diz-se que

1 se relaciona com 1 2 se relaciona com 2.

● Em geral, uma relação binária pode ser definida por uma descrição da relação, ao invés da l ista dos pares ordenados. A descrição fornece uma caracterização dos elementos per tencentes à relação.

● Exemplo: S = {Maria, José, Carlos} e Maria tem 10 anos, José, 11 e Carlos, 9.

x R y se e somente se x é mais novo que y.

O par (Maria,Maria) está na relação?

Carlos se relaciona com José?

José se relaciona com alguém?

De Um para Um: se cada primeira ordenada e segunda ordenada aparecem apenas uma vez na relação.

De Um para Muitos: se alguma primeira ordenada aparece mais de uma vez.

De Muitos para Um: se alguma segunda ordenada aparece em mais de um par.

De Muitos para Muitos: se alguma primeira ordenada aparece em mais de um par e alguma segunda ordenada aparece em mais de um par.

● Exemplo: S = {1,2} e R1={(1,1),(2,2)} é uma relação binária de um para um .

● R2={(1,1),(1,2)} não é.

● R2 é uma relação de um para muitos .

● Classif ique as relações vistas nos exemplos anteriores.

Seja R uma relação binária em um conjunto S. Então:

R é reflexiva quando para todo x de S(x,x) per tencer a R.

R é simétrica quando para todo x,y de S(x,y) per tencer a R implicar em (y,x)

per tencer a R. R é transit iva quando para todo x, y, z de

S(x,y) e (y,z) per tencer a R implicar em

(x,z) per tencer a R.

Uma relação que seja reflexiva, simétrica e transitiva é dita relação de equivalência.

R é anti-simétrica quando para todo x,y de S

(x,y) ∈ R e (y,x) ∈ R implicar em x=y.

Que propriedades as relações abaixo satisfazem?

1) S={1,2} e x R y se e somente se x + y é par.

2) Exemplo: S = {Maria, José, Carlos} e Maria tem 10 anos, José,11 e Carlos, 9.x R y se e somente se x é mais novo que y.

3) S = {1,2,3} e x R y se e somente se x = y ou x >y.

4) S={aluno da turma de matemática discreta} e xRy se e somente se x e y estão na mesma

f i la.Ver l ivro Fundamentos Matemáticos, pág.

209, 210, 211, 212.

As relações de equivalência dividem o conjunto sobre o qual ela é definida em classes de equivalência. Nelas, todos os elementos se relacionam e não há relação com nenhum outro de fora da classe.

Ex.: IN e xRy se x+y for par.Nesse caso temos duas classes, a dos pares e a dos ímpares.

Ex.: S é o conjunto de alunos de uma sala e xRy se e só se x e y estiverem na mesma f i la. Como são as classes nesse caso?

Uma relação em um conjunto S que seja reflexiva, anti-simétrica e transit iva é chamada de ordem parcial em S.

Exemplo 1: S = IN e xRy se e só se x ≤ yÉ reflexiva, pois x ≤ x.É anti-simétrica, pois x ≤ y e y ≤ x implica em

x=y.É transit iva, pois x ≤ y e y ≤ z implica em x ≤ z.

Def.: Se R é uma relação de ordem parcial sobre o conjunto S, então o par ordenado (S,R) é chamado conjunto parcialmente ordenado.

Verif ique quais os pares (S,R) abaixo são conjuntos parcialmente ordenados:

Exercício 1: S={1,2,3,4,5,6} e xRy se e só se x divide y.

Exercício 2: S é o conj. de pessoas de Recife

xRy se e só se x é pelo menos tão alto quanto y.

Exercício 3: S é o conjunto de retas do plano e xRy se e só se x e y forem retas paralelas

Sendo S um conjunto f inito podemos representar visualmente um conjunto parcialmente ordenado (S,R) por um diagrama de Hasse.

Cada elemento de S é representado por um ponto, denominado nó ou vér tice do diagrama.

Predecessor de um número: Se xRy, dada a relação R, então temos duas opções:

x = y ou x ≠ y.Se x ≠ y, dizemos que x é um predecessor

de y, ou que y é um sucessor de x.

Se y é um sucessor de x e não existe nenhum outro predecessor entre x e y, então dizemos que x é um predecessor imediato de x.

Considere S = {1,2,3,6,12,18} e xRy se x divide y.

Determine os pares da relação, escreva todos os predecessores de todos os elementos e os imediatos de 6.

Ver ex. 10, pág. 203.

Cada elemento de S é representado por um ponto no 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.

Agora, represente o exemplo citado anteriormente, através do seu diagrama de Hasse.

Ex. 20, 21, 23, 24, 25 da pág. 212 e 213.