ClasesMatematicasDiscretas2

Vista previa del material en texto

Funciones
Matemáticas Discretas
Funciones
Dr. José Antonio Camarena Ibarrola 1
Facultad de Ing. Eléctrica, Universidad Michoacana, México.
Febrero, 2020
Funciones
Outline
Funciones
Funciones
Definción de una función
• Sean dos conjuntos no vaćıos A y B. Una función f : A→ B es un mapeo
que asigna a cada elemento de A en un y solo un elemento de B
• Ejemplo Cada estudiante obtiene una calificación al realizar un exámen
[Ros11]
• Al conjunto A le llamamos dominio
• Al conjunto B le llamamos Codominio
Funciones
• Una función f es una regla de correspondencia que nos dice a cual
elemento de dominio A le corresponde cual elemento del codominio B
• Si al elemento a ∈ A le corresponde el elemento b ∈ B, entonces
escribimos:
f (a) = b
[Ros11]
• Decimos que b es la imagen de a
• Al conjunto de todas las imágenes de elementos de A le llamamos rango
• En los lenguajes de programación especificamos el dominio y el codominio
al definir una función, por Ej:
int floor(float x) ...
Funciones
Operaciones con funciones
• Si f1 y f2 son funciones que aplican A en B, entonces f1 + f2 y f1f2 también
son funciones de A en B
• Ejemplo. Sea f1(x) = x2 y f2(x) = 3x , entonces
(f1 + f2)(x) = f1(x) + f2(x) = x
2 + 3x
• Para esas mismas funciones (f1f2)(x) = f1(x)f2(x) = (x2)(3x) = 3x3
Funciones
Imagen de un subconjunto del dominio de una función
• Sea f una función que aplica al conjunto A en el conjunto B y sea S un
subconjunto de A
• Entonces f (S) representa la imagen de S y es el conjunto de elementos
de B que son imagen de algún elemento de S
f (S) = {t | ∃s ∈ S(t = f (s)}
• Por ejemplo, sea A = {a, b, c, d , e} y B = {1, 2, 3, 4} y sea f(a)=2,
f(b)=1, f(c)=4,f(d)=1 y f(e)=1, entonces si S = {b, c, d}, entonces
f (S) = {1, 4}
Funciones
Funciones Inyectivas
• Una función es inyectiva si cada elemento del rango es imagen de un y
solo un elemento del dominio
[Ros11]
• También se les conoce como funciones uno a uno
• Ejemplo: La función f : Z→ Z defeinida como f (x) = x + 1 es una
función inyectiva
• Ejemplo: La función f : Z→ Z definida como f (x) = x2 no es una función
inyectiva puesto que f (1) = f (−1) = 1
Funciones
Funciones Sobreyectivas
• Una función es sobreyectiva si cada elemento del rango es imagen de al
menos un elemento del dominio
[Ros11]
• Ejemplo: La función f : Z→ Z definida como f (x) = x + 1 es sobreyectiva
• Ejemplo: La función f : Z→ Z definida como f (x) = x2 no es sobreyectiva
ya que ningún entero al elevarse al cuadrado resulta -1
Funciones
Tipos de funciones
[Ros11]
Una cuando una función es tanto inyectiva como sobreyectiva, decimos que es
una función biyectiva, también se conocen como uńıvocas
Funciones
Mas operaciones con funciones
• Si f es una función biyectiva, entonces existe la inversa de f , denotada
f −1 y f −1(b) = a siempre que f (a) = b
[Ros11]
Dado que f (x) = x + 1 es biyectiva, tiene inversa, supongamos que la
imagen de x es y , entonces y = x + 1, de donde x = y − 1 y esta debe ser
la imagen de f −1, por lo tanto f −1(y) = y − 1
Funciones
Mas operaciones con funciones
• Sea la función g : A→ B y f : B → C , se define la composición de
funciones f ◦ g : A→ C como (f ◦ g)(x) = f (g(x))
[Ros11]
• Ejemplo: Sea f (x) = x2 y g(x) = x + 2, entonces
(f ◦ g)(x) = f (g(x)) = f (x + 2) = (x + 2)2 = x2 + 4x + 4
• Observe que la composición de funciones no es una operación conmutativa
• Ejemplo: (g ◦ f )(x) = g(f (x)) = g(x2) = x2 + 2
Funciones
Gráfica de una función
• La gráfica de una función es el conjunto de parejas ordenadas
{(a, b) | a ∈ A ∧ f (a) = b}
• Ejemplo la función f : Z→ Z definida como f (x) = x2 tiene la gráfica:
[Ros11]
Funciones
Funciones Piso y Techo
• La función piso denotada como f (x) = bxc y la función techo denotada
como f (x) = dxe
[Ros11]
• Ejemplo: El número de bytes necesarios para almacenar 100 bits es:
d100/8e = d12,5e = 13
• Cuantos paquetes de 53 bytes se pueden transmitir en un minuto si la
velocidad de transmisión es de 500 kbps?
Solución: En un paquete de 53 bytes hay 53× 8 = 424 bits, en un minuto
se pueden transmitir 500, 000× 60 = 30, 000, 000 bits, entonces el número
de paquetes que se pueden transmitir en un minuto es
b30, 000, 000/424c = 70, 754 paquetes
Funciones
Propiedades de las funciones piso y techo
• En la siguiente tabla x es un número real y n es un número entero
[Ros11]
Funciones
Propiedades de las funciones piso y techo
• Existen otras propiedades de las funciones piso y techo además de las
incluidas en la tabla anterior
• Por ejemplo b2xc = bxc+ bx + 1/2c
• Demostración por casos: Sea x = n + �
• Caso 1) 0 ≤ � < 1/2
2x = 2n + 2�, entonces b2xc = 2n porque 0 ≤ 2� < 1
Por otra parte bxc+ bx + 1/2c = bn + �c+ bn + �+ 1/2c = n + n = 2n
• Caso 2) 1/2 ≤ � < 1
2x = 2n + 2� = 2n + 2�+ 1− 1 = (2n + 1) + (2�− 1), entonces
b2xc = 2n + 1 porque 0 ≤ 2�− 1 < 1
Por otra parte
bxc+ bx + 1/2c = bn + �c+ bn + �+ 1/2c = n + n + 1 = 2n + 1
Funciones
Funciones Parciales
• Una función parcial no está definida para los elementos del dominio que no
pertenecen al dominio de definición de la función, cuando el dominio de
definición es igual al dominio, decimos que es una función total.
• Ejemplo: La función f : Z→ R donde f (n) =
√
n es una función parcial
que no está definida para los enteros negativos, por lo que el dominio de
definición de esta función es el conjunto de enteros no negativos.
Funciones
Secuencias
• Una secuencia es una función de un subconjunto de los enteros
({0, 1, 2, 3, ...} o {0, 1, 2, 3, ...}) a otro conjunto
• La imagen del entero n la denotamos an (en lugar de f(n))
• an es un término de la secuencia y denotamos a la secuencia completa
mediante {an}
• Ejemplo: la secuencia {an} donde an = 1/n es 1,1/2,1/3,1/4,...
• Una secuencia del tipo: a, ar , ar 2, ar 3, ..., donde a y r son números reales
es una progresión geométrica
• Una secuencia del tipo a, a + d , a + 2d , a + 3d , ..., donde a y d son
números reales es una progresión artimética
Funciones
Recurrencias
• una recurrencia es una ecuación que expresa an en función de términos
anteriores de la secuencia
• La secuencia de Fibonacci está definida como f0 = 0, f1 = 1 y
fn = fn−1 + fn−2 para n ≥ 2
• La secuencia es 0,1,1,2,3,5,8,...
• Decimos que hemos resuelto una recurrencia si hemos encontrado una
fórmula cerrada para el n-ésimo término de la secuencia
• Ejemplo: sea la recurrencia a1 = 2, an = an−1 + 3, entonces:
a2 = 2 + 3
a3 = 2 + 3 + 3 = 2 + 2× 3
a4 = 2 + 3 + 3 + 3 = 2 + 3× 3
:
an = an−1 + 3 = 2 + (n − 1)× 3
• Está técnica se conoce como iteración, en particular se hicieron
sustituciones hacia adelante, alternativamente se pudo haber resuelto
mediante sustituciones hacia atrás
an = an−1 + 3 = an−2 + 3 + 3 = an−2 + 2× 3 = ... =
an−(n−1) + (n − 1)× 3 = a1 + (n − 1)× 3 = 2 + (n − 1)× 3
Funciones
Cardinalidad de conjuntos infinitos
• Para conjuntos infinitos la cardinalidad es una medida relativa del tamaño
del conjunto en comparación con otro
• Decimos que un conjunto es infinito contable o infinito numerable si tiene
la misma cardinalidad que la del conjunto de enteros positivos
• Dos conjuntos tienen la misma cardinalidad si existe una correspondencia
uno a uno (una función biyectiva) entre esos dos conjuntos
• Ejemplo: La figura muestra una correspondencia uno a uno entre Z+ y el
conjunto de enteros positivos impares, lo cual demuestra que es un infinito
contable
[Ros11]
• Se demostró que ese conjunto es infinito contable encontrando la función
biyectivaf (n) = 2n − 1
Funciones
Conjuntos contables o numerables
• Que un conjunto sea infinito contable significa que sus elementos se
pueden listar
• Para demostrar que Z es infinito contable considere que estos se pueden
listar de la siguiente manera:
0, 1,−1, 2,−2, 3,−3, ...
• Alternativamente podemos encontrar una función biyectiva f : Z+ → Z
f (n) =
{
n
2
∀n par
− n−1
2
∀n impar
FuncionesEl conjunto de los racionales positivos es infinito contable
• Podemos listar a los elementos de Q+
• cada número racional se puede expresar como la razón de dos enteros
• Ponemos en el primer renglón a aquellos con denominador 1, en el
segundo renglón a los de denominador 2, etc
• Se listan en la secuencia de la figura (los que no están encerrados en
ćırculo no porque se repetiŕıan)
[Ros11]
Funciones
El conjunto de los números reales no es contable
• Argumento de Diagonalización de Georg Cantor en 1879.
• Es una demostración por contradicción (asumimos que śı en infinito
contable y luego buscamos una contradicción)
• Si R es infinito contable, entonces también lo es el subconjunto que está
entre 0 y 1 y entonces se pueden listar los números reales entre 0 y 1 en
algún orden r1,r2,r3,...
r1 = 0.d11d12d13d14...
r2 = 0.d21d22d23d24...
r3 = 0.d31d32d33d34...
r4 = 0.d41d42d43d44...
• ahora considere el número r = 0.d1d2d3d4... Formado de manera que
di = 4 si dii 6= 4 y di = 5 si dii = 4
• Este número está constrúıdo de modo que no puede estar en la lista pues
tiene al menos un d́ıgito diferente respecto a cada número de la lista
• Lo cual contradice el que todos los reales entre 0 y 1 están en la lista
Funciones
Dudas
antonio.camarena@umich.mx
Funciones
Bibliograf́ıa
K. Rosen.
Discrete Mathematics and Its Applications.
McGraw-Hill Education, 2011.
	Funciones