Slides 11 0607

Prévia do material em texto

Matemática Discreta
Aula nº 11
Francisco Restivo
2007-04-11
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?
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.
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.
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.
9
Definições de Cantor:
Sendo A e B dois conjuntos finitos tais que |A| = α e |B| = β, então
α + β = |A∪B|, desde que A∩B=Φ
αβ = |A×B|
βα = |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.
11
Exemplo:
Verificar se há dependência funcional entre A1 e A3.
A1 A2 A3 A4
α1 β1 γ2 δ1
α1 β2 γ2 δ3
α1 β3 γ2 δ5
α2 β4 γ1 δ1
α3 β3 γ2 δ2
α3 β1 γ2 δ4
α3 β2 γ2 δ4
X1={α1, α2, α3}, X2={β1, β2, β3, β4}, X3={γ1, γ2}, X4={δ1, δ2, δ3, δ4, δ5}
S = {(α1, γ2), (α2, γ1), (α3, γ2)} é uma função!
A coluna A3 é redundante (desperdiça espaço) e pode originar 
erros.
A1 A3
12
Exemplo mau:
No. encomenda Referência Nome Morada Quantidade Preço
... ... ... ... ... ...
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.
	Matemática Discreta