profesonal

Apuntes de Matem´tica Discreta
a
6. Relaciones

Francisco Jos´ Gonz´lez Guti´rrez
e
a
e
C´diz, Octubre de 2004
a

Universidad de C´diz
a

Departamento de Matem´ticas
a

ii

Lecci´n 6
o

Relaciones
Contenido
6.1

6.2
6.3
6.4

6.5

Generalidades . . . . . . . . . . . . . . . . . . .
6.1.1 Relaci´n . . . . . . . . . . . . . . . . . . . . .
o
6.1.2 Igualdad deRelaciones . . . . . . . . . . . . .
Relaciones Binarias . . . . . . . . . . . . . . .
6.2.1 Dominio e Imagen . . . . . . . . . . . . . . .
Matriz de una Relaci´n . . . . . . . . . . . . .
o
6.3.1 Definici´n . . . . . . . . . . . . . . . . . . . .
o
Grafo Dirigido de una Relaci´n . . . . . . . .
o
6.4.1 Definici´n . . . . . . . . . . . . . . . . . . . .
o
6.4.2 Representaci´n Gr´fica de unGrafo Dirigido
o
a
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

Las matem´ticas aparecen como la ciencia que estudia las relaa
ciones entre ciertos objetos abstractos.
Emile Borel

En esta lecci´nestudiaremos algunas estructuras b´sicas que pueden representarse a trav´s de la relaci´n
o
a
e
o
entre elementos de conjuntos. Las relaciones tienen una importancia fundamental tanto en la teor´ como
ıa
en las aplicaciones a la inform´tica.
a
Una estructura de datos tales como una lista, una matriz o un ´rbol, se usan para representar conjuntos
a
de elementos junto con una relaci´n entre losmismos.
o
Las relaciones que son parte de un modelo matem´tico est´n a menudo impl´
a
a
ıcitamente representadas por
relaciones en una estructura de datos.
Aplicaciones num´ricas, recuperaci´n de informaci´n y problemas de redes son algunos ejemplos donde
e
o
o
las relaciones ocurren como parte de la descripci´n del problema, y la manipulaci´n de relaciones es
o
o
importante en laresoluci´n de procedimientos.
o
Las relaciones tambi´n juegan un importante papel en la teor´ de computaci´n, incluyendo estructuras
e
ıa
o
de programas y an´lisis de algoritmos.
a
131

Universidad de C´diz
a

Departamento de Matem´ticas
a

En esta lecci´n desarrollaremos algunas de las herramientas fundamentales y los conceptos asociados a
o
las relaciones.

6.1

GeneralidadesHemos estudiado ya dos relaciones importantes entre proposiciones: la implicaci´n y la equivalencia.
o
Tambi´n hemos estudiado la relaci´n de subconjunto para conjuntos. En ´lgebra y c´lculo son impore
o
a
a
tantes las relaciones entre variables; en geometr´ lo son las relaciones entre figuras. Hasta el momento
ıa
no hemos necesitado una definici´n precisa de la palabra relaci´n. Sinembargo, sin una definici´n formal
o
o
o
es dif´ responder preguntas sobre relaciones. ¿Qu´ se quiere dar a entender, por ejemplo, cuando se
ıcil
e
dice que dos relaciones aparentemente diferentes son iguales?
En la realidad que nos circunda existen relaciones entre elementos, entre conjuntos y entre elementos y
conjuntos. Existen relaciones de parentesco, de amistad, de paisanaje, etc.,...