Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav07_lecture_4 [2007/03/28 09:49] iulian.dragos |
sav07_lecture_4 [2007/03/28 14:45] cedric.jeanneret |
||
|---|---|---|---|
| Line 8: | Line 8: | ||
| We use weakest preconditions, although you could also use strongest postconditions or any other variants of the conversion from programs to formulas. | We use weakest preconditions, although you could also use strongest postconditions or any other variants of the conversion from programs to formulas. | ||
| + | |||
| Line 41: | Line 42: | ||
| havoc(x) = {(s,t) | ∀y "y"≠"x".t("y")=s("y")} | havoc(x) = {(s,t) | ∀y "y"≠"x".t("y")=s("y")} | ||
| - | FIXME | + | This is the relation that links all states where all variables but x remain unchanged. Intuitively, it makes sense that proving Q holds after visiting the havoc(x) relation, it is the same than proving Q for all values of x. |
| + | |||
| + | wp(Q,havoc(x)) = {(x1,y1) | ∀(x2,y2). ((x1,y1),(x2,y2)) ∈ havoc(x) -> (x2,y2) ∈ Q} | ||
| + | = {(x1,y1) | ∀(x2,y2). y1 = y2 -> (x2,y2) ∈ Q} | ||
| + | = {(x1,y1) | ∀x2. Q[y2:=y1]} | ||
| + | = ∀x. Q | ||
| + | |||
| + | Note that instead of using states s<sub>1</sub> and s<sub>2</sub>, pairs (x<sub>1</sub>,y<sub>1</sub>) and (x<sub>2</sub>,y<sub>2</sub>) are used. y stands for all unchanged variables. | ||
| * By wp semantics of havoc and assume | * By wp semantics of havoc and assume | ||