Hoare tripla per assegnazione P {x / E} x: = E {P}

Question

Sto cercando di capire la logica Hoare presentato a Wikipedia, logica Hoare su Wikipedia A quanto pare, se ho capito bene, un Hoare $$ tripla \ {P \} ~ C ~ \ {Q \} $$ mezzi

se P appena prima C, allora Q tiene subito dopo C, fino a quando termina C. (A)

Tuttavia, lo schema di assegnazione assioma sembra essere interpretati in modo diverso:

$$ \ frac {} {\ {P [x / E] \} ~~ x: = E ~~ \ {P \}} $$

Il wikipedia dice:

I mezzi assegnazione assioma che la verità di $ \ {P [x / E] \} $ è equivalente alla verità dopo-assegnazione di $ \ {P \} $. Così erano $ \ {P [x / E] \} $ true prima della cessione, per l'assioma assegnazione, quindi $ \ {P \} $ sarebbe vero successivi a cui. Al contrario, sono stati di $ \ {P [x / E] \} $ false prima l'istruzione di assegnazione, $ \ {P \} $ deve poi essere falsa di conseguenza.

Credo che il Hoare tripla solo afferma che se P [x / E] prima di x: = E, allora P (x) detiene, dopo x: = E. Non è così affermano, per sua definizione, che se P (x) detiene, dopo x: = E, allora P [x / E] detiene prima x: = E.

La mia domanda ingenua è, come si può $ \ {P [x / E] \} $ prima della cessione può essere equivalente a $ \ {P \} $ dopo la cessione? Fa questo in contraddizione con il punto (A) all'inizio del post?

Answer 1

Si noti che ciò che Wikipedia sta dicendo è che

I mezzi assegnazione assioma che la verità di $ \ {P [x / E] \} $ è equivalente a verità dopo-assegnazione di $ \ {P \} $.

In altre parole, ($ P $ detiene dopo l'esecuzione di $ x: = E $) if ($ P [x / E] $ detiene prima dell'esecuzione). Questo è equivalente alla definizione $ A $ che hai fornito, che è generalmente una definizione più intuitiva per Hoare tripla.

Answer 2

Sembra che la formulazione del testo Wikipedia è flakey in una certa misura:

I mezzi assegnazione assioma che la verità di {P [x / E]} equivalente per la verità dopo-assegnazione di {P}.

L'assioma incarico non vuol dire che. E 'solo significa che la verità di {P [x / E]} implica la verità dopo-assegnazione di P {}. Ciò non significa che la "equivalenza".

Tuttavia, l'equivalenza è anche un fatto valido. E 'solo che l'assioma Hoare per l'assegnazione non lo dice.

Una buona fonte per una trattazione chiara e rigorosa di Hoare-come sistemi di prova è Apt e Olderog di verifica sequenziale e Concurrent programmi .

Answer 3

E 'significa più qualcosa del tipo

se P era vero prima di C allora Q sarà vero dopo.

Ci sono considerazioni di tempo, perché di solito C cambierà l'ambiente.

Pensate a questo esempio: $ C = (x: = 42) $ e $ P = (x> 10) $. Poi l'istanza di vostra regola ha un senso.

EDIT: considerazioni di tempo sono importanti. Qui, $ P $ dove "$ x = E $" (vale a dire dopo) è equivalente a $ P [x / E] $ (prima). Nota che "$ x = E $" è solo per designare il "dopo":. Non è una reale parità dato $ x $ può apparire in $ E $

Ad esempio

$$ \ {0 42> 10 \} ~~ x: = 0 ~~ \ {x + 42> 10 \} $$ $$ \ {x + 42> 10 \} ~~ x: = x + 42 ~~ \ {x> 10 \} $$

può aiutare a dimostrare che

$$ \ {\ mbox {true} \} ~~ x: = 0 ~; ~ x: = x + 42 ~~ \ {x> 10 \} $$

Una nota a parte, personalmente ho trovato la notazione $ P [x / E] $ molto confuso.