Funciones
1a1
muchos a muchos
1 a muchos
Capítulo 4 Funciones
4.1 Funciones
Definición Dados los conjuntos no vacíos A, B, una
función, o transformación f de A a B, definida por f : A  B,
es una relación de A a B donde cada elemento de A aparece
exactamente una vez como primera componente de un par
ordenado de la relación.
Capítulo 4 Funciones
4.1 Funciones
Suele escribirse f(a) = b cuando (a, b) es un par ordenado de
la función f. Para (a, b)f, b se denomina imagen de a en f,
mientras que a es un antecedente de b. Además la definición
sugiere que f es un método para asociar a cada
a  A una única b  B; este proceso se denota mediante
f(a) = b. Por tanto, (a, b) , (a, c)  f implica que b = c.
Capítulo 4 Funciones
4.1 Funciones
EJEMPLO Para A = {1, 2, 3}, B = {w, x, y, z}, f = {(1, w),
(2, x), (3, x)} es una función y, por tanto una relación de A a
B. R1 = {(1, w), (1, x), (2, x)}, R2 = {(1, w), (2, w), (2, x),
(3, z)} son relaciones, pero no funciones, de A a B. (¿Por
qué no lo son?).
Capítulo 4 Funciones
4.1 Funciones
Definición Para la función f : A  B, A y B se denominan
dominio y codominio de f, respectivamente. El subconjunto
de B formado por aquellos elementos que aparecen como
segundas componentes en los pares ordenados de f, se llama
imagen de f y también se define por f(A).
Capítulo 4 Funciones
4.1 Funciones
Para A = {1, 2, 3}, B = {w, x, y, z}, f = {(1, w), (2, x), (3, x)}
1. el dominio de f ={1, 2, 3},
2. el codominio de f = {w, x, y, z},
3. y la imagen de f= f(A) ={w, x}.
Capítulo 4 Funciones
4.1 Funciones
Estas ideas se pueden representar mediante un diagrama de
Venn, como en la figura siguiente. Este diagrama muestra
que a puede considerarse como una entrada que es
transformada mediante f en la correspondiente salida f(a).
Capítulo 4 Funciones
4.1 Funciones
EJEMPLO En el lenguaje de programación BASIC, la
función del mayor entero, denotada por INT, es una función
definida para el dominio de todos los números reales, es
decir, INT: RZ, donde INT(X)=X, si X es un entero; si X
no lo es, INT(X)= al entero situado inmediatamente a la
izquierda de X. Por ejemplo, INT(5.1) = 5 e INT(-7.8) = -8.
Aquí el codominio y la imagen son el conjunto Z.
Capítulo 4 Funciones
4.1 Funciones
En Pascal se presenta la función trunc (por truncamiento),
que es una función con valores enteros definida en R. La
función elimina la parte fraccionaria de un número real. Por
ejemplo, trunc(3.78) = 3, trunc(5) = 5, trunc(-7.22) = -7.
Capítulo 4 Funciones
4.1 Funciones
Al almacenar una matriz en una disposición unidimensional
muchos lenguajes de programación lo hacen por filas. Aquí
si A = (aij)nn es una matriz de n  n, la primera fila de A se
almacena en las posiciones 1, 2, 3,..., n de la disposición si
se comienza con a11 en la posición 1. Entonces, el registro
a21 se halla en la posición n + 1, mientras que el a34 ocupa
la posición 2n + 4 de la disposición. Para determinar la
posición de cualquier registro aij, 1 i, j n, a partir de A, se
define la función de acceso f de los registros de A a las
posiciones 1,2,3, ..., n2 de la disposición. Aquí una fórmula
para la función de acceso es f(aij) = (i – 1)n + j.
Capítulo 4 Funciones
4.1 Funciones
Dada una relación de A a B. Ya se ha analizado una función
entre estas relaciones, y ahora se desea contar el número
total de funciones de A a B.
Capítulo 4 Funciones
4.1 Funciones
Para el caso general, sean A, B conjuntos con A = m, B = n.
En consecuencia, si A = {a1, a2, ..., am}, B = {b1, b2, ... ,bn},
una función típica f : A  B se puede describir por medio
de {(a1, x1), (a2, x2), ..., (am, xm)}. Se puede seleccionar
cualquier elemento entre los n de B para x1 y a continuación
hacer lo mismo para x2. (Se puede elegir cualquier elemento
de B para x2 de modo que se puede elegir un mismo
elemento de B para x1 y para x2). Este proceso de selección
continúa hasta que uno de los n elementos de B sea
finalmente seleccionado para xm. Así, por la regla del
A
producto, hay nm = B funciones de A a B.
Capítulo 4 Funciones
4.1 Funciones
43
B
A
Por tanto, si A = 3 y B = 4 entonces hay
=
= 64
B
funciones de A a B y 34 = A = 81 funciones de B a A.
Funciones Uno a Uno
Capítulo 4 Funciones
4.2 Funciones uno a uno
Definición Una función f : AB se llama uno a uno o
inyectiva si cada elemento de B aparece a lo sumo una vez
como la segunda componente de un par ordenado de f.
Si f : A  B es uno a uno, con A, B finitos, entonces A  B .
Para conjuntos generales A, B, si f: AB es uno a uno,
entonces para a1,a2 A, f(a1)=f(a2)  a1=a2. Entonces, una
función de este tipo se puede caracterizar como aquella
donde cada elemento de la imagen es imagen de
exactamente un elemento del dominio.
Capítulo 4 Funciones
4.2 Funciones uno a uno
EJEMPLO Sea A={1,2,3}, B={1,2,3,4,5}. La función
f={(1,1),(2,3),(3,4)} es una función inyectiva de A a B.
Mientras que g={(1,1),(2,3),(3,3)}es una función de A a B,
aunque no es inyectiva, pues g(2)=g(3), pero 23.
Para A, B del ejemplo hay 215 relaciones de A a B, y 53 de
ellas son funciones. Lógicamente, la siguiente cuestión que
se quiere resolver es ¿Cuántas funciones f : A  B son
uno a uno?.
Capítulo 4 Funciones
4.2 Funciones uno a uno
Con A={a1,a2,...,am}, B ={b1,b2,...,bn}, mn, una función
uno a uno f: AB tiene la forma {(a1,x1),(a2,x2),...,(am,xm)},
donde hay n selecciones posibles para x1 (cualquier
elemento de B), n–1 selecciones posibles para x2 (cualquier
elemento posible de B, excepto el seleccionado para x1), n–
2 selecciones posibles para x3, etc., y se concluye con n–
(m–1)= n–m+1 selecciones posibles para xm. Por la regla del
producto, el número de funciones uno a uno de A a B es
n(n–1)(n–2)...(n–m+1) = n! /  n  m  ! = P(n,m) = P( A , B )
Capítulo 4 Funciones
4.2 Funciones uno a uno
Definición Si f : A  B y A1  A, entonces
f(A1)=  b  B b  f  a  para algún a  A1 
EJEMPLO Sea f: R  R dada por f(x) = x2.
Entonces, f(R) = la imagen de f = [0, +]. La imagen de Z
en f es f(Z) = {0,1,4,9,16,...}.
Capítulo 4 Funciones
4.2 Funciones uno a uno
Teorema Sea f: A  B con A1, A2  A. Entonces,
a) f(A1  A2) = f(A1)  f(A2)
b) f(A1  A2)  f(A1)  f(A2)
c) f(A1  A2) = f(A1)  f(A2) cuando f es inyectiva.
Capítulo 4 Funciones
4.2 Funciones uno a uno
Demostración Se prueba el apartado b) y se deja el resto
como ejercicio.
Para cualquier bB,
b f(A1  A2)  b = f(a), para algún a  A1  A2 
(b = f(a), a  A1) y (b = f(a), a  A2) 
b  f(A1) y b  f(A2)  b  f(A1)  f(A2),
de modo que f(A1  A2)  f(A1)  f(A2).
Capítulo 4 Funciones
4.2 Funciones uno a uno
Definición Si f: A  B y A1  A, f A  a  : A1  B se
denomina restricción de f a A1 si f A  a  = f(a) para toda a
A1.
1
1
Definición Sea A1  A y f: A1  B. Si g: A  B y g(a) =
f(a) para toda a A1, g se denomina extensión de f a A.
EJEMPLO Sea A = {w, x, y, z}, B = {1, 2, 3, 4, 5}, A1={w,
y, z}. Sean f: AB, g: A1B. Entonces, g = f A y f es una
extensión de g de A1 a A. Obsérvese que para la función
dada g: A1  B hay cinco formas de extender g de A1 a A.
1
Funciones Suprayectivas:
Números de Stirling de 2do Tipo
Capítulo 4 Funciones
4.3 Funciones suprayectivas
Definición Si f: A  B, f se llama sobre o suprayectiva si
f(A)=B (es decir, si para toda b  B existe al menos un a A
tal que f(a) = b).
EJEMPLO La función f: R  R definida por f(x) = x3 es
una función suprayectiva pero g: R  R dada por x2 no lo
es, ya que g(R) =[0, +)  R.
Capítulo 4 Funciones
4.3 Funciones suprayectivas
EJEMPLO Con A = {1, 2, 3, 4}, B = {x, y, z}, f1 = {(1, z),
(2, y), (3, x), (4, y)} y f2={(1,x), (2, x), (3, y), (4, z)} son
funciones de A sobre B. La función g = {(1, x), (2,x), (3,y),
(4,y)} no es suprayectiva, pues g(A) = {x, y} B.
Capítulo 4 Funciones
4.3 Funciones suprayectivas
EJEMPLO Si A = {x, y, z} y B = {1, 2}, entonces todas las
funciones f: A  B son suprayectivas, excepto f1={(x, 1), (y,
1), (z, 1)} y f2={(x, 2), (y, 2), (z, 2)}, funciones constantes;
A
de modo que hay B –2 = 23–2 = 6 funciones suprayectivas
de A a B.
En general, si A = m  2 y B = 2, hay 2m – 2 funciones
suprayectivas de A a B.
EJEMPLO Para A = {w, x, y, z} y B = {1, 2, 3} hay 34
funciones de A a B. Si se consideran los subconjuntos de B
de tamaño 2, hay 24 funciones de A a {1, 2}, 24 de A a {2,
3
3}, y 24, de A a {1, 3}; así se obtienen 3(24) =  2  2 funciones
 
