Y binarias [G4.1]. Composición [H4.1]. Clausuras [H4.1]

conjuntos y relaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

11


CONTENIDONotación de Conjuntos [G3.1]. Relaciones entre conjuntos[G3.1]. Operaciones sobre conjuntos [G3.1]. Relaciones binarias [G4.1]. Composición [H4.1]. Clausuras [H4.1].Problemas de caminos [H4.1]. Relaciones de equivalencia[H4.1]. Particiones [H4.1]. Generación de relaciones de equivalencia [H4.1]. Relaciones de orden [G4.1]. Órdenes parciales [G4.1]. Reticulado [M2]. Reticulado con primer y último elemento [M2]. Ordenamiento Topológico [G4.2].Órdenes bien fundados [H4.3].

GERSTING, JUDITH L. “Mathematical Structures for Computer Science: A Modern Approach to Discrete Mathematics”. W H Freeman & Co, 2006.

HEIN, JAMES. “Discrete Structures, Logic and Computability”. Jones and Bartlett Publishers 1995

MONTEIRO, LUIZ. “Algebras de Boole”. Universidad Nacional del Sur, 2002.




22

teoría de conjuntos

Un conjunto es una colección de elementos u objetos y un elemento es un miembro de un conjunto.

Tradicionalmente, los conjuntos se notan utilizando letras mayúsculas y los elementos utilizando letras minúsculas.

El símbolo ∈ significa “pertenece” y es usado para representar el hecho de que un elemento pertenece a un conjunto particular:

a∈A significa que el elemento a pertenece al conjunto A.

b∉A significa que b no es un elemento de A.Las llaves {} son utilizadas para indicar un conjuntoA = {2, 4, 6, 8, 10} 3∉A y 2∈A




33


Los elementos del conjunto no tienen impuesto un orden. Listar elementos más de una vez es redundante.

Dos conjuntos son iguales si y sólo si contienen los mismos elementos.

Por lo tanto, A = B significa (∀x)[(x ∈ A → x ∈ B) ∧ (x ∈ B → x ∈ A)]




44


Conjunto finito e infinito: descripto por el número de elementos en un conjunto.

Los miembros de conjuntos infinitos no pueden ser listados, pero se puede indicar un patrón para listar elementos.

EjemploS = {x | x es un entero positivo par} o utilizando una notación más formal:

S = {x | P(x)} significa(∀x)[(x ∈ S → P(x)) ∧ (P(x)→ x ∈ S)] donde P(x) indica una propiedad (predicado) de x(ejemplo PositivoPar(x)).

Por lo tanto, todo elemento de S tiene la propiedad P y todo aquello que tiene la propiedad P es un elemento de S.




55

teoría de conjuntos - ejemplos

Describir cada uno de los siguientes conjuntos listando sus elementos:

{x | x es un mes con exactamente 30 días}{Abril, Junio, Septiembre, Noviembre}

{x | x es un entero y 4 < x < 9}{5, 6, 7, 8}

¿Cuál es la propiedad P (predicado) para cada uno de los siguientes conjuntos? {1, 4, 9, 16}{x | x es uno de los primeros cuatro cuadrados

perfectos}{2, 3, 5, 7, 11, 13, 17, ….}

{x | x es un número primo}




66

conceptos básicos de teoría de conjuntos

Un conjunto que no tiene miembros es llamado nulo o vacío y estárepresentado mediante ∅ o {}.

Notar que ∅ es diferente de {∅}. El último es un conjunto con 1 elemento, que es el elemento vacío.




77

conceptos básicos de teoría de conjuntos

Algunas notaciones útiles para definir conjuntosN = conjunto de enteros no negativos (notar

que asumimos 0 ∈ N).Z = conjunto de todos los enteros.Q = conjunto de todos los números

racionales.R = conjunto de todos los números reales.C = conjunto de todos los números

complejos.




88

intervalos abiertos y cerrados

{x ∈ R | -2 < x < 3}Denota el conjunto que contiene todos los

números reales entre -2 y 3. Este es un intervalo abierto, lo que significa que los puntos -2 y 3 no están incluidos.

{x ∈ R | -2 ≤ x ≤ 3}Conjunto similar pero en un intervalo cerrado.

Incluye todos los números del intervalo abierto descripto arriba y los extremos.




99

relaciones entre conjuntos

Dado los conjuntos A y B, A se dice subconjunto de B si y sólo si todo elemento de A es también elemento de B.

Simbólicamente: A ⊆ B ⇔ (∀x), si x ∈ A, entonces x ∈ B.Si A ⊆ B y A ≠ B, entonces existe al menos un

elemento de B que no es elemento de A. En ese caso se dice que A es un subconjunto propio de B.

Simbólicamente se denota A ⊂ B




1010

cardinalidad

La cardinalidad de un conjunto es el número de elementos dentro del conjunto.

La cardinalidad de un conjunto S se denota |S|.




1111

conjunto de conjuntos

A partir de cada conjunto podemos generar muchos subconjuntos. El conjunto cuyos elementos son todos estos subconjuntos se conoce como el conjunto potencia.

