Teoria De La Computacion
Enviado por superheroe007 • 31 de Enero de 2015 • 224 Palabras (1 Páginas) • 153 Visitas
Números enteros como conceptos definidos recursivamente
Hemos mencionado que las demostraciones por inducción resultan útiles cuando el objeto en cuestión está definido de manera recursiva. Sin embargo, nuestros primeros ejemplos eran inducciones sobre números Enteros, que normalmente no interpretamos como “definidos recursivamente”.
No obstante, existe una Definición natural de carácter recursivo de los enteros no negativos, y esta definición se adapta a la forma. En que se realizan las inducciones sobre los números enteros: desde objetos definidos en primer lugar a otros definidos con posterioridad.
Base. 0 es un entero.
Paso Inductivo. Si n es un entero, entonces n+1 también lo es
La prueba por inducción consiste en demostrar que una proposición se cumple para todos los elementos mínimos del tipo, y que si la propiedad se cumple para todas las subestructuras de una cierta estructura S, entonces se debe cumplir también para S.
Inductivo
Es aquel método científico que obtiene conclusiones generales a partir de premisas particulares.
Inducciones Estructurales
En la teoría de autómatas, existen varias estructuras definidas recursivamente sobre las que es necesario demostrar proposiciones. Los familiares conceptos sobre árboles y expresiones son ejemplos importantes de estas estructuras.
Como las inducciones, todas las definiciones recursivas tienen un caso base, en el que se definen una o más estructuras elementales, y un paso de inducción, en el que se definen estructuras más complejas en función de las estructuras definidas previamente.
...