Funções Rosen 5 th ed., §1.8

Dep

art

am

en

to d

e In

form

áti

ca –

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

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Funções

• Conceito familiar no cálculo

• Função real f, que associa a cada número xR um valor particular y=f(x), onde yR.

• Noção generalizada– Conceito de associar elementos de um

conjunto qualquer a elementos de um outro conjunto qualquer

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Definição Formal

• Sejam A e B dois conjuntos, então dizemos que um função f de A em B (f:AB) é uma associação de um único elemento f(x)B a cada elemento xA.

• Generalizações desta Idéia:– Função f associa zero ou elemento de B

a cada elemento xA.– Funções de n argumentos; relations.

• Mais na frente veremos

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Gráficos de Funções

• Podemos representar uma função f:AB como o conjunto de pares ordenados {(a,f(a)) | aA}.– Isto torna f uma relação entre A e B:– Para cada aA, 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.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

• Funções pode ser representadas graficamente:

• •

AB

a b

f

f

••••

•

•

••

• x

y

GráficoGrafo BipartidoDiagrama de Venn

A B

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

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.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

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.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

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

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

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}

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Notação

• Podemos escrever YX para denotar o conjunto F de todas as possíveis funções f: XY.

• Assim, f YX é outra maneira de dizer que f: XY.

• Notação apropriada – Para X e Y finitos

|F| = |Y||X|.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Detalhe

• Se usarmos F0, T1, então um subconjunto TS é 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} )

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Terminologia

• Se escrevemos f:AB, e f(a)=b (onde aA & bB), 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:AB é o

conjunto de todas as imagens de elementos de A.

– Dizemos que f:AB mapeia A em B.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Funções

• Considere a função f:PC 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.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Funções

• Let us re-specify f as follows:

• f(Linda) = Moscow

• f(Max) = Boston

• f(Kathy) = Hong Kong

• f(Peter) = Boston

• Is f still a function?

yesyes

{Moscow, Boston, Hong {Moscow, Boston, Hong Kong}Kong}

What is its range?What is its range?

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Funções

• Other ways to represent f:

•Boston•Peter

•Hong Kong

•Kathy

•Boston•Max

•Moscow•Linda

•f(x)•x LindaLinda

MaxMax

KathyKathy

PeterPeter

BostonBoston

New New YorkYorkHong Hong KongKong

MoscowMoscow

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Funções

• Se o domínio de f for grande, é conveniente especificar f com uma fórmula, e.g.:

• f:RR • f(x) = 2x

• Isto leva a:• f(1) = 2• f(3) = 6• f(-3) = -6• …

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

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

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Funções

• Seja f:AB.• Se tomarmos um subcon• If we only rejunto SA, o conjunto

de todas as imagens de elementos sS é denominado imagem de S.

• Denotada por f(S):• f(S) = {f(s) | sS}

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

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}

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Composição

• A composição de duas funções g:AB e f:BC, denotada por fg, é definida como

• (fg)(a) = f(g(a))• Isto significa que:

– a primeira função é aplicada ao elemento aA, – 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.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Composição

• Exemplo:

• f(x) = 7x – 4, g(x) = 3x,

• f:RR, g:RR

• (fg)(5) = f(g(5)) = f(15) = 105 – 4 = 101

• (fg)(x) = f(g(x)) = f(3x) = 21x - 4

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Composição

• Composição de função e sua inversa:

• (f-1f)(x) = f-1(f(x)) = x

• É a função identidade I(x) = x.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Propriedades das Funções

• Uma função f:AB é dita injetora sss x, yA (f(x) = f(y) x = y) x, yA(x,y: xy f(x)f(y)).

• F é injetora sss não mapeia dois elementos distintos de A no mesmo elemento de B.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva


• 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) = Moscowg(Linda) = Moscow

g(Max) = Bostong(Max) = Boston

g(Kathy) = Hong g(Kathy) = Hong KongKong

g(Peter) = New Yorkg(Peter) = New York

G é G é é injetora??

SimSim

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva


