Matematicas Discretas Unidad 5

5.1. -Conceptos básicos relacionales

5.1.1.-Producto cartesiano

5.1.2 .-Relación binaria

5.1.3.- Representación de relaciones (matrices, conjuntos, grafos, diagrama de flechas)

5.2.-Propiedades de las relaciones (reflexiva, irreflexiva, simétrica, asimétrica, anti simétrica, transitiva)

5.3.-Relaciones de equivalencias (erraduras, clases de equivalencia, particiones)

5.4.- Función inyectiva, función biyectiva, función suprayectiva)

5.5.-Aplicación de las relaciones y las funciones en la computación

5.1. -Conceptos básicos relacionales

Dados dos conjuntos A y B, el producto cartesianos de estos dos conjuntos es el conjunto formado por todos los pares ordenados (a,b) donde a es un elemento de A y b es un elemento de B. Dados dos conjuntos A y B una relación es un subconjunto del producto cartesiano A x B. Un elemento a, que pertenece al conjunto A, está relacionado con un elemento b, que pertenece al conjunto B, si el par (a, b) pertenece a un subconjunto G (llamado grafo) del producto cartesiano A x B.

Ejemplo: Sean A = {a, b, c} y B = {1, 2} dos conjuntos. El producto cartesiano A x B = {(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)}. Una relación sería R = {(a,1),(c,2)}. A las relaciones también se les llama correspondencias.

5.1.1 Producto cartesiano

Considere dos conjuntos arbitrarios A y B. El conjunto de todas las parejas ordenadas (a, b) en donde a ? A y b ? B se llama producto o producto cartesiano de A y B. La definición de producto cartesiano puede extenderse fácilmente al caso de más de dos conjuntos. Se llama producto cartesiano de dos conjuntos A y B y se representa A x B, al conjunto de pares ordenados (a, b), tales que el primer elemento pertenece al primer conjunto y el segundo elemento al segundo conjunto. Es decir: A x B = {(a, b) / a ? A, b ? B} El producto cartesiano, en general, no es conmutativo. Es decir: A x B ? B x A. Puede ocurrir que los conjuntos A y B sean coincidentes. EJEMPLO: Si A = {a, b, c} y B = {1, 2, 3, 4}, el producto cartesiano es: A x B = {(a, 1), (a, 2), (a, 3), (a, 4), (b, 1), (b, 2), (b, 3), (b, 4), (c, 1), (c, 2), (c, 3), (c, 4)} Se puede representar gráficamente por medio de puntos en un plano, como se muestra a continuación. Aquí, cada punto P representa una pareja ordenada (a, b) de números reales y viceversa; la línea vertical a través de P encuentra al eje x en a, y la línea horizontal a través de P encuentra el eje y en b. A esta representación se le conoce como diagrama cartesiano.

Hay otra manera de visualizar una relación y es a través de una representación gráfica, donde se destaquen los puntos en el plano que pertenecen a A y los puntos que pertenecen a B. Se trazan flechas que indican la relación que existe entre cada elemento del conjunto A y su correspondiente en el conjunto B. A esta representación gráfica se le conoce como un diagrama de flechas.

5.1.2 Relación Binaria

Una relación binaria es una relación matemática R entre los elementos de dos conjuntos A y B. Una relación de este tipo se puede representar mediante pares ordenados, :1 Sean A y B dos conjuntos. Una relación (binaria) R de A en B es un subconjunto de A × B. Si (x, y) 2 R diremos que x está relacionado con y por R. Note que en la definición R es simplemente un subconjunto de parejas ordenadas de A × B.

Debido a que este tipo de relaciones son las mas frecuentes, el termino “relación” denota generalmente una relación binaria; adoptaremos este criterio cuando no haya confusión y especificaremos las que no sean binarias con términos tales como “ternaria” o “n-aria”.

Si (a, b) 2 R diremos que a esta relacionado con b y lo notaremos por aRb. Si (a, b) /2 R, escribiremos aR/b y diremos que a no esta relacionado con b. EJEMPLO

Sea el conjunto A = {x, y, z}. El grafo de la siguiente figura representa una relación binaria definida en A, puesto que los pares (x, z), (y, x) (y, y) constituyen un subconjunto de A x A.

Se dice que dos elementos a y b están relacionados, y se escribe a R b, “a está relacionado con b mediante la relación binaria R”, cuando el par ordenado (a, b) pertenece al subconjunto del producto cartesiano que define la relación. Si dos elementos a y b no están relacionados mediante R en algún sentido, escribiremos a R b o b R a o ambas cosas.

Propiedades de una relación binaria Las principales propiedades que puede presentar una relación binaria R definida en un conjunto A se indican en la siguiente tabla, junto con sus respectivas condiciones.

Ejemplo: Sea A = {huevos, leche, ma´iz} y B = {vacas, cabras, gallinas}. Escribir la relacion R de A a B definida por: (a, b) 2 R () a es producido por b

Solucion La relacion seria: R = {(huevos,gallinas),(leche,vacas),(leche,cabras)}

5.1.3 .-Representación de relaciones(matrices, conjuntos ,grafos, diagrama de flechas )

Un método para el estudio de las relaciones de manera algorítmica es utilizando matrices compuestas de ceros y unos. Definición:

2.4.1 Sean A y B conjuntos finitos de la forma:

Si R es una relación de A en B. La relación R puede ser representada por la matriz , donde La matriz se denomina matriz de R. En otras palabras la matriz, de ceros y unos, de R tiene un 1 en la posición cuando está relacionado con , y un 1 en está posición si no está relacionado con . Obsérvese en la definición anterior que los elementos de A y B han sido escritos en un orden particular pero arbitrario. Por lo tanto, la matriz que representa una relación depende de los órdenes usados para A y B. Cuando A = B usamos el mismo orden para A y B. Ejemplo:

Sean . Consideremos la siguiente relación de : .

Entonces la matriz de R es Recíprocamente, dando los conjuntos A y B con m y n elementos respectivamente, una matriz de m x n formada de ceros y unos determina una relación de A en B, como se ilustra en el siguiente ejemplo. Ejemplo:

Determinemos las parejas ordenadas que están en la relación R representada por la matriz Puesto que R consiste de aquellas parejas ordenadas , con , se sigue que

Representación de relaciones usando conjuntos. Un conjunto es una colección de objetos considerada como un objeto en sí. Los objetos de la colección pueden

...