Differences

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

--- sav07_lecture_4 [2007/03/27 16:35]
leander.eyer
+++ sav07_lecture_4 [2007/03/27 16:48]
leander.eyer
@@ Line 270: / Line 270: @@
   assume(x ∉ alloc);
   alloc = alloc ∪ {x}
@@ Line 275: / Line 276: @@
 ==== 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 289: @@
 ===== Proving formulas with uninterpreted functions =====
@@ Line 302: / Line 305: @@
 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:
+Recall the following properties of the relation **equivalence**:
   - 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)
+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)
 Equality is a congruence with respect to all function symbols.