Computacion

Instituto Tecnológico de Campeche.


Matemáticas Discretas.


Unidad 5. Relaciones.


Ricarte Daniel Heredia Cu.



Conceptos Básicos.
Producto Cartesiano
Si tenemos dos conjuntos A y B, y tratamos de armar todos los pares posibles formados por un elemento del conjunto A y un elemento del conjunto B, obtendremos el producto cartesiano de los dos conjuntos. Se escribe: AxBPodemos representarlo de diferentes formas: diagramas de flechas, diagramas arbolados, tablas y gráficos cartesianos. Cada par que formemos con un elemento de A y uno de B, en ese orden, recibe el nombre de par ordenado.
Llamaremos producto cartesiano de dos conjuntos que simbolizaremos como AXB a todos los pares de elementos ordenados que podamos formar tomando como primer elemento un elementodel conjunto A y como segundo un elemento del conjunto B
Ejemplo:
Sea los conjuntos A={1,2,3} y B={4,5,6} se tiene:
AXB={(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5) ,(3,6)}
El producto cartesiano AXB no es igual al producto cartesiano BXA
Si los conjuntos A y B tienen elementos comunes, entonces los elementos del producto cartesiano de la forma (a,a), se les llama elementos diagonales.
Siel producto cartesiano fuese de un mismo conjunto AXA puede escribirse de forma simbólica como A2.
Si el producto cartesiano lo forman más de dos conjuntos los elementos del producto cartesiano lo formaran grupos de elementos tomados ordenadamente de cada uno de los conjuntos que lo forman tomando un elemento del primer conjunto, otro del segundo otro del tercero y así hasta llegar al ultimo.Para representar gráficamente el producto cartesiano utilizaremos la representación cartesiana que consiste en trazar unos ejes perpendiculares, en el eje horizontal colocaremos los elementos del conjunto A y en el eje vertical los elementos del conjunto B,los elementos del producto cartesiano los forman los puntos de intercepción que se obtienen al trazar por los elementos del conjunto A paralelasal eje vertical y por los elementos del conjunto B paralelas al eje horizontal.

Relación binaria.
Una relación binara R sobre A y B, conjuntos no vacíos, indicada como RA, B, es un subconjunto de AxB. Formalmente hablando sería. Entonces, RA, B es un conjunto de pares con e .
A los conjuntos A y B se les conoce como conjunto de partida y conjunto de llegada. Al conjunto de elementos de Aque aparecen en la relación se llama dominio y se representa Dom(R) . Al conjunto de elementos de B que aparecen en la relación se llama imagen y se representa Im(R) .
Evidentemente, también puede darse el caso A=B, donde la relación toma la forma .
Las siguientes notaciones son válidas xRy, R(x,y), Rxy(notación polaca) y se leen x relacionado con y según R.
Ejemplos:
1. A= {0, 1, 2, 3}, B={0,1, 2, 3, 4, 5}, RA,B={, , , , , , , , , , , , , }.
2. A ={0, 1, 2, 3}, , RA,B={, , , , , , , , , , , }.
3. A= {0,1,2,3}, RA2=A2={, , , , , , , , , , , , , , , }.
4. A= {0,1,2,3}, RA2=A2={, , , }.
5. Sea C los siguientes cuerpos del Sistema Solar Interior:
C={Sol, Mercurio, Venus, Tierra, Luna, Marte, Fobos, Deimos}, se define la relación x gira alrededor de y como G={, , , , , , }.Representación de relaciones (matrices, conjuntos, grafos, diagrama de flechas).
Los ejemplos de relaciones que más se presentan en el área de la 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 usandomatrices
Un método para el estudio de las relaciones de manera algorítmica es utilizando matrices compuestas de ceros y unos.
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á...