Tecnología de la ProgramaciónSemántica Operacional

David Cabrero Souto

Facultad de InformáticaUniversidade da Coruña

Curso 2007/2008

Verificación formal

Recordar descriptores BOE:

Diseño de algoritmosAnálisis de algoritmosLenguajes de programaciónDiseño de programas: Descomposición modular ydocumentaciónTécnicas de verificaciónPruebas de programas

Pruebas de programas: validación

Ejecución de un conjunto de tests generados sintética omanualmente.

Prueba formal de propiedades: verificación

Demostración formal de propiedades .Necesitamos una definición formal del significado (semántica)de los lenguajes de programación.

Verificación formal

Recordar descriptores BOE:

Diseño de algoritmosAnálisis de algoritmosLenguajes de programaciónDiseño de programas: Descomposición modular ydocumentaciónTécnicas de verificaciónPruebas de programas

Pruebas de programas: validación

Ejecución de un conjunto de tests generados sintética omanualmente.

Prueba formal de propiedades: verificación

Demostración formal de propiedades .Necesitamos una definición formal del significado (semántica)de los lenguajes de programación.

Verificación formal

Recordar descriptores BOE:

Diseño de algoritmosAnálisis de algoritmosLenguajes de programaciónDiseño de programas: Descomposición modular ydocumentaciónTécnicas de verificaciónPruebas de programas

Pruebas de programas: validación

Ejecución de un conjunto de tests generados sintética omanualmente.

Prueba formal de propiedades: verificación

Demostración formal de propiedades .Necesitamos una definición formal del significado (semántica)de los lenguajes de programación.

Verificación formal

Recordar descriptores BOE:

Diseño de algoritmosAnálisis de algoritmosLenguajes de programaciónDiseño de programas: Descomposición modular ydocumentaciónTécnicas de verificaciónPruebas de programas

Pruebas de programas: validación

Ejecución de un conjunto de tests generados sintética omanualmente.

Prueba formal de propiedades: verificación

Demostración formal de propiedades .Necesitamos una definición formal del significado (semántica)de los lenguajes de programación.

Verificación formal

Recordar descriptores BOE:

Diseño de algoritmosAnálisis de algoritmosLenguajes de programaciónDiseño de programas: Descomposición modular ydocumentaciónTécnicas de verificaciónPruebas de programas

Pruebas de programas: validación

Ejecución de un conjunto de tests generados sintética omanualmente.

Prueba formal de propiedades: verificación

Demostración formal (base matemática) de propiedades .Necesitamos una definición formal del significado (semántica)de los lenguajes de programación.

Verificación formal

Recordar descriptores BOE:

Diseño de algoritmosAnálisis de algoritmosLenguajes de programaciónDiseño de programas: Descomposición modular ydocumentaciónTécnicas de verificaciónPruebas de programas

Pruebas de programas: validación

Ejecución de un conjunto de tests generados sintética omanualmente.

Prueba formal de propiedades: verificación

Demostración formal (base matemática) de propiedades (paratodos los casos).Necesitamos una definición formal del significado (semántica)de los lenguajes de programación.

Verificación formal

Recordar descriptores BOE:

Diseño de algoritmosAnálisis de algoritmosLenguajes de programaciónDiseño de programas: Descomposición modular ydocumentaciónTécnicas de verificaciónPruebas de programas

Pruebas de programas: validación

Ejecución de un conjunto de tests generados sintética omanualmente.

Prueba formal de propiedades: verificación

Demostración formal (base matemática) de propiedades (paratodos los casos).Necesitamos una definición formal del significado (semántica)de los lenguajes de programación.

Lenguaje de ejemplo

IMP (IMPerativo)Estructuras básicas:

SecuenciaAlternativaRepetición

Cambio de estado: variables y asignación.Tipos básicos: enteros, strings.Tipos compuestos: arrays.Funciones.

IMP. Sintaxis aproximada

IMP ::= ’eof’| CMDS ’eof’

CMDS ::= CMD ’;’| CMD ’;’ CMDS