de A a B que no son suprayectivas. Sin embargo, antes de
3
4
aceptar 3 –  2  2 como respuesta, ha de tenerse en cuenta que
 
no todas las funciones son diferentes, pues, cuando se
tienen en cuenta todas las funciones de A a {1,2}, se
elimina entre otras, la función {(w,2), (x,2), (y,2), (z,2)}. Al
considerar las funciones de A a {2,3}, se suprime la misma
función: {(w,2), (x,2), (y,2), (z,2)}. Por tanto, en el resultado
se eliminaron dos veces las funciones constantes. Al adaptar
el resultado a esto, se halla que hay 34 –  3  2 4 + 3 =
4
4
 3 4  3  4  3 4
  3    2   1
 3
2
1
2
 
funciones suprayectivas de A a B.
Capítulo 4 Funciones
4.3 Funciones suprayectivas
Si se mantiene B = {1, 2, 3}, para cualquier conjunto A, con
. A = m  3, hay  3  3 m   3  2 m   3 1 m funciones suprayectivas
 3
2
1




 
de A a B.
Capítulo 4 Funciones
4.3 Funciones suprayectivas
Los ejemplos anteriores sugieren como fórmula general:
para conjuntos finitos A, B con A = m  n= B hay
n m  n 
 n 
m
m
n2  n  m
n 1  n  m
  n  
  n  1  
  n  2       1   2    1  1
