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

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.

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

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

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.

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}

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.

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.

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.

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

cardinalidad

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

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

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.

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.

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

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}

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

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.

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

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

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

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

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

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

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.

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

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)

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.

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.

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

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

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

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

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

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

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

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.

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.

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)

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.

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

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

⎢ ⎢ ⎢ ⎢

⎥ ⎥ ⎥ ⎥

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

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

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

correspondencias

matriz deadyacencia

relación binaria

grafo dirigido sin arcos paralelos

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

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)

matriz de alcance y clausura transitiva

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

Matriz de adyacencia

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

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

algoritmo de Warshall: clausura transitiva

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

= M4= M5

matriz de adyacencia ponderada

⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢

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

07102010

Grafo ponderado

Matriz de adyacenciaponderada

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)

distancias mínimas

Para el siguiente grafo ponderado calcular las distancias mínimas

20⎥⎥⎥⎥

⎢⎢⎢⎢

∞∞∞∞∞

∞∞

5.1100205.00

)3()2( M

5.110045.00

⎥⎥⎥⎥

⎢⎢⎢⎢

∞∞∞∞∞

∞∞

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

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

⎥⎥⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢⎢⎢

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

0300300

102010100

⎥⎥⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢⎢⎢

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

0545040

0300300

10154010100

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

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

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.

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}

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|

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.

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

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

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

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

.[c]ρ .[e]ρ

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

.[c]ρ .[e]ρ

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

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(ρ))

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?

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

ó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

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

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.

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

diagramas de Hasse

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

{c,d}{a,b}

{a,c}{b,c}

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

{a,b,c,d}

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

diagrama de Hasse

EjercicioDar ejemplos de conjuntos S y

relaciones ρ para los siguientes diagramas de Hasse

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

no son diagramas de Hasse

Notar: las siguientes figuras no son diagramas de Hasse

¿Por qué?a

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

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.

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

Ejemplo

{c,d}{a,b}

{a,c}{b,c}

{a,b,c,d}

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

Ejemplo

{c,d}{a,b}

{a,c}{b,c}

{a,b,c,d}

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

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

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

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

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

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

Ejemplo:

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

aVbEjemplo:

Ejemplos

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

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

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

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.

reticulados

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

Si Si No

reticulados

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

Si No Si

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

reticulados

EjercicioCuáles de los siguientes conjuntos

ordenados son reticulados inferioresreticulados superioresreticulados

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

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.

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.

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.

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.

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

La recíproca no es válida.

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.

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)

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.

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

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)

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

Aplicando TopSort:

y así siguiendo …Obtenemos por ejemplo:

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

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

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

Documents

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

Bases Teoricas Chany

Teoricas de enfermeria

Bases teoricas

Conectivismo bases teoricas

Rupturas teoricas

CONJUNTOS El fundamento mas importante para el estudio de los lenguajes y autómatas es la Teorıa de Conjuntos. En efecto, siempre que hablemos de formalizar.

Autómatas Celulares

NOCIONES TEORICAS GENERALES

BASES TEORICAS - virtual.urbe.edu

AUTÓMATAS CELULARES

Autómatas Mínimos - Encontrar el autómata mínimo. · Minimización de Autómatas Deterministas Resultados Algoritmo Autómatas Mínimos Encontrar el autómata mínimo. ... número

Autómatas programables Twido Autómatas programables Twido

10.DISTRIBUCIONES TEORICAS

Teoricas Juego

AUTÓMATAS PROGRAMABLES Programación básica de autómatas · PDF fileRoberto Álvarez Sindín marzo - abril 2011 Curso: 11FP35CF187 AUTÓMATAS PROGRAMABLES Programación básica

Generalidades teoricas

Maquinas Autómatas

Teoricas Enfermería Infantil

Resumen autómatas

Teoricas Neuromuscular