Relaciones-y-funciones

Vista previa del material en texto

1
Coordinación de Ciencias Computacionales - INAOE
Matemáticas Discretas
Relaciones y funciones
Cursos Propedéuticos 2010
Ciencias Computacionales
INAOE
Dr. Luis Villaseñor Pineda
villasen@inaoep.mx
http://ccc.inaoep.mx/~villasen
2
Relaciones y funciones
 Relaciones
 Propiedades de relaciones
 Clases de equivalencia
 Conjuntos parciales y totalmente ordenados
 Funciones
3
Producto cartesiano
 Dados dos conjuntos A y B, el producto cartesiano
AxB se define por:
 AB = { (x, y) | xA, yB}
 Ejemplo:
 {a,b}{1,2,3} = {(a,1),(b,1),(a,2),(b,2),(a,3),(b,3)}
 Note que los elementos (x, y) son pares ordenados: 
hay una diferencia entre (a, 2) y (2, a)
 En general: AB ≠ BA
4
Relaciones
 Dados dos conjuntos A y B, una relación binaria R
de A a B es determinada por un subconjunto R 
AB
 Se dice que “aRb” si y solo si (a, b)R
 Si A=B, se dice que R es una relación en A
http://ccc.inaoep.mx/~villasen
2
5
Ejemplo
 Sea U={1, 2, 3, …,7}, A={2, 3, 4} y B={4, 5}, las 
siguientes son ejemplos de relaciones de A a B:
 Ø
 {(2, 4), (2, 5)}
 {(2, 4), (3, 4), (4, 5)}
 {(2, 4), (3, 4), (4, 4)}
6
Ejemplo
 La relación de menor que < en el conjunto de 
números naturales N se describe por el conjunto:
 {(0,1),(0,2),(1,2),(0,3),…}  NN
 La relación de igualdad “=“ en R se define por el 
conjunto:
 {(x, x) | xR}  RR
7
Propiedades de las relaciones
 Una relación R en A es reflexiva si:
 Si (a, a)  R para toda a  A
 Una relación R en A es antireflexiva si:
 Si (a, a)  R para toda a  A
8
Ejemplo
 Se A={1, 2, 3, 4}, considere las siguientes relaciones 
R sobre A y determine si son reflexivas:
 R={(1, 1), (2, 2), (3, 3)}
 No es reflexiva
 R={(x, y)| x, y  A, x ≤ y}
 Es reflexiva
3
9
Propiedades de las relaciones
 Una relación R es simétrica si:
 Si (a,b)R entonces (b,a)R
 Una relación R en A es antisimétrica si:
 Si (a,b)R y (b,a)R entonces a=b
 Una relación R es transitiva si:
 Si (a,b)R y (b,c)R entonces (a,c)R
10
Ejemplo
 Sea A={1, 2, 3} y R una relación en A
 R={(1,2),(2,1),(1,3),(3,1)}
 Simétrica y no reflexiva
 R={(1,1),(2,2),(3,3),(2,3)}
 Reflexiva y no simétrica
 R={(1,1),(2,2),(3,3),(2,3),(3,2)}
 Simétrica y reflexiva
 R={(1,1),(2,3),(3,3)}
 No Simétrica y no reflexiva
11
Ejemplo
 Sea A={1, 2, 3, 4}
 R={(1,1),(2,3),(3,4),(2,4)}
 Es una relación transitiva en A
 R={(1,3),(3,2)}
 No es transitiva
12
Ejemplo
 Sea A={1, 2, 3}
 R={(1,2),(2,1),(2,3)}
 No simétrica y no antisimetrica
 R={(1,1),(2,2)}
 Simétrica y antisimetrica
4
13
Ordenamientos
 Relaciones comunes tales como ≤ definen 
ordenamientos
 Una relación R en A es un ordenamiento parcial si y 
sólo si es una relación reflexiva, antisimétrica y 
transitiva
 (A, R) es un conjunto ordenado parcialmente o 
poset si R es un ordenamiento parcial en A
14
Ordenamientos
 Si a  b ó b  a, entonces los elementos a y b son 
comparables
 Si todos los pares a y b posibles son comparables, 
es un ordenamiento total o cadena
15
Ejemplo
 Sea A={1, 2, 3, 4, 6, 12} y sea R la relación en A 
dada por (x, y)  R si x divide exactamente a y
 R es reflexiva
 R es transitiva
 R es antisimétrica
 Por lo tanto R define un ordenamiento parcial en A
16
Relaciones de equivalencia
 Una relación R en A es una relación de equivalencia
si y sólo si es reflexiva, simétrica y transitiva
 La notación común para una equivalencia en A es “=“
 Dada una relación de equivalencia R en A, para cada 
