Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
CONTENIDO
1.1 Relaciones y sus propiedades
1.2 Relaciones de equivalencia y particiones.
1.3 Relaciones de orden parcial y retículos
1.4 Aplicaciones
Se dice que R es una relación de equivalencia si es:
Reflexiva
Simétrica
Transitiva
Por ejemplo, sea A={1,2,3,4,5,6}
R={(1,1),(1,2),(2,1),(2,2),(3,3), (4,4),(4,5),(5,4),(5,5),(6,6)}
GRAFO Y MATRIZ DE UNA RELACIÓN
R={(1,1),(1,2),(2,1),(2,2),(3,3), (4,4),(4,5),(5,4),(5,5),(6,6)}
1 2 3 4 5 6
1 1 1 0 0 0 0
2 1 1 0 0 0 0
3 0 0 1 0 0 0
4 0 0 0 1 1 0
5 0 0 0 1 1 0
6 0 0 0 0 0 1
1
2
3
4
5
6
1
2
3
4
5
6
EJERCICIOS
Sean los conjuntos A=B={1,2,3,4,5} y la relación
R={(1,1),(1,3),(1,4),(2,1),(2,4),(2,5),(3,3),(3,4),(3,5),
(4,2),(4,4),(5,1),(5,3),(5,5)}, obtenga el grafo y la
representación matricial correspondiente
Sean los conjuntos A=B={1,2,3,4} y la relación
R={(1,1),(1,2),(2,1),(2,4),(3,4),(4,2),(4,3),(4,4)},
obtenga el grafo y la representación matricial
correspondiente
CLASES DE EQUIVALENCIA Y PARTICIONES
Una relación de equivalencia tiene clases de equivalencia y éstas forman particiones.
Las clases de equivalencia son conjuntos que contienen a todos los elementos b B y que están relacionados con a A. Se indica:
[a] = {b| b B, aRb}
Una partición es un conjunto de clases de equivalencia. Es un subgrafo completo.
Deben estar contenidos todos los elementos del conjunto A.
La intersección entre las clases de equivalencia es vacia.
EJERCICIO:
Verifique que R es una relación de equivalencia.
Sean A=B={1,2,3,4,5} y R={(1,1),(1,2),(1,5),(2,1),
(2,2),(2,5),(3,3),(3,4),(4,3),(4,4),(5,1),(5,2),(5,5)}.
Obtenga la matriz y grafo correspondiente.
Como R es una relación de equivalencia, entonces
sus clases de equivalencia son:
[1] = {1,2,5} Todos los elementos relacionados con 1
[2] = {1,2,5} Todos los elementos relacionados con 2
[3] = {3,4}
[4] = {3,4}
[5] = {1,2,5}
De esto obtenemos
[1] = [2] = [5]
[3] = [4]
Dos particiones:
P ={{1,2,5},{3,4}}
EJERCICIO
Considera la siguiente relación sobre el conjunto
de los enteros:
R3={(a,b) | a=b o a=-b}
¿Es una relación de equivalencia?:
SOLUCIÓN
Simétrica:
Si a=b o a=-b, entonces b=a o b=-a.
Transitiva
a=+-b y b=+-c implica que a=+-c
Relación de equivalencia
Clase de equivalencia
Un entero es equivalente a sí mismo y a su negativo
en esta relación de equivalencia, entonces
[a] = {-a, a}.
Este conjunto contiene dos distintos enteres a menos que
a=0. Por ejemplo, [7] = {-7, 7} , [-5]={-5, 5}, y [0]={0}.
EJERCICIOS
Sea R una relación sobre el conjunto de los reales,
tal que aRb si y sólo si a-b es un entero.
Sea R una relación sobre el conjunto de cadenas
de letras del Español, tal que aRb si y sólo si
l(a)=l(b), donde l(x) es la longitud de la cadena x.
¿R es una relación de equivalencia?
SOLUCIÓN
Sea R una relación sobre el conjunto de los reales,
tal que aRb si y sólo si a-b es un entero.
Reflexiva
Porque a-a=0 es un entero para todo número real a, aRa
para todos los números reales a.
Simétrica
Suponemos que aRb. Entonces a-b es un entero, así b-a es
también un entero. Por lo tanto, bRa y R es simétrica.
Transitiva
Si aRb y bRc, entonces a-b y b-c son enteros. Por lo tanto, a-
c=(a-b)+(b-c) es también un entero. Por lo tanto, aRc.
Entonces, R es transitiva.
R es una relación de equivalencia.
Sea R una relación sobre el conjunto de cadenas
de letras del Español, tal que aRb si y sólo si
l(a)=l(b), donde l(x) es la longitud de la cadena x.
¿R es una relación de equivalencia?
Reflexiva
a es una cadena, l(a)=l(a). aRa, así R es reflexiva.
Simétrica
Suponga que aRb, así que l(a)=l(b). Entonces bRa, porque
l(b)=l(a). Por lo tanto, R es simétrica.
Transitiva
Suponga que aRb y bRc. Entonces l(a)=l(b) y l(b)=l(c). Por lo
tanto, l(a) = l(c), así aRc. R es transitiva.
R es una relación de equivalencia
EJERCICIOS
Sea R una relación sobre el conjunto de los
números reales tal que xRy si y sólo si x y y son
números cuya diferencia es menor que 1, es decir,
|x-y| < 1. Demuestra que no es una relación de
equivalencia.
CONJUNTO PARCIALMENTE ORDENADO
Sea R una relación en un conjunto A, y sea R una relación de
orden parcial. El conjunto A con R se llama conjunto
parcialmente ordenado y se denota como (A,R).
Dada una relación de orden parcial, esta puede representarse
mediante un grafo dirigido de orden parcial
b a
c
DIAGRAMAS DE HASSE 1. Los lazos de cada nodo pueden ser eliminados para simplificar el
grafo.
2. Si se eliminan las aristas que representan la propiedad transitiva.
3. Las flechas pueden omitirse y los círculos se reemplacen por punto.
El diagrama resultante de un orden parcial, mucho más simple que su
grafo dirigido, se llamará diagrama de Hasse de un orden parcial o de un
conjunto parcialmente ordenado.
b a
c
1
b a
c
b a
c
2 3
a
b
c
Diagrama de Hasse
DIAGRAMA DE HASSE
Es una representación gráfica simplificada de un conjunto
parcialmente ordenado finito. Esto se consigue eliminando
información redundante. Para ello se dibuja una arista
ascendente entre dos elementos solo si uno sigue a otro sin haber
otros elementos intermedios.
Ejemplo Sea S={a,b,c} y sea P el conjunto potencia de S, es decir
P={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}. Dibujar el diagrama de
Hasse del conjunto parcialmente ordenado con el orden .
{a}
{a,b,c}
{b,c} {a,c}
{a,b}
{b} {c}
sea el conjunto A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20,
30, 60} (todos los divisores de 60). Este conjunto
está ordenado parcialmente por la relación de
divisibilidad.
Diagrama de Hasse:
La relación "< " en Z + no es un orden parcial
porque no es reflexiva.
Las ordenes parciales mas comunes son las
relaciones >= y <= en Z y N .
EJERCICIOS 1. Dibujar el diagrama de Hasse de la relación a>=b
(en orden alfabético), donde a,b A, A={a,b,c,d,e,f}
2. Sea A={1,2,3,4,12}, Examine el orden parcial de la
divisibilidad en A (aRb si y sólo si b/a). Dibuja el
diagrama de Hasse.
12
4
3
2
1
Ejemplo
Sea S un conjunto no vacío. Definimos R como
(contenido en o igual a) P(S). Claramente, (P(S),
), es un conjunto de orden parcial.
A P(S), A A
A, B P(S), A B y B A => A = B
A, B, C, P(S), si A B y B C => A C
Por lo tanto, es una relación de orden
parcial sobre P(S) (conjunto potencia de S).
Ejemplo
Sea ≤ un orden parcial sobre el conjunto de los
enteros (Z), y a, b, c son enteros. Claramente
a ≤ a; a Z
Si a ≤ b y b ≤ a entonces, a = b, donde a,b Z
Si a ≤ b y b ≤ c entonces a ≤ c, donde a, b, c Z
Por lo tanto, (Z, ≤ ) es un conjunto de orden parcial
(poset).
Ejercicio
Dibuje el diagrama de Hasse que represente el
orden parcial {(a,b) | a|b} sobre {2, 4, 5, 10, 12,
20, 25}.
Nota: a|b = (división entera) a
b
Solución
La relación es:
R={ (2,2), (2, 4), (2, 12), (4,4), (4, 12), (5,5), (5,10), (5,
20), (5, 25), (10,10), (10, 20), (20,20) }
Elemento Maximal
Elemento Minimal
Elemento Máximo
Elemento Mínimo
Mínima Cota Superior
Máxima Cota Inferior
ELEMENTOS EXTREMOS DE LOS CONJUNTOS
PARCIALMENTE ORDENADOS
Sea (A,R) un conjunto parcialmente ordenado.
Un elemento xA se llama elemento maximal de A si para todo
aA, ax entonces xRa.
ELEMENTO MAXIMAL
a1
b1
a2
b2
a3
b3
Elementos
maximales a1,a2,a3
Ejemplo 1 : sea A el conjunto
parcialmente ordenado de todos los
números reales no negativos con el
orden parcial <=, en este caso no
existen elementos maximales.
a
b
c Ejemplo 2 : En este caso
el elemento maximal es
c
Sea (A,R) un conjunto parcialmente ordenado.
Un elemento yA se llama elemento minimal de A si para todo
bA, by entonces bRy.
ELEMENTO MINIMAL
a1
b1
a2
b2
a3
b3
Elementos
minimales b1,b2,b3
Ejemplo 1: sea A el conjunto
parcialmente ordenado de todos los
números reales no negativos con el
orden parcial <=, en este caso el cero es
el elemento minimal.
a
b
c
Ejemplo 2 : En este caso
el elemento minimal es
a
Sea (A,R) un conjunto parcialmente ordenado.
Un elemento xA se llama elemento máximo de A y es único si
para todo aA, entonces aRx existe.
ELEMENTO MÁXIMO
a
b
Elemento máximo a
Ejemplo 1: sea A el conjunto
parcialmente ordenado de todos
los números reales no negativos
con el orden parcial <=, en este
caso no existe un elemento
máximo.
a
b
c Ejemplo 2 : En este caso
el elemento máximo es c
Sea (A,R) un conjunto parcialmente ordenado.
Un elemento yA se llama elemento mínimo de A y es único, si
para todo aA, entonces yRa existe.
ELEMENTO MÍNIMO
a
Elemento mínimo b
Ejemplo 1: sea A el conjunto
parcialmente ordenado de todos
los números reales no negativos
con el orden parcial <=, en este
caso el cero es el elemento
mínimo.
b
a
b
c Ejemplo 2 : En este caso
el elemento mínimo es a
Sea (A,R) un conjunto parcialmente ordenado y B un subconjunto de A.
aA ,a es cota superior de B si bRa para todo bB.
a’A a’ es mínima cota superior(MCS)(LUB) de B si a’ es una cota superior de b y si a’Ra’’ para todas las demás a’’ cotas superiores de B.
Ejemplo: Sea A={a,b,c,d,e,f,g,h} con el siguiente diagrama de Hasse, determinar las cotas superiores y su mínima cota superior para los subconjuntos B1={a,b} y B2={c,d,e}.
MÍNIMA COTA SUPERIOR
b a
c
d e
f g
h
B1 tiene como cotas superiores a c,d,e,f,g,h
y como mínima cota superior tiene a c
B2 tiene como cotas superiores a f,g,h
y no tiene mínima cota superior porque no
existe fRg
Sea (A,R) un conjunto parcialmente ordenado y B un subconjunto de A.
yA ,y es cota inferior de B si yRb para todo bB.
y’A, y’ es máxima cota inferior(MCI)(GLB) de B si y’ es una cota inferior de B y si y’’Ry’ para todas las demás y’’ cotas inferiores de B.
Ejemplo: Sea A={a,b,c,d,e,f,g,h} con el siguiente diagrama de Hasse, determinar las cotas inferiores y su máxima cota inferior para los subconjuntos B1={a,b} y B2={c,d,e}.
MÁXIMA COTA INFERIOR
b a
c
d e
f g
h
B1 no tiene cotas inferiores y por ende no
tiene
máxima cota inferior
B2 tiene como cotas inferiores a a,b,c
y su máxima cota inferior es c
1. Dados los diagrama de Hasse determinar los maximales, minimales, máximo, mínimo.
Define dos subconjuntos de A y determina cotas inferiores, superiores, mínima cota superior, máxima cota inferior.
EJERCICIOS
a b
d e {a}
{a,b,c}
{b,c} {a,c}
{a,b}
{b} {c}
Ejercicio
Encontrar la mínima cota superior y máxima cota
inferior de los conjuntos {3, 9, 12} y {1, 2, 4, 5, 10} si
existen en el poset (Z+, |)
Solución
Encontrar la mínima cota superior y máxima cota inferior
de los conjuntos {3, 9, 12} y {1, 2, 4, 5, 10} si existen en el
poset (Z+, |)
Un entero es una cota inferior de {3,9,12} si 3, 9 y 12 son
divisibles por este entero. Tales enteros son 1 y 3
unicamente. Claramente 3 es la máxima cota inferior de
{3,9,12}.
Similarmente la máxima cota inferor para {1,2,4,5,10} es 1.
Un entero es una cota superior para {3, 9, 12} si es divisible
por 3, 9 y 12. Los enteros con esta propiedad son los
divisibles por la mínima cota superior de 3, 9 y 12, el cual
es 36. Es decir, 36 es la minima cota superior para el
conjunto {3, 9, 12}.
Similarmente 20 es la minima cota superior para el
conjunto {1,2,4,5,10}
Retícula (red o lattice)
El conjunto parcialmente ordenado (A,R) es una
retícula (red o lattice) si para cualquier x,yA la
MCS{x,y} (denotada x y) y MCI{x,y} (denotada
xy) existen.
Ejemplo 1 : sea A el conjunto parcialmente
ordenado de todos los números naturales con el
orden parcial ≤, en este caso
Para todo a,bN
MCS{a,b}=mínimo{a,b},
MCI{a,b}=máximo{a,b}
Por tanto es una retícula
Ejemplo 2, retícula
En este caso el diagrama de Hasse representa a los
divisores positivos de 20, y si cumple que sea una retícula
dado que:
1
2 5
4 10
20 CS{1,2} ={2,4,10,20}
MCS{1,2}={2}
CS{1,4} ={4,20}
MCS{1,4}={4}
CS{1,20} ={20}
MCS{1,20}={20}
CS{1,5} ={5,10,20}
MCS{1,5}={5}
CS{1,10} ={10,20}
MCS{1,10}={10}
CS{2,4} ={4,20}
MCS{2,4}={4}
CS{2,5} ={10,20}
MCS{2,5}={10}
CS{2,10} ={10,20}
MCS{2,10}={10}
CS{2,20} ={20}
MCS{2,20}={20}
CS{4,10} ={20}
MCS{4,10}={20}
CS{4,20} ={20}
MCS{4,20}={20}
CS{5,4} ={20}
MCS{5,4}={20}
CS{5,10} ={10,20}
MCS{5,10}={10}
CS{5,20} ={20}
MCS{5,20}={20}
CS{10,20} ={20}
MCS{10,20}={20}
CI{1,2} ={1}
MCI{1,2}={1}
CI{1,4} ={1}
MCI{1,4}={1}
CI{1,20} ={1}
MCI{1,20}={1}
CI{1,5} ={1}
MCI{1,5}={1}
CI{1,10} ={1}
MCI{1,10}={1}
CI{2,4} ={1,2}
MCI{2,4}={2}
CI{2,5} ={1}
MCI{2,5}={1}
CI{2,10} ={1,2}
MCI{2,10}={2}
CI{2,20} ={1,2}
MCI{2,20}={2}
CI{4,5} ={1}
MCI{4,5}={1}
CI{4,10} ={1,2}
MCI{4,10}={2}
CI{4,20} ={1,2,4}
MCI{4,20}={4}
CI{5,10} ={1,5}
MCI{5,10}={5}
CI{5,20} ={1,5}
MCI{5,20}={5}
CI{10,20} ={1,2,5,10}
MCI{10,20}={10}
Lattice
Un poset en el que cada par de elementos tiene
ambos una minima cota superior y una máxima
cota inferior se llama lattice.
Ejemplo
El poset ({1,2,4,8}, | ) es un lattice
El poset (P(S), ) es un lattice, para cualquier A S,
B S
A υ B = minima cota superior de A y B, ( sup{a,b}= a v b )
A ∩ B = máxima cota inferior de A y B, ( inf{a,b} = a ˄ b )
Propiedad
Retículo
Si aRb <-> a v b = b y a ˄ b= a
Es decir, siempre existen a v b y a ˄ b entre los
elementos relacionados. Sólo hay que revisar, los que
son incomparables.
Ejemplo:
Sup(2,3)=6 Inf(2,3)=1
Sup(3,4)=12 Inf(3,4)=1
Sup(4,6)=12 Inf(4,6)=2
Es una retícula, porque todos tienen supremo (Sup) e
ínfimo (Inf).
Ejercicio
Sea (A; R) con A={serpiente, pollito, canario, gato,
león, araña, hormiga } y la relación “tiene menos
patas que o es el mismo animal que” ¿El
diagrama de hasse es un lattice?
Solución
No es un lattice, porque
No hay Sup(pollito, canario)
Cotas superiores(pollito, canario)={gato, león,
hormiga, araña}, pero no hay forma de definir
la inferior cota superior, es decir, ninguna
precede a todas.