Relações

Prévia do material em texto

Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Relac¸o˜es
Renata de Freitas e Petrucio Viana
Instituto de Matema´tica, UFF
Outubro de 2010
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Suma´rio
• Relac¸o˜es.
• Operac¸o˜es sobre relac¸o˜es.
• Propriedades ba´sicas.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
De Roever
• Semaˆntica relacional de
programas.
De Roover
(1943 – ****)
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Motivac¸a˜o
• Objetos podem ser especificados de acordo com a maneira
como eles se relacionam com outros objetos.
Exemplo:
Renata e´ a melhor professora que eu ja´ tive.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
• Va´rios conceitos matema´ticos importantes podem ser
vistos como relac¸o˜es.
Exemplos:
=, ≤, ∈, ⊆
444
444Relac¸a˜o
sim/na˜o
a, b
//
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
• Programas, determin´ısticos ou na˜o-determin´ısticos, podem
ser vistos como relac¸o˜es.
Exemplos:
444
444MDC
4
12, 8
//
444
444Divisorcomum
2
12, 8
//
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
“Relac¸o˜es esta˜o em toda parte!”
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Definic¸a˜o
Definic¸a˜o Sejam A e B conjuntos. Dizemos que R e´ uma
relac¸a˜o de A em B se R ⊆ A× B.
Observe que relac¸o˜es sa˜o conjuntos de pares ordenados.
• ∅ e´ uma relac¸a˜o.
• Se A e B sa˜o conjuntos, enta˜o A× B e´ uma relac¸a˜o.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Exemplos importantes
(a) =
(b) ≤, <, ≥ e >
Em N, as relac¸o˜es ≤ e < sa˜o definidas a partir de +.
Definic¸a˜o Sejam a, b ∈ N. Dizemos que a ≤ b se, e
somente se, existe c ∈ N tal que a + c = b.
Definic¸a˜o Sejam a, b ∈ N. Dizemos que a < b se, e
somente se, existe c ∈ N∗ tal que a + c = b.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Exemplos importantes
Em R, a relac¸a˜o ≤ e´ definida a partir de + e 2.
Definic¸a˜o Sejam a, b ∈ R. Dizemos que a ≤ b se, e somente
se, existe c ∈ R tal que a + c2 = b.
Exerc´ıcio Definir ≤ em Z e em Q.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Exemplos importantes
(c) Divisibilidade.
Em N, a relac¸a˜o de divisibilidade | e´ definida a partir da
operac¸a˜o de multiplicac¸a˜o.
Definic¸a˜o Sejam a, b ∈ N. Dizemos que a|b se, e
somente se, existe c ∈ N tal que a · c = b.
Exerc´ıcio Definir | em Z, em Q e em R.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Exemplos importantes
(d) Primos entre si.
Definic¸a˜o Sejam a, b ∈ N. Dizemos que a e b sa˜o primos
entre si se, e somente se, para todo c ∈ N, se c |a e c |b,
enta˜o c = 1.
Definic¸a˜o Sejam a, b ∈ Z. Dizemos que a e b sa˜o primos
entre si se, e somente se, para todo c ∈ Z, se c |a e c |b,
enta˜o c = 1 ou c = −1.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Exemplos importantes
(e) Congrueˆncia mo´dulo n.
Questa˜o Como jogar par ou ı´mpar com 3 pessoas?
E com 4 pessoas?
E com 5?
E com n, n ∈ N∗?
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Operac¸o˜es sobre relac¸o˜es
Noc¸o˜es e operac¸o˜es usuais sobre conjuntos adequam-se a`s
relac¸o˜es, pois relac¸o˜es sa˜o conjuntos.
∈, ⊆, =, ∪, ∩, −
Observac¸o˜es:
• Os objetos que pertencem a uma relac¸a˜o sa˜o pares
ordenados.
• Para a aplicac¸a˜o da operac¸a˜o de complementac¸a˜o, deve-se
considerar um universo adequado.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Operac¸o˜es sobre relac¸o˜es
Existem operac¸o˜es especiais que se aplicam a relac¸o˜es, que
levam em conta que os elementos das relac¸o˜es sa˜o pares
ordenados.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Reversa˜o
Definic¸a˜o Seja R uma relac¸a˜o de A em B.
O reverso de R e´ a relac¸a˜o:
R−1 = {(b, a) ∈ B × A : (a, b) ∈ R}.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Propriedades ba´sicas de −1
(1) (R−1)−1 = R
(2) R−1 = R−1
(3) (R ∩ S)−1 = R−1 ∩ S−1
(4) (R ∪ S)−1 = R−1 ∪ S−1
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Composic¸a˜o
Definic¸a˜o
Sejam R ⊆ A× B e S ⊆ C × D.
A composic¸a˜o de R com S e´ a relac¸a˜o:
R ◦ S = { (x , z) ∈ A× D :
existe y ∈ B ∩ C tal que
(x , y) ∈ R e (y , z) ∈ S }.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Propriedades ba´sicas de ◦
(1) (R ◦ S) ◦ T = R ◦ (S ◦ T )
(2) R ◦ R = ???
(3) R ◦ S = ???
(4) R ◦ S = ???
(5) R ◦ (S ∩ T ) = ???
(6) R ◦ (S ∪ T ) = ???
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Relac¸o˜es especiais
Definic¸a˜o Sejam A e B conjuntos.
(a) ∅ e´ uma relac¸a˜o de A em B.
(b) A× B e´ uma relac¸a˜o de A em B.
(b) IdA = {(a, a) : a ∈ A} e´ uma relac¸a˜o de A em A,
chamada identidade em A.
(b) DfA = {(a, b) ∈ A× A : a 6= b} e´ uma relac¸a˜o de A em
A, chamada diversidade em A.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Propriedades ba´sicas das relac¸o˜es
especiais
Para toda relac¸a˜o R ⊆ A× B:
(1) R ◦ IdB = R
(2) IdA ◦ R = R
(3) ???
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Princ´ıpio ba´sico da
investigac¸a˜o cient´ıfica
“Se esta´ complicado, simplifique.”
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
Endorrelac¸o˜es
Definic¸a˜o Seja A um conjunto. Dizemos que R e´ uma
endorrelac¸a˜o em A se R ⊆ A× A.
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
A´lgebra das endorrelac¸o˜es
Para todas as relac¸o˜es R,S ,T em A:
(1) (R ◦ S) ◦ T = R ◦ (S ◦ T )
(2) R ◦ IdA = IdA ◦ R = R
(3) R ◦ ∅ = ∅ ◦ R = ∅
(4) R ◦ (S ∪ T ) = (R ◦ S) ∪ (R ◦ T )
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜es
Propriedades
ba´sicas
A´lgebra das endorrelac¸o˜es
(5) (R ∩ S)−1 = R−1 ∩ S−1
(6) (R ∪ S)−1 = R−1 ∪ S−1
(7) (R−1)−1 = R
(8) R−1 = R−1
(9) (R ◦ S)−1 = S−1 ◦ R−1
Relac¸o˜es
Renata de
Freitas e
Petrucio
Viana
Relac¸o˜es
Operac¸o˜es
sobre relac¸o˜esPropriedades
ba´sicas
Exerc´ıcios
1. Exerc´ıcios do Menezes
(Paulo B. Menezes, Matema´tica Discreta para Computac¸a˜o e
Informa´tica, 2a. edic¸a˜o, Sagra Luzzatto / Instituto de Informa´tica da
UFRGS, Porto Alegre, 2006).
2. Exerc´ıcios do Scheinerman
(E.R. Scheinerman, Matema´tica Discreta, Thomson, Sa˜o Paulo,
2006).
3. Exerc´ıcios da Lista 8.
	Relações
	Operações sobre relações
	Propriedades básicas