CMD ::= ’skip’| Type Variable ’:=’ EXP| Variable ’:=’ EXP| Type Variable ’[’ Exp ’]’ ’:=’ EXP| Variable ’[’ Exp ’]’ ’:=’ EXP| ’if’ EXP ’then’ CMDS ’else’ CMDS ’fi’| ’while’ EXP ’do’ CMDS ’done’| ’print’ EXP

Semántica operacional

Define la semántica de un lenguaje de programación enfunción de los cambios de estado que producen cada una delas instrucciones del lenguaje.No es adecuado para todo tipo de lenguajes.El estado se representa mediante un modelo o abstracción.

IMP- Definición (I)

Conjuntos sintácticos asociados con IMP.

números NBooleanos T = {true, false}Posiciones de memoria LocExpresiones aritméticas AexpExpresiones booleanas BexpComandos Com

IMP- Definición (I)

Conjuntos sintácticos asociados con IMP.

números NBooleanos T = {true, false}Posiciones de memoria LocExpresiones aritméticas AexpExpresiones booleanas BexpComandos Com

IMP- Definición (I)

Conjuntos sintácticos asociados con IMP.

números NBooleanos T = {true, false}Posiciones de memoria LocExpresiones aritméticas AexpExpresiones booleanas BexpComandos Com

IMP- Definición (I)

Conjuntos sintácticos asociados con IMP.

números NBooleanos T = {true, false}Posiciones de memoria LocExpresiones aritméticas AexpExpresiones booleanas BexpComandos Com

IMP- Definición (I)

Conjuntos sintácticos asociados con IMP.

números NBooleanos T = {true, false}Posiciones de memoria LocExpresiones aritméticas AexpExpresiones booleanas BexpComandos Com

IMP- Definición (I)

Conjuntos sintácticos asociados con IMP.

números NBooleanos T = {true, false}Posiciones de memoria LocExpresiones aritméticas AexpExpresiones booleanas BexpComandos Com

IMP- Definición (II)

Convenciones

n,m son variables en N n,m ∈ NX ,Y son variables en Loc X ,Y ∈ Locai son variables en Aexp ai ∈ Aexpbi son variables en Bexp bi ∈ Bexpci son variables en Com ci ∈ Com

IMP- Definición (II)

Convenciones

n,m son variables en N n,m ∈ NX ,Y son variables en Loc X ,Y ∈ Locai son variables en Aexp ai ∈ Aexpbi son variables en Bexp bi ∈ Bexpci son variables en Com ci ∈ Com

IMP- Definición (II)

Convenciones

n,m son variables en N n,m ∈ NX ,Y son variables en Loc X ,Y ∈ Locai son variables en Aexp ai ∈ Aexpbi son variables en Bexp bi ∈ Bexpci son variables en Com ci ∈ Com

IMP- Definición (II)

Convenciones

n,m son variables en N n,m ∈ NX ,Y son variables en Loc X ,Y ∈ Locai son variables en Aexp ai ∈ Aexpbi son variables en Bexp bi ∈ Bexpci son variables en Com ci ∈ Com

IMP- Definición (II)

Convenciones

n,m son variables en N n,m ∈ NX ,Y son variables en Loc X ,Y ∈ Locai son variables en Aexp ai ∈ Aexpbi son variables en Bexp bi ∈ Bexpci son variables en Com ci ∈ Com

IMP- Definición (Aexp)

Expresiones aritméticasAexp ::= n

| X| a0 + a1| a0 − a1| a0 ∗ a1

IMP- Definición (Bexp)

Expresiones booleanasBexp ::= true

| false| a0 = a1| a0 <= a1| not b| b0 and b1| b0 or b1

IMP- Definición (Comm)

InstruccionesComm ::= skip

| X := a| c0; c1| if b then c0 else c1 fi| while b do c done

Estados

El conjunto de estados Σ está formado por las funciones:σ : Loc− > N

(Sólo variables enteras)Dado un estado σ, representaremos el valor de la posicion Xcomo:

σ(X )

Y la extensión de un estado σ[X ← m]:

σ[X ← m](Y ) =

