Relações

Relações

Relações

Ao estudarmos conjuntos, estamos interessados em certas propriedades de seus elementos ou em relações entre conjuntos. Ou seja, queremos analisar sua estrutura.

Relações Binárias

Na vida real, quando dizemos que duas pessoas, Maria e José, se relacionam, entendemos que Maria e José se distinguem dos demais pares de pessoas por haver uma relação que eles satisfazem ou verificam.

Ex.Maria e José são casados.

Maria e José são colegas de trabalho.

Maria e José não se entendem.

Maria manda em José

Em matemática é análogo: distinguimos determinados pares de objetos dos demais porque seus elementos satisfazem alguma relação que os elementos dos demais pares, em geral, não satisfazem.

Relações Binárias

Dados dois conjuntos S e T

Uma relação R entre S e T é dada por

R SxT

Uma relação binária R em S é dada por

R SxS = S2

Relações Binárias

Ex.: Sejam S= {1,2} e T = {2,3}

Temos que SxT = {(1,2), (1,3), (2,2), (2,3)}

• Relação de igualdade: os elementos do par são iguais.

O único par do “universo” (SxT) que satisfaz essa relação é (2,2),

• Relação menor do que: isto é, primeiro elemento do par é menor do que o segundo.

Três pares se distinguem: (1,2), (1,3), (2,3).

Relações Binárias

Definição de uma relação ST:

• com palavras • pela enumeração dos pares ordenados que a

satisfazem.• Por uma fórmula relacional• Pela definição do conjunto

Usaremos a notação xy ou (x,y) para indicar que o par ordenado (x,y) satisfaz ou pertence à relação : x y (x,y) .

Uma relação ST também é denotada por (ST)

.

Relações Binárias

Exemplos. Sejam S = {1,2} e T = {2,3,4} : • descrição: x y x+y é ímpar.

• x y x+y = 2n+1, com n N

• x y = {(1,2), (1,4), (2,3)}

• = {(x,y) | x S e y T e x+y é ímpar}

Seja PESSOA um conjunto de pessoas, podemos ter:

casado-com(PESSOA, PESSOA)

Relações Binárias

• Para cada uma das seguintes relações binárias em NN, determine quais dos pares ordenados apresentados pertencem à :

a. x y x = y+1 ((2,2), (2,3), (3,3), (3,2)

b. x y x divide y (2,4), (2,5), (2,6)

c. x y x é ímpar (2,3), (3,4), (4,5), (5,6)

d. x y x > y2 (1,2), (2,1), (5,2), (5,4), (4,3))

Relações n-árias

→Dados os conjuntos S1, S2, ..., Sn, uma relação n-ária em S1S2...Sn é um subconjunto de S1S2...Sn. Neste caso para uma relação em S1S2...Sn escrevemos (s1, s2, ...,sn) se s1, s2, ...,sn pertence à relação.

→Exemplo: A= {1,2}, B = {2}, C = {2,3}.

ABC = {(1,2,2), (1,2,3), (2,2,2), (2,2,3)}

(x,y,z) x=y=z = {(2,2,2)}

(x,y,z) x>y = ??

Relações unárias

• Uma relação unária em um conjunto S é um subconjunto particular de S.

• Um elemento x de S satisfaz ou pertence à se, e somente se, x pertence ao subconjunto que define a relação.

• Exemplo 1: O conjunto dos números pares P (subconjunto de N) é definido pela relação:

x x é par.

• Exemplo 2: Para o conjunto pessoa podemos ter a relação unária maior-de-idade(PESSOA).

Relações em um conjunto S

Uma relação binária em um conjunto S é um subconjunto de S2 = (SxS).

Ex.: x y xy em N

Analogamente, uma relação n-ária em um conjunto S é um subconjunto de Sn.

Ex.: (x,y,z) x+y=z em N.

Definições

Seja uma relação binária em SxT. Então, consiste de um conjunto de pares ordenados da forma (s,t).

é uma relação um-para-um se cada primeiro elemento s e cada segundo elemento t aparecem exatamente uma vez na relação.

Formalmente: se (s,t) e (s,t’) então t=t’ e se (s,t) e (s’,t) então s=s’

Ex.: Sejam S = {2,5,7,9} e T = {1,3,4,5}

= {(2,4), (5,5), (7,3), (9,1}

Definições

é uma relação um-para-muitos se algum primeiro elemento s aparece mais de uma vez.

Ex.: = {(7,4), (2,5), (2,3)}

é uma relação muitos-para-um se algum segundo elemento t fizer par com mais de um primeiro elemento s..

Ex.: = {(2,4), (3,4), (5,2)}

é uma relação muitos-para-muitos se pelo menos um s fizer par com mais de um t e pelo menos um t fizer par com mais de um s..

Ex.: = {(7,4), (2,5), (9,4), (2,3)}

Operações sobre relações

• Seja B o conjunto de todas as relações binárias em um dado conjunto S:

B = P(SxS) = {: é uma relação binária em S}• Isto é, se B, então S2 .• Assim, se e B, então podemos aplicar as

operações de conjuntos à e resultando em novos subconjuntos de S2, isto é, em novas relações binárias:

• x ( ) y x y ou x y• x ( ) y x y e x y• x ’ y não x y.

Exercícios

1. Sejam e duas relações binárias em S={1,2,3,4,5} definidas por:

x y x = y e x y x < y. Encontre:

a. b. ’

c. ’

d. e. ’

2. Analise as relações

pai-de(PESSOA,PESSOA),

casado-com(PESSOA, PESSOA) e

trabalha-em(PESSOA,EMPRESA)

Quanto às características

um-para-um, um-para-muitos, etc.)

Propriedades das relações

Seja uma relação binária em S.

é reflexiva quando xx para todo x S.

é simétrica quandoxy se, e somente se yx para todo x e y S.

é transitiva quando, xy e yz implica xz para todo x, y e z S.

é anti-simétrica quando xy e yx implica x = y para todo x e y S.

Exemplo

Seja S = N os naturais, e x y x+y é par. é reflexiva. é transitiva. é simétrica

Fecho de uma relação

Se uma relação em um conjunto S não tem uma certa propriedade, podemos tentar estender a fim de obter uma relação * em S que tenha a propriedade.

Uma relação binária * em um conjunto S é dita ser o fecho de uma relação em S relativo à propriedade P se:

1 * tem a propriedade P;

2 * ;

3 * é a ‘menor’ relação contendo com a propriedade P

Fecho de uma relação

Obs.: a nova relação * conterá todos os pares ordenados que contém mais os pares ordenados adicionais necessários para que a propriedade desejada se verifique. Portanto, *.

• Exemplo: • Seja S = {1,2,3} e = {(1,1), (1,2), (1,3), (3,1), (2,3)}

• Então,

- o fecho reflexivo de em S é:

* = {(1,1), (1,2), (1,3), (3,1), (2,3), (2,2), (3,3)}

- o fecho simétrico de em S é:

* = {(1,1), (1,2), (1,3), (3,1), (2,3), (2,1), (3,2)}

Exercício

Seja S = {a,b,c,d} e

= {(c,c), (a,c), (a,d), (b,d), (c,a)}

• Encontre os fechos reflexivo, simétrico e transitivo de .