Para un conjunto S, usamos ℘(S) para denotar el conjunto potencia de S.

Para el conjunto S = {1, 2, 3} ; ℘(S) = {∅ ,{1}, {2}, {3}, {1,2}, {1,3}, {2,3},

{1,2,3}}Para un conjunto con n elementos, el conjunto

potencia tiene 2n elementos.




1212

operaciones sobre conjuntos

Un par ordenado de elementos se escribe (x,y)Dos pares ordenados (a,b) y (c,d) son

iguales si y sólo si a = c y b = d.Si S = {2,3} los pares ordenados del

conjunto son (2,2), (2,3), (3,2), (3,3).Si para todo x, y ∈ S, x ° y ∈ S, entonces S se

dice cerrado bajo la operación °.La operación binaria ° es una operación

binaria sobre un conjunto S si para cada par ordenado (x,y) de elementos de S, x ° yexiste, es único, y es un miembro de S.




1313

operaciones binarias sobre un conjunto

Ejemplosx ° y = x/y; S =conjunto de enteros positivos

S no es cerrada bajo división (1/2 no es un entero positivo).

x ° y = x/y; S =conjunto de los racionales positivosx ° y = xy; S = R

00 no está definidox ° y = máximo de x e y; S = Nx ° y = x + y; S = conjunto de números de Fibonacci S={0,

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … } S no es cerrado bajo suma ya que, 1+3 = 4 y 4 no es

un número de Fibonacci

X

X

X

√

√




1414

operaciones sobre conjuntos

Sean A, B ∈ ℘(S). La unión de los conjuntos A y B, denotada A ∪ B es el conjunto que contiene todos los elementos que están en el conjunto A o en el conjunto B. Es decir A ∪ B = {x | x ∈ A ∨ x ∈ B}. La intersección de los conjuntos A y B, denotada A ∩ B contiene todos los elementos que son comunes a ambos conjuntos, es decir A ∩ B = {x | x ∈ A ∧ x ∈ B}




1515

conjuntos disjuntos, universal y diferencia

Dados los conjuntos A y B, si A ∩ B = ∅, entonces A y B son conjuntos disjuntos. En otras palabras, no existen elementos en A que están también en B.Para un conjunto A ∈ ℘(S),el complemento denotado ~A o A′, es el conjunto de todos los elementos que no están en A.

A′ = {x | x ∈ S ∧ x ∉ A }La diferencia A-B es el conjunto de elementos en A que no están en B. Es también conocido como el complemento de B relativo a A.

A - B = {x | x ∈ A ∧ x ∉ B }Notar que A – B = A ∩ B′ ≠ B – A




1616

producto cartesiano

El producto cartesiano de A y B denotado simbólicamente A × B se define como

A × B = {(x,y) | x ∈ A ∧ y ∈ B }EjemploSea A = {a, b, c} y B = {1, 2, 3}A × B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c,

2), (c, 3)}¿Es A × B = B × A?El producto cartesiano de un conjunto consigo mismo se

denota A × A o A2

Generalizando:An representa el conjunto de todas las n-tuplas (o n-uplas)

(x1, x2, …, xn) de elementos en A.




1717

identidades básicas de conjuntos

Dados los conjuntos A, B, y C, y un conjunto universal S y el conjunto vacío ∅, la siguientes propiedades se verifican:

Propiedad conmutativa (pc)A ∪ B = B ∪ A A ∩ B = B ∩ A

Propiedad asociativa (pa)A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∩ (B ∩ C) = (A ∩ B) ∩ C

Propiedad distributiva (pd)A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

Propiedades de identidad (pi)∅ ∪ A = A ∪ ∅ = A S ∩ A = A ∩ S = A

Propiedades de complemento (comp)A ∪ A′ = S A ∩ A′ = ∅




1818

más identidades de conjuntos

Ley de doble complemento(A′)′ = A

Leyes de idempotenciaA ∪ A = A A ∩ A = A

Leyes de absorciónA ∪ (A ∩ B) = A A ∩ (A ∪ B) = A

Representación alternativa de la diferenciaA - B = A ∩ B′

Inclusión en uniónA ⊆ A ∪ B B ⊆ A ∪ B

Inclusión de intersecciónA ∩ B ⊆ A A ∩ B ⊆ B

Propiedad transitiva de subconjuntos Si A ⊆ B, y B ⊆ C, entonces A ⊆ C




1919

identidades de conjuntos

EjemploUsar las identidades de conjuntos para probar

[A ∪ (B ∩ C)] ∩ ([A′ ∪ (B ∩ C)] ∩ (B ∩ C)′) = ∅

Prueba:[A ∪ (B ∩ C)] ∩ ([A′ ∪ (B ∩ C)] ∩ (B ∩ C)′) =([A ∪ (B ∩ C)] ∩ [A′ ∪ (B ∩ C)]) ∩ (B ∩ C)′ = (pa)([(B ∩ C) ∪ A] ∩ [(B ∩ C) ∪ A′]) ∩ (B ∩ C)′= (pc)[(B ∩ C) ∪ (A ∩ A′)] ∩ (B ∩ C)′ = (pd)[(B ∩ C) ∪ ∅] ∩ (B ∩ C)′ = (comp.)(B ∩ C) ∩ (B ∩ C)′ = (pi)∅ (comp.)




