Departamento de Informática – E D L M
Funções
Rosen 5th ed., §1.8
Estruturas Discretas e Lógica Matemática
Dep. de Informática – UFMA
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções
• Conceito familiar no cálculo
• Função real f, que associa a cada
número xR um valor particular
y=f(x), onde yR.
• Noção generalizada
– Conceito de associar elementos de um
conjunto qualquer a elementos de um
outro conjunto qualquer
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Definição Formal
• Sejam A e B dois conjuntos, então
dizemos que um função f de A em B
(f:AB) é uma associação de um
único elemento f(x)B a cada
elemento xA.
• Generalizações desta Idéia:
– Função f associa zero ou elemento de B
a cada elemento xA.
– Funções de n argumentos; relations.
• Mais na frente veremos
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Gráficos de Funções
• Podemos representar uma função
f:AB como o conjunto de pares
ordenados {(a,f(a)) | aA}.
– Isto torna f uma relação entre A e B:
– Para cada aA, existe somente um par
(a,b).
• Podemos representar os pares
ordenados como pontos em um plano.
– Assim desenhamos uma curva com um
único y para cada x.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
• Funções pode ser representadas
graficamente:
f
a•
A
f
•
b
A
•
•
•
•
•
B
•
•
•
•
y
Grafo Bipartido
B
Diagrama de Venn
x
Gráfico
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções que já vimos
• Uma proposição pode ser vista como uma
funçãoque leva de “situações”em valores
veradade {T,F}
– p=“Está chovendo.”
– s=nossa situação aqui hoje
– p(s){T,F}.
• Um operador proposicional pode ser visto
como uma função de pares ordenados em
valores verdade: e.g., ((F,T)) = T.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Mais funções
• Um predicado pode ser visto como
uma função de objetos em
proposições:
P :≡ “tem 2 metros de altura”;
P(Zé) = “Zé tem 2 metros de altura.”
• Uma bit string B de comprimento n
pode ser vista como uma função de
números {1,…,n}(posições dos bits)
em bits {0,1}.
E.g., B=101  B(3)=1.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Continuando
• Um conjunto S sobre um universo U
pode ser visto como uma função dos
elementos de U em {T, F}, definindo
se cada elemento de U está no
conjunto S
• Suponha U={0,1,2,3}. Então
S={3} S(0)=S(1)=S(2)=F, S(3)=T
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Continuando
• Um conjunto de operadores tal como
,, pode ser visto como uam
função de pares de conjuntos em
conjuntos.
– Exemplo: (({1,3},{3,4})) = {3}
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Notação
• Podemos escrever YX para denotar o
conjunto F de todas as possíveis
funções f: XY.
• Assim, f  YX é outra maneira de
dizer que f: XY.
• Notação apropriada
– Para X e Y finitos
|F| = |Y||X|.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Detalhe
• Se usarmos F0, T1, então um
subconjunto TS é uma função de S
em {0,1}
• P(S) pode ser representado como
{0,1}S (o cojunto de todas as funções
de S em {0,1} )
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Terminologia
• Se escrevemos f:AB, e f(a)=b (onde
aA & bB), podemos dizer:
– A é o domínio de f.
– B b é o contra-domínio de f.
– b é a imagem de a em f.
– O conjunto imagem de f:AB é o
conjunto de todas as imagens de
elementos de A.
– Dizemos que f:AB mapeia A em B.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções
• Considere a função f:PC com
P = {Linda, Max, Kathy, Peter}
C = {Boston, New York, Hong Kong, Moscow}
•
•
•
•
f(Linda) = Moscow
f(Max) = Boston
f(Kathy) = Hong Kong
f(Peter) = New York
• O conjunto imagem de f é C.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções
• Let us re-specify f as follows:
•
•
•
•
f(Linda) = Moscow
f(Max) = Boston
f(Kathy) = Hong Kong
f(Peter) = Boston
yes
What is its range?
{Moscow, Boston, Hong Kong}
• Is f still a function?
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções
• Other ways to represent f:
•x
•f(x)
Linda
Boston
•Linda
•Moscow
Max
New York
•Max
•Boston
•Kathy
•Hong
Kong
Kathy
Hong Kong
•Peter
•Boston
Peter
Moscow
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções
• Se o domínio de f for grande, é conveniente
especificar f com uma fórmula, e.g.:
• f:RR
• f(x) = 2x
•
•
•
•
•
Isto leva a:
f(1) = 2
f(3) = 6
f(-3) = -6
…
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções
• Sejam f1 e f2 funções de A em R.
• Então a soma e o produto de f1 e f2 são
também funções de A em R definidas por:
• (f1 + f2)(x) = f1(x) + f2(x)
• (f1f2)(x) = f1(x) f2(x)
• Exemplo:
• f1(x) = 3x, f2(x) = x + 5
• (f1 + f2)(x)= f1(x)+f2(x)=3x + x + 5 = 4x + 5
• (f1f2)(x) = f1(x) f2(x) =3x(x + 5) = 3x2 + 15x
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções
• Seja f:AB.
• Se tomarmos um subcon
• If we only rejunto SA, o conjunto
de todas as imagens de
elementos sS é denominado
imagem de S.
• Denotada por f(S):
• f(S) = {f(s) | sS}
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções
•
•
•
•
•
•
•
•
•
Considere a seguinte função:
f(Linda) = Moscow
f(Max) = Boston
f(Kathy) = Hong Kong
f(Peter) = Boston
Qual a imagem de S = {Linda, Max} ?
f(S) = {Moscow, Boston}
Qual a imagem de S = {Max, Peter} ?
f(S) = {Boston}
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Composição
• A composição de duas funções g:AB e
f:BC, denotada por fg, é definida como
• (fg)(a) = f(g(a))
• Isto significa que:
–
–
–
–
•
a primeira função é aplicada ao elemento aA,
mapeando ele em um elemento de B,
Então f é aplicada a este elemento de B
Mapeando eme em um elemento de C.
Assim:
– função composta mapeia elementos de A em C.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Composição
• Exemplo:
• f(x) = 7x – 4, g(x) = 3x,
• f:RR, g:RR
• (fg)(5) = f(g(5)) = f(15) = 105 – 4 =
101
• (fg)(x) = f(g(x)) = f(3x) = 21x - 4
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Composição
• Composição de função e sua inversa:
• (f-1f)(x) = f-1(f(x)) = x
• É a função identidade I(x) = x.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
• Uma função f:AB é dita injetora sss
– x, yA (f(x) = f(y)  x = y)
– x, yA(x,y: xy  f(x)f(y)).
• F é injetora sss não mapeia dois
elementos distintos de A no mesmo
elemento de B.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
•
•
•
•
De novo
f(Linda) = Moscow
f(Max) = Boston
f(Kathy) = Hong
Kong
• f(Peter) = Boston
• F é injetora?
– Não,
– Max e Peter são
mapeados na
mesma imagem.
g(Linda) = Moscow
g(Max) = Boston
g(Kathy) = Hong Kong
g(Peter) = New York
G é é injetora?
Sim
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
• Como provar que um função é injetora?
• Olhe a definição primeiro:
• x, yA (f(x) = f(y)  x = y)
• Exemplo:
• f:RR
• f(x) = x2
• Use contra exemplo pra provar que não é:
• f(3) = f(-3), but 3  -3, so f is not one-to-one.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
•
•
•
•
•
•
•
•
•
… outro exemplo:
f:RR
f(x) = 3x
Injetora: x, yA (f(x) = f(y)  x = y)
Mostrar que : f(x)  f(y) quando x  y
xy
3x  3y
f(x)  f(y),
assim se x  y, então f(x)  f(y), logo, f é
injetora.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
• A função f:AB com A,B  R é
denominada estritamente crescente, se
• x,yA (x < y  f(x) < f(y)),
• E estritamente descrescente se
• x,yA (x < y  f(x) > f(y)).
• Um função que é estritamente crescente ou
estritamente descrescente é injetora.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
• Uma função f:AB é denominada
sobrejetora, sss para cada elemento
bB existe um elemento aA com f(a)
= b.
• Se o cojunto imagem for igual ao
contra-domínio
• Uma função f: AB é bijetora sss é
injetora e sobrejetora.
• Logo: se f é bijetora e A e B são
conjuntos finitos, então |A| = |B|.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
•
•
•
•
•
•
F é injetora?
Linda
Não.
F é sobrejetora?
Max
Não.
F é bijetora?
Kathy
Não.
Peter
Boston
New York
Hong Kong
Moscow
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
•
•
•
•
•
•
F é injetora? Linda
Não.
Max
F é sobrejetora?
Sim.
Kathy
F é bijetora?
Peter
Não.
Boston
New York
Hong Kong
Moscow
Paul
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
•
•
•
•
•
•
F é injetora?
Sim.
F é sobrejetora?
Não.
F é bijetora?
Não.
Linda
Boston
Max
New York
Kathy
Hong Kong
Peter
Moscow
Lübeck
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
• F é injetora?
Linda
• Não.
• F não é função Max
Boston
New York
Kathy
Hong Kong
Peter
Moscow
Lübeck
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Propriedades das Funções
•
•
•
•
•
•
F é injetora?
Sim
F é sobrejetora?
Sim
F é bijetora?
Sim
Linda
Boston
Max
New York
Kathy
Hong Kong
Peter
Moscow
Helena
Lübeck
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Inversa
• As funções bijetora possuem uma
função inversa.
• f:AB tem como função inversa
• f-1:BA com f-1(b) = a tal que f(a) = b.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Inversa
Exemplo:
A inversa é dada por:
f-1(Moscow) = Linda
f(Linda) = Moscow
f-1(Boston) = Max
f(Max) = Boston
f-1(Hong Kong) = Kathy
f(Kathy) = Hong Kong f-1(Lübeck) = Peter
f(Peter) = Lübeck
f-1(New York) = Helena
f(Helena) = New York
Inversão so é possível
É um função bijetora para bijetoras
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Inversa
Linda
Boston
f
Max
New York
f-1
Kathy
Peter
Helena
• f-1:CP não é
Hong Kong função
• Não está definida
para todos os
Moscow
elementos de C
• Associa duas
Lübeck
imagens a New
York.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Função teto e piso
• Mapeiam números reais em inteiros (RZ).
• Piso(floor) associa rR ao maior zZ com z
 r, denotado por r.