aA la clase de equivalencia [a] se define por { x | 
(x,a)R }.
5
17
Ejemplo
 Equivalencias modulo 3 en Z tal que:
 [0] = {…,–6,–3,0,3,6,…} y [1] = {…,–5,–2,1,4,7,…}
 Sea A={1, 2, 3}
 R={(1,1),(2,2),(2,3),(3,2),(3,3)}
 R={(1,1),(2,2),(3,3)}
 R={(1,1),(1,3),(2,2),(3,1),(3,3)}
 Son relaciones de equivalencia
18
Particiones
 Una partición de un conjunto A es un conjunto de 
subconjuntos {Aj} tal que:
 AiAj =  para todo ij
 A = j Aj
19
Ejemplo
 Sea A={1, 2, 3, …,10}, las siguientes son ejemplos 
de particiones de A:
 A={1, 2, 3, 4, 5}, B={6, 7, 8, 9, 10} 
 A={1, 3, 5, 7, 9}, B={2, 4, 6, 8, 10}
 A={1, 2, 3}, B={4, 6, 7, 9}, A={5, 8, 10}
 Ai={i, i+5}, 1 ≤ i ≤ 5
20
Composiciones
 La composición T = SR  AC de dos relaciones 
SAB y RBC se define como 
T = { (a,c) | tal que existe bB con (a,b)S y (b,c)R }
 La composición de relaciones es asociativa
 Para relaciones R en A se pueden definir potencias:
R1 = R y Rn+1 = RRn para todo entero n
6
21
Matrices y relaciones
 Una relación R de A = {a1,…,am} a B = {b1,…,bn} 
puede representarse por una matriz M(R) de 
dimensión mn de 0/1 :
 Si aiRbj  R entonces el elemento (i, j) en M(R) es 1,
 Si aiRbj  R entonces el elemento (i, j) en M(R) es 0.
22
Matrices y relaciones
 Si se utiliza la “adición booleana” 1+1=1, entonces la 
composición de dos relaciones se puede calcular 
mediante la matriz producto:
 M(RS) = M(R)∙M(S)
Un repaso de lo visto hasta ahora
23 24
EJEMPLO Sea U = {1, 2, 3, ... , 7}, A = {2, 3, 4},
B = {4, 5}. Entonces,
a) A  B = {(2, 4), (2, 5), (3, 4),(3, 5),(4, 4), (4, 5)}.
b) B  A = {(4, 2), (4, 3), (4, 4), (5, 2), (5, 3), (5, 4)}.
c) B2=B  B = {(4, 4), (4, 5), (5, 4), (5, 5)}
d) B3=B  B  B = ; (4, 5, 5)B3.  Bcbacba ,,,,
Producto Cartesiano 
7
25
EJEMPLO Si U =R, R  R = se conoce como el plano
real de la geometría coordenada y del cálculo
bidimensional. El subconjunto R+R+ es el interior del
primer cuadrante de este plano. Así mismo, R3 representa
el espacio euclidiano tridimensional donde las superficies
tridimensionales, como esferas y planos, son
subconjuntos importantes.
Producto Cartesiano 
26
EJEMPLO Un experimento E se desarrolla de la
siguiente forma: se lanza un sólo dado y se anota el
resultado; a continuación, se lanza una moneda al aire y
se anota el resultado. Determínese un espacio muestral
M para E.
Denótese por E1 la primera parte del experimento E y
sea M1 = {1, 2, 3, 4, 5, 6} un espacio muestral para E1.
Así mismo sea M2={CA,CZ} un espacio muestral para
E2, la segunda parte del experimento. Entonces, M = M1
M2 es un espacio muestral para E.
Producto Cartesiano 
27
Este espacio muestral se puede representar gráficamente
con un diagrama de árbol.
Producto Cartesiano 
28
EJEMPLO En el torneo de tenis de Wimbledon, las mujeres
juegan a lo sumo 3 sets en un partido. Triunfa quien gane
primero 2 sets. Si N y E representan a las 2 jugadoras, el
diagrama de árbol refleja las 6 maneras en que puede
ganarse el encuentro.
Producto Cartesiano 
8
29
EJEMPLO Sea U = {1, 2, 3, ... , 7}, A = {2, 3, 4},
B = {4, 5}. Las siguientes son relaciones de A a B.
a)  b) {(2,4)} c) {(2, 4), (2, 5)}
d) {(2, 4), (3, 4), (4, 4)} e) {(2, 4), (3, 4), (4, 5)}
f) A  B.
¿cuántas relaciones de A a B existen?
Relaciones
30
En general, para conjuntos finitos A, B donde = m y
= n, hay 2mn relaciones de A a B, incluyendo la
relación vacía y la propia relación A  B.
A
B
Relaciones
Como = 6, por la definición se deduce que hay 26
relaciones posibles de A a B.
BA 
31
EJEMPLO Sea B = {1, 2}  N, U = P(B) y A = U ={,
{1}, {2}, {1, 2}}. El siguiente es un ejemplo de relación
binaria en A: R = {(, ), (, {1}), (, {2}), (, {1,
2}), ({1}, {1}), ({1},{1,2}), ({2}, {2}), ({2}, {1,2}),
({1,2}, {1,2})}. Se puede decir que la relación R es una
relación de subconjunto donde (C, D) R si y sólo si
C, D  B y C  D.
Relaciones
32
EJEMPLO Si A = U =Z+, se define una relación binaria
R en el conjunto A como . Se trata de la
conocida relación “es menor o igual que” para el
conjunto de los enteros positivos,
  yxyx ,