n
 n  1
n  2
2
1
n 1
 n 
m
  n  k 
    1 
k 0
n  k
k
 n 
m
  n  k 
    1 
k 0
n  k
n
k
funciones suprayectivas de A a B.
Capítulo 4 Funciones
4.3 Funciones suprayectivas
EJEMPLO Sea A = {1, 2, 3, 4, 5, 6, 7} y B ={w, x, y, z}.
Si se aplica la fórmula general con m = 7, n = 4, hay
4 7
  4
4
4 7
   3
3
4 7
   2
2
4
4 7 3
k 4 
7
k 4 
7
 4  k     1 
 4  k   8400
  1    1 
k 0
k 0
1
4  k
4  k
funciones de A sobre B.
El resultado es también la respuesta al siguiente problema:
se desea distribuir, 7 objetos diferentes en 4 recipientes
distintos sin dejar ningún recipiente vacío. Esto puede
resolverse por funciones suprayectivas.
Capítulo 4 Funciones
4.3 Funciones suprayectivas
EJEMPLO En la compañía CH, Juana la directora, tiene
una secretaría, Teresa, y otras tres auxiliares. Si hay que
procesar 7 cuentas, ¿de cuantas formas las puede distribuir
Juana para que cada auxiliar trabaje al menos en una cuenta
y el trabajo de Teresa incluya, aunque sólo haga eso, la
cuenta más elevada?.
Capítulo 4 Funciones
4.3 Funciones suprayectivas
Si Teresa trabaja sólo en la cuenta más elevada, entonces las
otras seis cuentas se pueden distribuir entre las tres
auxiliares administrativas de  3  1 k  3  3  k  6 = 540


k 0
3  k 
formas. (540 = el número de funciones suprayectivas f: A
 B con A = 6, B = 3).
Si Teresa trabaja en otra cosa, además de en la cuenta más
elevada, las asignaciones se pueden hacer de
 4 
6
 k  0  1  4  k  4  k 


