Cómo encontrar el bucle invariante en Hoare Triples

Question

Oye, soy nuevo en Hoare Triples, y no puedo entender en encontrar los invariantes de bucle en la hipótesis.Por ejemplo, esto, mientras que el bucle

[x>1 & y>1] WHILE x>0 DO x:=x-1; y:=y+2 END [x+y>5].

El invariante es [2x + y> 5] pero no entiendo cómo encontrarlo.Una explicación paso a paso sobre cómo encontrarlo será muy apreciado.

Answer 1

Primero entiende el significado del bucle invariante. Significa una condición que es cierta en cada iteración del programa / algoritmo al principio, así como a la terminación del bucle. Tu programa es algo así.

$$ x> 1 \ texto {y} y> 1 $$

$$ \ texto {wills} x> 0 $$

$$ \ hspace {4cm} \ texto {do} x:= x - 1, y:= y + 2 $$

$$ \ texto {final} $$

$$ x + y> 5 $$

$ 2x + y> 5 $ es un invariante como lo describió. Es visible desde el programa que tanto $ x $ y $ y $ será mayor que $ 1 $ durante la primera iterataión del bucle. Por lo tanto, en la primera iteración de While Loop $ 2x + y> 5 $ (puede probarlo). Aviso en cada iteración del bucle while, el valor del $ x $ obtiene una disminución por valor $ 1 $ y El valor de Y está aumentando por dos, así que la desigualdad $ 2x + y> 5 $ estará satisfecho. Puedes probarlo. Ahora llega a la condición de terminación, en este punto $ x $ será un número negativo y mi reclamo es el valor de $ y $ va a ser al menos $ 5 $ . Por lo tanto, el invariante $ 2x + y> 5 $ si es verdadero a través de la iteración del bucle while.

Ejemplo:

Let $ x= 2 $ y $ y= 2 $ , luego $ 2 \ veces 2 + 2= 6> 5 $ está satisfecho. Ahora en la segunda iteración $ x= 1, y= 4 $ por lo $ 1 \ veces 2 + 4> 5 $ Satisfecho. Ahora $ x= 0, y= 6 $ , bucle terminado, $ 2 \ veces 0 + 6> 5 $ .