Was ist der Unterschied zwischen vollständiger Korrektheit und teilweiser Korrektheit?


Antwort 1:

Eine vollständige Korrektheitsangabe ist auch eine teilweise Korrektheitsangabe. Partielle Korrektheit ist schwächer, weil sie die zusätzliche Hilfe von 'S terminates' benötigt, um zu der Schlussfolgerung zu gelangen: R gilt im Endzustand.

Für eine teilweise Korrektheitsspezifikation {Q} S {R} können Sie die folgenden Informationen erhalten: Wenn ein Startzustand gegeben ist, der Q erfüllt, kann S enden oder nicht. Wenn S endet, erreichen Sie nach der Ausführung von S einen Endzustand, der R erfüllt. Wenn nicht, ist R unbrauchbar, da es keinen Endzustand gibt.

Beispielsweise:

{x == 10}
während (y! = 0):
    y = y - 1
x = 0
{x == 0}

Es handelt sich um eine teilweise Richtigkeitsangabe. Wenn y mit einer Zahl gleich oder größer als 0 initialisiert wird, wird S beendet und danach ist x 0. Wenn y mit einer negativen Zahl beginnt, wird S für immer wiederholt, und da es nicht endet, werden Sie keinen Zustand erreichen. ' nach der Hinrichtung von S. '

Tatsächlich kann R alles sein, wenn S eine Dead-Loop ist. Zum Beispiel für jedes Q und R:

{Q}
während (wahr):
    y = y - 1
{R}

ist immer eine teilweise Richtigkeitsangabe.

Wenn Q nicht stark genug ist, können Sie die Beendigung von S nicht garantieren, geschweige denn den Zustand nach der Ausführung von S begründen. In diesem Fall können Sie eine Bedingung manuell hinzufügen: S bricht ab. Mit Q und it kann die Argumentation fortgesetzt werden.

Für die vollständige Korrektheitsspezifikation {Q} S {R} ist Q stark genug, um die Beendigung von S zu garantieren, sodass Sie schließen können, dass S beendet wird und der Endzustand R erfüllt.

Beispielsweise:

{x == 10}
während (x! = 0):
    x = x - 1
{x == 0}

ist eine vollständige Richtigkeitsangabe.

Übrigens: Ich bin nicht sicher, ob die Antwort richtig ist, da die Frage mit Political Correctness markiert ist. Während die Definition in der Frage genauso aussieht wie in der Informatik.