Como encontrar o invariante de loop em triplos hoare

Question

Ei, sou novo em triplos Hoare e não consigo entender como encontrar os invariantes de loop na hipótese.Por exemplo, este loop while

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

O invariante é [2x + y > 5], mas não entendo como encontrá-lo.Uma explicação passo a passo sobre como encontrá-lo será muito apreciada.

Answer 1

Primeiro entenda o significado do loop invariante.Significa uma condição que é verdadeira em cada iteração do programa/algoritmo no início e no final do loop.Seu programa é algo assim.

$$ x > 1 ext{ e } y >1 $$

$$ ext{Enquanto } x >0 $$

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

$$ exto{Fim}$$

$$x + y > 5$$

$2x+y >5$ é um invariante como você descreveu.É visível no programa que ambos $x$ e $y$ será maior que $1$ durante a primeira iteração do loop.Então, na primeira iteração do loop while $2x+y > 5$(você pode provar isso).Observe em cada iteração do loop while o valor do $x$ obtém diminuição em valor $1$ e o valor de y está aumentando em dois, então a desigualdade $2x+y >5$ ficará satisfeito.Você pode provar isso.Agora vamos para a condição de término, neste ponto $x$ será um número negativo e minha reivindicação é o valor de $y$ vai ser pelo menos $5$.Assim o invariante $2x+y > 5$ si true durante a iteração do loop while.

Exemplo :

Deixar $x=2$ e $y=2$, então $2 \vezes 2+2 = 6 > 5$ é satisfeito.Agora na segunda iteração $ x = 1, y = 4$ então $1 \vezes 2+4 > 5$ satisfeito.Agora $ x = 0, y = 6 $, loop encerrado, $2 \vezes 0+6 > 5$.