4
k
= 1560 formas (1560 = el número de
funciones suprayectivas g: C  D con C =6, D =4).
Por lo tanto, las asignaciones se pueden hacer de 540 +
1560 = 2100 formas en las condiciones anteriores.
Ahora se prosigue al análisis de la distribución de objetos
distintos en recipientes sin dejar ninguno vacío, pero en este
caso los recipientes son idénticos.
EJEMPLO Si A ={a, b, c, d}, B = {1, 2, 3} hay 36
funciones suprayectivas de A a B, o 36 formas de distribuir
4 objetos diferentes en tres recipientes distintos, sin dejar
ninguno vacío (y sin tener en cuenta la posición de los
objetos en un recipiente dado). Entre estas 36 distribuciones
se halla la siguiente colección de seis (una de las seis
posibles):
1) {a, b}1 {c}2 {d}3
2) {a, b}1 {d}2 {c}3
3) {c}1 {a, b}2 {d}3
4) {c}1 {d}2 {a, b}3
5) {d}1 {a, b}2 {c}3
6) {d}1 {c}2 {a, b}3,
Nota: {c}2 significa que c está en el segundo recipiente.
Ahora, si no hay diferencia entre los recipientes, estas 6 =
3! distribuciones se hacen idénticas, de modo que hay
36/(3!) = 6 formas de distribuir los distintos objetos a, b, c,
d en tres recipientes idénticos sin dejar ninguno vacío.
 n 
m







1
n

k
n  k
hay  k  0


n
k
En general, para m  n
formas de
distribuir m objetos distintos entre n recipientes numerados
(y por lo tanto, no idénticos) sin dejar ninguno vacío. Al
suprimir los números de los recipientes para que sean
idénticos, se halla que hay una distribución de estos n (no
vacíos) recipientes idénticos que se corresponde con n! de
tales distribuciones de los recipientes numerados. Así, el
número de formas para distribuir los m objetos distintos en
n recipientes idénticos, sin dejar ninguno vacío, es
 n 
m







1
n

k

n  k
n! k  0


1
n
k
Capítulo 4 Funciones
4.3 Funciones suprayectivas
1
n!


m
  n  k 
n  k
k




1
 k 0
n
n
Esto se denota por S(m, n), y se denomina número de
Stirling de segundo tipo.
Se observa que para A = m  n = B , hay n!  S(m, n)
funciones suprayectivas de A a B.
Capítulo 4 Funciones
4.3 Funciones suprayectivas
En la siguiente tabla se relacionan algunos números de
Stirling de segundo tipo.
Capítulo 4 Funciones
4.3 Funciones suprayectivas
EJEMPLO Para m  n,  i 1 S  m , i  es el número de formas
de distribuir m objetos distintos en n recipientes idénticos,
admitiendo la posibilidad de recipientes vacíos. En la cuarta
fila de la tabla anterior se observa que hay 1 +7 + 6 = 14
formas de distribuir los objetos a, b, c, d en tres recipientes
idénticos con la posibilidad de recipientes vacíos.
n
Capítulo 4 Funciones
4.3 Funciones suprayectivas
Teorema Sea n un número positivo con 1  n  m.
entonces,
S(m + 1, n) = S(m, n – 1) + nS(m, n).
Capítulo 4 Funciones
4.3 Funciones suprayectivas
A = {a 1 , a 2 ,  , a m , a m  1 }
S(m+1,n)

n recipientes idénticos
am+1 está sola
en un recipiente
S(m,n-1)
am+1 no está sola en un recipiente
1.-Distribuir n objetos en n recipientes.
2.- am+1 puede colocarse en uno de estos
nS(m,n)
Capítulo 4 Funciones
4.3 Funciones suprayectivas
Demostración Sea A = {a1, a2, ... , am, am+1}. Entonces,
S(m + 1, n) cuenta el numero de formas en que los objetos
de A pueden distribuirse en n recipientes idénticos, sin dejar
ningún vacío.
Demostración ...(continuación)
Hay S(m, n – 1) formas de distribuir a1, a2, ... , am, en n – 1
recipientes idénticos sin dejar ninguno vacío. Así al colocar
am+1 en el recipiente vacío restante se obtienen S(m, n – 1)
distribuciones contadas de S(m + 1, n), es decir, aquellas
distribuciones donde am+1 está sola en un recipiente. Otra
opción es distribuir a1, a2, ... , am, en los n recipientes
idénticos sin que ninguno quede vacío, se obtienen S(m, n)
distribuciones. Sin embargo, para cada una de estas S(m, n)
distribuciones, los n recipientes se pueden distinguir ahora
por su contenido. Al seleccionar uno de los n recipientes
distintos para am+1 se tienen nS(m, n) distribuciones del total
de S(m + 1, n) , esto es, aquellas donde am+1 está en el
mismo recipiente que otro objeto de A. El resultado se
obtiene mediante la regla de la suma.
Descargar

Producto cruz Relaciones y Funciones