Se observa que (7,7),(7,11)R,
y (8,2)R, (7,11)R también
se puede denotar como 7R 11;
(8,2)R se transforma en 8R
2 son ejemplos de notación
infija en una relación.
Relaciones
9
33
Para cualquier conjunto A  U , A   = . Así mismo
  A = .
Relaciones
34
Para cualquier conjuntoA  U , A   = . Así mismo
  A = .
Relaciones
Si A    , sea (a, b)  A  . Entonces, a A y b
 , lo cual es imposible.
35
Teorema Para conjuntos arbitrarios A, B, C  U.
a) 
b) 
c) 
d)
     CABACBA 
     CABACBA 
     CBCACBA 
     CBCACBA 
Relaciones
El producto cartesiano y las operaciones binarias de
unión e intersección están interrelacionados con el
siguiente teorema.
36
EJEMPLO Dado un conjunto finito A con =n, resulta
que = n2, de modo que hay relaciones en A.
¿Cuántas son reflexivas?
2
2
n
A
AA 
Relaciones
10
37
Si A ={a1, a2, ... ,an}, una relación R en A es reflexiva si
.  R . Al considerar los otros n2–n pares
ordenados de A  A (los de la forma , 1  i, j  n,
i  j) conforme se construye una relación reflexiva R en
A, se incluye o excluye cada uno de estos pares
ordenados, hay relaciones reflexivas en A.
  niaa
ii
1,
 
ji
aa ,
 nn 2
2
Relaciones
38
Recordando una relación R en un conjunto A se llama
simétrica si (x, y)  R (y, x)  R para x, y  A.
¿Cuántas son simétricas?
Relaciones
39
Para contar las relaciones simétricas en A={a1,a2, ... ,an},
se escribe AA como A1A2, donde A1= y
A2= de modo que cada par en AA
está exactamente en uno de los conjuntos A1, A2.
Para A2, |A2| = |AA| – |A1| = n
2–n = n(n–1), un entero par.
El conjunto A2 contiene (1/2)(n
2–n) subconjuntos de la
forma {(ai,aj),(aj,ai)},1ijn. Al establecer una relación
simétrica R en A, para cada par ordenado de A1, se
dispone de la selección usual de exclusión o inclusión.
Para los (1/2)( n2 – n) subconjuntos de pares ordenados
en A2, se dispone de las mismas opciones. Por tanto, por
la regla del producto, hay = relaciones
simétricas en A.
  niaa
ii
1,
  jinjiaa
ji
 ,,1,
  nnn 

2
2/1
22
  nn 22/1
2
40
Relaciones
¿Cuántas son reflexivas y simétricas?
11
41
Se tiene sólo una opción para cada par ordenado en A1. 
De modo que hay relaciones en A que son 
reflexivas y simétricas. 
Relaciones
¿Cuántas son reflexivas y simétricas?
  nn 22/1
