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 ser cualquier cosa: personas, números, colores, letras, figuras, etc. Cada uno de los objetos en la colección es un elemento o miembro del conjunto. Por ejemplo, el conjunto de los colores del arcoíris es: AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta}

Un conjunto suele definirse mediante una propiedad que todos sus elementos comparten. Por ejemplo, para los números naturales, si consideramos la propiedad de ser un número primo, el conjunto de los número primos es: P = {2, 3, 5, 7, 11, 13, …}

Un conjunto queda definido únicamente por sus miembros y por nada más. En particular el orden en el que se representen estos es irrelevante. Además, cada elemento puede aparecer de manera idéntica una sola vez, esto es, no puede haber elementos totalmente idénticos repetidos. Por ejemplo: S = {Lunes, Martes, Miércoles, Jueves, Viernes} = {Martes, Viernes, Jueves, Lunes, Miércoles} AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta} = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta, Naranja} Los conjuntos pueden ser finitos o infinitos. El conjunto de los número naturales es infinito, pero el conjunto de los planetas en el sistema solar es finito (tiene ocho elementos). Además, con los conjuntos pueden combinarse mediante operaciones, de manera similar a las operaciones con números. Los conjuntos son un concepto básico, en el sentido de que no es posible definirlos en términos de nociones más elementales, por lo que su estudio puede realizarse de manera informal, apelando a la intuición y a la lógica. Por otro lado, son el concepto fundamental de la matemática: mediante ellos puede formularse el resto de objetos matemáticos, como los números y las funciones, entre otros. Su estudio detallado requiere pues la introducción de axiomas y conduce a la teoría de conjunto Representación de relaciones usando grafos.

Un grafo es el principal objeto de estudio de la teoría de grafos. Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binaria entre elementos de un conjunto. Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas). Un grafo G es un par ordenado G = (V,E), donde:

• V es un conjunto de vértices o nodos, y • E es un conjunto de aristas o arcos, que relacionan estos nodos.

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden del grafo G a su número de vértices, | V | . El grado de un vértice o nodo V es igual al número de arcos E que se encuentran en él. Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden. EJEMPLO:

• V:={1,2,3,4,5,6} • E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1 ~ 2. • En la teorías de las categorías una categoría puede ser considerada como un multigrafo dirigido, con los objetos como vértices y los morfismos como aristas dirigidas. • En ciencias de la computación los grafos dirigidos son usados para representar máquinas de estado finito y algunas otras estructuras discretas. • Una relación binaria R en un conjunto X es un grafo

...