Inducci N Estructural
Páginas: 2 (296 palabras)
Publicado: 16 de abril de 2015
Inducción estructural: Mediante este método podemos demostrar que una propiedad S(x) cumpla para todos los elementos de determinado conjunto A que posea un orden bienfundamentado <
(x:A) (S(x) -> S(sgte(x))) -> (x:A) (S(x))
Ahora para los que no tengan un conocimiento sobre lo que trata la teoría deconjuntos y sobre lo que se refiere a poseer un orden bien fundamentado, he aquí un breve ejemplo.
Pongamos el ejemplo de los números Naturales donde se define al conjunto N={0, 1, 2, 3….} para que este posea un orden bien fundamentado > debe poseer un elemento mínimo que es 0 y este se define como
0={}
luego tenemos un generador que llamaremossiguiente y se definirá como
sgte(x)=x ∪ {x}
entonces como el mínimo es 0 se debe de cumplir que si ∀ x ∈ N -> sig(x) ≠ 0, y a partir de ahí vamos generando conjunto1=sig(0)={0}
2=sig(1)={0,1}
3=sig(2)={0,1,2}
y se define al orden < como
a a ⊂ b
como podemos apreciar hemos logrado establecer un orden en el conjunto de los Naturales
¿Yahora como podemos hacer una inducción estructural?
Para lograr hacer una Inducción estructural debemos identificar el paso base, que en este caso va a ser el elemento mínimode nuestro conjunto, luego de eso hacer una hipótesis inductiva para el elemento x y lograr demostrar que para el sgte(x) esta también es verdadera.
¿Cómo podemos aplicar loaprendido para la verificación de software y en que nos beneficia?
Elemental mi querido lector, al poder contemplar como un conjunto los valores admitidos por nuestroprograma, podremos contemplar las excepciones y hacer nuestro software más robusto e inquebrantable para el usuario. He aquí un pequeño ejemplo de cómo aplicar todo lo descrito
(x:A) (S(x) -> S(sgte(x))) -> (x:A) (S(x))
Ahora para los que no tengan un conocimiento sobre lo que trata la teoría deconjuntos y sobre lo que se refiere a poseer un orden bien fundamentado, he aquí un breve ejemplo.
Pongamos el ejemplo de los números Naturales donde se define al conjunto N={0, 1, 2, 3….} para que este posea un orden bien fundamentado > debe poseer un elemento mínimo que es 0 y este se define como
0={}
luego tenemos un generador que llamaremossiguiente y se definirá como
sgte(x)=x ∪ {x}
entonces como el mínimo es 0 se debe de cumplir que si ∀ x ∈ N -> sig(x) ≠ 0, y a partir de ahí vamos generando conjunto1=sig(0)={0}
2=sig(1)={0,1}
3=sig(2)={0,1,2}
y se define al orden < como
a a ⊂ b
como podemos apreciar hemos logrado establecer un orden en el conjunto de los Naturales
¿Yahora como podemos hacer una inducción estructural?
Para lograr hacer una Inducción estructural debemos identificar el paso base, que en este caso va a ser el elemento mínimode nuestro conjunto, luego de eso hacer una hipótesis inductiva para el elemento x y lograr demostrar que para el sgte(x) esta también es verdadera.
¿Cómo podemos aplicar loaprendido para la verificación de software y en que nos beneficia?
Elemental mi querido lector, al poder contemplar como un conjunto los valores admitidos por nuestroprograma, podremos contemplar las excepciones y hacer nuestro software más robusto e inquebrantable para el usuario. He aquí un pequeño ejemplo de cómo aplicar todo lo descrito
Leer documento completo
Regístrate para leer el documento completo.