Slides 12

Prévia do material em texto

1
Matemática Discreta
Aula nº 12
Francisco Restivo
2006-04-07
2
Funções injectivas e sobrejectivas:
Uma função pode ser tal que elementos diferentes do seu domínio 
tenham a mesma imagem no seu codomínio,
Ou então que existam elementos do seu codomínio que não são 
imagem de nenhum elemento do seu domínio.
Definições:
Seja f: A ® B uma função.
A função f diz-se injectiva se 
"a,a’ÎA, se (a,b),(a’,b’)Îf Ù a¹a’ então b¹b’.
A função f diz-se sobrejectiva se 
"bÎB, $aÎA tal que (a,b)Îf.
Em R´R, a função quadrado não é injectiva nem sobrejectiva.
E a função 3x – 7?
2
3
Teorema:
Dada uma função f: A ® B entre dois conjuntos finitos,
Se f é injectiva, então |A| £ |B|
Se f é sobrejectiva, então |A| ³ |B|
Função injectiva:
todas as imagens são diferentes
Função sobrejectiva:
todas os elementos de B são imagens
4
Teoremas:
Se duas funções f: A ® B e g: B ® C são ambas injectivas, então 
a função composta g°f também é injectiva.
Se duas funções f: A ® B e g: B ® C são ambas sobrejectivas, 
então a função composta g°f também é sobrejectiva.
3
5
Não funciona em sentido contrário, mas…
Teoremas:
Dadas duas funções f: A ® B e g: B ® C se a função composta 
g°f é injectiva, então f é injectiva.
Dadas duas funções f: A ® B e g: B ® C se a função composta 
g°f é sobrejectiva, então g é sobrejectiva.
6
Funções bijectivas:
Uma função f: A ® B simultâneamente injectiva e sobrejectiva, diz-
se bijectiva (ou uma bijecção).
Função bijectiva: correspondência um a um
Teoremas:
A composição de duas bijecções é uma bijecção.
Se A e B são finitos, então |A| = |B|
A função identidade é uma bijecção.
4
7
Função inversa:
Será que invertendo o sentido das setas da função f: A ® B se 
obtem uma função g: B ® A? Não é garantido!
Tem se ser sobrejectiva, para todos os elementos de B terem uma 
imagem. E tem de ser injectiva, para nenhum elemento de B ter 
mais do que uma imagem.
Teorema:
Se f: A ® B é uma função, a relação g = {(b, a) Î B× A: (a, b) Î f} 
é uma função se e só se f é uma bijecção.
Definição:
Se f: A ® B é uma bijecção, a função g: B ® A definida por g(b)=a
se e só se f(a)=b designa-se por função inversa de f, f-1.
Teorema:
Se f: A ® B é uma função e f-1: B ® A a sua inversa, f-1°f e f°f-1 são
identidades.
8
Cardinalidade (referência muito breve a Cantor):
Segundo Cantor, dois conjuntos finitos A e B têm a mesma 
cardinalidade, |A| = |B|, se existir uma bijecção f: A ® B.
Um conjunto com a cardinalidade de Z+ diz-se infinito contável. A 
sua cardinalidade é ?0 (alef zero).
O conjunto R não é infinito contável. Não é possível encontrar uma 
bijecção f: Z+ ® R (prova-se por contradição). A sua cardinalidade
é c (de continuum).
Cantor descobriu uma sequência infinita de diferentes 
cardinalidades infinitas:
?0 = |Z+|
?1 = |P(Z+)|
?2 = |P(P(Z+))|, etc.
5
9
Definições de Cantor:
Sendo A e B dois conjuntos finitos tais que |A| = a e |B| = ß, então
a + ß = |AÈB|, desde que AÇB=F
aß = |A×B|
ßa = |C|, em que C é o conjunto de todas as funções A ® B.
Hipótese de Cantor:
c = ?1
Gödel, outro grande matemático, provou em 1938 que é
impossível provar que c ¹ ?1.
O conjunto de todas as funções binárias com N bites tem 
cardinalidade 2N. Porquê?
10
Aplicação às bases de dados relacionais:
Uma base de dados relacional com atributos A1, A2, …, An é um 
conjunto de relações entre os conjuntos Xi de dados associado 
aos atributos Ai. Cada relação R Í X1´X2´…´ Xm é uma tabela. 
Cada elemento é um registo.
Dependência funcional:
Um atributo Aj diz-se funcionalmente dependente do atributo Ai se 
não ocorrem registos com o mesmo valor de Ai e diferentes 
valores de Aj.
Se projectarmos a relação R nos atributos Ai e Aj, obtem-se uma 
relação S com todos os pares ordenados (xi, xj) que figuravam em 
R.
Se S for uma função, há dependência funcional entre Ai e Aj: Aj
deduz-se de Ai.
6
11
Exemplo:
Verificar se há dependência funcional entre A1 e A3.
d4g2b2a3
d4g2b1a3
d2g2b3a3
d1g1b4a2
d5g2b3a1
d3g2b2a1
d1g2b1a1
A4A3A2A1
X1={a1, a2, a3}, X2={b1, b2, b3, b4}, X3={g1, g2}, X4={d1, d2, d3, d4, d5}
S = {(a1, g2), (a2, g1), (a3, g2)} é uma função!
A coluna A3 é redundante (desperdiça espaço) e pode originar 
erros.
A1 A3
12
Exemplo mau:
..................
PreçoQuantidadeMoradaNomeReferênciaNo. encomenda
Se fizermos uma projecção por Nome e Morada, corremos o risco 
de obter mais que uma morada para o mesmo nome, por simples 
erro de introdução de dados!
Segunda forma normal: nenhum atributo não primário é
funcionalmente dependente em nenhum subconjunto de uma 
chave.
Terceira forma normal: além disso, sempre que um atributo não 
primário é funcionalmente dependente de um conjunto de 
atributos, este contem uma chave como um subconjunto.