WikiDer > Hoarelogica

Hoarelogica ist eine formale Logik, die im Informatik wird verwendet, um darüber zu sprechen Programme zu begründen. Sie ist nach dem Schöpfer der Basis des Mechanismus benannt, Tony Hoare.

Hoaretriples und Korrektheit

Hoarelogica ist eine Anwendung der Prädikatsrechnung zur Programmentwicklung. Die Logik war in 1969 durch Tony Hoare im Artikel Eine axiomatische Grundlage für die Computerprogrammierung eingeführt. Das Hoare-Triple ist die Grundlage der Hoare-Logik:

${displaystyle {P}S{Q}}$,

in welchem ${Anzeigestil P}$ und ${Anzeigestil Q}$ sind logische Prädikatsformeln, die eine Menge von Zuständen beschreiben und ${Anzeigestil S}$ eine oder mehrere Anweisungen. Das heisere Triple ${displaystyle {P}S{Q}}$ bedeutet, dass, wenn sich ein Programm in einem Zustand befindet, in dem die Bedingung ${Anzeigestil P}$ (die Voraussetzung) gilt, und ${Anzeigestil S}$ ausgeführt wird, befindet sich das Programm dann in einem Zustand, in dem die Bedingung ${Anzeigestil Q}$ (die Postbedingung) gilt.

Ein heiseres Triple ${displaystyle {P}S{Q}}$ ist teilweise richtig, wenn: wenn geldt ${Anzeigestil P}$ im aktuellen Zustand wahr ist, und ${Anzeigestil S}$ ausgeführt wird, dann in dem Zustand, der nach ${Anzeigestil S}$ ausgeführt wird, ${Anzeigestil Q}$. Das könnte sein ${Anzeigestil S}$ endet nie, weil ${Anzeigestil S}$ endet in einer Endlosschleife (${Anzeigestil S}$beendet dann nicht). In diesem Fall gibt es keinen Zustand nach der Ausführung ${Anzeigestil S}$, und möge ${Anzeigestil Q}$ sei also eine willkürliche Formel.

Ein heiseres Triple ${displaystyle {P}S{Q}}$ ist ganz richtig, wenn es teilweise richtig ist und ${Anzeigestil S}$ endet immer.

Regeln zum Beweis der Hoare-Logik

Die Hoare-Logik enthält Beweisregeln, mit denen es möglich ist, die teilweise oder vollständige Richtigkeit eines Hoare-Tripels zu beweisen. Die ursprünglichen Beweisregeln verwendeten eine einfache, sequentielle Programmiersprache, aber viele Erweiterungen der Logik wurden von anderen entwickelt. Für eine einfache Programmiersprache bestehend aus Variablen, Zuweisungen, bedingten Sprüngen (wenn dann sonst) und Schleifen (während B tut) besteht die hoare Logik, mit der partielle Korrektheit bewiesen werden kann, aus folgenden Beweisregeln (für vollständige Korrektheit ist zusätzlich ein Beweis erforderlich, der das Programm immer beendet):

Attributionsaxiom

Mit dem Zuweisungsaxiom kann man über Variablenzuweisungen nachdenken.

${displaystyle {P[x eckslash f]} x{mathrel {:=}}f {P}}$

Hier steht ${displaystyle P[x Schrägstrich f]}$ für die Formel ${Anzeigestil P}$ wobei alle Vorkommen der Variablen ${Anzeigestil x}$ ersetzt werden durch ${displaystyle f}$. Mit diesem Axiom lässt sich zum Beispiel beweisen, dass das hoare Tripel ${Anzeigestil {y>5}x:=y{x>5}}$ ist richtig.

Inferenzregel

Die Inferenzregel kann die Vorbedingung eines Hoare-Triples verstärken oder die Nachbedingung abschwächen:

${displaystyle {frac {P' o Pquad {P} S {Q}quad Q o Q'}{{P'} S {Q'}}}}$

Kompositionsregel

Die Kompositionsregel ermöglicht das Nachdenken über Programme, die aus mehr als einem Befehl bestehen.

${displaystyle {frac {{P} S {Q}quad {Q} T {R}}{{P} Smathop {;} T {R}}}}$

Iterationsregel

Die Iterationsregel ermöglicht es Ihnen, über Schleifen nachzudenken.

${displaystyle {frac {{Plan B} S {P}}{{P} {mbox{while }}B{mbox{ do }}S {Plan lnot B}}}}$

In der obigen Zeile, ${Anzeigestil B}$ die Schleifenbedingung: Wenn die Schleife endet, dann ist ${Anzeigestil B}$ Nicht mehr wahr. Die Formel ${Anzeigestil P}$ ist eine Schleifeninvariante, eine Formel, die kurz davor und kurz danach immer wahr ist ${Anzeigestil S}$ ist durchgeführt.

Auswahlregel

Die Wahlregel wird verwendet, um zu argumentieren wenn-dann-sonst-Übungen.

${displaystyle {frac {{Plan B} S {Q}quad {Plan zB B} T {Q}}{{P} {mbox{if }}B{mbox{ then }}S{mbox{ else }}T { F}}}}$

Schwächste Voraussetzungen

Ein Beitrag aus dem Jahr 1975 zur heiseren Logik, von Edsger W. Dijkstraße, sollte schwächste Voraussetzungen geben. Die schwächste Voraussetzung einer Formel ${Anzeigestil Q}$ zu einem Programm een ${Anzeigestil S}$, geschrieben ${displaystyle {mathit {wp}}(S,Q)}$, ist die schwächste Bedingung ${Anzeigestil P}$ (die Bedingung, dass die größte Menge von Programmzuständen erfüllt) so dass ${displaystyle {P}S{Q}}$ ist ein völlig korrektes hoares Tripel (d.h. unter anderem das ${Anzeigestil S}$ beendet).

Die schwächste Voraussetzung lässt sich wie folgt berechnen:

• Vergeben:

${displaystyle {mathit {wp}}(x:=f,Q)=Q[x Backslash f]}$

• Sequentielle Zusammensetzung:

${displaystyle {mathit {wp}}(Smathop {;} T,Q)={mathit {wp}}(S,{mathit {wp}}(T,Q))}$

• Wahl:

${displaystyle {mathit {wp}}({ ext{if }}B{ ext{ then }}S{ ext{ else }}T,Q)=(B o {mathit {wp}}(S,Q))Land (zB B o {mathit {wp}}(T,Q))}$

• Wiederholung:

${displaystyle {mathit {wp}}({ ext{while }}B{ ext{ do }}S,Q)=existiert k,H_{k}}$

bei welchem

• ${displaystyle H_{0}=zB Elch Q}$
• ${displaystyle H_{k ​​​​1}=H_{0}lor {mathit {wp}}(S,H_{k})}$

Hier ist ${displaystyle H_{k}}$ induktiv definiert.

Literatur

• WAGEN. heiser. Eine axiomatische Grundlage für die Computerprogrammierung (pdf-Datei). Im: Mitteilungen der ACM. 12(10): 576–585, 1969.
• W.H.J. Feijen und A.J.M. aus Gasteren. Über eine Methode der Multiprogrammierung. Springer-Verlag, 1999.
• E. W. Dijkstra und C. S. Schölten. Prädikatenkalkül und Programmsemantik. Springer-Verlag, 1990.