Facultad de Ciencias Exactas, Ingenierı́a
y Agrimensura (FCEIA - UNR)
Tecnicatura Universitaria en Inteligencia Artificial
Lógica
Unidad 2: Relaciones de equivalencia. Relaciones de orden.
Definición:
Sean A y B conjuntos de un mismo universo, el producto cartesiano de A y B, denotado A × B, se
define como:
A × B = {(a, b) | a ∈ A, b ∈ B}
A los elementos de A × B los llamamos pares ordenados.
Propiedad:
Si A y B son conjuntos finitos, se tiene:
|A × B|= |A|.|B|
Ejemplo:
Sean A = {1, 2, 3} y B = {4, 5}
A × B = {(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}
Definición (generalización del producto cartesiano):
Sean A0 , . . . , An ⊆ U, el producto cartesiano de A0 , . . . , An , denotado A0 × . . . × An , se define como:
A0 × . . . × An = {(a0 , . . . , an ) | ai ∈ Ai , 0 ≤ i ≤ n}
Definiciones:
Sean A y B conjuntos de un mismo universo, una relación R de A a B es un subconjunto de A × B.
Si (x, y) ∈ R escribimos x R y.
Llamamos dominio de R al conjunto {x ∈ A/(x, y) ∈ R para algún y ∈ B}.
Llamamos conjunto imagen de R al conjunto {y ∈ B/(x, y) ∈ R para algún x ∈ A}.
Ejemplo:
Sean A = {1, 2, 3} y B = {4, 5, 6}. Los siguientes conjuntos son relaciones de A a B:
R1 = {(1, 4), (2, 5), (2, 6), (3, 4)}
R2 = {(1, 6)}
(x, y) ∈ R3 si x divide a y
Ejercicios:
Sean A = {1, 2, 3, 4, 5} y B = {2, 4, 6, 8}
2022 1/5
1. Determinar si los siguientes conjuntos son relaciones de A a B:
a. {(1, 1), (2, 2), (4, 6)}
b. {(5, 2), (5, 4), (5, 6), (5, 8)}
c. {(6, 1), (8, 2)}
2. Escribir las siguientes relaciones como pares ordenados:
a. (x, y) ∈ R si x ≤ y
b. (x, y) ∈ R si x + y = 6
Definiciones:
Una relación binaria sobre un conjunto A es un subconjunto de A × A.
Para estudiar las propiedades de una relación binaria puede ser útil representarla con una digráfica.
Digráfica de una relación:
1. Se dibuja un vértice por cada elemento de A.
2. Para cada (x, y) ∈ R se dibuja una flecha de x a y.
Ejemplo:
Sea X = {1, 2, 3, 4} y R definida como (x, y) ∈ R si x ≤ y
Definiciones: Sea R una relación binaria sobre un conjunto X, decimos que:
R es reflexiva si (x, x) ∈ R para todo x ∈ X.
R es simétrica si para todo x, y ∈ X, si (x, y) ∈ R entonces (y, x) ∈ R.
R es transitiva si para todo x, y, z ∈ X, si (x, y), (y, z) ∈ R entonces (x, z) ∈ R.
R es antisimétrica si para todo x, y ∈ X, si (x, y) ∈ R y x ̸= y entonces (y, x) ∈
/ R.
Ejemplos:
Las siguientes relaciones están definidas sobre {1, 2, 3, 4}
R1 = {(1, 1), (1, 2), (2, 2), (2, 1)}
• R1 no es reflexiva, pues (3, 3) ∈
/ R.
2022 2/5
• R1 es simétrica.
• R1 es transitiva.
• R1 no es antisimétrica, pues (1, 2) y (2, 1) ∈ R.
R2 = {(1, 1), (2, 2), (3, 3), (4, 4)}
• R2 es reflexiva.
• R2 es simétrica.
• R2 es transitiva.
• R2 es antisimétrica.
R3 = {(1, 4), (4, 2)}
• R3 no es reflexiva, pues (1, 1) ∈
/ R.
• R3 no es simétrica, pues (1, 4) ∈ R y (4, 1) ∈
/ R.
• R3 no es transitiva, pues (1, 4), (4, 2) ∈ R3 y (1, 2) ∈
/ R3 .
• R3 es antisimétrica.
Definiciones:
Una relación R sobre un conjunto A es una relación de equivalencia si es reflexiva, simétrica y
transitiva.
Dada una relación de equivalencia R en un conjunto A y un elemento a ∈ A, el conjunto R(a) se
llama clase de equivalencia de a, y se nota [a], es decir, [a] = {x ∈ A : (a, x) ∈ R}.
Ejemplos:
La relación R1 del ejemplo anterior no es de equivalencia ya que no es reflexiva.
La relación R2 del ejemplo anterior es de equivalencia.
En A = {1, 2, 3} tenemos la siguiente relación de equivalencia:
R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
Las clases de equivalencia de R son:
[1] = {x ∈ A : (1, x) ∈ R} = {1, 2}
[2] = {x ∈ A : (2, x) ∈ R} = {1, 2}
[3] = {x ∈ A : (3, x) ∈ R} = {3}
Observemos que [1] = [2], esto sucede siempre que dos elementos estén relacionados dado que
la relación es de equivalencia.
Propiedad:
Sean R una relación de equivalencia en un conjunto A y a, b ∈ A. Entonces:
(a, b) ∈ R si y solo si [a] = [b].
(a, b) ∈
/ R si y solo si [a] ∩ [b] = ∅.
2022 3/5
Ejemplo: Congruencia módulo m.
Sea R sobre el conjunto Z la siguiente relación de equivalencia:
(a, b) ∈ R si y solo si a − b es múltiplo de 2
Para esta relación en particular si (a, b) ∈ R notamos a = b(mod 2) y se dice que a y b son congruentes
módulo 2.
Veamos algunos ejemplos de elementos relacionados:
5 = 9(mod 2) ya que 5 − 9 = −4 y −4 es múltiplo de 2.
30 = −4(mod 2) ya que 30 − (−4) = 34 y 34 es múltiplo de 2.
¿6 = 5(mod 2)? No, pues 6 − 5 = 1 y 1 no es múltiplo de 2.
¿Cuáles son las clases de equivalencia de esta relación?
Se puede observar que todos los números pares están relacionados entre sı́ y que todos los impares
están relacionados entre sı́, por lo tanto solo tenemos dos clases de equivalencia:
[1] = {x ∈ Z/x es impar}
[2] = {x ∈ Z/x es par}
Esta relación se puede generalizar para otros números además del 2 y es una relación muy conocida
y utilizada en el ámbito de la programación.
En general, dado m ∈ Z fijo, se define la relación congruencia módulo m en Z como
a = b(mod m) si y solo si a − b es múltiplo de m
Dos elementos están relacionados si tienen el mismo resto en la división por m. Tendremos las si-
guientes clases de equivalencia [0], [1], [2], ..., [m − 1].
Definiciones:
Una relación R sobre un conjunto A es un orden parcial, o una relación de orden parcial, si R es
reflexiva, antisimétrica y transitiva. Al par (A, R), lo llamamos conjunto parcialmente ordenado.
Si (A, R) es un conjunto parcialmente ordenado, decimos que A es totalmente ordenado si para todos
x, y ∈ A ocurre que (x, y) ∈ R o (y, x) ∈ R. En este caso, decimos que R es un orden total.
Ejemplo:
Sea R = {(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)} definida sobre A = {a, b, c}
R es reflexiva.
R es antisimétrica.
R es transitiva.
Podemos afirmar que R es una relación de orden parcial y (A, R) es un conjunto parcialmente
ordenado.
2022 4/5
¿Es R un orden total? Si.
Ejemplos: Las siguientes relaciones sobre el conjunto A = {1, . . . , 10} son relaciones de orden parcial.
(x, y) ∈ R1 si x ≤ y
(x, y) ∈ R2 si x divide a y
Observemos que R1 es un orden total, ya que para todo x, y ∈ A, se tiene que x ≤ y o y ≤ x.
Ejercicio:
Sea X = {1, 2, 3, 4, 5}, trazar la digráfica de las siguientes relaciones y determinar si son reflexivas,
simétricas, transitivas o antisimétricas:
1. R1 = {(1, 1), (2, 3), (4, 4)}
2. R2 = {(1, 1), (2, 2), (2, 3), (3, 3), (3, 1), (4, 4)}
3. R3 = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)}
4. (x, y) ∈ R4 si x = y
5. (x, y) ∈ R5 si x > y
¿Cuáles son de equivalencia? ¿Cuáles son de orden parcial? ¿Son órdenes totales?
2022 5/5
