Pourquoi la règle d'affectation de la façon dont il est en Hoare Logique?

cs.stackexchange https://cs.stackexchange.com/questions/118322

Question

Pourquoi la règle d'affectation de la façon dont il est en Hoare Logique/Sémantique Axiomatique?Je ne peut pas envelopper la tête autour de laquelle la règle d'affectation de l'est vers l'arrière à partir de ce que j'attendais.

Je comprends Hoare logique de l'utiliser pour prouver propositions formelles de l'état d'un programme de commandes sont exécutées.Ainsi, si nous exécutons la commande $$x:=e$$ Je me serais attendu que le prochaine l'état a une telle substitution...mais il semble que la substitution se produit avant nous avons d'exécuter la mission que je trouve bizzare.Je me serais attendu:

$$ \{ P \} x:= e \{P[e/x]\}$$

Étant donné que $P$ sont des énoncés au sujet du programme de l'état.

Je suis sûr qu'il y est une bonne explication pour cela, et désolé si c'est une question de base, je sais que cela doit être.Mais quelqu'un peut-il m'expliquer?

Question Bonus:

Pourquoi ne pas écrire la règle d'affectation en tant que:

$$ \{ Q \} x:= e \{Q[x/e]\}$$

remarque ce n'est PAS le même que ma suggestion parce que nous avons le $x$ et $e$ inversées.c'est à diredans la post-condition où nous avons une $e$ nous avons $x$ (ce qui est bien parce que l'état nous venons d'exécuter, c'est que $x$ contient la valeur de $e$, et nous devrions donc être en mesure de remplacer $e$ pour $x$ dans la post-condition si la pré-condition de l'aide.

Related posts que j'ai lu qui ne l'ont pas aidé:

Annexe:

Pour nous dyslexiques, à cette question, c'est ce que le remplacement de la notation signifie:

$$ P[e/x] = P[e \x] $$

c'est à direremplacer chaque occurrence de $x$ avec l'expression/terme/thingie $e$.

Était-ce utile?

La solution

Alors, après avoir lu et pensé à cela, ceci est mon explication ( Merci logiciel Fondations ):

La confusion clé pour moi semble être la signification de $ p [e / x] $ (remplace chaque instance libre de x avec e). Ce que cela se trouve où que vous voyez le symbole $ x $ supprimer littéralement le retirer et placer $ e $ . par exemple. $ p [e / x]= (x + y + 1) [E / x] \ à p [e / x]= (E + Y + 1) $ Donc, remarquez comment $ x $ a littéralement disparu de $ p $ . Donc, ce que nous voulons, c'est une fois que nous faisons la mission:

$$ x:= e $$

que la déclaration est vraie si nous avions $ x $ au lieu de $ e $ . Donc, si la règle est:

$$ \ {p [e / x] \ \ \ \} x:= E \ {p \} $$

Alors ce que nous voulons, c'est que lorsque nous branchons $ x $ pour $ e $ nous voulons le déclaration en considération pour être vraie. Donc, avant que nous ayons commencé le code, nous avons $ p [e / x] $ . Ensuite, nous exécutons l'affectation et toutes les instances de $ e $ disparaissent et nous obtenons $ x remplace les. Que doit être vrai si le code qui a exécuté était affectation (puisque $ x $ maintient maintenant la valeur $ E $ , vous pouvez donc supprimer $ E $ 's et place $ x $ ).

C'est l'explication du concept abstrait. Permet (sans vergogne) Utilise l'exemple de fondations logicielles (SF):

{{y= 1}} x ::= y {{x= 1}} en anglais: Si nous commençons dans un état où la valeur de y est 1 et que nous assignions y à x, alors nous allons Terminer dans un état où X est 1. C'est-à-dire que la propriété d'être égale à 1 est transférée de y à x.

Un autre paragraphe utile de SF:

De même, dans {{Y + z= 1}} x ::= y + z {{x= 1}} La même propriété (étant égale à une) est transférée à X de l'expression Y + Z sur le côté droit de l'affectation. Plus généralement, si A est une expression arithmétique, alors {{A= 1}} x ::= a {{x= 1}} est un triple Hoare valide.

addendum de la grande observation du commentaire:

Il est important de reconnaître que la règle { P [ e / X ] } X := e { P } permet à la fois l'expression e et la variable X se produire dans la postcondition. En d'autres termes, la règle d'inférence vous permet de déduire une postconition dans laquelle tout sous-ensemble des occurrences de e dans la condition préalable ont été remplacés par X , y compris aucun d'entre eux. De plus, il vous permet de déduire simultanément toutes ces postconditions postérieures.

réponse à bonus pourquoi est

1) $ \ {p [e / x] \} x:= E \ {p \} $

mieux que

2) $ \ {q \ \} x:= E \ {q [x / e] \} $ :

Outre le point subtil du remplacement de X avec des expressions qui pourraient être invisibles (par exemple, E= 0, devrions-nous remplacer $ 0 $ avec un nombre infini de $ x $ 'S? Et si les zéros ne sont pas là ... Les règles doivent être syntaxiques mais je pense qu'il est préférable d'éviter de telles confusions), je pense que c'est la raison: < / p>

Quelle est la règle d'affectation de capturer, c'est que nous attribuons l'expression e à la variable x. Ainsi, seul X devrait être "remplacé" par e. Intuitivement, dans le code (ou plus précisément l'état du programme $ \ sigma $ ) lorsque x commence à maintenir la valeur E, il ne signifie pas aléatoire que partout où Il peut y avoir un e il devient x après avoir exécuté la mission x:= e $ . En fait, ce que cela signifie, c'est que maintenant dans la post-état, nous avons X's. Maintenant, ces x sont si nous n'avions pas l'affectation devrions avoir la valeur de $ e $ c'est-à-dire que "annuler" le remplacement / attribution de la commande de remplacement. Pas toutes les autres expressions aléatoires e. En bref, la seule façon de savoir où placer le correct E est en commençant par la poste après l'affectation, puis à partir de la place E. Si nous le faisons en arrière, nous ne remplacerons peut-être pas que nous ne voulions pas remplacer (même si elles étaient probablement vraies, ce que je suppose qu'ils devraient depuis que nous disons X maintient la valeur E après avoir attribué E à X).

Autres conseils

Supposons que nous sont en cours d'exécution du programme x := e, et laissez $\sigma$ être l'état initial, et $\sigma'$ être l'état final.

L'intuition fondamentale est ici:la valeur de $x$ dans le final état $\sigma'$ est la même que la valeur de l'expression $e$ dans le initiale état $\sigma$.En effet, ce dernier est la valeur que nous lui $x$ avec la commande x := e.

Donc, si $P(-)$ est une propriété sur les valeurs, la formule $P(\mbox{$x$dans l'état final})$ est équivalent à $P(\mbox{$e$-dans-le-état initial})$.En d'autres termes $P(x)$ dans le postcondition (dans l'état $\sigma'$) est vraiment à la hauteur $P(e)$ dans le condition préalable (dans l'état $\sigma$).

À l'aide de la substitution est seulement d'une manière plus formelle à considérer la postcondition comme une "formule qui dépend de l' $x$", c'est à direcomme $P(x)$, et puis nécessitant $P(e)$ comme condition préalable.

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top