Hoare triple para asignación P {x / E} x: = E {P}

Question

Estoy tratando de comprender la lógica de Hoare presentado en Wikipedia, lógica de Hoare en Wikipedia Al parecer, si he entendido bien, un triple de Hoare $$ \ {P \} ~ ~ C \ {Q \} $$ medios

si P justo antes de C, entonces Q sostiene inmediatamente después de C, siempre y cuando C termina. (A)

Sin embargo, el esquema de asignación axioma parece interpretarse de una manera diferente:

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

La Wikipedia dice:

Los medios de asignación axioma de que la verdad de $ \ {P [x / E] \} $ es equivalente a la verdad después de la asignación de $ \ {P \} $. Por lo tanto eran $ \ {P [x / E] \} $ true antes de la asignación, por el axioma asignación, entonces $ \ {P \} $ sería cierto posterior a la que. Por el contrario, fueron de $ \ {P [x / E] \} $ false antes de la instrucción de asignación, $ \ {P \} $ debe entonces ser falsa en consecuencia.

Creo que el triple de Hoare sólo afirma que si P [x / E] antes de x: = E, entonces P (x) se cumple después de x: = E. No afirman, por su definición, que si P (x) tiene después de x: = E, entonces P [x / E] sostiene antes de x: = E.

Mi pregunta es ingenua, ¿cómo puede $ \ {P [x / E] \} $ antes de la asignación puede ser equivalente a $ \ {P \} $ después de la asignación? ¿Contradice esto con el punto (A) al comienzo de mi post?

Answer 1

Tenga en cuenta que lo que Wikipedia está diciendo es que

Los medios de asignación axioma de que la verdad de $ \ {P [x / E] \} $ es equivalente a la después de la asignación de verdad de $ \ {P \} $.

En otras palabras, ($ P $ mantiene después de la ejecución de $ x: = E $) if ($ P [x / E] $ mantiene antes de la ejecución). Esto es equivalente a la definición $ A $ que ya ha proporcionado, que generalmente es una definición más intuitiva para Hoare triple.

Answer 2

Parece que la redacción del texto de Wikipedia es raro en cierta medida:

Los medios de asignación axioma de que la verdad de {P [x / E]} es equivalente a la verdad después de la asignación de {P}.

El axioma asignación no quiere decir eso. Sólo significa que la verdad de P {[x / E]} implica la verdad después de la asignación de {P}. Esto no significa que la "equivalencia".

Sin embargo, la equivalencia es también un hecho válido. Es sólo que el axioma Hoare para la asignación no lo dice.

Una buena fuente para un tratamiento claro y riguroso de Hoare-como sistemas de prueba es Apt y Olderog de La verificación de programas concurrentes y secuenciales .

Answer 3

Significa más algo así como

si P era cierto antes C entonces Q será verdad después de eso.

Hay consideraciones de tiempo porque por lo general C cambiará el medio ambiente.

Think de este ejemplo: $ C = (x: = 42) $ y $ P = (x> 10) $. A continuación, la instancia de la regla tiene sentido.

EDIT: consideraciones de tiempo son importantes. Aquí, $ P $ donde "$ x = E $" (es decir, después) es equivalente a $ P [x / E] $ (antes). Tenga en cuenta que "$ x = E $" es sólo para designar el "después":. No es una verdadera igualdad desde $ x $ puede aparecer en $ E $

Por ejemplo

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

puede ayudarle a demostrar que

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

En una nota lateral, Yo he encontrado la notación $ P [x / E] $ muy confuso.