Relaciones
Matemticas discretas
Equipo D
Guadalupe Prez SotoGerardo Jurez AcostaRen Ivn Castillo
PrezCarlos Uriel Jimnez PereyraJoel Ortega MejaRelacionesEquipo
DMISTIMatemticas discretasDefinicinDados 2 conjuntos no vacos A y
B, una relacin R es un conjunto de pares ordenados donde el primer
elemento a est relacionado con el segundo elemento b por medio de
cierta propiedad o caracterstica. La relacin se indica aRb:Una
relacin podra representarse como una tabla que muestra la
correspondencia de unos elementos con respecto a otros. Por
ejemplo:
DefinicinMaestroMateriaJorgeSistemas DigitalesDomingoLenguajes
algortmicosIgnacioEstructuras de
DatosJorgeGraficacinRaymundoProgramacin IIManuelSistemas
OperativosEzequielSistemas DigitalesDefinicinA = {x | x es un
maestro}B = {y | y es una carrera de la carrera de ingeniera en
sistemas computacionales}R = {(Jorge, Sistemas Digitales),
(Domingo, Lenguajes algortmicos), (Ignacio, Estructuras de Datos),
(Jorge, Graficacin), (Raymundo, Programacin II), (Manuel, Sistemas
Operativos), (Ezequiel, Sistemas Digitales)}Las relaciones se
forman si se cumple cierta proposicin, esa proposicin puede ser
textual, como en el caso anterior ("Imparte la materia"), pero
tambin puede ser planteada en el lenguaje matemtico.
DefinicinSean los conjuntos
Y sea R una relacin de A en B, en donde cada elemento de A es
divisible entre 13 y cada elemento de B es primo.
Como resultado se obtiene la siguiente relacin:R = {(13,2),
(13,3), (13,5), (13,7), (13,11), (13,13), (13,17), (13,19), (26,2),
(26,3), (26,5), (26,7), (26,11), (26,13), (26,17), (26,19)}
DefinicinHay que observar que las relaciones tambin se pueden
representar como un conjunto de pares ordenados en donde el
elemento a A est relacionado con el segundo elemento b B, por medio
de cierta condicin establecida. En este caso la condicin es que el
primer elemento de los pares ordenados sea un entero entre 10 y 30,
divisible entre 13, y el segundo elemento es un entero positivo
primo menor o igual a 20. Otra forma de representar este conjunto
es:DefinicinR = {(a,b) | a Z, b Z+; a es divisible entre 13; 10
< a < 30; b es primo; b 20}
DefinicinExiste otra forma de representar una relacin cuando es
de un conjunto en si mismo, es decir, cuando la relacin es binaria:
los grafos dirigidos.
Un grafo dirigido o digrafo es un par ordenado D = (A,R) donde A
es un conjunto finito y R es una relacin binaria definida sobre A.
Al conjunto A lo llamaremos conjunto de nodos o vrtices de D. A los
elementos de R los llamaremos arcos o aristas del digrafo D.
DefinicinRepresentacin grfica del digrafo D = (A,R), siendo A el
conjunto {a, b, c, d} y R = {(a, a), (a, c), (b, c)}.
Producto cartesianoEl producto cartesiano de los conjuntos A y B
que se denota como A x B, es la combinacin de todos los elementos
del conjunto A con todos los elementos del conjunto B. En teora de
conjuntos esto equivale al conjunto universo.Una relacin R de A en
B (R: A B) es un subconjunto del producto cartesiano A x B. Si y ,
entonces a su vez el producto cartesiano tambin es una relacin.
Producto cartesianoSean los conjuntos
A = {1, 2, 3} y B = {a, b}
Al producto cartesiano A x B contiene todos los pares ordenados
que resultan de relacionar todos los elementos del conjunto A, con
todos los elementos del conjunto B como se muestra en la siguiente
figura:
Producto cartesiano
Producto cartesianoEsta figura a su vez muestra otra forma de
representar una relacin: Un "diagrama de flechas" en el que se
muestran claramente los elementos que pertenecen a cada conjunto,
as como la relacin entre ellos. Tambin es fcil ver que A x B B x
A.Composicin de relacionesDefinicin: Sean R: X Y y S :Y Z dos
relaciones. La composicin de R y S, que se denota como R S,
contiene los pares ( x, z ) si y slo si existe un objeto intermedio
y tal que ( x, y ) est en R y ( y, z ) est en S.
Por consiguiente, x(R S)z = Existe y tal que xRy e yRz existen.
Para determinar si (x, z) est en la relacin R S, se necesita
siempre un intermediario, tal que sean vlidas xRy e yRz.
Composicin de relacionesSe tienen cinco personas A, B, C, D y E.
C es dueo del camin llamado Machakito y E es dueo del camin llamado
Imperioso. A es amigo de B y D, B es amigo de C y C es amigo de E.
Sea R la relacin "x es amigo de y" y sea S la relacin "y es dueo
del camin z". Calcular la relacin R S.
Solucin: Si R es la relacin "x tiene a y como amigo" y si S es
la relacin "y es el dueo del camin z " entonces el par ( x, z ) est
en R S si existe un intermediario y tal que x tiene a y como amigo
e y es dueo del camin z. Las relaciones R y S estn dadas por R={
(A, B), (A, D), (B, C), (C, E)} S = {(C, Machakito), (E,
Imperioso)} R S - {(B, Machakito), (C, Imperioso)}
B tiene acceso a un camin a travs del intermediario C, que es
dueo de Machakito y C tiene acceso a un camin a travs de
intermediario E, que es dueo de Imperioso.
Composicin de relacionesLa composicin de dos relaciones se puede
representar mediante un grafo. Sean R : X Y y S : Y Z. Ahora se
dibujan todos los nodos de X a la izquierda, todos los nodos de Z a
la derecha, y todos los nodos del conjunto intermediario Y en el
medio. Asumimos que los miembros de X van desde xl hasta x4,, los
miembros de Y van desde y1 hasta y4, y los miembros de Z van desde
z1 hasta z5. De acuerdo con lo que hemos dicho antes, el par (x i,
z k) est en R o S si y slo si existe un intermediario yj. tal que
hay un arco que va, desde xj. hasta yi y desde ste a zk. A
continuacin se enumeran sistemticamente todos los pares de R S:
(x1, z2 ) R S a travs del intermediario y1 (x1, z1) R S a travs del
intermediario y2 (x1, z4) R S a travs del intermediario y2 (x4, z3)
R S a travs del intermediario y3
La relacin resultante entonces es R S = {(x1, z2), (x1, z1),
(x1, z4), (x4, z3)}
Composicin de relaciones
Composicin de relacionesLa composicin es una operacin
asociativa; esto es, si R, S y P son tres relaciones, entonces se
cumple lo siguiente:
(R S) P = R (S P)
Por consiguiente, los parntesis se pueden eliminar en los casos
que involucren la composicin de varias relaciones.
Tipos de RelacionesReflexivaUna relacin R sobre un conjunto X es
reflexiva si
O en otra forma:
Reflexiva12345678910
12345678910
IrreflexivaUna relacin R sobre un conjunto X es irreflexiva
si
O en otra forma:
SimtricaUna relacin R sobre un conjunto X es simtrica si
O en otra forma:
Simtrica
AsimtricaUna relacin R sobre un conjunto X es asimtrica si
O en otra forma:
AntisimtricaUna relacin R sobre un conjunto X es antisimtrica
si
x y12345611211311411151161111TransitivaUna relacin R sobre un
conjunto X es transitiva si
Orden ParcialUna relacin R sobre un conjunto X es un orden
parcial si R es reflexiva, antisimtrica y transitiva.
RELACIONES EQUIVALENTESQUE ES UNA RELACION EQUIVALENTE? Una
relacin de equivalecia es aquella que tiene las tres
propiedades:
ReflexivaSimetricaTransitiva
Por otro lado, una relacion de equivalencia tiene clases de
equivalencia y estas forman particiones. Una particion es un
subgrafo completo.Que es una clase de equivalencia?
Son conjuntos que contienen a todos los elementos b B y que
estan relacionados con aA. Los elementos del primer conjunto se
encierran entre corchetes, de forma que una clase de equivalencia
se puede indicar como 11. Matematicas para la computacin, Jos
Alfredo Jimnez Murillo, Editorial Alfaomega, pag. 235.[a]={b | bB ,
aRb}
TeoremaSea R una relacin de equivalencia sobre un conjuntofinito
X. Si cada clase de equivalencia tiene r elementos, entonces
existen I X /r clases de equivalencia.Demostracin. Sean X1,
X2.....Xk las distintas clases de equivalencia. Como estos
conjuntos separan a X, |X| = |X1| +|X2| +..+|Xk| =r+r++r=krde donde
se sigue la conclusion.
Ejemplo e importanciaLa relaciones de equivalencia son
importantes porque es una propiedad que deben tener las redes en el
rea de computacin, en donde la computadora 1 de una red puede
enviar informacion a la computadora 2, pero ademas la computadora 2
puede enviar informacion o comunicarse con la computadora 1; esta
es la propiedad de simetria. Port otro lado , toda computadora
tiene comunicacion consigo misma, con lo cual se cumple la
propiedad de reflexiva. Asi como si existe un camino de
comunicacion para ir de 1 a 2,(1,2), y uno para ir de (2,5), debe
haber uno de (1,5)con lo cual se cumple la propiedad de
transitividad. 11. Matematicas para la computacin, Jos Alfredo
Jimnez Murillo, Editorial Alfaomega, pag. 235.RED
Computadora 1Computadora 2Computadora 5ParticionesSi
entonces
Una particin de un conjunto X divide a X en subconjuntos que no
se traslapan. Ms formalmente, una coleccin s de subconjuntos no
vacios de X es una particin del conjunto X si todo elemento de X
pertenece exactamente a un miembro de s. Observe que si s es una
particin de X, s es ajena por pares y U s=X.
Suponga que se tiene un conjunto X de 10 bolas rojas (R), azules
(B) y verdes (G). Si devidimos las bolas en los conjuntos R, G y B
de acuerdo con su color, la familia {R, G, B} es una particin de
X.
Una particin puede utilizarse para definir una relacin. Si s es
particin de X, podemos decir que x R y si para algn conjunto S s, x
y x pertenecen a S.
TeoremaSea s una particin de in conjunto X, decimos que x R y si
para algn conjunto de S en s, x y y pertenecen a S. Entonces R es
reflexiva, simtrica y transitiva.DemostracinSea x X. Por la
definicin de particin, x pertenece a algn miembro de S de s. As x R
x y R es reflexiva.
Supongamos que x R y, entonces x y y pertenecen a algn conjunto
S s. Como y y x pertenecen a S, y R x y R es simtrica.
Por ultimo, supongamos que x R y y y R z. Entonces x y y
pertenecen a algn conjunto S s y y y z pertenecen a algn conjunto T
s. Como y pertenece exactamente a algn miembro de s, debe cumplirse
que S=T. Por lo tanto, x y y pertenecen a Sy x R z. Se ha
demostrado que R es transitivaMatricesMatrizUna matriz es una forma
conveniente de representar una relacin R de X a Y. Una computadora
puede utilizar esta representacin para analizar una relacin. Se
etiquetan los renglones con los elementos de X (con cierto orden
arbitrario) y las columnas con los elementos de Y (con cierto orden
arbitrario). Entonces colocamos un 1 en el renglon x y la columna y
si x R y un cero en caso contrario. Esta matriz es la matriz de
relacin R.Sea la matriz de la relacin
R={(a,a),(b,b),(c,c),(d,d),(b,c),(c,d)}sobre {a,b,c,d} con respecto
al orden a,b,c,d es
Observe que la matriz de relacin sobre un conjunto X siempre es
una matriz cuadrada.
Podemos analizar con rapidez si una relacin R sobre un conjunto
X es reflexiva analizando la matriz A de R (con respecto de cierto
orden).
La relacin R es reflexiva si y slo si A tiene unos en la
diagonal principal.
La relacin R es reflexiva si y solo si (x/x) R para toda x X.
Esta solo se cumple cuando la diagonal principal consta de
unos.Podemos determinar si una relacin R Sobre un conjunto X es
simtrica, analizando la matrix A de R (con respecto de cierto
orden).
La relacin R es simtrica si y slo si para toda i y j, la ij-sima
entrada de A es igual a la ji-sima entrada de A.
De manera menos formal, R es simtrica si y slo si A es simtrica
con respecto de la diagonal principal. La razn es que R es simtrica
si y slo si siempre que (x,y) est en R, entonces (y,x) tambin esta
en R.
Esta condicin se cumple cuando A es simtrica con respecto de la
diagonal principal.Tambin podemos determinar si una elacin R es
antisimtrica analizando la matriz R (con respecto de cierto
orden).
No existe una forma sencilla de verificar si una relacin R sobre
X es transitiva analizando la matriz de R.
Teorema Sea R1 una relacin de X en Y y sea R2 una relacin de Y
en Z. Elijanse ordenes de X, Y y Z. Todas las matrices de las
relaciones estn dadas respecto de estos rdenes. Sea A1 la matriz de
R1 y A2 la matriz de R2 . La matriz de la relacin de R2 o R1 se
obtiene reemplazando cada trmino distinto de cero en el producto de
matrices A1 A2 por 1.DemostracinSea R1 la relacin de X={1,2,3} en
Y={a,b} definida por:R1 ={(1,a),(2,b),(3,a),(3,b)}
Y sea R2 la relacin de Y en Z ={x,y,z} definida
por:R2={(a,x),(a,y),(b,y),(b,z)}
Si este valor es distinto de cero, entonces su o rv es distinto
de cero. Entonces s 0 y u 0. Esto significa que (i,a) R1 y (a,k) R2
. Esto implica que (i,k) R2 R1. Se ha demostrado que si la ik-sima
entrada en A1 A2 es distinta de cero entonces, (i,k) R2 R1. El
reciproco tambin es verdadero como se demuestra a continuacin.
Supongamos que (i,k) R2 R1, entonces:
Si 1 se cumple, entonces s=1 y u=1 y su + rv es distinto de
cero. De manera anloga, si se cumple 2, rv=1 y de nuevo tenemos que
su + rv es distinto de cero. Se ha demostrado que si (i,k) R2 R1,
entonces la ik-sima entrada en A1 A2 es distinta de cero.
Para obtener la matriz de la relacin R2 R1 , solo hay que
cambiar todas las entradas distintas de cero en A1 A2 por unos. As,
la atriz de la relacin R2 R1 , con respecto de los ordenes
previamente elegidos 1,2,3 y x,y,z previamente es
Bases de datos RelacionalesQu es una base de datos?Una base de
datos es una coleccin de registros controlada mediante una
computadora. Por ejemplo, una base de datos de una lnea area podra
contener los registros de las reservaciones, programacin de los
vuelos, equipo, etc. Los sistemas de cmputo permiten guardar
grandes cantidades de informacin en bases de datos. Los datos estn
disponibles para su uso mediante varias aplicaciones. Los sistemas
de administracin de bases de datos son programas que permiten a los
usuarios tener acceso a Ia informacin contenida en las bases de
datos.
El modelo de base de datos relacional, se basa en el concepto de
una relacin n-aria. Las columnas de una relacin n-aria se llaman
atributos (o campos). El dominio de un atributo es un conjunto al
cual pertenecen todos los elementos en ese atributo.Un atributo
individual o una combinacin de atributos para una relacin es una
clave si los valores de los atributos definen de manera nica una
n-ada. Un sistema de administracin de bases de datos responde a
consultas. Una consulta es una solicitud de informacin en la base
de datos.
EjemploLa cual se puede colocar de la siguiente manera:
SeleccinEl operador de seleccin elige ciertas n-adas de una
relacin. Las elecciones se realizan dando condiciones sobre los
atributos. Por ejemplo, para la relacin JUGADOR
ProyeccinMientras que el operador de seleccin elige los
renglones de una relacin, el operador de proyeccin elige las
columnas. Adems, se eliminan los duplicados. Por ejemplo, para la
relacin JUGADOR:
FusinLos operadores de seleccin y de proyeccin controlan una
nica relacin; el operador fusin controla dos relaciones. La
operacin de fusin sobre las relaciones R1 y R2 comienza examinando
todos los pares de n-adas, uno de R1 y otro de R2. Si se satisface
la condicin de fusin, las n-adas se combinan para formar una nueva.
La condicin de fusion especifica una relacin entre un atributo de
R1 y un atributo de R2.
Ejemplo:Como condicin consideremos:Nmero de identificacin =
Nmero de identificacin del jugador.
Esta operacin se expresa comoJUGADOR [Nmero de identificacin =
NIJ] ASIGNACION.
EjercicioDeterminar los nombres de todas las personas que juegan
en un equipo.Para obtener los nombres, basta proyectar sobre el
atributo Nombre. Obtenemos la relacin:
Formalmente, podemos especificar estas operaciones comoTEMP : =
JUGADOR [Nmero de identificacin = Nmero de identificacin del
jugador] ASIGNACION TEMP [Nombre]
