PDF de programación - 5 RELACIONES

5 RELACIONES



5.1. Conjuntos parcialmente ordenados



Las relaciones transitivas antisimétricas conducen a los órdenes parciales. De
hecho , existen dos tipos de órdenes parciales, según indicamos mediante la
siguiente definición.



DEFINICION

Una relación R : S « S se denomina un orden parcial débil si es reflexiva,
antisimétrica y transitiva. R se denomina un orden parcial estricto si no es
reflexiva,antisimétrica y transitiva.

Los órdenes parciales , débiles y estrictos están íntimamente relacionados. De
hecho, si R es un orden parcial estricto, su cierre reflexivo es un orden parcial
débil. Por otra parte, si S es un orden parcial débil sobre cierto conjunto A y si

es la relación de identidad sobre A, entonces

es un orden parcial estricto.



EJEMPLO

La relación < es un orden parcial estricto : es no reflexiva, antisimétrica y transitiva.
El cierre reflexivo de < es £ , y esta relación es un orden parcial débil: es reflexiva,
antisimétrica y transitiva. Por otra parte, se obtiene el orden parcial estricto < a
partir del orden parcial débil £ mediante la eliminación de todos los pares de la
forma ( x,x ).



Todos los ordenes parciales estrictos son no cíclicos, esto es, es imposible

encontrar una
por consiguiente , es
imposible encontrar un camino que comience y finalice en x. La razón es que un

tal que

camino de tamaño s = s' desde a establecería

y para relaciones

transitivas
Por lo tanto en una relación transitiva, todo camino que
comience y termine en el mismo punto x implica que xRx es verdadera, puesto
que un orden parcial estricto es irreflexivo, esto es imposible.

pág. 1

Esto tiene una implicación importante para las llamadas funciones. Si xRy significa
que la función x puede llamar a la función y, y se puede determinar que estas
llamadas a funciones forman un orden parcial, entonces es imposible que las
llamadas causen un bucle.

La noción de conjunto parcialmente ordenado es muy importante.

5.2. ORDENES ESPECIALES

Las ordenes especiales se refiere aquellos arreglos no comunes es el caso de las
Matrices de relaciones.

Una matriz en una manera conveniente de representar una relación R de X a Y.
Esta representación se puede usar en una computadora, para analizar la relación.
Se etiquetan los renglones con elementos de X( en algún orden arbitrario), Y se
etiquetan las columnas con elementos de Y (de nuevo, en algún orden arbitrario),
y se etiquetan las columnas con elementos de Y (de nuevo, el algún orden
arbitrario). Después , el elemento en el renglón x y la columna y se hace igual a 1
si x R y , y a 0 de otra manera. Esta matriz se llama matriz dela relación R
(relativa al orden de X y Y).



Ejemplo

La matriz de relación

R =

{
,1(

b

,1(),

d

,2(),

c

,3(),

c

,3(),

b

}),4(),

a



a Y {
,=

}dcba

,

,

respectos a los ordenes 1,2,3,4 y a, b, c, d es

De X= {

}4,3,2,1=



dcba



1

2

3

4










1010

0100

0110

0110

0001












Teorema

Sea R , una relación de X a Y y sea R una relación de Y a Z. Seleccione el oren de
X Y y Z. Sea A1 la matriz de relación R1 y sea A2la matriz de relación R2 respectos
a los ordenes seleccionados. La matriz de la relación R2 o R1 respecto al orden

pág. 2

seleccionado se obtiene sustituyendo por 1 cada término diferente de cero en la
matriz de producto A1 A2







5.3. RELACIONES DE EQUIVALENCIA

Definición

Sean A un conjunto y R una relación. Se dice que R es una relación de
equivalencia si R es reflexiva, simétrica y transitiva.

Suponga que se tiene un conjunto de X de 10 pelotas, cada una de las cuales es
roja, azul, ó verde. Si se dividen las pelotas en conjuntos R, A, y V de acuerdo con
el color, la familia {

es una partición de X.

}VAR ,
,

Una partición es útil para definir una relación . Si S es una partición de X,se puede
S ∈ ,tanto x como y
definir x R y de modo que signifique que para algún conjunto
perteneces a S. Para el ejemplo la relación obtenida se describe como “es del
mismo color que”. El siguiente teorema muestra este tipos de relación siempre es
reflexiva, simétrica y transitiva.

S



Teorema

Sea S una partición de un conjunto X. Defina xRy de modo que signifique que para
algún conjunto S en S, tanto x como y pertenecen a S. Entonces R es reflexiva,
simétrica y transitiva.

Ejemplo

