leccion 6 matematicas

Apuntes de Matem´atica Discreta
6. Relaciones

Francisco Jos´e Gonz´alez Guti´errez
C´adiz, Octubre de 2004

Universidad de C´
adiz

Departamento de Matem´
aticas

ii

Lecci´
on 6

Relaciones
Contenido
6.1

6.2
6.3
6.4

6.5

Generalidades . . . . . . . . . . . . . . . . . . .
6.1.1 Relaci´
on . . . . . . . . . . . . . . . . . . . . .
6.1.2 Igualdad de Relaciones .. . . . . . . . . . . .
Relaciones Binarias . . . . . . . . . . . . . . .
6.2.1 Dominio e Imagen . . . . . . . . . . . . . . .
Matriz de una Relaci´
on . . . . . . . . . . . . .
6.3.1 Definici´
on . . . . . . . . . . . . . . . . . . . .
Grafo Dirigido de una Relaci´
on . . . . . . . .
6.4.1 Definici´
on . . . . . . . . . . . . . . . . . . . .
6.4.2 Representaci´
on Gr´
afica de unGrafo Dirigido
Propiedades de las Relaciones . . . . . . . . .
6.5.1 Reflexividad . . . . . . . . . . . . . . . . . . .
6.5.2 Simetr´ıa . . . . . . . . . . . . . . . . . . . . .
6.5.3 Asimetr´ıa . . . . . . . . . . . . . . . . . . . .
6.5.4 Antisimetr´ıa . . . . . . . . . . . . . . . . . .
6.5.5 Transitividad . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

. . . . . . . . . .
. . . . . . . . . . .
. .. . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .

131
132
132
132
133
135
135
136
136
136
138
138
139
141
142
145

Lasmatem´
aticas aparecen como la ciencia que estudia las relaciones entre ciertos objetos abstractos.
Emile Borel

En esta lecci´on estudiaremos algunas estructuras b´asicas que pueden representarse a trav´es de la relaci´on
entre elementos de conjuntos. Las relaciones tienen una importancia fundamental tanto en la teor´ıa como
en las aplicaciones a la inform´
atica.
Una estructura de datostales como una lista, una matriz o un ´arbol, se usan para representar conjuntos
de elementos junto con una relaci´
on entre los mismos.
Las relaciones que son parte de un modelo matem´atico est´an a menudo impl´ıcitamente representadas por
relaciones en una estructura de datos.
Aplicaciones num´ericas, recuperaci´
on de informaci´on y problemas de redes son algunos ejemplos donde
lasrelaciones ocurren como parte de la descripci´on del problema, y la manipulaci´on de relaciones es
importante en la resoluci´
on de procedimientos.
Las relaciones tambi´en juegan un importante papel en la teor´ıa de computaci´on, incluyendo estructuras
de programas y an´
alisis de algoritmos.
131

Universidad de C´
adiz

Departamento de Matem´
aticas

En esta lecci´on desarrollaremosalgunas de las herramientas fundamentales y los conceptos asociados a
las relaciones.

6.1

Generalidades

Hemos estudiado ya dos relaciones importantes entre proposiciones: la implicaci´on y la equivalencia.
Tambi´en hemos estudiado la relaci´
on de subconjunto para conjuntos. En ´algebra y c´alculo son importantes las relaciones entre variables; en geometr´ıa lo son las relaciones entrefiguras. Hasta el momento
no hemos necesitado una definici´
on precisa de la palabra relaci´
on. Sin embargo, sin una definici´on formal
es dif´ıcil responder preguntas sobre relaciones. ¿Qu´e se quiere dar a entender, por ejemplo, cuando se
dice que dos relaciones aparentemente diferentes son iguales?
En la realidad que nos circunda existen relaciones entre elementos, entre conjuntos y entre...