Hoare tripla per assegnazione P {x / E} x: = E {P}
-
16-10-2019 - |
Domanda
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?
Soluzione
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.
Altri suggerimenti
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 .
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.