2
42
Recordando una relación R en A es un ordenamiento
parcial si y sólo si es una relación reflexiva, antisimétrica
y transitiva
Sea A un conjunto y R una relación en A. El par (A, R)
se llama conjunto parcialmente ordenado si la relación R
en A es un orden parcial, o una relación de ordenamiento
parcial. Si a A se le denomina conjunto parcialmente
ordenado, se sobre entiende que hay un orden parcial R
en A que convierte a A en este conjunto parcialmente
ordenado.
Relaciones de Orden
43
EJEMPLO Sea A el conjunto de cursos ofrecidos en una
universidad. Defínase la relación R en A mediante x R y
si x e y son el mismo curso o si x es un requisito previo
para y. Entonces, R transforma a A en un conjunto
parcialmente ordenado.
EJEMPLO Defínase R en A = {1, 2, 3, 4} por x R y, si ,
es decir, x divide a y. Entonces, R ={(1, 1), (2, 2), (3, 3),
(4, 4), (1, 2), (1, 3), (1, 4), (2, 4)} es un orden parcial y
(A, R) es un conjunto parcialmente ordenado.
Relaciones de Orden
44
EJEMPLO En el conjunto A = {1, 2, 3, 4, 5}, la relación
R en A, definida por x R y si x  y, es un orden parcial,
que transforma a A en un conjunto parcialmente
ordenado que se puede denotar por (A, ).
Si B = {1, 2, 4}  A, el conjunto ={(1, 1), (2, 2), (4, 4),
(1, 2), (1, 4), (2, 4)} es un orden parcial en B.
Relaciones de Orden
12
45
En general si R es un orden parcial en A, entonces para
cualquier subconjunto B de A, convierte a B
en un conjunto parcialmente ordenado, donde el orden
parcial de B se induce de R.
  R BB
Relaciones de Orden
46
Definición Si (A, R) es un conjunto parcialmente
ordenado, un elemento max  A se llama maximal de A si
para toda a  A, max R a  max = a
Un elemento min  A se denomina minimal de A si para
toda b  A, b R min  b = min
Relaciones de Orden
47
EJEMPLO Sea U = {1, 2, 3} y A = P(U).
Sea R la relación de subconjunto en A. Entonces U es
maximal, mientras que  es minimal para este conjunto
parcialmente ordenado.
Para B, la colección de subconjuntos propios de {1, 2, 3},
sea R la relación de subconjunto en B . En el conjunto
parcialmente ordenado (B, ), {1, 2}, {1, 3}, {2, 3} son
elementos maximales, mientras que  es el único
elemento minimal.
Relaciones de Orden
50
Definición Si (A, R) es un conjunto parcialmente
ordenado, un elemento x  A se denomina elemento
mínimo si x R a, para todo a  A. El elemento y  A se
denomina máximo si a R y para toda a  A.
Relaciones de Orden
13
51
EJEMPLO Sean U = {1, 2, 3} y R la relación de
subconjunto.
a) Con A = P(U), (A, ) tiene a  como elemento
mínimo y a U como máximo.
b) Para B = la colección de subconjuntos no vacíos de U,
(B, ) tiene a U como elemento máximo. No existe
elemento mínimo, pero si tres elementos minimales.
Relaciones de Orden
52
Para un conjunto parcialmente ordenado (A, R), es
posible tener varios elementos maximales y minimales.
¿Qué sucede con los elementos mínimo y máximo?
Relaciones de Orden
53
Teorema Si el conjunto parcialmente ordenado (A, R)
tiene algún elemento máximo (mínimo), ese elemento es
único.
Demostración Supóngase que x, y A y que ambos son
elementos máximos. Como x es un elemento máximo,
yR x. Así mismo, x R y, pues y es un elemento máximo.
Como R es antisimétrico, x = y.
Relaciones de Orden
54
Recordemos que R en un conjunto A es una relación de
equivalencia si es reflexiva, simétrica y transitiva.
Relaciones de equivalencia
EJEMPLO Sea nZ+. Para x, y  Z, se define la relación
R de módulo n por medio de x R y si y sólo si, x – y es
un múltiplo de n. Con n = 7, se halla que 9 R 2, -3 R 11,
(14,0) R pero 3 R 7.
14
55
Si R es una relación en A, R será una relación de
equivalencia y un orden parcial en A si y sólo si es la
relación de igualdad en A.
Para cualquier conjunto A, es una relación de
equivalencia en A, y si A = {a1, a2, ... , an}, la relación de
equivalencia más pequeña en A es R= .
AA 
  niaa
ii
1,
Relaciones de equivalencia
56
EJEMPLO Sea A=R y para cada iZ, sea Ai=[i, i+1).
Entonces constituye una partición de R.
Definición Sea R una relación de equivalencia en un
conjunto A. Para cualquier x  A, la clase de equivalencia
de x, denotada por [x], se define mediante
 xyAyx R][ 
Relaciones de equivalencia
57
EJEMPLO Defínase la relación R en Z, por xRy, si 4
divide a (x–y). Para esta relación se encuentra que
[0] = {..., -8, -4, 0, 4, 8, 12, ...} = {4k  kZ}
[1] = {..., -7, -3, 1, 5, 9, 13, ...} = {4k + 1  kZ }
[2] = {..., -6, -2, 2, 6, 10, 14, ...} = {4k + 2 kZ }
[3] = {..., -5, -1, 3, 7, 11, 15, ...} = {4k + 3 kZ }
{[0], [1], [2], [3]} proporciona una partición de Z.
Relaciones de equivalencia
58
Demostración
a) Este resultado se obtiene de la propiedad reflexiva de R
b) Si x R y , sea w [x]. Entonces, w R x; además como R
es transitiva, w R y. Por tanto, w  [y] y [x]  [y]. Con R
simétrica, x R y  y R x. De este modo, si t [y], entonces
t R y y por la propiedad transitiva, t R x. De ahí que t  [x]
e [y] [x]. Por tanto [x] = [y]. A la inversa sea [x] = [y].
Como por el apartado a) x  [x], entonces x  [y] o x R y.
c) Esta propiedad plantea que las clases de equivalencia
sólo se pueden relacionar de dos maneras: son idénticas o
disjuntas…
Teorema Si R es una relación de equivalencia en un
conjunto A y x, y A, entonces: a) x [x]; b) x R y si y
sólo si [x] = [y] y c) [x] = [y] o [x]  [y] = .
15
59
c) Continuación... partimos de que [x]  [y] y [x]  [y] .
Si [x]  [y]  , entonces sea v  A con v  [x] y v  [y].
Por tanto, v R x, v R y  x R y. Además por el apartado
b), x R y  [x] = [y]. Esto contradice la hipótesis de que [x]
 [y], por tanto se rechaza la hipótesis de que [x]  [y]  ,
y de ahí se obtiene el resultado.
Relaciones de equivalencia
60
Obsérvese que si R es una relación de equivalencia en A,
entonces, de acuerdo con a) y c) del teorema anterior,las
distintas clases de equivalencia determinadas por R
constituyen una partición de A.
EJEMPLO Si A ={1, 2, 3, 4, 5} y R = {(1, 1), (2, 2), (2,
3), (3, 2), (3, 3), (4, 4), (4, 5), (5, 4), (5, 5)}, entonces R
es una relación de equivalencia en A, [1] = {1}, [2] =
{2,3}=[3], [4]={4,5}=[5] y A = [1]  [2]  [4].
Relaciones de equivalencia
61
Funciones
 Una función f:AB del conjunto A a B es la 
relación fAB tal que cada aA está relacionada 
con un único b tal que (a,b)f
 Notación f(a)=b, o f:a  b
 A es el dominio de f y B es el codominio
 El valor f(a)=b es la imagen de aA bajo f
 El conjunto { f(a) | aA } es el rango de f
62
Ejemplo
 Sea A={1, 2, 3} y B={w, x, y, z}:
 ¿Es f={(1, w), (2, x)} una función de A a B?
 No
 ¿Es f={(1, w), (2, w), (2, x), (3, z)} una función de A a B?
 No
 ¿Es f={(1, w), (2, x), (3, x)} una función de A a B?
 Si
16
63
Ejemplo
 ¿Cuál es el dominio (dominio máximo ) de la función 
h dada por?
 -2 < w < 3
6
1
)(
2


ww
wh
64
Composición de funciones
 Sean f: A  B y G: B  C dos funciones. La 
composición de las funciones f y g, denotada por (g o
f) es la función:
 (g o f): A  C tal que
 Para todo a  A, (g o f)= g(f(a))
65
Tipos de funciones
 Una función es inyectiva o uno a uno si para cada 
x  A tiene una única imagen f(a):
 Si f(x)=f(y) entonces x=y.
 Elementos distintos de A tienen siempre imágenes distintas
 Sea f: R  R donde f(x)= 3x + 7 para toda x
 Es una función uno a uno
66
Ejemplo
 Sea A={1, 2, 3} y B={1, 2, 3, 4, 5}. 
 ¿Es g={(1, 1),(2, 3),(3, 3)} una función uno a uno de 
A a B?
 No
17
67
Tipos de funciones
 Una función es sobre o suprayectiva si para cada 
yB existe una xA tal que f(x)=y:
 Si yB entonces existe una xA tal que f(x)=y
 Sea f: R  R donde f(x)= x3 para toda x
 ¿Es una función sobre o suprayectiva?
 Si
68
Tipos de funciones
 Una función es una biyección entre A y B si es una 
función uno a uno y suprayectica
 Sea A={1, 2, 3 , 4} y B={w, x, y, z}. 
 ¿Es f={(1, w), (2, x), (3, y), (4, z)} de A a B una biyección?
 Si
69
Ejemplos
 La función lineal f:ZZ, definida por f(x)=x+2
 Es inyectiva
 Es suprayectiva
 Es biyectiva
 La identidad I:AA es siempre una biyección