Relaciones
LÓGICA Y MATEMÁTICA DISCRETA
Tema 3
2021/2022
Mar Angulo Martínez
2
Tema 3. Relaciones
3.1. Relaciones binarias
3.2. Propiedades y representación
3.3. Relaciones de equivalencia
3.4. Relaciones de orden
3.5. Elementos extremales
3.6. Retículos
3.7. Ejemplos de relaciones de equivalencia
3
❑ Dados 𝐴1 , 𝐴2 ,… 𝐴𝑛
𝑠𝑒 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎 𝒓𝒆𝒍𝒂𝒄𝒊ó𝒏 𝑹 𝑎 𝑢𝑛 𝑠𝑢𝑏𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜
𝑑𝑒𝑙 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑜 cartesiano 𝐴1x 𝐴2x… x𝐴𝑛 Es decir, R ⊂ 𝐴1x 𝐴2x… x𝐴𝑛
❑ Si R ⊂ 𝐴1 x 𝐴2 x… x𝐴𝑛 es una relación n-aria
❑ Si R ⊂ 𝐴1 x 𝐴2 x𝐴3 es una relación ternaria
❑ Si R ⊂ 𝐴1 x 𝐴2 es una relación binaria
❑ El concepto de relación implica la existencia de n-tuplas o enumeraciones de
elementos de los distintos conjuntos, donde el orden es fundamental.
4
Relaciones binarias
❑ Relación binaria de A en B es una correspondencia entre
dos conjuntos A y B;
❑ es un subconjunto R de pares ordenados (a,b) є AxB tales que a es
un elemento del conjunto A y b es un elemento de B
R = {(a,b)/ (a,b) є AxB y aRb}
✓ a es el antecedente de la relación y b es el sucesor de a
✓ Dominio de una relación: es el conjunto de todos los antecedentes
✓ Rango o Imagen de una relación es el conjunto de todos los sucesores
❑ Relación definida sobre un conjunto A es una relación
binaria cuando A=B R = {(a,b)/ (a,b) є AxA y aRb}
5
Relaciones binarias
Ejemplos
Las relaciones entre elementos de conjuntos se dan en variados contextos:
❖ -entre un número entero y sus divisores
❖ -entre una empresa y su número de teléfono
❖ -entre un número real y otro que es mayor que él
❖ -entre un programa informático y una de las variables que emplea
❖ -entre un lenguaje de programación y una sentencia válida en el mismo
❖ -entre una recta y otra o entre una recta y un plano
❖ -entre miembros de una familia: ser padre, ser hijo, ser hermano…
❖ -entre dos de ciudades que están conectadas por un vuelo de una compañía aérea
❖ -relación de entre las distintas fases de un proyecto
❖ -forma de almacenar información en bases de datos informáticas
Las relaciones se aplican en redes de comunicación, en planificación
de proyectos, en bases de datos…
6
Relaciones binarias
aRb (a,b) ∈ R
(a relacionado con b a través de R)
❖ Ejemplo 1:
A={conjunto de ciudades} B= {conjunto de CCAA}
(Madrid,Madrid) єR, (Málaga, Andalucía) єR…
❖ Ejemplo 2:
A= {1,2,3,4,5,6}
1) Relación binaria definida por aRb a|b
R= { (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,4), (2,6), (3,3), (3,6), (4,4), (5,5), (6,6)}
2) Relación binaria definida por aRb a>b
R= { (2,1), (3,1), (4,1), (5,1), (6,1), (3,2), (4,2), (5,2), (6,2), (4,3), (5,3), (6,3), (5,4), (6,4),(6,5)}
3) Relación binaria definida por aRb a-b>3
R= {(5,1), (6,1), (6,2)}
7
Relaciones binarias
❖ Ejemplo 3
R1={(a,b)/ a>b}
R2={(a,b)/ a=b ó a=-b}
R3={(a,b)/ a=b+1}
¿Cuáles de ellas contienen a cada uno de los siguientes pares
(1,1), (1,2), (1,3), (2,1), (1,-1), (2,2)?
❖ Ejemplo 4
Determinar el dominio y la imagen en las relaciones definidas en el ejemplo 2
8
Relaciones binarias
❑ Una relación en un conjunto A es una relación de A en A.
Es por tanto un subconjunto de AxA
❖ Ejemplo 5
Si en A = [-2,2] se define una relación xRy sii x2+y2=1
Determinar R
Obtener también su dominio y su imagen.
LA FRASE "JOSE TIENE 25 AÑOS" ES UNA
PROPOSICION
FALSO VERDADERO