Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
sav07_lecture_4 [2007/03/27 16:38] leander.eyer |
sav07_lecture_4 [2007/03/27 16:48] leander.eyer |
||
|---|---|---|---|
| Line 289: | Line 289: | ||
| ===== Proving formulas with uninterpreted functions ===== | ===== Proving formulas with uninterpreted functions ===== | ||
| + | |||
| + | |||
| Line 303: | 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. | 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 = x (everything is equal to itself) | ||
| - x = y -> y = x (reflexivity) | - x = y -> y = x (reflexivity) | ||
| - x = y ∧ y = z -> x = z (transitivity) | - 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. | Equality is a congruence with respect to all function symbols. | ||