Warum ist die Auftragsregel die Art und Weise, wie es in Horoy Logic ist?

Question

Warum ist die Auftragsregel die Art und Weise, wie es sich in der Horno-Logik / axiomatischen Semantik handelt? Ich kann meinen Kopf nicht umwickeln, warum die Zuweisungsregel zurückgekehrt ist, von dem, was ich erwartet habe.

Ich verstehe die Horologik, um formale Vorschläge des Status eines Programms als Befehle auszuführen. Wenn wir also den Befehl $$ x:= E $$ ausführen> Es scheint jedoch, dass die Substitution vor passiert, die wir die Aufgabe ausführen, die ich bizzare finde. Ich hätte erwartet:

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

Angesichts der $ p $ sind Anweisungen zum Programmstatienten.

Ich bin sicher, dass es eine gute Erklärung dafür gibt und tut mir leid, wenn dies eine grundlegende Frage ist, ich weiß, dass es sein muss. Aber kann jemand es mir erklären?

---

Bonusfrage:

Warum schreiben wir nicht die Zuordnungsregel als:

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

notieren Sie sich nicht dasselbe als mein ursprünglicher Vorschlag, da wir den $ x $ und $ E $ herumgetauscht. dh in der Nachbedingung, wo immer wir einen $ E $ haben, setzen wir einen $ x $ (das ist in Ordnung Da die Anweisung, die wir nur ausführen, ist, dass $ x $ den Wert von $ E $ hält, so sollten wir In der Lage sein, $ E $ für $ x $ in der Nachbedingung in der Nachbedingung, wenn die Vorbedingung hilft. < / p>

---

Verwandte Beiträge, die ich gelesen habe, die nicht geholfen habe:

.
• Hoare Triple für den Auftrag P {x / e} x := E {p}
• Wikipedia Hoare Logic
• https://www.quora.com/unanswed/why-is-the-tsignment-Rule-the-the--tum-is-in-Hoare-Logic
• https://www.reddit.com/r/programmingLanguages/ Kommentare / E8SUHH / WARUM_IST_THE_ASSIGNT_RULE_THE_WAY_It_Is_In_HOARE /

---

Anhang:

Für uns Legasthenics, in dieser Frage, bedeutet dies, was die Substitutionsnotation bedeutet:

$$ p [e / x]= p [e \ t \ to x] $$

d. H. Ersetzen Sie jedes freie Auftreten von $ x $ mit Ausdruck / Laufzeit / Thingie $ E $ .

Answer 1

also nach dem Lesen und Nachdenken darüber mehr dies ist meine Erklärung ( danke Software Fundamente ):

Die Schlüsselverwirrung für mich scheint die Bedeutung von $ P [e / x] $ (ersetzt jede freie Instanz von X mit E). Was dies tut, ist, wo auch immer Sie das Symbol $ x $ buchstäblich entfernen und $ E $ entfernen. z.B. $ p [e / x]= (x + y + 1) [e / x] \ to p [e / x]= (e + y + 1) $ Beachten Sie, wie $ x $ buchstäblich von $ P $ verschwunden ist. Also, was wir wollen, ist, sobald wir die Aufgabe erledigen:

$$ x:= E $$

dass die Anweisung trifft, wenn wir $ x $ anstelle von $ e $ hätten. Also, wenn die Regel ist:

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

was wir wollen, ist dann, wenn wir $ x $ für $ e $ wollen Erklärung in Betracht, um wahr zu sein. Bevor wir den Code begonnen haben, haben wir $ P [e / x] $ . Dann führen wir die Zuordnung und alle Instanzen von $ E $ verschwinden und wir erhalten $ x $ Sie ersetzen. Das muss seien Sie true, wenn der Code, der ausgeübt wurde (seit $ x $ jetzt den Wert $ E $ , so dass Sie $ E $ 's und Place $ x $ ).

das ist die Erklärung des abstrakten Konzepts. Verwenden Sie (schamlos) Verwenden Sie die Software-Fundamente (SF) Beispiel:

{{y= 1}} x ::= y {{x= 1}} in englisch: Wenn wir in einem Zustand anfangen, in dem der Wert von Y 1 ist und y x x, dann werden wir y Beenden Sie in einem Zustand, in dem X 1 ist. Das heißt, die Eigenschaft, gleich 1 zu sein, wird von y nach x übertragen.

Ein weiterer nützlicher Absatz von SF:

in ähnlicher Weise in {{Y + z= 1}} x ::= y + z {{x= 1}} Dieselbe Eigenschaft (gleich einem) wird von dem Expression y + z auf der rechten Seite der Zuordnung auf X vom Ausdruck y + z übertragen. Im Allgemeinen, wenn ein arithmetischer Ausdruck ist, dann {{a= 1}} x ::= a {{x= 1}} ist ein gültiges Hoare Triple.

---

Addendum aus der tollen Beobachtung des Kommentars:

Es ist wichtig, diese Regel zu erkennen { P. [ E. / X. ] } X. :=. E. { P. } erlaubt sowohl den Ausdruck E. und die Variable. X. in der Postkondition auftreten. Mit anderen Worten, die Inferenzregel ermöglicht Ihnen, eine Nachbedingung abzuleiten, in der jede Teilmenge der Vorkommnisse von E. in der Voraussetzung wurde ersetzt X. , auch keinen von ihnen. Darüber hinaus können Sie alle diese unterschiedlichen Nachbedingungen gleichzeitig ableiten.

---

Antwort auf Bonus, warum ist

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

besser als

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

Neben dem subtilen Punkt des Ersetzens von X mit Ausdrücken, die unsichtbar sein könnten (z. B. E= 0, sollten wir $ 0 $ durch eine unendliche Anzahl von $ x $ Was ist, wenn die Nullen nicht vorhanden sind ... Die Regeln sollten syntaktisch sein, aber ich denke, es ist besser, solche Verwirrungen zu vermeiden), denke ich, dass dies der Grund ist: < / p>

Welche Aufgabe der Zuordnung sollte die Erfassung sein, dass wir dem Ausdruck E der Variablen X zugewiesen werden. Somit sollte nur X von E "ersetzt" werden. Intuitiv, im Code (oder genauer der Status des Programms $ \ Sigma $ ), wenn X den Wert E anwendet, bedeutet dies nicht zufällig, wo überall wo Möglicherweise ist ein E-ES X, der nach der Ausführung der Zuordnung $ x:= E $ ausgeführt wird. In der Tat, was es bedeutet, ist, dass wir jetzt in der Nachbedingung X haben. Jetzt, wenn wir nicht die Aufgabe haben, sollte der Wert von $ E $ d. H. Wir nur "Rückgängig", den Ersatz / Zuweisung, den der Assignment-Befehl tat. Nicht jeder andere zufällige Ausdruck e. Kurz gesagt, der einzige Weg, um zu wissen, wo er den richtigen E-E-Mails platzieren soll, ist das, indem er in der Nachbedingung beginnt, nachdem die Zuordnung durchgeführt wurde, und beginnend von dort ENER. Wenn wir es rückwärts tun, könnten wir die E-Mails ersetzen. Wir wollten nicht ersetzen (auch wenn sie wahrscheinlich wahr waren, was ich vermute, dass sie sagen, da wir sagen, dass x den Wert E nach dem Zuweisen von E auf x hält).

Answer 2

Nehmen Sie an, wir führen Programmx := e aus, und lassen Sie den Anfangszustand $ \ Sigma $ Seien Sie der Anfangszustand und $ \ Sigma ' $ Seien Sie der letzte Zustand.

Die entscheidende Intuition hier ist: der Wert von $ x $ in der Final staat $ \ Sigma '$ ist derselbe wie der Wert des Ausdrucks $ E $ in der staatlichen initial staat "Math-Container"> $ \ Sigma $ . Tatsächlich ist Letzteres der Wert, den wir $ x $ mit dem Befehl generationspoDicetagcode zuweisen.

somit, wenn $ p (-) $ eine Eigenschaft auf Werten ist, die Formel $ P (\ mbox { $ x $ -in -in-the-Final-staat}) $ ist entspricht $ p (\ mbox {$ E $ -in -in-the-the-the-state}) $ . Mit anderen Worten $ P (x) $ in der postweite (in staatlicher $ \ Sigma ' $ ) äquivalent ist wirklich zu $ p (e) $ in der -voraussetzung (in state $ \ Sigma $ ).

Die Verwendung der Substitution ist nur eine formaler, um die Postkondition als "Formel, die von $ x $ abhängig zu sein, in Betracht ziehen, dh als $ P (x) $ , und dann erforderlich, und dann erforderlich $ p (e) $ als Vorbedingung.