Matematicas Discretas. Unidad 5. (Relaciones. 5.1 Conceptos Basicos Hasta 5.5 Aplicaciones De Las Relaciones Y Las Funciones En La Computadora

Instituto Tecnológico Superior de Coatzacoalcos

ING. EN

Nombre del Alumno: ____________
Apellido Paterno Apellido Materno Nombre(s)

PORTAFOLIO DE EVIDENCIAS

Asignatura

No. Control: Semestre: __1__ Grupo: ___

Fecha de inicio: 30/05/12 Fecha de término: _________


Nombre del Docente:Apellido Paterno Apellido Materno Nombre(s)

-------------------------------------------------

-------------------------------------------------

-------------------------------------------------

-------------------------------------------------
UNIDAD 5

Relaciones.

5.1- Conceptos básicos.
5.1.1- Producto cartesiano.
5.1.2- Relación binaria.
5.1.3- Representación derelaciones (matrices, conjuntos, grafos, diagramas de flechas)
5.2- Propiedades de las relaciones (reflexiva, irreflexiva, simétrica, asimétrica, antisimetrica, transitiva).
5.3- Relaciones de equivalencia (cerraduras, clases de equivalencia, particiones).
5.4- Funciones (inyectiva, suprayectiva, biyectiva)
5.5- Aplicaciones de las relaciones y las funciones en la computación.

5.1 CONCEPTOS BASICOS.PAREJA ORDENADA

Se dice que una pareja ordenada es un esquema en el que un elemento x de un conjunto esta relacionado con un elemento y de otro conjunto.

Una pareja ordenada así definida se escribirá de la siguiente manera: (x, y), donde x pertenece al primer conjunto e y pertenece al segundo conjunto.

A•B
A = {a, b} B= {1, 2, 3}

R = {(a, 1); (a, 3); (b, 2); (b, 3)}

5.1.1PRODUCTO CARTESIANO.

Es la relación entre los elementos de un conjunto con los otros elementos de otro conjunto. Como los polinomios.

Ejemplo:

A = {a, b}, B= {1, 2, 3}

A•B= {(a, 1); (a, 3); (b, 2); (b, 3)}

5.1.2 RELACION BINARIA.

Una relación binaria R de un conjunto X es un conjunto Y es un subconjunto del producto cartesiano XxY si el par ordenado (x, y) pertenece a la relaciónescribimos que elemento “x” se relaciona con el elemento “y”. Decimos que “x” está relacionada con “y”. Si (x=y), decimos que la relación binaria sobre el conjunto X.
El conjunto {x € X | (x, y) € R´ y € Y} es el dominio de R el conjunto {y € Y | (x, y) € R´ x € X}

Si una relación se indica mediante una tabla el dominio está formado por los miembros de la primera columna y el rango formadopor los miembros de la segunda columna.
X= {2, 3, 4}, Y= {3, 4, 5, 6, 7}

R= {(x, y) | X divide a Y con residuo 0}

| 3 | 4 | 5 | 6 | 7 |
2 | | (2,4) | | (2,6) | |
3 | (3,3) | | | (3,6) | |
4 | | (4,4) | | | |
x | y |
2 | 4 |
2 | 6 |
3 | 3 |
3 | 6 |
4 | 4 |

5.1.3 REPRESENTACION DE RELACIONES.

Los ejemplos de relaciones que más se presentan en el área dela computación son aquellas que están definidas sobre conjuntos finitos. En esta sección se trataran dos formas de representar dichas relaciones y su uso para poder identificar las propiedades vistas en la sección anterior.

Representación de relaciones usando matrices
Un método para el estudio de las relaciones de manera algorítmica es utilizando matrices compuestas de ceros y unos.
 Sean A yB 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

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 representarrelaciones binarias 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.

Representación de relaciones usando diagramas de flechas.

Una forma...