{m Y = X ,

σ(Y ) si Y 6= X .

Indistintamente σ[X ← m] ó σ[m/X ]

Evaluación

Evaluación de una expresión aritmética a en un estado σ< a, σ >→ n

Evaluación de una expresión booleana b en un estado σ< b, σ >→ {true, false}

Ejecución de una instrucción c en un estado σ< c, σ >→ σ′

Secuentes

Si las premisas son ciertas, se puede deducir la conclusión.

< premisas >< conclusion >

F1 . . .FnG1 . . .Gm

F1 . . .Fn → G1 . . .Gm

Las usaremos para definir la semántica operacional.

Evaluación de expresiones aritméticas

Constantes

< n, σ >→ n

Variables

< X , σ >→ σ(X )

Suma< a0, σ >→ n < a1, σ >→ m< a0 + a1, σ >→ n + m

Resta< a0, σ >→ n < a1, σ >→ m< a0 − a1, σ >→ n −m

Multiplicación

< a0, σ >→ n < a1, σ >→ m< a0 ∗ a1, σ >→ n ∗m

Evaluación de expresiones aritméticas

Constantes

< n, σ >→ n

Variables

< X , σ >→ σ(X )

Suma< a0, σ >→ n < a1, σ >→ m< a0 + a1, σ >→ n + m

Resta< a0, σ >→ n < a1, σ >→ m< a0 − a1, σ >→ n −m

Multiplicación

< a0, σ >→ n < a1, σ >→ m< a0 ∗ a1, σ >→ n ∗m

Evaluación de expresiones aritméticas

Constantes

< n, σ >→ n

Variables

< X , σ >→ σ(X )

Suma< a0, σ >→ n < a1, σ >→ m< a0 + a1, σ >→ n + m

Resta< a0, σ >→ n < a1, σ >→ m< a0 − a1, σ >→ n −m

Multiplicación

< a0, σ >→ n < a1, σ >→ m< a0 ∗ a1, σ >→ n ∗m

Evaluación de expresiones aritméticas

Constantes

< n, σ >→ n

Variables

< X , σ >→ σ(X )

Suma< a0, σ >→ n < a1, σ >→ m< a0 + a1, σ >→ n + m

Resta< a0, σ >→ n < a1, σ >→ m< a0 − a1, σ >→ n −m

Multiplicación

< a0, σ >→ n < a1, σ >→ m< a0 ∗ a1, σ >→ n ∗m

Evaluación de expresiones aritméticas

Constantes

< n, σ >→ n

Variables

< X , σ >→ σ(X )

Suma< a0, σ >→ n < a1, σ >→ m< a0 + a1, σ >→ n + m

Resta< a0, σ >→ n < a1, σ >→ m< a0 − a1, σ >→ n −m

Multiplicación

< a0, σ >→ n < a1, σ >→ m< a0 ∗ a1, σ >→ n ∗m

Evaluación de expresiones booleanas (I)

Constantes

< true, σ >→ true < false, σ >→ false

Comparación aritmética

< a0, σ >→ n < a1, σ >→ m< a0 = a1, σ >→ true

n = m

< a0, σ >→ n < a1, σ >→ m< a0 = a1, σ >→ false

n 6= m

< a0, σ >→ n < a1, σ >→ m< a0 <= a1, σ >→ true

n <= m

< a0, σ >→ n < a1, σ >→ m< a0 <= a1, σ >→ false

n > m

Evaluación de expresiones booleanas (I)

Constantes

< true, σ >→ true < false, σ >→ false

Comparación aritmética

< a0, σ >→ n < a1, σ >→ m< a0 = a1, σ >→ true

n = m

< a0, σ >→ n < a1, σ >→ m< a0 = a1, σ >→ false

n 6= m

< a0, σ >→ n < a1, σ >→ m< a0 <= a1, σ >→ true

n <= m

< a0, σ >→ n < a1, σ >→ m< a0 <= a1, σ >→ false

n > m

Evaluación de expresiones booleanas (II)

Negación

< b, σ >→ true< not b, σ >→ false

< b, σ >→ false< not b, σ >→ true

Conectivas lógicas

< b0, σ >→ t0 < b1, σ >→ t1< b0 and b1, σ >→ t

t = t0 ∧ t1

< b0, σ >→ t0 < b1, σ >→ t1< b0 or b1, σ >→ t

t = t0 ∨ t1

Evaluación de expresiones booleanas (II)

Negación

< b, σ >→ true< not b, σ >→ false

< b, σ >→ false< not b, σ >→ true

Conectivas lógicas

< b0, σ >→ t0 < b1, σ >→ t1< b0 and b1, σ >→ t

t = t0 ∧ t1

< b0, σ >→ t0 < b1, σ >→ t1< b0 or b1, σ >→ t

t = t0 ∨ t1

Evaluación de and optimizada

Implementación habitual

< b0, σ >→ false< b0 and b1, σ >→ false

< b0, σ >→ true < b1, σ >→ false< b0 and b1, σ >→ false

< b0, σ >→ true < b1, σ >→ true< b0 and b1, σ >→ true

Ejecución de instrucciones (I)

Skip

< skip, σ >→ σ

Asignación

< a, σ >→ m< X := a, σ >→ σ[X ← m]

Secuencia< c0, σ >→ σ′′ < c1, σ

′′ >→ σ′

< c0; c1, σ >→ σ′

Ejecución de instrucciones (I)

Skip

< skip, σ >→ σ

Asignación

< a, σ >→ m< X := a, σ >→ σ[X ← m]

Secuencia< c0, σ >→ σ′′ < c1, σ

′′ >→ σ′

< c0; c1, σ >→ σ′

Ejecución de instrucciones (I)

Skip

< skip, σ >→ σ

Asignación

< a, σ >→ m< X := a, σ >→ σ[X ← m]

Secuencia< c0, σ >→ σ′′ < c1, σ

′′ >→ σ′

< c0; c1, σ >→ σ′

Ejecución de instrucciones (II)

If< b, σ >→ true < c0, σ >→ σ′

< if b then c0 else c1 fi, σ >→ σ′

< b, σ >→ false < c1, σ >→ σ′

< if b then c0 else c1 fi, σ >→ σ′

While< b, σ >→ false

< while b do c done, σ >→ σ

< b, σ >→ true < c, σ >→ σ′′

< while b do c done, σ′′ >→ σ′

< while b do c done, σ >→ σ′

Ejecución de instrucciones (II)

If< b, σ >→ true < c0, σ >→ σ′

< if b then c0 else c1 fi, σ >→ σ′

< b, σ >→ false < c1, σ >→ σ′

< if b then c0 else c1 fi, σ >→ σ′

While< b, σ >→ false

< while b do c done, σ >→ σ

< b, σ >→ true < c, σ >→ σ′′

< while b do c done, σ′′ >→ σ′

< while b do c done, σ >→ σ′

Derivaciones

Derivación. Secuencia de aplicación de reglas.Axioma. Regla sin premisas.Instancia de un regla. Sustituimos las metavariables porvalores concretos.Las derivaciones representan ejecuciones de lasinstrucciones o evaluaciones de las expresiones.Ejemplo. a ≡ (X + 5) + (7 + 9) y σ0 = {X ← 0}¿< a, σ0 >?

< X , σ0 >→ 0 < 5, σ0 >→ 5< (X + 5), σ0 >→ 5

< 7, σ0 >→ 7 < 9, σ0 >→ 9< (7 + 9), σ0 >→ 16

< (X + 5) + (7 + 9), σ0 >→ 21 >

Terminación

Si w ≡ while true do skip,¿ ∀σ, ∃σ′t .q. < w , σ >→ σ′ ?

Preguntas

¿ Son iguales ?

skip ∼

b := 1 > 2;x := 1;while b do

x := x *2;b := x < 500;

done

Después de este código, ¿ X es par ?

while x < 3000 dox := x * 2;

done

Relaciones de equivalencia

a0 ∼ a1 iff(∀n ∈ N , ∀σ ∈ Σ, < a0, σ >→ n⇐⇒< a1, σ >→ n)

b0 ∼ b1 iff(∀t∀σ ∈ Σ, < b0, σ >→ t ⇐⇒< b1, σ >→ t)c0 ∼ c1 iff(∀σ, σ′ ∈ Σ, < c0, σ >→ σ′ ⇐⇒< c1, σ >→ σ′)

Prueba simple

ProposiciónSea w ≡ while b do c done con b ∈ Bexp, c ∈ Commentonces:

w ∼ if b then c; w else skip fiDemostración.Método menos laborioso: inducción de reglas.

Inducción matemática

Sea P(n) una propiedad de los números naturales.El principio de inducción matemática dice que para demostrarque P(n) es cierto para todos los números naturales essuficiente con demostrar que:

P(0) es cierto.Si P(m) es cierto, entonces también lo es P(m+1), paracualquier número natural m.

Es decir,

(P(0) & (∀m ∈ ω.P(m)⇒ P(m + 1)))⇒ ∀n ∈ ω.P(n)

Ejercicio. Demostrar que la propiedad P(n) se cumple paralos números naturales.

P(n) ⇐⇒n∑

i=1

(2i − 1) = n2

Inducción estructural

¿ Cómo demostramos que la evaluación de expresionesaritméticas en IMP es determinista ?

< a, σ >→ m & < a, σ >→ m′ ⇒ m = m′

Sea P(a) una propiedad de las expresiones aritméticas.Para demostrar que (P(a) se cumple para todas lasexpresiones artiméticas es suficiente con demostrar que:

Se cumple para todos los número P(m).Se cumple para todas la variables P(X ).Para todas la expresiones aritméticas a0, a1, si P(a0) y P(a1)se cumplen, entonces también se cumple P(a0 + a1).Para todas la expresiones aritméticas a0, a1, si P(a0) y P(a1)se cumplen, entonces también se cumple P(a0 − a1).Para todas la expresiones aritméticas a0, a1, si P(a0) y P(a1)se cumplen, entonces también se cumple P(a0 × a1).

Inducción estructural

¿ Cómo demostramos que la evaluación de expresionesaritméticas en IMP es determinista ?

< a, σ >→ m & < a, σ >→ m′ ⇒ m = m′

Sea P(a) una propiedad de las expresiones aritméticas.Para demostrar que (P(a) se cumple para todas lasexpresiones artiméticas es suficiente con demostrar que:

Se cumple para todos los número P(m).Se cumple para todas la variables P(X ).Para todas la expresiones aritméticas a0, a1, si P(a0) y P(a1)se cumplen, entonces también se cumple P(a0 + a1).Para todas la expresiones aritméticas a0, a1, si P(a0) y P(a1)se cumplen, entonces también se cumple P(a0 − a1).Para todas la expresiones aritméticas a0, a1, si P(a0) y P(a1)se cumplen, entonces también se cumple P(a0 × a1).

Inducción estructural cont.

(∀m ∈ N.P(m))& (∀X ∈ Loc.P(X ))& (∀a0,a1 ∈ Aexp.P(a0) y P(a1)⇒ P(a0 + a1))& (∀a0,a1 ∈ Aexp.P(a0) y P(a1)⇒ P(a0 − a1))& (∀a0,a1 ∈ Aexp.P(a0) y P(a1)⇒ P(a0 ∗ a1))⇒ ∀a ∈ Aexp.P(a)

Inducción estructural cont.

Proposición Para toda expresión aritmética a y números m y m′

< a, σ >→ m & < a, σ >→ m′ ⇒ m = m′

Demostración

Inducción bien fundada

Las anteriores son casos particulares.

Relación bien fundada Es una relación binaria ≺ sobre unconjunto A tal que no hay cadenas descendientesinfinitas · · · ≺ ai ≺ · · · ≺ a1 ≺ a0

Si a ≺ b decimos que a es un predecesor de b.

Es irreflexiva. 6 ∃a/a ≺ a

a � b ⇐⇒ a = b o a ≺ bProposición Sea ≺ una relación binaria en el conjunto A. La

relacion ≺ está bien fundada iff todos lossubconjuntos no vacíos Q de A tienen un elementominimal, i.e. un elemento m tal que

m ∈ Q&∀b ≺ m.b 6∈ Q

Inducción bien fundada

Las anteriores son casos particulares.

Relación bien fundada Es una relación binaria ≺ sobre unconjunto A tal que no hay cadenas descendientesinfinitas · · · ≺ ai ≺ · · · ≺ a1 ≺ a0

Si a ≺ b decimos que a es un predecesor de b.

Es irreflexiva. 6 ∃a/a ≺ a

a � b ⇐⇒ a = b o a ≺ bProposición Sea ≺ una relación binaria en el conjunto A. La

relacion ≺ está bien fundada iff todos lossubconjuntos no vacíos Q de A tienen un elementominimal, i.e. un elemento m tal que

m ∈ Q&∀b ≺ m.b 6∈ Q

Inducción bien fundada

Las anteriores son casos particulares.

Relación bien fundada Es una relación binaria ≺ sobre unconjunto A tal que no hay cadenas descendientesinfinitas · · · ≺ ai ≺ · · · ≺ a1 ≺ a0

Si a ≺ b decimos que a es un predecesor de b.

Es irreflexiva. 6 ∃a/a ≺ a

a � b ⇐⇒ a = b o a ≺ bProposición Sea ≺ una relación binaria en el conjunto A. La

relacion ≺ está bien fundada iff todos lossubconjuntos no vacíos Q de A tienen un elementominimal, i.e. un elemento m tal que

m ∈ Q&∀b ≺ m.b 6∈ Q

Inducción bien fundada (cont.)

Demostración

≺ está bien fundada⇐ m ∈ Q&∀b ≺ m.b 6∈ Q

Supongamos que todo conjunto no vacio de A tiene un elementominimal. Si ... ≺ ai ≺ ... ≺ a1 ≺ a0 es una cadena infinitadescendente, entonces el conjunto Q = {ai | i ∈ w} sería no vacíosin un elemento minimal. Por lo tanto ≺ está bien fundada.

≺ está bien fundada⇒ m ∈ Q&∀b ≺ m.b 6∈ Q

Suponer que Q es un subconjunto no vacío de A. Construimos unacadena de elementos de esta forma: tomamos un elemento a0 deQ. Inductivamente, asumimos que hemos construido en Q unacadena de elememntos an ≺ ... ≺ a0. Si no existe un b ∈ Q t.q.b ≺ an parar la construcción. En caso contrario tomar an+1 = b.Como ≺ es bien fundada la cadena ... ≺ ai ≺ ... ≺ a1... ≺ a0 nopuede ser infinita. Si es finita, de la forma an ≺ ... ≺ a0 con∀b ≺ an.b 6∈ Q. Tomar como elemento minimal an.

El principio de Inducción bien fundada

Sea ≺ una relacion bien fundada en un conjunto A. Sea Puna propiedad. Entonces ∀a ∈ A.P(a) iff:

∀a ∈ A.([∀b ≺ a.P(b)]⇒ P(a))

PruebaLa prueba se basa en la observación de que cualquiersubconjunto no vacío Q de un conjunto A con una relaciónbien fundada ≺ tiene un elemento minimal.

⇒Trivial⇐Asumimos ∀a ∈ A.([∀b ≺ a.P(b)]⇒ P(a)) y producimos unacontradicción suponiendo que ¬P(a) para algún a ∈ A.Entonces, tiene que existir un elemento minimal m para elconjunto {a ∈ A | ¬P(a)}. Pero entonces ¬P(m) y sinembargo ∀b ≺ m.P(m), lo cual contradice la asumción.

El principio de Inducción bien fundada

Sea ≺ una relacion bien fundada en un conjunto A. Sea Puna propiedad. Entonces ∀a ∈ A.P(a) iff:

∀a ∈ A.([∀b ≺ a.P(b)]⇒ P(a))

PruebaLa prueba se basa en la observación de que cualquiersubconjunto no vacío Q de un conjunto A con una relaciónbien fundada ≺ tiene un elemento minimal.

⇒Trivial⇐Asumimos ∀a ∈ A.([∀b ≺ a.P(b)]⇒ P(a)) y producimos unacontradicción suponiendo que ¬P(a) para algún a ∈ A.Entonces, tiene que existir un elemento minimal m para elconjunto {a ∈ A | ¬P(a)}. Pero entonces ¬P(m) y sinembargo ∀b ≺ m.P(m), lo cual contradice la asumción.

El principio de Inducción bien fundada

Sea ≺ una relacion bien fundada en un conjunto A. Sea Puna propiedad. Entonces ∀a ∈ A.P(a) iff:

∀a ∈ A.([∀b ≺ a.P(b)]⇒ P(a))

PruebaLa prueba se basa en la observación de que cualquiersubconjunto no vacío Q de un conjunto A con una relaciónbien fundada ≺ tiene un elemento minimal.

⇒Trivial⇐Asumimos ∀a ∈ A.([∀b ≺ a.P(b)]⇒ P(a)) y producimos unacontradicción suponiendo que ¬P(a) para algún a ∈ A.Entonces, tiene que existir un elemento minimal m para elconjunto {a ∈ A | ¬P(a)}. Pero entonces ¬P(m) y sinembargo ∀b ≺ m.P(m), lo cual contradice la asumción.

El principio de Inducción bien fundada

Sea ≺ una relacion bien fundada en un conjunto A. Sea Puna propiedad. Entonces ∀a ∈ A.P(a) iff:

∀a ∈ A.([∀b ≺ a.P(b)]⇒ P(a))

PruebaLa prueba se basa en la observación de que cualquiersubconjunto no vacío Q de un conjunto A con una relaciónbien fundada ≺ tiene un elemento minimal.

⇒Trivial⇐Asumimos ∀a ∈ A.([∀b ≺ a.P(b)]⇒ P(a)) y producimos unacontradicción suponiendo que ¬P(a) para algún a ∈ A.Entonces, tiene que existir un elemento minimal m para elconjunto {a ∈ A | ¬P(a)}. Pero entonces ¬P(m) y sinembargo ∀b ≺ m.P(m), lo cual contradice la asumción.

Ejemplos

Inducción matemática

n ≺ m ⇐⇒ m = n + 1

Inducción estructural

a ≺ b ⇐⇒ a es una subexpresión directa de b

Ejemplos

Inducción matemática

n ≺ m ⇐⇒ m = n + 1

Inducción estructural

a ≺ b ⇐⇒ a es una subexpresión directa de b

Ejercicio

Algoritmo de Euclides (máximo común divisor)Euclid ≡while (not (M = N)) do

if (M <= N) thenN := N - M;

elseM := M - N;

fidone

Teorema (Terminación). Para todos los estados σ

σ(M) ≥ 1 & σ(N) ≥ 1⇒ ∃σ′. < Euclid , σ >→ σ′

Ejercicio

Algoritmo de Euclides (máximo común divisor)Euclid ≡while (not (M = N)) do

if (M <= N) thenN := N - M;

elseM := M - N;

fidone

Teorema (Terminación). Para todos los estados σ

σ(M) ≥ 1 & σ(N) ≥ 1⇒ ∃σ′. < Euclid , σ >→ σ′

Ejercicio. Prueba

Deseamos probar que la propiedad

P(σ)⇔ ∃σ′. < Euclid , σ >→ σ′

se cumple ∀σ ∈ S = {σ ∈ Σ | σ(M) ≥ 1 & σ(N) ≥ 1}Usaremos inducción bien fundada sobre la relación:

σ‘ ≺ σ iff (σ′(M) ≤ σ(M) & σ′(N) ≤ σ(N)) &

(σ′(M) 6= σ(M) o σ′(N) 6= σ(N))

Ejercicio. Prueba

Deseamos probar que la propiedad

P(σ)⇔ ∃σ′. < Euclid , σ >→ σ′

se cumple ∀σ ∈ S = {σ ∈ Σ | σ(M) ≥ 1 & σ(N) ≥ 1}Usaremos inducción bien fundada sobre la relación:

σ‘ ≺ σ iff (σ′(M) ≤ σ(M) & σ′(N) ≤ σ(N)) &

(σ′(M) 6= σ(M) o σ′(N) 6= σ(N))