2020

relaciones binarias

La notación x ρ y implica que el par ordenado (x, y) satisface la relación ρ.

Ejemplo:Sea S = {1, 2, 4}, entonces el producto

Cartesiano de S con sí mismo es: S × S = {(1,1), (1,2), (1,4), (2,1), (2,2), (2,4), (4,1), (4,2), (4,4)}

El subconjunto de S × S que satisface la relaciónx ρ y ↔ x = 1/2y, es: {(1, 2), (2, 4)}




2121

relaciones binarias

Una relación binaria sobre S es un subconjunto de S × S

Entonces, sabemos que una relación binaria ρ es un subconjunto con la propiedad:

x ρ y ↔ (x, y) ∈ ρEjemplo:Sea ρ definida sobre S tal que x ρ y ↔ x + y es impar, donde S = {1, 2}

ρ es {(1,2), (2,1)}.




2222

relaciones sobre múltiples conjuntos

Dados n conjuntos S1, S2, …., Sn para n > 2, una relación n-aria sobre S1 × S2 × … × Snes un subconjunto de S1 × S2 × … × Sn.

EjemplosSea S = {1, 2, 3} y T = {2, 4, 7}.Sea x ρ y ↔ x = y/2.ρ = {(1,2), (2,4)}.

Sea S = {2, 4, 6, 8} y T = {2, 3, 4, 6, 7}.Cuál es el conjunto que satisface la relación

x ρ y ↔ x = (y + 2)/2.El conjunto es {(2,2), (4,6)}.




2323

tipos de relaciones

Uno a uno: Si cada primer componente y cada segundo componente aparece sólo una vez en la relación. Uno a muchos: Si el mismo primer componente aparece con más de un segundo componente.Muchos a uno: Si un segundo componente aparece con más de un primer componente. Muchos a muchos: Si al menos un primer componente aparece con más de un segundo componente y al menos un segundo componente aparece con más de un primer componente.




2424

tipos de relaciones

EjemplosSea S = {2, 5, 7, 9}. Identificar el tipo de

las siguientes relaciones:

{(5,2), (7,5), (9,2)}{(2,5), (5,7), (7,2)}{(7,9), (2,5), (9,9), (2,7)}

muchos a unouno a uno

muchos a muchos




2525

propiedades de las relaciones binarias

Sea ρ una relación binaria sobre un conjunto S. Entonces:

ρ reflexiva significa(∀x) (x∈S → (x,x)∈ ρ)ρ simétrica significa (∀x)(∀y) (x∈S ∧ y∈S ∧ (x,y) ∈ ρ → (y,x)∈ ρ)ρ transitiva significa(∀x)(∀y)(∀z) (x∈S ∧ y∈S ∧ z∈S ∧ (x,y)∈ρ ∧

(y,z)∈ρ → (x,z)∈ρ)ρ antisimétrica significa(∀x)(∀y) (x∈S ∧ y∈S ∧(x,y) ∈ ρ ∧ (y,x)∈ ρ → x = y)




2626

propiedades de las relaciones binarias

EjemploConsidere la relación ≤ sobre el conjunto de

números naturales N.¿Es reflexiva? Sí, dado que para cada entero no negativo a,

a ≤ a.¿Es simétrica? No, dado que a ≤ b no implica b ≤ a.¿Es transitiva? Si, dado que si a ≤ b y b ≤ c, entonces a ≤ c.




2727

composición de relaciones

Las relaciones pueden ser usualmente definidas en término a otras relaciones

“Es nieto de” puede definirse en términos de “Es hijo de”

Si ρ1 es una relación binaria sobre A×B y ρ2 es una relación binaria sobre B×C, entonces la composición de ρ1 y ρ2 es la relación binaria ρ1◦ρ2 sobre A × C definida como a(ρ1◦ρ2 )c si y sólo si aρ1b y bρ2c para algún b∈B.




2828

composición de relaciones

Si ρ es una relación binaria sobre A×Ausamos ρn para denotar la composición de ρ consigo misma n veces.

EsNietoDe = EsHijoDe2

Más precisamenteρ0 ={(a,a)|a∈A}ρn+1 = ρn ◦ρ




2929

clausuras de relaciones

Una relación binaria ρ* sobre el conjunto S es la clausura de una relación ρsobre S con respecto a la propiedad Psi:ρ* tiene la propiedad Pρ ⊆ ρ*ρ* es un subconjunto de cualquier otra

relación sobre S que incluye ρ y tiene la propiedad P




3030

clausuras de relaciones

