conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8....

111
conjuntos y relaciones LENGUAJES LENGUAJES FORMALES FORMALES Y Y AUT AUT Ó Ó MATAS MATAS conjuntos y relaciones CONTENIDO Notació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]. Ordenamiento Topológico [G4.2]. Órdenes bien fundados [H4.3]. Retículo [M2]. Retículo con primer y último elemento [M2]. Elementos irreducibles y elementos primos de un retículo finito [M2]. 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.

Transcript of conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8....

Page 1: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

conjuntos y relaciones

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]. Ordenamiento Topológico [G4.2]. Órdenes bien fundados [H4.3]. Retículo [M2].Retículo con primer y último elemento [M2]. Elementos irreducibles y elementos primos de un retículo finito [M2].

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.

Page 2: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

teoría de conjuntos

Los conjuntos son herramienta poderosa en ciencias de la computación para resolver problemas reales.

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 implica 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

Page 3: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

teoría de conjuntos

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)]

Page 4: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

teoría de conjuntos

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.

Page 5: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

ejemplos de teoría de conjuntos

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}

Page 6: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 7: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

conceptos básicos de teoría de conjuntos

Algunas notaciones útiles para definir conjuntos

N = 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.

Page 8: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 9: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 10: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

cardinalidad

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

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

Page 11: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 12: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 13: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 14: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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}

Page 15: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 16: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 17: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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′ = ∅

Page 18: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 19: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.)

Page 20: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)}

Page 21: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)}.

Page 22: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)}.

Page 23: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 24: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 25: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)

Page 26: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

propiedades de las relaciones binarias

EjemploConsidere la relación ≤ sobre el conjunto de

números naturales N.¿Es reflexiva? Si, 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.

Page 27: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 28: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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 ◦ρ

Page 29: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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:1. ρ* tiene la propiedad P2. ρ ⊆ ρ*3. ρ* es un subconjunto de cualquier otra

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

Page 30: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)}.

Page 31: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 32: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)}

Page 33: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)}

Page 34: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 35: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 36: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 37: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)

Page 38: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

°

Page 39: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

⎢ ⎢ ⎢ ⎢

⎥ ⎥ ⎥ ⎥

Page 40: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 41: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 42: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 43: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

correspondencias

matriz deadyacencia

relación binaria

grafo dirigido sin arcos paralelos

Page 44: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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 ∧∨ =

Page 45: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)

Page 46: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

matriz de alcance y clausura transitiva

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

Matriz de adyacencia

Page 47: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

matriz de alcance y clausura transitiva

Page 48: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

matriz de alcance y clausura transitiva

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

Page 49: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 50: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

algoritmo de Warshall: clausura transitiva

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

= M4= M5

Page 51: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

matriz de adyacencia ponderada

4

1

10

6

27

⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢

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

07102010

6040

Grafo ponderado

Matriz de adyacenciaponderada

Page 52: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)

Page 53: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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 =

⎥⎥⎥⎥

⎢⎢⎢⎢

∞∞∞∞∞

∞∞

=

Page 54: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 55: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

algoritmo de Floyd: distancias mínimas

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*

Page 56: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

algoritmo de Floyd: distancias mínimas

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

Page 57: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)}.

Page 58: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 59: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 60: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

clases de equivalencia (repaso)

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.

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|

Page 61: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

clases de equivalencia (repaso)

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.

Page 62: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 63: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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,...}

Page 64: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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] ρ

Page 65: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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]ρ

Page 66: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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]ρ

Page 67: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

generación de relaciones de equivalencia

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

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

Respuesta:Obtenemos la clausura reflexiva,

simétrica y transitiva de ρ.

Page 68: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

generación de relaciones de equivalencia

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

Notar lo siguiente:1. r(t(ρ)) = t(r(ρ)) 2. r(s(ρ)) = s(r(ρ)) 3. s(t(ρ)) ⊆ t(s(ρ))

Page 69: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

generación de relaciones de equivalencia

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?

Page 70: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)},

Page 71: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

ó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

Page 72: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

ó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.

Page 73: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 74: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 75: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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}

{}

Page 76: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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}?

Page 77: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

diagrama de Hasse

EjercicioDar ejemplos de conjuntos S y

relaciones ρ para los siguientes diagramas de Hasse

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

Page 78: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

no son diagramas de Hasse

Notar: las siguientes figuras no son diagramas de Hasse

¿Por qué?a

b

d

c

a b

cd

e

Page 79: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 80: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 81: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

cadenas y anticadenas

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,c,d}{a,b,d}{a,b,c} {b,c,d}

{a,b,c,d}

{}

Page 82: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

cadenas y anticadenas

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,c,d}{a,b,d}{a,b,c} {b,c,d}

{}

{a,b,c,d}

Page 83: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 84: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

elementos especiales

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

Page 85: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

elementos especiales

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

Page 86: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

elementos especiales

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

Page 87: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

elementos especiales

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

Page 88: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

elementos especiales

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:

Page 89: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

elementos especiales

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:

Page 90: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

elementos especiales

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

Page 91: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 92: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 93: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 94: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 95: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

reticulados

EjercicioCuáles de los siguientes conjuntos

ordenados son reticulados inferioresreticulados superioresreticulados

(a)

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

Page 96: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

elementos especiales

Un elemento i de un reticulado R se dice irreducible si:i no es primer elemento de R.Si i = a V b entonces i = a ó i = b.

a

b

c

d

e

a

bc

de

f

a

b c d

e

ab

c

de

g

f

h

Page 97: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

elementos especiales

Un elemento p de un reticulado R se dice primo si:p no es primer elemento de R.Si p ≤ a V b entonces p ≤ a ó p ≤ b.

a

b

c

d

e

a

bc

de

f

a

b c d

e

ab

c

de

g

f

h

Page 98: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

criterio para determinar elementos irreducibles

En un reticulado finito, no trivial, R; i es un elemento irreducible si y sólo si el conjunto ordenado

Zi = {z ∈ R : z < i }tiene último elemento.

a

b

c

d

e

a

bc

de

f

a

b c d

e

ab

c

de

g

f

h

Page 99: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

criterio para determinar elementos primos

En un reticulado finito, no trivial, R; p es un elemento primo si y sólo si el conjunto ordenado

Zp = {z ∈ R : p ≤ z}tiene último elemento.

a

b

c

d

e

a

bc

de

f

a

b c d

e

ab

c

de

g

f

h

Page 100: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

lemas

Lema: En un reticulado R todo elemento primo es irreducible.

La recíproca no es válida.

a

b c d

e

a

b

cd

e

Page 101: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 102: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)

Page 103: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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.

Page 104: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 105: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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)

Page 106: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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

Page 107: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

ejemplo: ordenamiento topológico (cont.)

Aplicando TopSort:

Page 108: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

ejemplo: ordenamiento topológico (cont.)

Aplicando TopSort:

Page 109: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

ejemplo: ordenamiento topológico (cont.)

Aplicando TopSort:

Page 110: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

ejemplo: ordenamiento topológico (cont.)

Aplicando TopSort:

y así siguiendo …Obtenemos por ejemplo:

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

Page 111: conjuntos y relacionescs.uns.edu.ar/~td/lfya2011/downloads/TEORICAS/Conjuntos y... · 2012. 8. 13. · conjuntos y relaciones LENGUAJES FORMALES Y AUTÓMATAS teoría de conjuntos

conjuntos yrelaciones

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

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