Come trovare il loop invariante in Hoare Triples

Question

Ehi, sono nuovo a Hoare Triples, e non riesco a capire di trovare gli invarianti del loop nell'ipotesi.Ad esempio questo mentre loop

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

.

L'invariante è [2x + y> 5] ma non capisco su come trovarlo.Una spiegazione passo dopo passo su come trovare sarà molto apprezzato.

Answer 1

Prima capisci il significato del loop invariante. Significa una condizione che è vera in ogni iterazione del programma / algoritmo all'inizio e alla terminazione del ciclo. Il tuo programma è qualcosa di simile.

$$ x> 1 \ testo {e} y> 1 $$

$$ \ text {while} x> 0 $$

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

$$ \ text {end} $$

$$ x + y> 5 $$

$ 2x + y> 5 $ è un invariante come hai descritto. È visibile dal programma che sia $ x $ e $ y $ sarà maggiore di $ 1 $ durante la prima iteraita del ciclo. Quindi nella prima iterazione di Thuch Loop $ 2x + y> 5 $ (puoi dimostrarlo). Avviso in ciascuna iterazione del modo in cui il valore del valore della $ x $ ottiene diminuzione per valore $ 1 $ e Il valore di Y sta diventando aumentato di due così disuguaglianti $ 2x + y> 5 $ sarà soddisfatto. Puoi dimostrarlo. Ora arriva alla condizione di terminazione, a questo punto $ x $ sarà un numero negativo e il mio reclamo è il valore della $ y $ sarà almeno $ 5 $ . Quindi l'invariante $ 2x + y> 5 $ si true attraverso l'iterazione del ciclo mentre loop.

Esempio:

Let $ x= 2 $ e $ y= 2 $ , quindi $ 2 \ volte 2 + 2= 6> 5 $ è soddisfatto. Ora nella seconda iterazione $ x= 1, y= 4 $ così $ 1 \ volte 2 + 4> 5 $ soddisfatto. Ora $ x= 0, y= 6 $ , loop terminato, $ 2 \ volte 0 + 6> 5 $ .