Differences

This shows you the differences between two versions of the page.

--- sav07_lecture_4 [2007/03/27 16:33]
leander.eyer
+++ sav07_lecture_4 [2007/03/28 14:49]
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.
@@ Line 41: / Line 43: @@
   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 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
@@ Line 193: / Line 202: @@
 The value of K is known for //global arrays// (statically defined). The case of dynamically allocated arrays (like the one in Java) will be dealt in a  further section.
@@ Line 217: / Line 227: @@
 Possible mathematical model: fields as functions from objects to objects.
-  left : Node => Node
+  left : Node -> Node
-  right : Node => Node
+  right : Node -> Node
 What is the meaning of assignment?
@@ Line 269: / Line 279: @@
   assume(x ∉ alloc);
   alloc = alloc ∪ {x}
@@ Line 274: / Line 285: @@
 ==== Dynamically allocated arrays ====
-When we allow dynamically allocated arrays, we introduce an additional parameter to the array function which identifies the array in question.
+When we allow dynamically allocated arrays, we introduce a new global function **array** which maps a pair (arrayID, index) to values.
   x[i] = v;
@@ Line 288: / Line 299: @@
 ===== Proving formulas with uninterpreted functions =====
+==== Congruence closure algorithm ====
+The congruence closure algorithm can be used to proove the correctness of quantifier free formulas by examining congruence closures of the statements in the formula.
+Recall the following properties of the relation **equivalence**:
+  - x = x (everything is equal to itself) (reflexivity)
+  - x = y -> y = x (symmetry)
+  - x = y ∧ y = z -> x = z (transitivity)
+A congruence is an equivalence relationship with the additional property
+  * (x1 = x2 ∧ y1 = y2) -> f(x1, y1) = f(x2, y2)
+  a ≡ b (mod n) is a congruence in respect to addition. Indeed:
+  a ≡ b (mod n) ∧ c ≡ d (mod n) -> a + c ≡ b + d (mod n)
-==== Congruence closure algorithm ====
-The congruence closure algorithm can be used to proove the correctness of quantifier free formulas by examining congruence closures of the statements in the formula.
-Recall the following properties of relations:
-  - x = x (everything is equal to itself)
-  - x = y -> y = x (reflexivity)
-  - x = y ∧ y = z -> x = z (transitivity)
-  - (x1 = x2 ∧ y1 = y2) -> f(x1, y1) = f(x2, y2) (equivalence in functions)
 Equality is a congruence with respect to all function symbols.