Teoria das Relações
Uma relação binária é um conjunto de
pares ordenados.
 Uma relação entre dois conjuntos X e Y
é um subconjunto do produto cartesiano
XY
 XY denota o conjunto de todas
^ [P(X x Y)
relações entre X e Y: XY =
Notação:

^ (a, b)  R
a R b=
^ (a, b)
a  b=
Exemplo de Relações
Sejam
cursos-CIn = {graduação, mestrado,
extensão, doutorado}
alunos
= {Maria, João, Ana,
Paulo, Mônica}
e a relação cursa, tal que
Maria cursa graduação
João cursa graduação
Ana cursa mestrado
Paulo cursa doutorado
Exemplo descrito formalmente
cursa: alunoscursos-CIn
cursa = {Maria  graduação,
João  graduação, Ana mestrado,
Paulo  doutorado}
ou
cursa: [P (alunoscursos-CIn)
 a:alunos; c:cursos-CIn 
a cursa c(a=Maria  c=graduação) 
(a=João  c=graduação) 
(a=Ana  c=mestrado) 
(a=Paulo  c=doutorado)
Alguns conceitos

Em R: XY, X é o tipo fonte (source)
de R e Y é o tipo destino (target) de R.

Um elemento x do tipo X pertence ao
domínio de R se existe yY tal que
x R y. Neste caso, y pertence a imagem
(range) de R.
Domínio
[X, Y]
dom _ : (XY)  [P X
 R: XY  dom R = {x:X | y:Y  x R y}
Alguns exemplos:
dom {} = {}
dom {x  y} = {x}
dom cursa = {Maria, João, Ana, Paulo}
Teoremas sobre domínio
dom (S  T) = dom S  dom T
Mas CUIDADO com a interseção!
podem ser diferentes
dom (S  T)
dom S  dom T
Exemplos:
dom ({1 2}  {1 3}) = dom {} = {}
dom {1 2}  dom {13} = {1}  {1} = {1}
Imagem
[X, Y]
ran _ : (XY)  [PY
 R: XY  ran R = {y:Y | x:X  x R y}
Alguns exemplos:
dom {} = {}
dom {x  y} = {y}
dom cursa = {graduação, mestrado,
doutorado}
Teoremas sobre imagem
ran (S  T) = ran S  ran T
Mas CUIDADO com a interseção!
podem ser diferentes
ran (S  T)
ran S  ran T
Exemplos:
ran ({1 2}  {3 2}) = ran {} = {}
ran {1 2}  ran {32} = {2}  {2} = {2}
Restrição de domínio

S R denota a relação formada a partir
de R, restringindo-se seu domínio ao
conjunto S.
Alguns exemplos:
{Maria, Ana} cursa = {Maria  graduação,
Ana  mestrado}
{Monica} cursa = {}
Definição formal
[X, Y]
_ _ : [PX  (XY)  (XY)
 S: [P X; R: XY 
S R = {x:X; y:Y | xS  x R y  x  y}
Teoremas
(S
R)R
T (S R) = (T  S ) R
Restrição de imagem

R S denota a relação formada a partir
de R, restringindo-se sua imagem ao
conjunto S.
Alguns exemplos:
cursa {graduação} = {Maria  graduação,
João  graduação}
cursa {extensão} = {}
Definição formal
[X, Y]
_ _ : (XY)  [PX  (XY)
 S: [P X; R: XY 
R S = {x:X; y:Y | yS  x R y  x y}
Teoremas
(R
S)  R
(R S) T = R (S  T)
(S R) T = S (R
T)
Subtração de domínio

S R denota uma relação com todos os
pares de R cujo 1o elemento não
pertence ao conjunto S
Alguns exemplos:
{Maria, Ana} cursa = {João  graduação,
Paulo  doutorado}
{Monica} cursa = cursa
Definição formal
[X, Y]
_ _ : [PX  (XY)  (XY)
 S: [P X; R: XY 
S R = {x:X; y:Y | xS  x R y  x  y}
Teoremas
dom (S R) = (dom R) \ S
S R = (X \ S) R
R = (S R)  (S R)
Subtração de imagem

R S denota uma relação com todos os
pares de R cujo 2o elemento não
pertence ao conjunto S.
Alguns exemplos:
cursa {graduação} = {Ana  mestrado,
Paulo  doutorado}
cursa {extensão} = cursa
Definição formal
[X, Y]
_ _ : (XY)  [PX  (XY)
 S: [P X; R: XY 
R S = {x:X; y:Y | yS  x R y  x y}
Teoremas
ran (R S) = (ran R) \ S
R S = R (Y \ S)
R = (R S)  (R S)