– 2.3 = 2, 2 = 2, 0.5 = 0, -3.5 = -4
• Teto (ceiling) associa rR ao menor zZ
com z  r, denotado por r.
– 2.3 = 3, 2 = 2, 0.5 = 1, -3.5 = -3
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Sequências
Rosen 5th ed., §1.8
Estruturas Discretas e Lógica Matemática
Dep. de Informática – UFMA
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Sequências
• Representam listas ordenadas de
elementos.
• É definida como uma função de um
subconjunto de N em um conjunto S.
• Usamos a notação an para denotar a
imagem do inteiro n
• Chamamos an de um termo da sequência.
• Subconjunto de N:
1 2 3 4 5 …
S:
2 4 6 8 10 …
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Sequências
• Usamos a Notação {an} para
descrever uma sequência.
• É conveniente descrever uma
sequência com uma fórmula.
• Por exemplo: a sequência do slide
anterior
{an}, where an = 2n.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
As Fórmulas de Sequências
Quais as fórmulas pras seguintes sequências
a1, a2, a3, … ?
1, 3, 5, 7, 9, …
an = 2n - 1
-1, 1, -1, 1, -1, …
an = (-1)n
2, 5, 10, 17, 26, …
an = n2 + 1
0.25, 0.5, 0.75, 1, 1.25 … an = 0.25n
3, 9, 27, 81, 243, …
an = 3n
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Strings
• Sequências finitas são denominadas
de strings, denotadas por a1a2a3…an.
• O comprimento de uma string S é o
número de termos que S possui.
• A string vazia não contém termos.
Possui comprimento zero
Prof. Anselmo Paiva
Somatórios
Departamento de Informática – E D L M
n
O que isto significa?
a
j m
j
•A variável j é denominada índice do
somatório, indo do seu limite inferior m ao
limite superior n.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Somatórios
Como expressar a soma dos primeiros mil
termos de uma sequência {an} com an=n2 para
n = 1, 2, 3, … ?
Escrevemos como
Qual o valor de
1000

