Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈...
Transcript of Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈...
![Page 1: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/1.jpg)
Conjuntos
Un conjunto es una coleccion de objetos.
Si a es un objeto y R es un conjunto entonces por
a ∈ R
se entiende que a pertenece a R.
Normalmente, podremos definir a un conjunto de dos maneras:
Por extension: Se enumeran en forma explıcita los elementos que pertenecen alconjunto. Por ejemplo,
A = {a, e, i, o, u}Esta forma de definir conjuntos funciona bien si el conjunto que queremosdefinir tiene un numero finito de elementos.
Por comprension: Un conjunto se define por comprension de la siguiente mane-ra:
{x |P (x)},
Jorge Baier Aranda, PUC 1
![Page 2: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/2.jpg)
es decir, al conjunto pertenecen todos los elementos x que cumplen con lapropiedad P .Alternativamente, podemos usar:
{x ∈ A |P (x)}Ejemplos:
1. {n |n ∈ N y n es par}.2. {p ∈ N | p es primo}.
Es preciso observar que en la primera definicion, la propiedad P no puede sercualquier cosa.
De hecho, la definicion acepta definir conjuntos como el siguiente:
R = {x |x 6∈ x},
es decir, el conjunto de todos los conjuntos que no pertenecen a sı mismos.
Esta definicion es contradictoria puesto que al hacernos la pregunta ¿R ∈ R? noobtenemos una respuesta.
Jorge Baier Aranda, PUC 2
![Page 3: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/3.jpg)
Supongamos que la respuesta es sı. Luego, por definicion del conjunto, R 6∈ RVW.
Supongamos que la respuesta es no. Luego, R 6∈ R, y, por la definicion de R, Rdebe pertenecer al conjunto R, es decir, R ∈ R! VW
Esto nos deja la leccion de que hay que ser cuidadoso con las propiedades que seescogen.
La segunda definicion de conjuntos es completamente segura cuando A es unconjunto fijo.
Jorge Baier Aranda, PUC 3
![Page 4: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/4.jpg)
Definiciones Elementales
Si todos los elementos de un conjunto A pertenecen a un conjunto B, diremosque A esta contenido en (o es subconjunto de) B. Esto se anota como
A ⊆ B,
oB ⊇ A.
Dos conjuntos A y B (A = B) son iguales si y solo si contienen los mismoselementos.
Un conjunto A es subconjunto propio de B si y solo si:
A ⊆ B y A 6= B,
que frecuentemente se escribe como:
A ( B
Jorge Baier Aranda, PUC 4
![Page 5: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/5.jpg)
Operaciones Elementales
A ∪B, es la union de A y B, y se define por:
{x |x ∈ A o x ∈ B}
A ∩B, es la interseccion de A y B, y se define por:
{x |x ∈ A y x ∈ B}
A−B, es la diferencia de A y B, y se define por:
{x |x ∈ A y x 6∈ B}
A×B, es el producto cartesiano de A y B, y se define por:
{(x, y) |x ∈ A y y ∈ B}
Jorge Baier Aranda, PUC 5
![Page 6: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/6.jpg)
2A, es el conjunto potencia de A y define por:
{x |x ⊆ A}
Jorge Baier Aranda, PUC 6
![Page 7: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/7.jpg)
Relaciones
Una relacion binaria R entre dos conjuntos A y B es un subconjunto del productocartesiano entre A y B, es decir, R ⊆ A×B.
Si el par (a, b) ∈ R, normalmente se acostumbra a decir que
aRb.
Si (a, b) 6∈ R, entonces decimos que (a, b) 6∈ R (o a 6 Rb).
Definicion 1. Una relacion binaria R sobre un conjunto A es un subconjuntode A×A.
Nos interesaran algunas propiedades de las relaciones.
Sea R una relacion binaria sobre un conjunto A. R podrıa tener alguna de lassiguientes propiedades:
Jorge Baier Aranda, PUC 7
![Page 8: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/8.jpg)
Refleja: R es refleja si y solo si:
aRa, para todo a ∈ A.
Simetrıa: R es simetrica si y solo si:
aRb entonces bRa, para todo a, b ∈ A.
Asimetrıa: R es asimetrica si y solo si:
aRb entonces b 6 Ra, para todo a, b ∈ A.
Antisimetrıa: R es antisimetrica si y solo si:
aRb y bRa implica que a = b, para todo a, b ∈ A.
Transitividad: R es transitiva si:
aRb y bRc implica que aRc, para todo a, b, c ∈ A.
Una relacion de equivalencia es una relacion simetrica, refleja y transitiva.
Jorge Baier Aranda, PUC 8
![Page 9: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/9.jpg)
Clausuras de Relaciones
Si P representa una propiedad o una coleccion de propiedades de relacion,entonces, la clausura-P de una relacion binaria R sobre un conjunto A, es elsubconjunto mas pequeno de A × A, que cumple la propiedad y que contiene aR.
Normalmente, la clausura refleja y transitiva de una relacion R sobre un conjuntocualquiera A, se anota como R∗ y se puede construir a partir de R siguiendo lassiguientes reglas:
• Si (a, b) ∈ R, entonces (a, b) ∈ R∗• (a, a) ∈ R∗, para todo a ∈ A.• Si (a, b) ∈ R∗ y (b, c) ∈ R∗, entonces (a, c) ∈ R∗.• Nada mas pertenece R∗
Jorge Baier Aranda, PUC 9
![Page 10: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/10.jpg)
SeaR = {(1, 3), (1, 1), (1, 4), (3, 2)},
definida sobre S = {1, 2, 3, 4}. Siguiendo las reglas de construccion de arriba seobtiene que:
R∗ = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 3),
(1, 2), (1, 4), (3, 2)}.
Jorge Baier Aranda, PUC 10
![Page 11: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/11.jpg)
Conjuntos Infinitos
No tiene mucho sentido hablar del “tamano” de un conjunto infinito.
Sin embargo, es razonable cuestionarse algunas cosas. Como por ejemplo:
¿Hay mas racionales que naturales?¿Son mas los multiplos de 2 que los de 4?¿Quienes son mas, los reales o los naturales?
Para poder comparar tamanos de conjuntos infinitos se de define la nocion deequinumeroso, con la idea intuitiva que dos conjuntos equinumerosos tienen “lamisma” cantidad de elementos.
Definicion 2. [Conjuntos equinumerosos] Dos conjuntos A y B son equinu-merosos si es que es posible definir una funcion biyectiva
f : A → B
Jorge Baier Aranda, PUC 11
![Page 12: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/12.jpg)
Ejemplo: El conjunto de multiplos de 2 y el de multiplos de 4 son equinumerosos.La funcion biyectiva esta dada por:
f(2k) = 4k.
Ejercicio: Demuestre que Z y N son equinumerosos.
Ejercicio: Demuestre N y N× N son equinumerosos.
Si A es un conjunto infinito, entonces se dice que A es contable si es que A yN son equinumerosos.
Jorge Baier Aranda, PUC 12
![Page 13: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/13.jpg)
Conjuntos incontables
Hay muchos conjuntos que son incontables.
El ejemplo mas clasico es el caso de 2N (Teorema de Cantor).
Demostracion: En efecto, supongamos que 2N es contable. Esto significa quelos elementos de 2N pueden ser enumerados como:
2N = {S0, S1, S2, . . .}
Si esta construccion es valida entonces podrıamos formar el siguiente conjunto:
D = {n ∈ N |n 6∈ Sn}
Debido a que D es un conjunto de naturales entonces deberıa ser igual a Sk paraalgun k.
La pregunta que nos hacemos es ¿k ∈ D?
Solo hay dos posibilidades:
Jorge Baier Aranda, PUC 13
![Page 14: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/14.jpg)
1. Supongamos que la respuesta es sı. Entonces k ∈ Sk, pero por la definicion deD, k 6∈ D, es decir k 6∈ Sk. VW
2. Supongamos que la respuesta es no. Entonces k 6∈ Sk y luego, dado que lapropiedad de D se verifica, tenemos que k ∈ D y por lo tanto k ∈ Sk. VW.
Podemos concluir que tal enumeracion para 2N no existe y por lo tanto 2N esincontable.
Jorge Baier Aranda, PUC 14
![Page 15: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/15.jpg)
Inducción
El principio de induccion matematica es esencial para demostrar propiedades delos numeros naturales.
Sin embargo, este principio se puede usar en general para demostrar cualquierpropiedad de conjuntos de elementos que se pueden construir inductivamente.
Nos referiremos al principio de induccion en los naturales y a definciones inducti-vas.
Jorge Baier Aranda, PUC 15
![Page 16: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/16.jpg)
Inducción en los Naturales
Sea P (n) una propiedad acerca de un numero natural arbitrario n, por ejemplo:
n∑i=0
i =n(n + 1)
2
Si se logra establecer:
1. P (0). (caso base)2. Si se cumple P (n) implica que se cumple P (n+1), para n ≥ 1 (paso inductivo).
Una vez demostrados estos dos puntos, es posible concluir que la P (n) se cumplepara cualquier natural n.
Ejercicio: Demuestre que∑n
i=0 i = n(n+1)2 .
Jorge Baier Aranda, PUC 16
![Page 17: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/17.jpg)
El principio de induccion completa establece que para demostrar una propiedadP sobre los naturales, basta con demostrar:
1. P (0). (caso base)2. Si se cumple P (0), P (1), . . . , P (n) implica que se cumple P (n+1), para n ≥ 1
(paso inductivo).
Jorge Baier Aranda, PUC 17
![Page 18: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/18.jpg)
Definiciones Inductivas
Las definiciones inductivas estan inspiradas en el principio de induccion.
Para definir una funcion (o propiedad) en forma inductiva se definen los casosbasicos y luego los casos inductivos.
En el caso basico se define la funcion (o propiedad) para los entes u objetos massimples1.
El (o los) casos inductivos tienen como caracterıstica que las definiciones de lafuncion (propiedad) de un ente se hace en funcion de el valor de la funcion(propiedad) para entes mas sencillos.
La siguiente es una definicion inductiva para la funcion factorial sobre losnaturales:
fact(n) =
{1 si n = 0n · fact(n− 1) en otro caso
1Los que no se definen en terminos de otros
Jorge Baier Aranda, PUC 18
![Page 19: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/19.jpg)
La serie de los numeros de Fibonacci tambien se puede definir de esta manera:
fn =
0 si n = 01 si n = 1fn + fn−1 en otro caso
El principio de induccion es especialmente adecuado para demostrar propiedadesde funciones definidas en forma inductiva.
Ejemplo: Demuestre que
f2n = fn−1 · fn+1 + (−1)n+1,
para todo natural n ≥ 1
Jorge Baier Aranda, PUC 19
![Page 20: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/20.jpg)
Grafos
Un grafo finito no dirigido G = (V,E) es un par formado por:
• V : Un conjunto de vertices, o nodos.• E: Un conjunto de pares no ordenados de vertices llamados aristas, o arcos.
Ejemplo:
V = {1, 2, 3, 4}E = {(i, j) | |i− j| = 1 o i = j}
Corresponde a la siguiente representacion grafica:
1 2 3 4
Un camino en un grafo G = (V,E) es una secuencia de vertices v1, v2, . . . , vn
tal que cada par (vi, vi+1) ∈ E para cada 1 ≤ i < n.
Jorge Baier Aranda, PUC 20
![Page 21: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/21.jpg)
Un grafo dirigido es un grado en el cual las aristas tienen un sentido.
Formalmente, es un par (V,E) donde
• V es un conjunto de vertices.• E es un conjunto de pares ordenados de elementos de V .
Ejemplo:
V = {1, 2, 3, 4}E = {i → j | i− j = 2 o i = j}
Si el arco u → v ∈ E, entonces se dice que u es el antecesor de v y que u es elsucesor de v.
Jorge Baier Aranda, PUC 21
![Page 22: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/22.jpg)
Árboles
Un arbol es un tipo especial de grafo dirigido, que cumple las siguientes propie-dades:
1. Hay un nodo v que no tiene predecesores y desde el cual hay un camino a cadanodo del grafo. (Tiene una raız ).
2. Exceptuando a la raız, cada vertice tiene exactamente un predecesor. (Un nodotiene a lo mas un padre).
En la jerga de arboles, se acostumbra decir padre en vez de antecesor e hijo envez de sucesor.
Adicionalmente, se puede suponer que los hijos de un mismo nodo estan ordenadosde izquierda a derecha.
Jorge Baier Aranda, PUC 22
![Page 23: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/23.jpg)
Símbolos, Alfabetos y Palabras
Un sımbolo es una entidad abstracta que no definiremos formalmente. Unadefincion del diccionario de la RAE:
Tipo de abreviacion de caracter cientıfico o tecnico, constituida por sig-nos no alfabetizables o por letras, y que difiere de la abreviatura en carecerde punto
Los sımbolos que utilizaremos en este curso son dıgitos y letras.
Un alfabeto es un conjunto finito de sımbolos.
Ejemplos:
Alfabeto binario = {0, 1}Alfabeto romano = {a, b, c, d, e, . . .}Alfabeto griego = {α, β, γ, δ, . . .}
Frecuentemente, usaremos la letra Σ para referirnos a alfabetos.
Jorge Baier Aranda, PUC 23
![Page 24: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/24.jpg)
Una palabra es una secuencia finita de sımbolos yuxtapuestos de algun alfabeto.
La palabra ε es una palabra con 0 sımbolos. Se acostumbra llamarla palabravacıa
El conjunto de las palabras sobre un alfabeto Σ puede ser definido por:
• ε es una palabra.• Si w es una palabra, entonces wa es una palabra, para todo a ∈ Σ.
Ejercicio: Demuestre que aba es una palabra sobre Σ = {a, b, c}.
Un lenguaje formal sobre un alfabeto Σ es un conjunto (posiblemente infinito)de palabras sobre Σ.
Jorge Baier Aranda, PUC 24
![Page 25: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/25.jpg)
Por ejemplo, si Σ = {a, e, i, o, u}, los siguientes son lenguajes:
L1 = {auu, eae, a}L2 = ∅
L3 = {ε, a, oa}
Es importante notar la diferencia entre los lenguajes ∅ y {ε}.
Jorge Baier Aranda, PUC 25
![Page 26: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/26.jpg)
Convenciones
Frecuentemente usaremos letras para designar tanto a sımbolos como palabras.Para distinguirlos usamos las siguientes convenciones:
• Las letras minusculas a, b, c y d seran usadas normalmente para designarsımbolos.
• Las letras minusculas u, v, w, x, y, z y w son usadas para designar palabras.• Las letras mayusculas L, R y S son usadas para designar lenguajes.
Jorge Baier Aranda, PUC 26
![Page 27: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/27.jpg)
Largo
El largo de una palabra w corresponde al numero de sımbolos que esta tiene y seanota como |w|.
Ejemplo: |abaco| = 5.
Podemos definir inductivamente la funcion largo por:
• |ε| = 0,• |wa| = 1 + |w|, donde w es una palabra.
Ejercicio: Usando la definicion, demuestre que |abaco| = 5
Jorge Baier Aranda, PUC 27
![Page 28: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/28.jpg)
Concatenación
Es posible concatenar dos palabras a traves de la operacion de concatenacion ◦.
De esta manera, si w1 = ca y w2 = sa,
w1 ◦ w2 = casa
La funcion de concatenacion se puede definir inductivamente mediante:
• x ◦ ε = x, para toda palabra x.• x ◦ wa = (x ◦ w)a, donde a es un sımbolo y x y w son palabras.
Ejemplo: Demuestre que ε ◦ x = x.
Hacemos la demostracion por induccion en el largo de x.
Jorge Baier Aranda, PUC 28
![Page 29: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/29.jpg)
• Caso base. x = ε (|x| = 0).
ε ◦ x = ε ◦ ε
= ε (por definicion de largo)
= x
• Paso inductivo. Supongamos que la propiedad se cumple para toda palabraw, de largo k. Demostraremos que, entonces, la propiedad se cumple paracualquier palabra de largo k + 1.(Hipotesis inductiva: ε ◦ w = w.)Demostracion:
ε ◦ wa = (ε ◦ w)a (por definicion de concatenacion)
= wa (por hipotesis inductiva)
Ejercicio: Demuestre que |x ◦ y| = |x|+ |y|.Ejercicio: Demuestre que (x ◦ y) ◦ z = x ◦ (y ◦ z).
Jorge Baier Aranda, PUC 29
![Page 30: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/30.jpg)
Reverso
Frecuentemente interesa obtener el reverso de una palabra w.
El reverso de una palabra w, escrito por wr, es una palabra que contiene losmismos elementos que w, pero con los sus sımbolos en secuencia inversa.
La funcion reverso se define de la siguiente manera:
• εr = ε.• (xa)r = axr, donde a ∈ Σ y x es una palabra sobre Σ.
Ejercicio: Demuestre que (x ◦ y)r = yr ◦ xr.
Jorge Baier Aranda, PUC 30
![Page 31: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/31.jpg)
Concatenación de Lenguajes
Tambien es posible definir la funcion de concatenacion para lenguajes.
De esta manera:L1 ◦ L2 = {x ◦ y |x ∈ L1, y ∈ L2}
Por ejemplo, si L1 = {aa, bda, ε} y L2 = {a, bb},
L1 ◦ L2 = {aaa, aabb, bdaa, bdabb, a, bb}
Notese que L ◦∅ = ∅ y que L ◦ {ε} = L (¿por que?).
La notacion Li se ocupa para denotar al lenguaje que resulta de la concatenacionde L i veces consigo mismo.
Li se puede definir inductivamente por:
L0 = {ε}
Li+1 = Li ◦ L
Jorge Baier Aranda, PUC 31
![Page 32: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/32.jpg)
Clausura de Kleene
La clausura de Kleene de un lenguaje L, que se anota como L∗, esta definidapor,
L∗ =∞⋃
i=0
Li.
Ejemplo: Si L = {a},
L∗ = {ε, a, aa, aaa, aaaa, aaaaa, . . .}
Si L = {0, 1},L∗ = {ε, 0, 1, 00, 01, 10, 11, 000, 001, . . .}
Generalizando, si Σ es un alfabeto cualquiera, entonces Σ∗ es el conjunto detodas las palabras sobre Σ.
Normalmente, se utiliza la notacion L+ como una abreviacion de L ◦ L∗.
Jorge Baier Aranda, PUC 32
![Page 33: Conjuntos - jabaier.sitios.ing.uc.cljabaier.sitios.ing.uc.cl/iic2222/intro.pdf · • Si (a,b) ∈ R∗ y (b,c) ∈ R∗, entonces (a,c) ... Si A es un conjunto infinito, entonces](https://reader031.fdocumento.com/reader031/viewer/2022021721/5bdeff9e09d3f237288b603b/html5/thumbnails/33.jpg)
Sufijos, Prefijos y Subpalabras
Una palabra x es prefijo de una palabra w, si existe una palabra y tal quexy = w.
Una palabra x es prefijo propio de una palabra w, si existe una palabra y, con|y| > 0 tal que xy = w.
Una palabra x es sufijo de una palabra w, si existe una palabra y tal que yx = w.
Una palabra x es sufijo propio de una palabra w, si existe una palabra y, con|y| > 0 tal que yx = w.
Una palabra y es subpalabra de una palabra w, si existen palabras x y z talesque xyz = w.
Jorge Baier Aranda, PUC 33