EjemploSea S = {1, 2, 3} y ρ = {(1,1), (1,2), (1,3), (3,1),

(2,3)}.No es reflexiva, transitiva, ni simétrica.La clausura reflexiva de ρ es {(1,1),(1,2),(1,3),

(3,1), (2,3), (2,2), (3,3)}.La clausura simétrica de ρ es

{(1,1), (1,2), (1,3), (3,1), (2,3), (2,1), (3,2)}.La clausura transitiva de ρ es

{(1,1), (1,2), (1,3), (3,1), (2,3), (3,2), (3,3), (2,1), (2,2)}.




3131

ejercicios

¿Cuáles de los siguientes pares pertenecen a la relación binaria ρ sobre N?x ρ y ↔ x + y < 7;

(1,3), (2,5), (3,3), (4,4)x ρ y ↔ 2x + 3y = 10;

(5,0), (2,2), (3,1), (1,3)Mostar la región del plano cartesiano

correspondiente a la relación ρ sobre R2:x ρ y ↔ x2 + y2 ≤ 25x ρ y ↔ x ≥ y




3232

ejercicios

Encontrar la clausura reflexiva, simétrica y transitiva de la relación ρ = {(a,a), (b,b), (c,c), (a,c), (a,d), (b,d), (c,a), (d,a)} sobre el conjunto S = {a, b, c, d}.

Identificar cada una de las siguientes relaciones sobre N como una a una, una a muchas, muchas a una o muchas a muchas:ρ = {(12,5), (8,4), (6,3), (7,12)}ρ = {(2,7), (8,4), (2,5), (7,6), (10,1)}ρ = {(1,2), (1,4), (1,6), (2,3), (4,3)}




3333

ejercicios

Sea S = {0, 1, 2, 4, 6}. ¿Cuáles de las siguientes relaciones tienen la propiedad reflexiva, simétrica, antisimétrica y transitiva? Encontrar las clausuras reflexiva, simétrica y transitiva.

ρ={(0,0),(1,1),(2,2), (4,4), (6,6), (0,1), (1,2),(2,4),(4,6)}

ρ ={(0,0),(1,1),(2,2),(4,4),(6,6),(4,6),(6,4)}ρ = {(0,1),(1,0),(2,4),(4,2),(4,6),(6,4)}




3434

grafos

Un grafo es un conjunto no vacío de nodos y un conjunto de arcos.

Trabajaremos solamente con grafos con un número finito de nodos y arcos.

Ejemplo




3535

definición formal de grafo

Un grafo es una tripla ordenada (N, A, g) donde:N = es un conjunto no vacío de nodosA = es un conjunto de arcosg = es una función que asocia con cada arco

un par ordenado x-y de nodos, llamados extremos.

Es importante notar que existen diferentes maneras de definir el concepto de grafo.




3636

grafos dirigidos

Un grafo dirigido (di-grafo) es una tripla ordenada (N, A, g) donde:N = es un conjunto no vacío de nodosA = es un conjunto de arcosg = es una función que asocia con cada arco

una par ordenado (x, y) de nodos donde x es el punto inicial e y es el punto terminal.




3737

grafos dirigidos

EjemploEn este ejemplo hay cuatro nodos y cinco arcos. N ={1,2,3,4}A = {a1,a2,a3,a4,a5}g(a1) = (1, 2)g(a2) = (1, 4)g(a3) = (1, 3)g(a4) = (3, 1)g(a5) = (4, 4)




3838

otros tipos de grafos

Grafo etiquetado: un grafo cuyos nodos tienen asociada información tal como los nombres de ciudades en un mapa aéreo.

Grafo ponderado: Un grafo donde cada arco tiene asociado un valor numérico o peso. Por ejemplo, un grafo donde se indica las distancias de diferentes rutas en un mapa aéreo.

°




3939

matriz de adyacencia

Dado un grafo con n nodos n1, n2, ... , nn. podemos formar una matriz de n × n donde la entrada i,j es el número de arcos entre los nodos ni y nj. Esta matriz se denomina matriz de adyacencia del grafo. La entrada aij = p cuando existen p arcos entre ni y nj

A =

1 1 0 00 0 1 10 1 0 00 0 1 0

⎡

⎣

⎢ ⎢ ⎢ ⎢

⎤

⎦

⎥ ⎥ ⎥ ⎥




4040

grafos dirigidos y matrices booleanas

Nos concentraremos en grafos dirigidos, no ponderados y sin arcos paralelos.

La matriz de adyacencia de estos grafos será una matriz booleana (elementos 0s y 1s) de dimensiones n × n, no necesariamente simétrica.

Existe una correspondencia uno a uno:

Grafos dirigidoscon n nodos,

sin arcos paralelos

Matrices Booleanas

de dimensión n×n




4141

grafos dirigidos y relaciones binarias

Dado un grafo dirigido G con n nodos y sin arcos paralelos donde N es el conjunto de nodos, podemos definir una relación binaria ρ como sigue :Si ni, nj ∈ N entonces

ni ρ nj ↔ existe un arco en G de ni a nj..

Dada una relación binaria ρ sobre un conjunto S de n elementos podemos construir un grafo G dirigido con n nodos y sin arcos paralelos como sigue:Si ni, nj ∈ S entonces

existe un arco en G de ni a nj.. ↔ ni ρ nj




4242

grafos dirigidos y relaciones binarias

Para el grafo G1obtenemos la siguiente relación {(1, 2), (1, 3), (3, 3), (4, 1), (4, 2), (4, 3)}.

Para el conjunto N ={1, 2, 3, 4} y la relación binaria {(1, 4), (2, 3), (2, 4), (4, 1)} sobre N, obtenemos el siguiente grafo G2

G1

G2




4343

correspondencias

matriz deadyacencia

relación binaria

grafo dirigido sin arcos paralelos




4444

composición y multiplicación booleana

Recordemos la composición de una relación consigo misma:

ρ0 ={(a,a)|a∈A}ρn+1 = ρn ◦ρDe manera análoga, dada una matriz de

adyacencia M podemos operarla consigo misma utilizando el productobooleano ◎:

M(0) = IM(n+1) = M(n) ◎ M donde [A◎B]i,j= )B(A jk,ki,

m1k ∧∨ =




4545

clausuras

reflexivaρ U ρ0

M v M(0)

simétricaρ U ρ c donde ρ c ={(x,y)|(y,x)∈ ρ } (se

denomina conversa de ρ )M v MT

transitiva (caso finito, n elementos)ρ U ρ 2 U ρ 3 U … U ρ n

M v M(2) v M(3) v … v M(n)




4646

matriz de alcance y clausura transitiva

Dado un grafo podemos utilizar su matriz de adyacencia para calcular caminos de diferentes longitudes.

Matriz de adyacencia




4747





4848


R=A(1) v A(2) v A(3) v A(4) v A(5)




4949

algoritmo de Warshall: clausura transitiva

Sea M la matriz de adyacencia para la relación ρ.El algoritmo de Warshall reemplaza M con la matriz

de adyacencia correspondiente a la clausura transitiva de ρ .

Warshall(matriz Booleana M de n × n)for k = 1 to n do

for i = 1 to n dofor j = 1 to n doM[i, j] = M[i, j] ∨ (M[i, k ] ∧ M[k, j ])

end forend for

end for




5050

algoritmo de Warshall: clausura transitiva

Obtener la clausura transitiva para el siguiente grafo utilizando el algoritmo de Warshall:

= M4= M5




5151

matriz de adyacencia ponderada

4

1

10

6

27

⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢

⎣

⎡

∞∞∞∞∞∞∞∞∞∞∞∞∞∞

07102010

6040

Grafo ponderado

Matriz de adyacenciaponderada




5252

distancias mínimas

Sea M una matriz de adyacencia ponderada de un grafo G.

Podemos calcular las distancias mínimas como sigue:

n=1,M(n)= MRepetir

Para cada par de nodos i,j, elegimos el camino más conveniente:M(n+1)

i,j=min(M(n)i,j, mink(M(n)

i, k + M(n)k, j))

n=n+1hasta que M(n+1) =M(n)




5353

distancias mínimas

Para el siguiente grafo ponderado calcular las distancias mínimas

G2.5

0.5

1.5

10

20⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

∞∞∞∞∞

∞∞

=

05.20

5.1100205.00

M )1(

)3()2( M

05.20

5.110045.00

M =

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

∞∞∞∞∞

∞∞

=




5454

algoritmo de Floyd: distancias mínimas

Sea M la matriz de adyacencia para un grafo ponderado.

El algoritmo de Floyd reemplaza M con la matriz de adyacencia correspondiente a la distancia más corta entre los vértices

Floyd(matriz Ponderada M de n × n)for k = 1 to n do

for i = 1 to n dofor j = 1 to n doM[i, j] = min(M[i, j] , M[i, k ] + M[k, j ])

end forend for

end for




5555


EjemploPara la matriz de adyacencia ponderada M obtenemos la matriz de adyacencia M* representando las distancias mínimas

⎥⎥⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢⎢⎢

⎣

⎡

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞

∞

=

05040

0300300

102010100

M

⎥⎥⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢⎢⎢

⎣

⎡

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞

=

0545040

0300300

10154010100

M*




5656


EjercicioUsar el algoritmo de Floyd para encontrar la matriz de distancias mínimas correspondiente a los siguientes grafos :

4

1

10

6

212

G2

G1

1

4

7 5

11 2

3 4

G3

2.5

0.5

1.5

10

20




5757

relación de equivalencia (repaso)

Una relación binaria sobre un conjunto Sque es reflexiva, simétrica y transitiva se llama relación de equivalencia sobre S.

EjemplosSobre N, x ρ y ↔ x + y es par.Sobre {1, 2, 3},

ρ ={(1,1), (2,2), (3,3), (1,2), (2,1)}.




5858

particiones de un conjunto (repaso)

Una partición P de un conjunto S es una colección de subconjuntos Ai ⊆ S, no vacíos y disjuntos, cuya unión es igual a S.P ={A1,A2,A3,…}1. Ai ≠∅ y Ai ⊆ S. 2. La unión de todos los Aies igual a S. 3. Ai ∩ Aj = ∅, para todo Ai, Aj ⊆ S, tales que i ≠ j.

S .h

.g.a

.b

.c .e

.f

.i

.d




5959

clases de equivalencia (repaso)

Sea ρ una relación de equivalencia sobre S y a ∈ S, entonces [a] es el conjunto de elementos de S con los que a se relaciona, y es llamado clase de equivalencia de a:

[a] = {b ∈ S | aρ b}Ejemploρ = {(a,a), (b,b), (a,b), (b,a), (c,c),(d,d),(c,d),(d,c), (e,e),(f,f),(e,f),(f,e), (g,g), (h,h),(i,i),(h,i),(i,h)}[a]={a,b}, [c]={c,d},[e]={e,f}, [g]={g}, [h]={h,i}

S .h

.g.a

.b

.c .e

.f

.i

.d




6060


EjerciciosPara las siguientes relaciones de

equivalencia, describir las correspondientes clases de equivalencia

1. x ρ y si y sólo si x es paralela a y o x coincide con y (sobre las rectas)

2. Sobre los naturales, x ρ y si y sólo six=y.

3. Sobre los reales, x ρ y si y sólo si |x|=|y|




6161


Ejercicios (continuación)4. Sea S={a/b | a,b son enteros, b <>0}.

Definir una relación de equivalencia sobre S y mostrar que es efectivamente una relación de equivalencia.

5. Un entero x es congruente con y módulo 4, simbolizado x ≡4y si y sólo sí x-y es múltiplo de 4. Mostrar que la relación ≡4 es una relación de equivalencia.




6262

relaciones de equivalencia y particiones (repaso)

Teorema:Si ρ es una relación de equivalencia

sobre S, entonces ρ induce una partición Pρ sobre S. Recíprocamente, toda partición P sobre S induce una relación de equivalencia ρP .

Ejercicio: Demostrar el teorema anterior




6363

particiones de un conjunto (repaso)

Ejercicio¿Qué relación ρ determina las siguientes

cuatro clases de equivalencia?[0] = {... , -8, -4, 0, 4, 8,...} [1] = {... , -7, -3, 1, 5, 9,...} [2] = {... , -6, -2, 2, 6, 10,...} [3] = {... , -5, -1, 3, 7, 11,...}




6464

conjunto cociente (repaso)

Sea ρ una relación de equivalencia. Definimos para todo a ∈ S,

[a]ρ ={b∈S| (a,b) ∈ ρ }[a]ρ es la clase de equivalencia de a,

según la relación ρEl elemento a ∈ [a]ρ se dice un

representante de la clase de equivalencia [a] ρ




6565

conjunto cociente (repaso)

El conjunto cociente S/ρ de S por una relación de equivalencia ρ es el conjunto de las clases de equivalencia según la relación ρ.

S .h

.g.a

.b

.c .e

.f

.i

.d

S/ρ .[h]ρ

.[g] ρ.[a]ρ

.[c]ρ .[e]ρ




6666

aplicación canónica (repaso)

La función que manda cada elemento de S a su clase de equivalencia se llama aplicación canónica

S .h

.g.a

.b

.c .e

.f

.i

.d

S/ρ .[h]ρ

.[g] ρ.[a]ρ

.[c]ρ .[e]ρ




6767

generación de relaciones de equivalencia

Pregunta:¿Dada un relación ρ , cómo se genera la

menor relación de equivalencia ρ’ que contiene a ρ ?

Respuesta:Obtenemos la clausura reflexiva,

simétrica y transitiva de ρ.




6868


Usamos r(ρ), s(ρ) y t(ρ) para referirnos a la clausura reflexiva, simétrica y transitiva de ρ respectivamente.

Probar las siguientes propiedades:1. r(t(ρ)) = t(r(ρ)) 2. r(s(ρ)) = s(r(ρ)) 3. s(t(ρ)) ⊆ t(s(ρ))




6969


Ejercicio:Sea A ={a,b,c} y ρ={(a,b),(a,c),(b,b)}.

Obtener t(s(r(ρ))). Obtener s(t(r(ρ))). ¿Cuáles de las relaciones de arriba es una relación de equivalencia?




7070

relación de orden parcial

Una relación binaria sobre un conjunto S que es reflexiva, antisimétrica y transitiva se llama relación de orden parcial sobre S.

EjemplosSobre N, x ρ y ↔ x ≤ y.Sobre {0,1}, x ρ y ↔ x = y2 ,

ρ = {(0,0), (1,1)}.Sobre enteros positivos, x ρ y ↔ x divide a

y.Sobre S = {a, b, c, d, e, f}

ρ = {(a,a), (b,b), (c,c), (d,d), (e,e), (f, f), (a,b), (a,c), (a,d), (a,e), (d,e)},




7171

órdenes estrictos y no estrictos

orden estricto x < y si y sólo si x ≤ y y x ≠ yorden no estricto o reflexivox ≤ y si y sólo si x < y o x = y

Observación: la relación < se puede definir en función de la relación ≤ y viceversa




7272

órdenes parciales

Un conjunto arbitrario parcialmente ordenado se denota (S, ≤).

En casos particulares, ≤ puede representar la relación de “menor o igual”, “subconjunto”“divide”, etc.

Sea (S, ≤). un conjunto ordenado. Se dice que el elemento b ∈ S cubre al elemento a ∈ S si

1) a < b;2) No existe ningún elemento x ∈ S tal que