Considere la relación

}5,53,51,5,4,42,4,5,3,3,31,3,4,2,2,2,5,1,3,1,2,1=R
)

) (

) (

) (

) (

)(

) (

) (

)(

)(

)(

(
{

) (

) (



}5,4,3,2,1

La relación es reflexiva porque (1,1),(2,2),/3,3),(4,4),(5,5) R∈ .La

En {
relación es simétrica por que siempre que (x,y) está en R,(y,x) también está en R.
Por último, la relación es transitiva porque siempre que (x,y) y (y,z) están en
R,(x,z) también está en R. Como R es reflexiva, simétrica y transitiva.R es un a
relación de equivalencia en {

}5,4,3,2,1

.

pág. 3

Teorema

Sea R una relación de equivalencia en un conjunto X Para cada

Xa ∈ ,sea







[ ] {
a

∈=

}aRxXx



( En palabras [ ]a es el conjunto de todos los elementos de X que están
relacionados con a). Entonces

S

=

{
aa

∈

}X


Es una partición de X.

Ejemplo

Existen dos clases de equivalencia para la relación de equivalencia.

}5,53,51,5,4,42,4,5,3,3,31,3,4,2,2,2,5,1,3,1,1,1=R
)

) (

) (

) (

) (

) (

) (

(
{

) (

) (

)(

)(

)(

)(



En {

}5,4,3,2,1

del ejemplo anterior a saber,

[ ]
1

=

[ ]
3

=

[ ] {
=
5

},5,3,1

, y [ ]
2

=

[ ] {
=
4

},4,2





Teorema

Sea R una relación de equivalencia en un conjunto finito X, Si cada clase de
equivalencia tiene r elementos, existen X /r clases de equivalencia.

Demostración

Sean

XX

,

1

Κ

,2

,

kX

las distintas clases de equivalencias. Como estos conjuntos

hacen una partición de X,

X

=

X

1

+

X

Κ2

+

+

X

k

++=

r

r

Κ

=+

r

kr



Y se deriva la conclusión

ejemplos

1) La relación R sobre Z definida por: a R b ⇔ a – b es múltiplo de 3.
2) Sea k∈Ν, la relación R sobre Z: a R b ⇔ a – b es múltiplo de k.

pág. 4

3) Dado un conjunto D ⊆ U, la relación: A R B ⇔ A ∩ D = B ∩ D
4) Sobre los números reales ℜ, la relación R: x R y ⇔ x – y ∈ Z
5) La relación R sobre ℜ2 definida por: (x,y) R (a,b) ⇔ x.y = a.b
6) La relación R sobre Z2 definida por: (m,n) R (p,q) ⇔ m+q = n+p



5.4 Relaciones generales

Las relaciones generalizan el concepto de funciones. La presencia la presencia del
par ordenado (a,b) en una relación se interpreta como que existe una de a de b. El
modelo de base de datos relacional que ayuda a los usuarios a tener acceso a
tener acceso a la información de una base de datos (una colección de registros
manejados por una computadora) se basa en el concepto de relación.



Se puede pensar en una relación de un conjunto a otro como en una tabla de lista
los elementos del primer conjunto que se relaciona como los elementos del
segundo conjunto. La tabla siguiente muestra que estudiantes están inscritos en
cuales cursos. Por ejemplo Guillermo toma Computación y Arte. María tomo
Matemáticas. En la terminología de las relaciones se dice que Guillermo, está
relacionada con Matemáticas.

Por supuesto, la tabla en realidad es sólo un conjunto de pares ordenados. De
manera abstracta, se define una relación como un conjunto de pares ordenados.
En este contexto, se considera que el primer elemento del par ordenado está
relacionado con el segundo elemento del par ordenado.

Estudiantes

Guillermo

Curso

Computación

María

Matemáticas

Guillermo

Arte

Beatriz

Historia

Beatriz

Computación

Davis

Matemáticas



Definición

pág. 5

Una relación (binaria) R de un conjunto X a un conjunto Y es un subconjunto de
producto cartesiano
,y se dice que x está
relacionada con y. Si X=Y se llama relación (binaria) sobre X.

YX × .Si (x,y) R∈ , se escribe

yRx

El conjunto





{
yxXx

∈

(

,

)

∈

Rpara

⋅

a

lg

una

}Yy
∈⋅


Se llama dominio de R. El conjunto

{
yxXy

∈

(

,

)

∈

Rpara

⋅

a

lg

una

}Yx
∈⋅








Se llama rango de R.

Una función es un tipo especial de relación. Una función f de X a Y es una

relación de X a Y que tiene la propiedades:

a) El dominio de f es igual X

b) Para cada

Xx ∈ , existe exactamente

Yy ∈ tal que (x,y)

f∈ .

Una relación R sobre un conjunto X se llama simétrica si para toda x,

Xy ∈ . Si

yxsi

,(

∈)

R

entonces

yx ∈)
,(

R

.

Una relación R sobre un conjunto X se llama antisimétrica si para toda x,

Xy ∈ .

yxsi

,(

∈)

R

y ≠ entonces

x

y

yx ∈)
,(

R

.

Si

Una relación R sobre un conjunto X se llama transitiva si para toda

Xzyx
,

∈,

. Si

zyyyxsi

∈),()

,(

R

y entonces

yx ∈)
,(

R

.















pág. 6

BIBLIOGRAFIA

• Matemáticas Discretas y Combinatoria ;Ralph P. Grimaldi 3° edición

Pretince Hall.

• Matematica Discretas Sexta edición Richard Johnsonbaugh; Pretince Hall.

• Matematicas Discretas eduard R. Sheninerman; thomson Leraning











































pág. 7

Actividades Complementarias

1.- Sea A el conjunto de cursos ofrecidos en una escuela. Definimos la

relación R sobre A como xRy si xy son el mismo curso o si x es un

prerrequisito para y. es un conjunto parcial mente ordenado?

2.-Verifique que la relación

{
,(
aa
reflexiva, simétrica, y transitiva.

R =

,(),

bb

}),(),

cc

sobre

X =

{
cba

,

,

},

es

3.-Determine la relación indicada es una relación de equivalencia en
{
}5,4,3,2,1
equivalencia.

.Si la la relación es una relación de equivalencia ,liste las clases de

})1,3(),3,1(),5,5(),4,4(),3,3(),2,2(),1,1(
})1,3(),3,1(),3,5(),5,3(),1,5(),5,1(),5,5(),4,4(),3,3(),2,2(),1,1(
yx
,(

divideax

3)

−

}y






a) {
b) {
c) {







pág. 8