M. en C. Arturo Lezama León Maestría en Ciencias, en Ciencias de la Computación. Septiembre –...
-
Upload
martita-gallegos -
Category
Documents
-
view
20 -
download
4
Transcript of M. en C. Arturo Lezama León Maestría en Ciencias, en Ciencias de la Computación. Septiembre –...
M. en C. Arturo Lezama LeónMaestría en Ciencias,
en Ciencias de la Computación.
Septiembre – Diciembre 2009
UNIVERSIDAD POLITÉCNICA DE PACHUCA
MAESTRÍA EN TECNOLOGÍAS DE LA INFORMACIÓN Y COMUNICACIONES
Matemáticas Discretas
ObjetivoAl finalizar el curso el alumno deberá
aprender un conjunto particular de realidades matemáticas, como aplicarlas y a pensar desde el punto de vista matemático para resolver problemas construyendo sus propios modelos.
ContenidoUnidad I. Lógica Matemática (3 semanas)Unidad II. Conjuntos (2 semanas)Unidad III. Relaciones y Funciones (3
semanas)Unidad IV. Algebra Booleana (3 semanas)Unidad V. Introducción a los Grafos y Árboles
(3 semanas)
Unidad III. Relaciones y FuncionesIII.1. RelacionesIII. 2. Dominio y ContradominioIII.3. Pares ordenadosIII. 4. Representación de las relacionesIII.5. Propiedades de las relacionesIII.6. Funciones y funciones diversasIII.7. Permutaciones
Objetivo U.III. Al termino de la unidad que el alumno
conocerá el uso de las relación y funciones mediante el entendimiento de las propiedades para emplearlas adecuadamente en la práctica.
III.1. RelacionesLa idea de una relación entre dos conjuntos
de objetos es común y bastante intuitiva.Ejemplos:
a) Si consideramos el conjunto A de todos los hombres vivos y el conjunto B de todas las mujeres vivas, entonces la relación P(padre) puede definirse de A en B. Así tenemos que si x A e y B, entonces x esta relacionado con y por la relación P si x es el padre de y. Se escribe x P y.
b) También podría considerarse la relación H haciendo que x H y significando que x es hijo de y.
c) Si A es el conjunto de los números reales, hay muchas relaciones que se usan de A en A, habitualmente. Ejemplo: es la relación de menor que (<) donde se establece que x esta relacionado con y si x < y.
d) En general son ejemplos las relaciones de orden: <, >, , ≥, K
e) Sea A={1,2,3,4} y R una relación de A en A. Si se sabe que: 1 R 2, 1 R 3, 1 R 4, 2 R 3, 2 R 4, 3 R 4. Entonces se sabe todo lo que se necesita sobre R. Y no es más que la relación “menor que”.
f) Se puede decir que se conoce completamente R si se conocen todos los pares relacionados por R. Se pueden escribir: R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} {( x, y)|x A, y B x R y}
Nota. Se puede observar que una relación entre conjuntos A y B puede ser considerada como un subconjunto de A x B y a su vez cualquier subconjunto de A x B puede ser considerado una relación.
R={(1,2),(4,3),(2,2)}
DefiniciónSean A y B conjuntos no vacios. Una relación R de A en B es un
subconjunto de A x B.Si R A x B y ( a, b) R, se dice que a está
relacionado con b por R y se escribirá: a R b
III.2. Dominio y ContradominioDominio: El dominio de R es el conjunto
formado por aquellos elementos de A que están relacionados con algún elemento de B. Se denota Dom(R)
Imagen, rango, contradominio ó codominio: Es el conjunto de elementos de B que está relacionado con algún elemento de A.
También llamado Imagen. Se denota Cod(R)
Ejemplos:a) Sean A={1,2,3} y B={ r, s} entonces R={(1,r),(2,r),
(3,r)} es una relación entre A y B donde Dom(R)=A y Cod(R)=B
b) Sea A={1,2,3,4,5}=B se define la siguiente relación (menor que) en A: a R b si y solo si a < b ( a, b A) R={(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)} por lo tanto Dom(R)={1,2,3,4} y Cod(R)={2,3,4,5}
c) Sea A=B=Z+, el conjunto de los números enteros positivos. Se define la siguiente relación R en Z+. a R b si y solo si a divide a b. Así por ejemplo 2 R 30 pero 30 R 2. Se tiene que Dom(R) =Cod(R)=Z+ ya que cada número se divide y es divisible por si mismo.
d) Sean A=B=R, el conjunto de todos los números. Se define la siguiente relación R en A. x R y si y solo si x e y satisfacen la ecuación Dom(R)=[-2,2] Cod(R )=[-3,3]
194
22
yx
Cod
Dom
III. 3. Pares ordenadosPareja ordenada (a, b) es un listado de
objetos a y b en un orden prescrito, donde a aparece en primer término y b, en segundo. En consecuencia, un par ordenado (o pareja ordenada) simplemente es una secuencia de longitud 2.
Matriz de una relaciónSi A y B son conjuntos finitos, con m y n
elementos respectivamente, y si R es una relación de A en B es posible representar a R con una matriz de MR=[m i j] que se denomina Matriz de R donde m i j = 1 si (a i, b j) R
0 si (a i, b j) R
A fila a i denota una fila i
B columna b j denota una columna j
Ejemplosa) Si A={1,2,3}, B={r,s} y R={(1,r),(2,s),(3,r)} entonces
La matriz de R es:
b) Recíprocamente, dados los conjuntos A y B con |A| = m y |B|=n, entonces una matriz de m x n cuyos elementos sean ceros y unos determina una relación.
Se puede denotar como:A={a1,a2,a3} y B={b1,b2,b3,b4} y (a i , b j) R si y solo si m i j = 1. Por tanto la relación queda como sigue:
R={(a1,b1),(a4,b4),(a1,b4),(a2,b2),(a2,b3),(a3,b1),(a3,b3)}
01
10
01
3
2
1
sr
0101
0110
1001
M
III.4. Representaciones de las relacionesSi A es un conjunto finito y R es una relación sobre A,
también se puede representar R gráficamente como sigue. Trace un pequeño circulo para cada elemento de A y marque el círculo con el elemento correspondiente de A. A estos círculos se los llama vértices. Trace una flecha, a la que se llama lado (arco), del vértice a i al vértice a j si y solamente si a i R a j,
La representación gráfica resultante de R se llama gráfica dirigida o dígrafo de R.
En consecuencia, si R es una relación sobre A, los lados o arcos del dígrafo de R corresponden exactamente a los pares de R, y los vértices corresponden exactamente a los elementos del conjunto A.
EjemploSean A={1,2,3,4}R={(1,1),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),
(4,1)}Entonces el dígrafo de R es
2
3
4
1
Ejercicio:Encuentre la relación determinada por:
2
3
4
1
Ejercicios1) Obtener el dominio, codominio y la
Matriz de cada una de las siguientes relaciones:a) A={4,5,6,7}, B={r, s, t, u, v}; R={(4,u),
(4,r),(5,r),(7,u),(5,v)}
b) A={1,2,3,4}, B={1,4,6,8,9}; a R b si y solo si b=a2
c) A={1,2,3,4,5,8}=B; a R b si y solo si b=a+1
d) A={1,2,3,4,5,8}=B; a R b si y solo si a es múltiplo de b
Ejercicios2) Encuentre la relación R en A
determinada por la matriz, su dominio y codominio
a) b)
0001
1100
0110
1011
RM
0101
1100
1001
RM
III.5. Propiedades de las relacionesPropiedad reflexivaPropiedad IrreflexivaPropiedad simétricaPropiedad asimétricaPropiedad anti simétricaRelaciones transitivasRelaciones de equivalenciaRelaciones de equivalencia y particionesOperaciones con las relaciones
Propiedad reflexivaUna relación R en un conjunto A es
Reflexiva si ( a, a) R para toda a A, es decir a R a, a A Propiedad Irreflexiva
Una relación R en un conjunto A es Irreflexiva si ( a, a) R para toda a A, es decir a R a, a A
Ejemplosa) Sea la relación I={( a, a)|a A} de modo que
representa la igualdad en el conjunto A. Por tanto, I es Reflexiva ya que (a, a) I para toda a A
b) Sea R={( a, b)A x A | a Kb} la relación de desigualdad en el conjunto A. R es Irreflexiva debido a que (a, a) R para toda a A.
c) Sea A={1,2,3} y R={(1,1),(1,2)} Esta relación no es reflexiva ya que (2,2) R y (3,3) R Tampoco es Irreflexiva ya que (1,1) R
Ejercicios1. Obtener la matriz asociada a la relación
reflexiva de igualdad sobre el conjunto A={1,2,3,4} Nota.- La matriz de una relación Reflexiva deberá tener “unos” en toda su diagonal.
2. Obtener la matriz asociada a la relación Irreflexiva de desigualdad sobre el conjunto A={1,2,3,4} Nota.- La matriz de una relación Irreflexiva deberá tener ceros en toda su diagonal.
Propiedad simétricaUna relación R en un conjunto A es
simétrica si se cumple que cuando a R b entonces también b R a
Si a R b b R aEjemploSea A el conjunto de las personas y la relación P={(x, x)A x A| x es primo de y}Como se puede verificar P es una relación
simétrica puesto que si “x es primo de y” entonces también y es primo de x”
Una operación no simétrica padre en hijo, hijo K padre
Propiedad asimétricaUna relación R en un conjunto A es
Asimétrica si cumple que cuando a R b entonces b R a si a R b b R a
Ejemplo:Sea A ={1,2,3,4} y la relación R={( x, y) A
x A | x>y}R={(4,3),(4,2),(4,1),(3,2),(3,1),(2,1)}Como se observa esta relación es asimétrica
puesto que si x R y (x > y) entonces x R y (y > x)
Propiedad anti simétricaUna relación R en un conjunto A es anti
simétrica si cumple que cuando a R b y b R a, entonces a=b
Si a R b y b R a b=aLa contrapositiva es que Si b Ka a R b o b R aEjemplo
Sea A=Z, el conjunto de los enteros y R={(x,y)AxA|x<y} como se puede comprobar R es Anti simétrica puesto que si x Ky y se cumple que x<y entonces y < x o en otro caso si y < x entonces x < y.
EjerciciosQué propiedades cumplen las siguientes
relaciones:a) A={1,2,3,4} y R={(1,2),(2,2),(3,4),(4,1)}
b) A=Z+, conjunto de enteros positiva y R={(a,b)AxA|a divide b}
Relaciones transitivasSe dice que una relación R en un conjunto
A es transitiva si siempre que se tiene a R b y b R c, entonces a R c. Con frecuencia es conveniente explicar lo que significa para una relación ser no transitiva. Una relación R en A es no transitiva si existen a, b y c en A de manera que a R b y b R c, pero a R c. Si no existen tales a, b y c, entonces R es transitiva.
Relaciones de equivalenciaUna relación R en un conjunto A se llama relación de
equivalencia si es reflexiva, simétrica y transitiva.Ejemplo:
Sea A el conjunto de todos los triángulos del plano y sea R la relación sobre A definida como sigue:
R={(a, b)A x A | a es congruente con b}Es fácil ver que R es una relación de equivalencia.Sea A={1,2,3,4} y seaR={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,4)}Sea A=Z, el conjunto de enteros, y supóngase que se define R
por a R b si y solo sí a b. ¿Es R una relación de equivalencia?Puesto que a a, R es reflexiva. Si a b, no necesariamente se
sigue que b a, por lo cual R no es simétrica. Incidentalmente R es transitiva, porque a b y b c implica que a c. Se ve que R no es una relación de equivalencia.
RecomendacionesSe apoyará en artículos relacionados con
las unidades de estudio, los cuales serán proporcionados por el Maestro.
Los motores de búsqueda recomendados son:CiteseerEbsHostIEEE
Referencias Matemáticas Discretas. 4ª. Ed. Johnsonbaugh. Prentice Hall Matemáticas Discretas. Kenneth A. Ross. Charles R. B. Wright.
Prentice-Hall . Hispanoamerica. Introducción a la teoría de automatas, lenguajes y computación.
John E. Hopcroft; Jeffrey D. Ullman. Ed. CECSA Fundamentos de lógica computacional. Juan Fausto Solís; Gildardo
Sánchez Ante. Ed. Trillas Languages and machines. Thomas A. Sudkamp. Wright State
University. Ed. Adisson Wesley. Álgebra moderna. Grupos-anillos-campos-teoría. I. N. Herstein. Trillas Conjuntos. Schaums, Discrete mathematical structures with applications to computer
science. Tremblay and Manohar. Mc Graw Hill Estructuras de matemáticas discretas para la computación. Bernard
Kolman, Robert C. Busby. Prentice Hall Hispanoamérica Introducción a la lógica simbólica. Jose Antonio Amaz. Trillas