Sistemas de Informação
Lógica e Matemática Discreta
Funções
Definição: Sejam S e T conjuntos. Uma função (aplicação) f de S em T, f : S → T , é um subconjunto de S×T tal que
cada elemento de S aparece exatamente uma vez como a primeira componente de um par ordenado.
•
•
•
S é o domínio da função e T é o contradomínio. Obs.: pode-se ter funções com mesmo domínio e
contradomínio - f : S → S , que será um subconjunto de S×S.
Os pares ordenados são (x, f(x)), onde x ∈ S e f(x) ∈ T.
f(x) é a imagem de x e x é a imagem inversa de x.
S
T
x•
f
• f(x)
Uma função é um caso particular de relação binária, pois uma função é um subconjunto com algumas restrições sobre
os pares ordenados. Por exemplo, uma relação do tipo um para muitos ou muitos para muitos não pode ser uma função.
A definição de função inclui funções de mais de uma variável. Veja o exemplo: Seja f : Z × N × {1,2} → Z dada por
3
f ( x, y , z ) = x y + z . Então, f ( −4,3,1) = ( −4) + 1 = −64 + 1 = −63 .
Uma definição completa de uma função necessita que se dê o domínio, o contradomínio e a associação de valores, onde
a associação de valores pode ser dada por uma descrição verbal, um gráfico, uma equação ou um conjunto de pares
ordenados.
Funções iguais : duas funções são iguais se elas têm o mesmo domínio, o mesmo contradomínio e a mesma associação
de valores do contradomínio a valores do domínio, isto é, os pares ordenados das duas funções devem ser os mesmos.
Exemplo: Sejam S = {1,2,3} e T={1,4,9}. A função f : S → T é definida por f = {(1,1), (2,4), (3,9)}. A função
x
g : S → T é definida por g ( x ) =
∑ (4k − 2)
k =1
. Verifique se f = g.
2
Abaixo temos a definição de duas funções úteis para analisar algoritmos.
1. a função piso x associa a cada número real x o menor inteiro maior ou igual a x;
2.
a função teto
x
associa a cada número real x o maior inteiro menor ou igual a x;
A função módulo denotada por f ( x) = x mod n , associa a cada x o resto da divisão de x por n. podemos escrever
x = qn + r , 0 ≤ r < n , onde q é o quociente e r é o resto da divisão. Ex.: 25 = 12×2+1, logo, 25 mod 2 = 1 .
Propriedades das funções
•
Função sobrejetora: uma função é sobrejetora (ou sobrejetiva) se sua imagem é igual ao seu contadomínio. Isto
é cada elemento no contradomínio será relacionado com algum elemento no domínio. Para provar que uma
função não é sobrejetora deve-se mostrar que algum elemento no contradomínio não é imagem de nenhum
elemento do domínio. Ex.: a função g : R → R definida por g ( x) = x 3 é sobrejetora. Para provar isso, seja r
um número real arbitrário e seja x = 3 r . Então x é um número real, de modo que x pertence ao domínio de g e
g ( x) = (3 r )3 = r . Logo, qualquer elemento do contradomínio é a imagem, sob g, de um elemento do domínio.
•
Função injetora: uma função é injetora (ou injetiva) se nenhum elemento do contradomínio é imagem de dois
elementos distintos no domínio (um para um). Isto é, cada elemento no domínio será relacionado a um único
elemento no contradomínio. Para provar que uma função não é injetora deve-se mostrar que dois elementos no
domínio se relacionam com o mesmo elemento no contradomínio. Ex.: a função g : R → R definida por
1
Sistemas de Informação
Lógica e Matemática Discreta
g ( x) = x 3 é injetora, pois, se x e y são números reais com g(x) = g(y), então x3 = y3 e x = y. A função
g : R → R definida por g ( x) = x2 não é injetora, pois f(-2) = f(2) = 4. Mas, a função f : N → N definida
por f ( x) = x 2 é injetora porque f(x)=f(y), então x 2 = y 2 e, como x e y são ambos não-negativos, x = y.
•
Função bijetora (bijetiva ou bijeção): é a função que é ao mesmo tempo sobrejetora e injetora. Ex.: a função
g : R → R definida por g ( x) = x 3 é uma bijeção.
Composição de funções
f : S → T e g : T → U . A função composta g o f é a função de S em U definida por
( g o f )( x) = g ( f ( x)) , sendo que x ∈ S e g(f(x)) ∈ U.
Definição: sejam
go f
S
x
T
•
U
•
•
x
T
•
g(f(x))
f(x)
Ex.: sejam
S
f : R → R e g : N → N , definidas por
U
•
•
f(x)
g(f(x))
f ( x ) = x2 + 1 e g ( x) = x 3 . A função composta g o f é:
g o f ( x) = ( x 2 + 1)3 , se x = -3, g o f ( −3) = ((−3) 2 + 1) 3 = 1000 . No entanto, a função composta f o g será:
f o g ( x ) = ( x 3) 2 + 1 = x 6 + 1 , se x = -3, f o g( −3) = ((−3)6 + 1 = 729 + 1 = 730 .
Função inversa
Seja f : S → T uma bijeção. Podemos obter uma função g de forma que g : T → S , isto é, em f, S é o domínio e T é o
contradomínio e, em g, T é o domínio e S é o contradomínio.
f
S
x
• f(x)
•
T
g
Função inversa de f é denotada por f −1 . Exemplo: dado f : S → T , definida por f(x) = 2x e S = {0, 1,2,3} e T = {0, 2,
4, 6}, a função inversa f −1 : T → S será y = 2x, isolando x temos: x =
S
f
0•
1•
2•
3•
•0
•2
•4
•6
T
T
y
x
, portanto, f −1( x ) = .
2
2
0•
2•
4•
6•
f −1
S
•0
•1
•2
•3
2
Sistemas de Informação
Lógica e Matemática Discreta
Exercícios
1) Quais das relações abaixo são funções do domínio no contradomínio indicado? Para as que não são, por que não?
a) f : S → T , onde S = T = {1,2,3}, f = {(1,1), (2,3), (3,1), (2,1)}
b) g : Z → N , onde g é definida por g(x) = |x| (módulo de x)
c) h : N → N , onde h é definida por h(x) = x – 4
d) f : S → T , onde S é o conjunto de todas as pessoas residentes em Ituiutaba, T é o conjunto de todos os números
de CPF e f associa a cada pessoa seu CPF
e) f : R → R , onde f é definida por f(x) = 4x -1
f) h : Z × N → Q , onde h é definida por h( x, y) =
x
( y + 1)
g) f : R 2 → R 2 , onde f é definida por f ( x, y ) = ( y + 1, x + 1)
h) g : Z 2 → N , onde g é definida por g ( x, y ) = x 2 + 2 y 2
2) Se f : Z → Z é definida por f(x) = 3x, encontre f(A) para:
a) A = {1,3,5}
b) A = {x | x ∈ Z e (∃y)(y ∈ Z e x = 2y)}
3) Sejam S = {0, 2, 4, 6} e T = {1, 3, 5, 7}. Determine se cada um dos conjuntos de pares ordenados a seguir é uma
função com domínio S e contradomínio T. Se esse for o caso, a função é injetora? É sobrejetora?
a) {(0,2), (2,4), (4,6), (6,0)}
b) {(6,3), (2,1), (0,3), (4,5)}
c) {(2,3), (4,7), (0,1), (6,5)}
d) {(2,1), (4,5), (6,3)}
e) {(6,1), (0,3), (4,1), (0,7), (2,5)}
Se houver alguma bijeção, encontre sua função inversa.
4) Defina f : R → R por f ( x) = x n , onde n é um inteiro positivo fixo. Para que valores de n a função f é bijetora?
5) Seja f : R → R dada por f(x) = 3x + 4. Descreva f −1 .
6) Calcule:
a) 31 mod 11
b) 16 mod 8
c) 22 mod 6
d) -7 mod 3
7) Defina f : N → N por f ( x) = x + 1 . Seja g : N → N dada por g ( x ) = 3x2 . Calcule:
a) ( g o f )(5)
b) ( f o g )( 5)
c) ( g o f )( x)
d) ( f o g)( x)
e) ( f o f )( x)
f) ( g o g )( x )
8) Para cada uma das funções f : R → R abaixo, encontre sua inversa, se possível:
a) f ( x) =
( x + 4)
3
b) f ( x) = x3
c) f ( x) = x 2
9) Quais das funções do exercício 1 são injetoras, sobrejetoras ou bijetoras? Descreva a função inversa das funções
bijetoras.
3