a < x < b.




7373

diagrama de Hasse

Los diagrama de Hasse son diagramas utilizados para representar visualmente conjuntos parcialmente ordenados con un número finito de elementos.

Construyendo Diagramas de Hasse:Dado un conjunto ordenado finito (S,≤):Cada elemento de S es representado por

un nodo del diagrama.Si b ∈ S cubre al elemento a ∈ S, el nodo b

se coloca por arriba del nodo a y ambos nodos se unen por un segmento de extremos a y b.




7474

b

a

cd

e

f

diagrama de Hasse

EjemploSea S = {a, b, c, d, e, f} ρ = {(a,a), (b,b), (c,c),

(d,d), (e,e), (f, f), (a, b), (a,c), (a,d), (a,e), (d,e)}

ρ a b c d e fabcdef




7575

diagramas de Hasse

Ejemplo:Sea A={a,b,c,d} S = ℘ (A) y ρ la relación ⊆

{d}

{c,d}{a,b}

{a}

{a,c}{b,c}

{b}

{b,d}

{c}

{a,d}

{a,c,d}{a,b,d}{a,b,c} {b,c,d}

{a,b,c,d}

{}




7676

diagrama de Hasse

Ejercicio¿Cuál es la relación de orden parcial ρcorrespondiente al siguiente diagrama de Hasse sobre el conjunto S={0,1,a,b,c}?




