Conjuntos Inductivos

Matemtica Discreta y Lgica 1
Material terico
Conjuntos inductivos, recursin y principio de induccin

Esquema de induccin
Veremos la induccin como mecanismo primitivo para definir conjuntos. La idea es tomar un conjunto conocido
de algn subconjunto
B0 S , definir formas de agrandar sucesivamente B0
S , partir
y considerar el conjunto que se obtiene
al lmite de este proceso.
El conjunto S debe ser un conjunto conocido y podr ser por ejemplo el conjunto
conjunto de las tiras de caracteres sobre determinado alfabeto.
de los nmeros naturales o el
A modo de ejemplo, veamos una definicin inductiva del conjunto de los nmeros pares:
Tomemos:
Como
Como base al conjunto
a los naturales
Como nica regla: si
{0}
es par, entonces
n+2
es par
Una observacin interesante en este punto es que podramos haber realizado otra definicin inductiva para el mismo
conjunto de los nmeros pares:
Tomemos:
Como
Como base al conjunto
a los naturales
Como nica regla: si
{0,2}
es par, entonces
n+4
es par
Los conjuntos son iguales, pero la forma de recorrer los elementos es distinta. As, demostrar que 10 es par podra
implicar seguir distintos caminos (e incurrir en distintos costos), dependiendo de la definicin inductiva que se considere.
Pgina 1 de 4
Material terico
Para continuar, deberemos presentar algunas definiciones.

