Hoare-Logik - vollständige Korrektheit der Schleifen

Betrachten Sie eine while-Schleife des Formulars:

$\texttt{while (C) {S}}$

mit die Bedingung und den Hauptteil der Schleife. $\texttt{C}$ $\texttt{S}$

Sei und jeweils eine Invariante und eine Variante dieser Schleife. Die Regel für die vollständige Korrektheit von while-Schleifen ist in meinem Lehrbuch gegeben durch: $\texttt{I}$ $\texttt{V}$

If $\texttt{I} \Rightarrow \texttt{V} \geq 0$

Und $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

Dann $[\texttt{I}] \, \texttt{while (C) {S}} \, [\texttt{I} \land \neg \texttt{C}]$

ich weiß, muss die Variante strikt abnehmen und auch durch Null begrenzt sein , damit die Schleife endet . Wenn ich das jedoch mathematisch übersetze, erhalte ich einen anderen Satz als in meinem Lehrbuch: $\texttt{V}$

[V \geq 0 \land V = v_{0}] S [V \geq 0 \land V < v_{0}]

$[\texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{V} \geq 0 \land \texttt{V} < v_0]$

Meine Frage : Sagen dieser letzte Satz und die Regel meines Lehrbuchs dasselbe darüber, was bewiesen werden muss, damit die Schleife endet? Mit anderen Worten: ist

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

das Gleiche wie

$\texttt{I} \Rightarrow \texttt{V} \geq 0$ zusammen mit $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

Warum oder warum nicht?

hoare-logic Dory
quelle

Die Behauptung, dass "𝚅 streng abnehmen muss und dass es auch durch Null begrenzt sein muss" ausreichend ist, ist irreführend. Sie brauchen auch, dass 𝚅 eine Funktion mit einem fundierten Bereich ist. Stellen Sie sich vor, Sie verwenden stattdessen die nicht negativen rationalen Zahlen und konstruieren ein Gegenbeispiel.

Kai

Antworten:

Sie sind insofern gleichwertig, als Sie jedes Mal, wenn Sie die Lehrbuchregel anwenden können, auch Ihre eigene Regel anwenden können und umgekehrt. Die Invariante für die beiden Regeln ist ähnlich, aber nicht gleich.

Konvertieren einer Lehrbuchregelinstanz in eine Instanz Ihrer Regel

Angenommen, wir haben eine Anwendung oder Ihre Lehrbuchregel. wir haben einige für die: $\texttt{I}$

$\texttt{I} \Rightarrow \texttt{V} \geq 0$ zusammen mit $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

Dann haben wir dank der obigen Implikation auch . Mit der Regel PrePost können wir die Invariante in ihre Entsprechung umschreiben und erhalten eine Anwendung Ihrer Regel: $\texttt{I} \iff \texttt{I} \land \texttt{V} \geq 0$

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

Hier verwenden wir dieselbe Invariante wie in der Lehrbuchregel.

Konvertieren einer Instanz Ihrer Regel in eine Lehrbuchregelinstanz

Nun zur umgekehrten Richtung. Angenommen, wir haben für Ihre Regel gefunden: $\texttt{I}$

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

Jetzt können wir nicht annehmen , daher können wir für die Lehrbuchregel verwenden. Wir können jedoch als neue Invariante . Wir haben trivialerweise durch Konstruktion (*). Weiter aus der Hypothese $\texttt{I} \Rightarrow \texttt{V} \geq 0$ $\texttt{I}$ $\texttt{I}' := \texttt{I} \land \texttt{V} \geq 0$ $\texttt{I}' \Rightarrow \texttt{V} \geq 0$

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

wir können erhalten (durch PrePost)

$[\texttt{I}' \land \texttt{C} \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I}' \land \texttt{V} < v_0]$ (**)

Die Eigenschaften (*) und (**) sind genau das, was wir brauchen, um die Lehrbuchregel anzuwenden.

Chi
quelle