Hoare triple pour l'attribution P {x / E} x: = E {P}

Question

Je suis en train de comprendre la logique de Hoare présenté à Wikipédia, Apparemment, si je comprends bien, un $$ triple Hoare \ {P \} ~ C ~ \ {Q \} $$ moyens

  

P si juste avant C, alors Q est titulaire immédiatement après C, aussi longtemps que se termine C. (A)

Cependant, le schéma d'axiome d'affectation semble être interprétée d'une manière différente:

$$ \ frac {} {\ {P [x / E] \} ~~ x: = E ~~ \ {P \}} $$

Le wikipedia dit:

Les moyens d'axiome d'affectation que la vérité de $ \ {P [x / E] \} $ est équivalente à la cession après-vérité de $ \ {P \} $. Ainsi étaient $ \ {P [x / E] \} $ true avant la cession, par l'axiome d'affectation, alors $ \ {P \} $ serait vrai après quoi. A l'inverse, étaient $ \ {P [x / E] \} $ false avant l'instruction d'affectation, $ \ {P \} $ doit alors être faux en conséquence.

Je pense que la triple Hoare seulement affirme que, si P [x / E] avant x: = E, P (x) occupe après x: = E. Il n'a pas d'affirmer, par sa définition, que si P (x) détient après x: = E, P [x / E] tient avant x: = E.

Ma question est naïve, comment peut $ \ {P [x / E] \} $ avant l'affectation peut être équivalent à $ \ {P \} $ après la cession? Est-ce en contradiction avec le point (A) au début de mon message?

Answer 1

Notez que ce Wikipedia dit que

  

Les moyens d'axiome d'affectation que la vérité de $ \ {P [x / E] \} $ est équivalente à la

vérité après la cession de $ \ {P \} $. >

En d'autres termes, ($ P $ tient après l'exécution de $ x: = E $) if ($ P [x / E] détient $ avant l'exécution). Cela équivaut à la définition de $ A $ vous fourni, qui est généralement une définition plus intuitive pour Hoare triple.

Answer 2

Il semble que le libellé du texte de Wikipedia est flakey dans une certaine mesure:

  

Les moyens d'axiome d'affectation que la vérité de {P [x / E]} est équivalent à la

vérité de {P} après affectation.

L'axiome d'affectation ne signifie pas que. Il signifie que seulement la vérité de {P [x / E]} implique l'après cession de vérité {P}. Cela ne signifie pas la « équivalence ».

Cependant, l'équivalence est également un fait valable. Il est juste que l'axiome Hoare pour l'affectation ne le dit pas.

Une bonne source pour un traitement clair et rigoureux des systèmes de preuve Hoare comme Apt et est Olderog Vérification séquentielle et de programmes concurrents .

Answer 3

Cela signifie plus quelque chose comme

  

si P était vrai avant C alors Q sera vrai après.

Il y a des considérations de temps parce que généralement C changera l'environnement.

Considérez cet exemple: $ C = (x: = 42) $ et $ P = (x> 10) $. Ensuite, l'instance de votre règle est logique.

EDIT: considérations de temps sont importants. Ici, équivaut à $ P [x / E] $ (avant) $ P $ où "$ x = E $" (à savoir après). Notez que « $ x = E $ » est juste pour désigner le « après ». Ce n'est pas une égalité réelle depuis $ x $ peut apparaître dans $ E $

Par exemple

$$ \ {0 42> 10 \} ~~ x: = 0 ~~ \ {x + 42> 10 \} $$ $$ \ {x + 42> 10 \} ~~ x: = x + 42 ~~ \ {x> 10 \} $$

peut vous aider à prouver que

$$ \ {\ mbox {true} \} ~~ x: = 0 ~; ~ x: = x + 42 ~~ \ {x> 10 \} $$

Sur une note côté, je trouve personnellement la notation $ P [x / E] $ très confus.