• Como provar que um função é injetora?• Olhe a definição primeiro: x, yA (f(x) = f(y) x = y)

• Exemplo:• f:RR• 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.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva


• … outro exemplo:• f:RR• f(x) = 3x• Injetora: x, yA (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.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva


• A função f:AB com A,B R é denominada estritamente crescente, se

x,yA (x < y f(x) < f(y)),

• E estritamente descrescente se x,yA (x < y f(x) > f(y)).

• Um função que é estritamente crescente ou estritamente descrescente é injetora.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva


• Uma função f:AB é denominada sobrejetora, sss para cada elemento bB existe um elemento aA com f(a) = b.

• Se o cojunto imagem for igual ao contra-domínio

• Uma função f: AB é bijetora sss é injetora e sobrejetora.

• Logo: se f é bijetora e A e B são conjuntos finitos, então |A| = |B|.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva


• F é injetora?

• Não.

• F é sobrejetora?

• Não.

• F é bijetora?

• Não.

LindaLinda

MaxMax

KathyKathy

PeterPeter

BostonBoston


MoscowMoscow

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva


• F é injetora?

• Não.


• Sim.

• F é bijetora?

• Não.

LindaLinda

MaxMax

KathyKathy

PeterPeter

BostonBoston


MoscowMoscow

PaulPaul

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva


• F é injetora?

• Sim.


• Não.

• F é bijetora?

• Não.

LindaLinda

MaxMax

KathyKathy

PeterPeter

BostonBoston


MoscowMoscow

LLüübeckbeck

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva


• F é injetora?

• Não.

• F não é função

LindaLinda

MaxMax

KathyKathy

PeterPeter

BostonBoston


MoscowMoscow

LLüübeckbeck

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva


• F é injetora?

• Sim


• Sim

• F é bijetora?

• Sim

LindaLinda

MaxMax

KathyKathy

PeterPeter

BostonBoston


MoscowMoscow

LLüübeckbeckHelenaHelena

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Inversa

• As funções bijetora possuem uma função inversa.

• f:AB tem como função inversa

• f-1:BA com f-1(b) = a tal que f(a) = b.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Inversa

Exemplo:Exemplo:

f(Linda) = Moscowf(Linda) = Moscow

f(Max) = Bostonf(Max) = Boston

f(Kathy) = Hong f(Kathy) = Hong KongKong

f(Peter) = Lf(Peter) = Lüübeckbeck

f(Helena) = New f(Helena) = New YorkYork

É um função É um função bijetorabijetora

A inversa é dada A inversa é dada por:por:

ff-1-1(Moscow) = Linda(Moscow) = Linda

ff-1-1(Boston) = Max(Boston) = Max

ff-1-1(Hong Kong) = (Hong Kong) = KathyKathy

ff-1-1(L(Lüübeck) = Peterbeck) = Peter

ff-1-1(New York) = (New York) = HelenaHelena

Inversão so é Inversão so é possível para possível para bijetorasbijetoras

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Inversa

• f-1:CP não é função

• Não está definida para todos os elementos de C

• Associa duas imagens a New York.

LindaLinda

MaxMax

KathyKathy

PeterPeter

BostonBoston


MoscowMoscow

LLüübeckbeckHelenaHelena

ff

ff-1-1

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Função teto e piso

• Mapeiam números reais em inteiros (RZ).

• Piso(floor) associa rR ao maior zZ com z r, denotado por r. 2.3 = 2, 2 = 2, 0.5 = 0, -3.5 = -4

• Teto (ceiling) associa rR ao menor zZ com z r, denotado por r.– 2.3 = 3, 2 = 2, 0.5 = 1, -3.5 = -3

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

SequênciasRosen 5th ed., §1.8

Estruturas Discretas e Lógica Matemática

Dep. de Informática – UFMA

Prof. Anselmo Paiva

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

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 …S: 2 4 6 8 10 …

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

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.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

As Fórmulas de Sequências

1, 3, 5, 7, 9, … aann = 2n - 1 = 2n - 1

-1, 1, -1, 1, -1, -1, 1, -1, 1, -1, ……

aann = (-1) = (-1)nn

2, 5, 10, 17, 26, 2, 5, 10, 17, 26, ……

aann = n = n22 + 1 + 1

0.25, 0.5, 0.75, 1, 1.25 0.25, 0.5, 0.75, 1, 1.25 ……

aann = 0.25n = 0.25n

3, 9, 27, 81, 243, …3, 9, 27, 81, 243, … aann = 3 = 3nn

Quais as fórmulas pras seguintes Quais as fórmulas pras seguintes sequências asequências a11, a, a22, a, a33, … ?, … ?

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

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

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Somatórios

•A variável j é denominada índice do somatório, indo do seu limite inferior m ao limite superior n.

n

mjja

O que isto significa?O que isto significa?

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Somatórios

• 1 + 2 + 3 + 4 + 5 + 6 = 21.

Escrevemos como Escrevemos como

1000

1

2

j

j

Qual o valor de ?Qual o valor de ?

6

1j

j

Muito trabalho pra calcular istoMuito trabalho pra calcular isto

Qual o valor de ?Qual o valor de ?

100

1j

j

Como expressar a soma dos primeiros mil Como expressar a soma dos primeiros mil termos de uma sequência {atermos de uma sequência {ann} com a} com ann=n=n22 para para n = 1, 2, 3, … ?n = 1, 2, 3, … ?

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Somatórios

•Gauss apresentou a seguinte fórmula:

n

j

nnj

1 2

)1(

Quando temos esta fórmula, podemos Quando temos esta fórmula, podemos calcular o valor de qualquer somatório:calcular o valor de qualquer somatório:

50502

10100

2

)1100(100100

1

j

j

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Séries Aritméticas

•Como:

n

j

nnj

1 2

)1(

Observe que:Observe que:

1 + 2 + 3 +…+ n/2 + (n/2 + 1) +…+ (n - 2) + (n - 1) + 1 + 2 + 3 +…+ n/2 + (n/2 + 1) +…+ (n - 2) + (n - 1) + nn

??????

= [1 + n] + [2 + (n - 1)] + [3 + (n - 2)] +…+ [n/2 + (n/2 + 1)]= [1 + n] + [2 + (n - 1)] + [3 + (n - 2)] +…+ [n/2 + (n/2 + 1)]

= (n + 1) + (n + 1) + (n + 1) + … + (n + 1) = (n + 1) + (n + 1) + (n + 1) + … + (n + 1) (com n/2 termos)(com n/2 termos)

= n(n + 1)/2.= n(n + 1)/2.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Séries Geométricas

•Como :

n

j

nj

a

aa

0

)1(

)1(

1

Observe que:Observe que:

S = 1 + a + aS = 1 + a + a22 + a + a33 + … + a + … + ann

??????

aS = a + aaS = a + a22 + a + a33 + … + a + … + ann + a + a(n+1)(n+1)

assim, (aS - S) = (a - 1)S = aassim, (aS - S) = (a - 1)S = a(n+1)(n+1) - 1 - 1

Entao, 1 + a + aEntao, 1 + a + a22 + … + a + … + ann = (a = (a(n+1)(n+1) - 1) / (a - - 1) / (a - 1).1).E.G.: 1 + 2 + 4 + 8 +… + 1024 = 2047.E.G.: 1 + 2 + 4 + 8 +… + 1024 = 2047.

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Séries Úteis

1.

2.

3.

4.

n

j

nj

a

aa

0

)1(

)1(

1

n

j

nnj

1 2

)1(

n

j

nnnj

1

2

6

)12)(1(

n

j

nnj

1

223

4

)1(

Dep

art

am

en

to d

e In

form

áti

ca –

E D

L

M

Prof. Anselmo Paiva

Somatórios Duplos

• Correspondendo a loops aninhados em linguagens de programação:

• Exemplo:

5

1

2

1i j

ij

5

1

)2(i

ii

5

1

3i

i

451512963

Documents

Funções Rosen 5 th ed., §1.8