Un alfabeto es un conjunto finito (o numerable) de smbolos o letras, por ejemplo:
D = {0,1,2,3,4,5,6,7,8,9}
digit ::= 0|1|2|3|4|5|6|7|8|9
Una palabra sobre un alfabeto es una secuencia (o cadena) de cero o ms smbolos del alfabeto, concatenados.
S * = {w | w
es una palabra con letras del alfabeto S
S = {w | w
es una palabra no vaca con letras del alfabeto S
A la palabra vaca la notaremos
A un conjunto de palabras se lo denomina lenguaje.
S*
S+
son ejemplos de lenguajes para cualquier alfabeto
pero nos concentraremos en lenguajes definidos de forma recursiva (aunque

forma recursiva).
S,
tambin podran definirse en
Por ejemplo:
S = {a, b, c}, y L1 S * definido inductivamente por:

i. a L1
( clusula base: no depende de otros objetos de L1 )
ii. Si w L1 , entonces bwb L1
( clusula recursiva: depende de otros objetos de L1 )
Sea
S = {a, b, c}, y L2 S * definido inductivamente por:

i. b L2
ii. Si w L2 , entonces awc L2
Sea
Con una definicin inductiva no slo definimos un conjunto sino que decimos la forma de construir objetos en l, e
implcitamente decimos que es la nica forma de construir objetos en el conjunto.
Para probar que un objeto pertenece a un conjunto inductivo basta con mostrar cmo lo formamos (su secuencia de
formacin est dada por las clusulas utilizadas).
Por ejemplo:
bbabb L1 ya que:
i. a L1
ii. Luego, bab L1
iii. Finalmente, bbabb L1
( aplicamos i )
( aplicamos ii )
( aplicamos ii )
En el ejemplo anterior, se hace evidente que todas las palabras del lenguaje
pero qu es tener un nmero par de smbolos
b ?
Pgina 2 de 4
L1
tendrn un nmero par de smbolos
b,
Material terico
Esquema de recursin primitiva

Sea
un conjunto definido inductivamente.
f : A B , alcanza con definir a f mediante ecuaciones que determinen:

f para los objetos de A obtenidos de aplicar clusulas base
f para los objetos de A obtenidos de aplicar clusulas inductivas, utilizando el valor de f
Para definir una funcin
El valor de
El valor de
en el
objeto inmediatamente anterior (llamada recursiva).

Dado un conjunto inductivo, sabemos exactamente cmo se construyen sus elementos. Esta informacin nos sirve para
definir funciones sobre sus elementos.
Por ejemplo, para nuestro lenguaje
Sea
L1 :
un conjunto arbitrario.
Un conjunto de ecuaciones como el siguiente basta para definir una nica funcin
i.
ii.
f : L1 B .
f (a ) := ...
f (bwb) := ... f ( w)...
Un ejemplo ms concreto y muy intuitivo ser el de la funcin largo:
Consideremos la funcin largo : L1

i.
ii.
N , definida por:
largo(a ) := 1
largo(bwb) := largo( w) + 2
El esquema de recursin primitiva nos permite definir funciones, siguiendo los pasos de una definicin inductiva.
Principio de induccin primitiva

Sea
un conjunto definido inductivamente.
Para probar que una propiedad se cumple para todos los objetos de
alcanza con:
Probar que la propiedad se cumple para los objetos de
Probar que la propiedad se cumple para los objetos de A obtenidos de aplicar clusulas inductivas,
suponiendo que la misma se cumple para objetos anteriores (hiptesis inductiva).
Por ejemplo, podramos demostrar que todos los objetos de
L1
tienen una cantidad impar de smbolos. Una prueba
L1
que aprovecha el conocimiento de cmo se generan los objetos de
i.
tiene una cantidad impar de smbolos
ii.
Si
obtenidos de aplicar clusulas base
tiene una cantidad impar de smbolos, entonces
sera de la forma:
bwb
tambin
En este punto vemos que podra ser til para la demostracin servirse de funciones definidas recursivamente sobre el
conjunto inductivo. En lugar de probar que los objetos de
L1
tienen una cantidad impar de smbolos podramos
considerar probar que tienen largo impar, utilizando la funcin largo que vimos previamente.
Pgina 3 de 4
Material terico
En el caso general, si queremos probar una propiedad
para las palabras de
L1 , aplicamos el principio de induccin
L1 .
para
P una propiedad sobre los objetos de L1 tal que:

i. P ( a ) se cumple
ii. Si P ( w) se cumple, entonces P (bwb) se cumple
Entonces, P se cumple para todos los objetos de L1 .
Sea
Debemos notar que el principio de induccin es dependiente del conjunto inductivo, y ms an, de las clusulas base e
inductivas de su definicin.
El principio de induccin, aplicado a un conjunto inductivo, nos permite probar proposiciones sobre todos los elementos
del conjunto inductivo:
Para todo
Para todo
Para todo
w
w
w
de
de
de
L1 , w tiene una cantidad impar de smbolos

L1 , largo( w) es impar
L1 , w es palndromo
Ejemplo: las expresiones aritmticas

Consideremos el alfabeto
A = {+, *, (, ), 0, 1, 2, ... } .
El lenguaje de las expresiones aritmticas,

i.
ii.
iii.
Exp A*
puede ser definido inductivamente por:
n {0, 1, 2, ... } , entonces n Exp

Si {x1, x2} Exp , entonces ( x1 + x 2) Exp
Si {x1, x2} Exp , entonces ( x1 * x 2) Exp
Si
Construimos entonces nuestro conjunto de expresiones aritmticas mediante el esquema de induccin. Ahora podemos
definir funciones sobre este conjunto inductivo, aplicando el esquema de recursin primitiva.
Sera til, por ejemplo, definir una funcin de evaluacin:
Sea la funcin
i.
ii.
iii.
eval : Exp N , definida por:
eval (n) := n
eval (( x1 + x 2)) := eval ( x1) + eval ( x 2)
eval (( x1* x 2)) := eval ( x1) * eval ( x 2)
Es importante darse cuenta que
Exp
es un lenguaje (un subconjunto de
A* ),
y por lo tanto sus elementos son
palabras (cadenas de smbolos sobre un alfabeto). En este contexto, los elementos + , * y cualquier n son
simplemente smbolos. Sin embargo, del lado derecho de la definicin de funcin, una aparicin de n significa un
nmero natural, y una aparicin de
implica la operacin binaria cerrada en los naturales de suma o producto.
Al esquema de recursin, y al principio de induccin que vimos los llamamos primitivos porque se basan en el objeto
inmediatamente anterior del conjunto inductivo.
Pgina 4 de 4

Conjuntos Inductivos

Cargado por

Copyright:

Formatos disponibles

Conjuntos Inductivos

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Conjuntos Inductivos

Cargado por

Copyright:

Formatos disponibles

Matemtica Discreta y Lgica 1