7777

diagrama de Hasse

EjercicioDar ejemplos de conjuntos S y

relaciones ρ para los siguientes diagramas de Hasse

(a) (b) (c) (d)




7878

no son diagramas de Hasse

Notar: las siguientes figuras no son diagramas de Hasse

¿Por qué?a

b

d

c

a b

cd

e




7979

elementos comparables e incomparables

Los elementos x e y se dicen comparables si x ≤ y o y ≤ x.

Si x e y no son comparables se dicenincomparables.

Ejemplo:a y c son comparables0 es comparable con todosa y b son incomparablesa y d son incomparables

a b

c d

0




8080

cadenas y anticadenas

Una cadena es un conjunto parcialmente ordenado en el que todo par de elementos es comparable.

Una anticadena es un conjunto parcialmente ordenado en el que todos los elementos son incomparables.




8181


También llamamos cadena a un subconjunto de un conjunto parcialmente ordenado que a su vez es una cadena.

Ejemplo

{d}

{c,d}{a,b}

{a}

{a,c}{b,c}

{b}

{b,d}

{c}

{a,d}


{a,b,c,d}

{}




8282


Y llamamos anticadena a un subconjunto de un conjunto parcialmente ordenado que a su vez es una anticadena.

Ejemplo

{d}

{c,d}{a,b}

{a}

{a,c}{b,c}

{b}

{b,d}

{c}

{a,d}


{}

{a,b,c,d}




8383

elementos especiales

Un elemento m de un conjunto ordenado (S,≤) se dice un elemento maximal (o máximo) de S si:

Si x ∈ S es tal que m ≤ x entonces x = mEjemplos

b

a

c

e

d b

a

c

e

d

d

a

b c




8484


Un elemento m de un conjunto ordenado (S,≤) se dice un elemento minimal (o mínimo) de S si:

Si x ∈ S es tal que x ≤ m entonces x = mEjemplos

b

a

c

e

d b

a

c

e

d

d

a

b c




8585


Ejemplos Conjunto N ordenado por la relación ≤Elemento mínimo: 0No tiene elementos máximos

Conjunto Z ordenado por ≤No existen elementos mínimos ni máximos

S = {1,2,4,8,12} ordenado por la relación “divide a”Elemento mínimo: 1Elementos máximos: 8 y 12




8686


Sea (S,≤) un conjunto ordenado. Se dice que un elemento 0 ∈ S es

primer elemento de S si:0 ≤ x; para todo x ∈ S

Ejemplos

no tiene primer

elemento

b

a

c

e

d b

a

c

e

d

d

a

b c




8787


Sea (S,≤) un conjunto ordenado. Se dice que un elemento 1 ∈ S es último elemento de S si:

x ≤ 1; para todo x ∈ S Ejemplos

no tiene últimoelemento

b

a

c

e

d b

a

c

e

d

d

a

b c




8888


Sea (S,≤) un conjunto ordenado. Dadosa, b ∈ S se dice que el elemento c ∈ S es el ínfimo de a y b y se nota c = a Λb si:c ≤ a y c ≤ bSi x ∈ S verifica x ≤ a y x ≤ b, entoncesx ≤ c

a b

aΛb