6 j 1
j
j2
?
j 1
• 1 + 2 + 3 + 4 + 5 + 6 = 21.
Qual o valor de
100
j
?
j 1
Muito trabalho pra calcular isto
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Somatórios
•Gauss apresentou a seguinte fórmula:
n

j 1
n(n  1)
j
2
Quando temos esta fórmula, podemos
calcular o valor de qualquer somatório:
100(100  1) 10100
j

 5050

2
2
j 1
100
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Séries Aritméticas
n
•Como:

j 1
n(n  1)
j
2
???
Observe que:
1 + 2 + 3 +…+ n/2 + (n/2 + 1) +…+ (n - 2) + (n - 1) + n
= [1 + n] + [2 + (n - 1)] + [3 + (n - 2)] +…+ [n/2 + (n/2 + 1)]
= (n + 1) + (n + 1) + (n + 1) + … + (n + 1)
(com n/2 termos)
= n(n + 1)/2.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Séries Geométricas
•Como :
( n 1)
a
 1 ???
j
a 

(a  1)
j 0
n
Observe que:
S = 1 + a + a 2 + a3 + … + a n
aS = a + a2 + a3 + … + an + a(n+1)
assim, (aS - S) = (a - 1)S = a(n+1) - 1
Entao, 1 + a + a2 + … + an = (a(n+1) - 1) / (a - 1).
E.G.: 1 + 2 + 4 + 8 +… + 1024 = 2047.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Séries Úteis
1.
n

j 1
n(n  1)
j
2
( n 1)
a
1
a 

(a  1)
j 0
n
2.
j
n(n  1)( 2n  1)
j 

6
j 1
n
3.
2
n
4.

j 1
2
2
n
(
n

1
)
j3 
4
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Somatórios Duplos
• Correspondendo a loops aninhados
em linguagens de programação:
5
• Exemplo:
2
 ij
i 1 j 1
5
  (i  2i )
i 1
5
  3i
i 1
 3  6  9  12  15  45
Prof. Anselmo Paiva