Invariable de boucle

Spécifiquement dans la logique de Floyd-Hoare de , l'exactitude partielle d'un tandis que la boucle est régie par la règle suivante de l'inférence :

$\ frac {\ {C \ terre I \} \ ; \ mathrm {} de corps \ ; \ {I \}} {\ {I \} \ ; \ mathbf {tandis que} \ (c) \ \ mathrm {} de corps \ ; \ {\ lnot C \ terre I \}}$

Règle ci-dessus est déductif étape qui a en tant que son lieu Hoare triple $\ {C \ terre I \} \ ; \ mathrm {} de corps \ ; \ {I \}$ . Ce triple est réellement une relation sur des états de machine. Si cette relation peut être montrée, la règle alors nous permet de conclure que l'exécution réussie du programme (c) body while mènera à partir d'un état dans lequel $I$ est vrai à un état dans lequel le $\ lnot C \ terre I$ se tient. Le booléen de formule I dans cette règle est connu en tant qu'invariable de boucle.

L'exemple suivant illustre comment cette règle fonctionne. Considérer le programme

tandis que (x<10) x : = x+1 ;

On peut alors prouver le triple suivant de Hoare :

$\ {x \ leq10 \} \ ; \ mathbf {tandis que} \ (x<10) \ x : = x+1 \ ; \ {x=10 \}$

Le C de condition de la boucle de while est $x<10$ . Un invariable utile I de boucle est le $x \ leq10$ . Dans ces prétentions il est possible de prouver le triple suivant de Hoare :

$\ {x<10 \ terre X \ leq10 \} \ ; X : = x+1 \ ; \ {x \ leq10 \}$

Tandis que ce triple peut être dérivé formellement des règles de la tâche de gouvernement de logique de Floyd-Hoare, il est également intuitivement justifié : Le calcul commence dans un état où $x<10 \ terre X \ leq10$ est vrai, qui signifie simplement que $x<10$ est vrai. Le calcul additionne 1 à x, ainsi il signifie que le $x \ leq10$ est encore vrai.

Sous ces lieux, la règle pour des boucles de while permet la conclusion suivante :

$\ {x \ leq10 \} \ ; \ mathbf {tandis que} \ (x<10) \ x : = x+1 \ ; \ {\ lnot (x<10) \ terre X \ leq10 \}$

Les jeux invariables de boucle un rôle important dans l'argument intuitif pour la justesse de la règle de Floyd-Hoare pour des boucles de while. L'invariable de boucle doit être vrai avant chaque itération du corps de boucle, et également après chaque itération du corps de boucle. Puisqu'une boucle de while est avec précision l'itération répétée du corps de boucle, elle suit que si l'invariable est vrai avant d'écrire la boucle, il doit également être vrai après sortie de la boucle.

En raison de la similitude fondamentale des boucles et des programmes récursifs du , la preuve de l'exactitude partielle des boucles avec des invariants est très semblable à prouver l'exactitude des programmes récursifs par l'intermédiaire de l'induction .

Random links: