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