Ejemplo:




8989


Sea (S,≤) un conjunto ordenado. Dados a, b ∈ S se dice que el elemento c ∈ S es el supremo de a yb y se nota c = a V b si:a ≤ c y b ≤ cSi x ∈ S verifica a ≤ x y b ≤ x, entonces c ≤ x

a b

aVbEjemplo:




9090


Ejemplos

a b

cd

a Λ b no existea V b no existea Λ d = da V d = a

a b

cd

f

gh

e

a Λ a =aa V a =aa Λ c =ca V c =a

a Λ b =ba V b =ab Λ d =cb V d =a




9191

lemas

Lema: Todo conjunto ordenado finito tiene, por lo menos, un elemento mínimo (máximo).

Lema: Si un conjunto ordenado tiene primer (último) elemento este es único.

Lema: En un conjunto ordenado si existe el ínfimo (supremo) de dos elementos, es único.




9292

reticulados

Un conjunto ordenado (S,≤), se dice un reticulado inferior si todo par de elementos de S tiene ínfimo.

Si Si No

a

b

d

c b

a

dc

e

a

cb d

e




9393

reticulados

Un conjunto ordenado (S,≤), se dice un reticulado superior si todo par de elementos de S tiene supremo.

Si No Si

a

b

d

c b

a

dc

e

a

cb d

e




9494

reticulados

Un conjunto ordenado (S,≤), se dice un reticulado si es un reticulado inferior y superior. Es decir si todo par de elementos de S tiene ínfimo y supremo.

Si No Noa

b

d

c b

a

dc

e

a

cb d

e




9595

reticulados

EjercicioCuáles de los siguientes conjuntos

ordenados son reticulados inferioresreticulados superioresreticulados

(a)

(b) (c) (d) (e)




9696

ordenamiento topológico

El ordenamiento topológico es un proceso para encontrar un orden total σ a partir de un orden parcial ρ sobre un conjunto finito, de manera tal que σsea una extensión de ρ. Esto significa que si x ρ y, entonces x σ y (o ρ ⊆ σ).

Este es un proceso de ordenamiento especializado, ya que arrancamos de un orden parcial para llegar a un orden total.




9797

algoritmo: ordenamiento topológico

TopSort(conjunto finito S;orden parcial sobre S)

i = 1 while S <> ∅

elegir un elemento minimal xi de S;S = S − {xi} i = i +1

end while//x1 < x2 < … < xn es un orden total que // extiende ρwrite(x1, x2, x3, …, xn)




9898

ejemplo: ordenamiento topológico

Ernesto y sus hermanos tienen una carpintería en Tandil donde fabrican sillas mecedoras con almohadones. El proceso de fabricación puede descomponerse en varias tareas, algunas de las cuales tienen otras tareas como pre-requisito. La tabla que presentaremos a continuación muestra el proceso de fabricación de las sillas mecedoras, los pre-requisitos y el número de horas requeridos para completar cada tarea.




9999

ejemplo: ordenamiento topológico (cont.)

Tarea pre-requisitohoras para completar

1. seleccionar la madera ninguna 3.02. tallar mecedores 1 4.03. tallar asiento 1 6.04. tallar respaldo 1 7.05. tallar apoyabrazos 1 3.06. elegir tela ninguna 1.07. cocer almohadón 6 2.08. ensamblar asiento y respaldo 3,4 2.09. incorporar apoyabrazos 5,8 2.010. incorporar mecedores 2,8 3.011. barnizar 9,10 5.012. agregar el almohadón 7,11 0.5




100100

diagrama de PERT

Definimos un orden parcial sobre el conjunto de tareas:

x ≤ y ↔ tarea x = tarea y o tarea x es requisito para la tarea y.

Construimos un diagrama de PERT (program evaluation and review technique) de manera similar a un diagrama de Hasse como sigue:Los nodos son tareas. Asociamos a los nodos información sobre tiempo requerido para completar la tarea.Orientamos el diagrama de tal manera que si x < y, entonces x aparece a la izquierda de y (el diagrama es de izquierda a derecha en lugar de abajo para arriba)




101101

ejemplo: diagrama de PERT (cont.)

Tarea pre-requisito

horas para

completar

1 ninguna 3.02 1 4.03 1 6.04 1 7.05 1 3.06 ninguna 1.07 6 2.08 3,4 2.09 5,8 2.0

10 2,8 3.011 9,10 5.012 7,11 0.5




102102


Aplicando TopSort:




103103


Aplicando TopSort:




104104


Aplicando TopSort:




105105


Aplicando TopSort:

y así siguiendo …Obtenemos por ejemplo:

6, 1, 7, 2, 3, 5, 4, 8, 10, 9, 11, 12.




106106

ejemplo: camino crítico

¿Cuál es el tiempo mínimo requerido paraconstruir una silla?

camino crítico: 1 4 8 10 11 12horas: 3.0+7.0+2.0+3.0+5.0+0.5=20.5

Documents

Y binarias [G4.1]. Composición [H4.1]. Clausuras [H4.1]