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 | ||
sav08:simple_qe_for_integer_difference_inequalities [2009/04/21 19:14] vkuncak |
sav08:simple_qe_for_integer_difference_inequalities [2009/04/21 19:17] vkuncak |
||
---|---|---|---|
Line 80: | Line 80: | ||
++++ | ++++ | ||
- | $y < x + K$\\ | ||
- | $y + 1 \le x + K$\\ | ||
- | $y + (1-K) \le x$++ | ||
- | |||
- | What are conjunctions of literals equivalent to? ++++ | $\exists y. \bigwedge_{i=1}^n x_i+K_i \le y \land \bigwedge_{j=1}^m y + L_j \le z_j$ ++++ | ||
- | |||
- | How do we eliminate existential quantifier? ++++|\\ | ||
- | Using $x_i + K_1 \le y$ and $y \le z_j - L_j$\\ | ||
- | |||
- | $\bigwedge_{i,j} x_i + K_i \le z_j - L_j$\\ | ||
- | $\bigwedge_{i,j} x_i + (K_i + L_j) \le z_j$ | ||
- | ++++ | ||
==Example== | ==Example== | ||
Line 99: | Line 87: | ||
$\forall y \exists x . x \leq y \wedge x \neq y $ | $\forall y \exists x . x \leq y \wedge x \neq y $ | ||
- | ++|\\ | + | ++++|\\ |
$\exists x . x \leq y \wedge (x < y \vee y < x)$\\ | $\exists x . x \leq y \wedge (x < y \vee y < x)$\\ | ||
$\exists x . x \leq y \wedge (x + 1 \leq y \vee y + 1 \leq x)$\\ | $\exists x . x \leq y \wedge (x + 1 \leq y \vee y + 1 \leq x)$\\ | ||
$(\exists x . x \leq y \wedge x + 1 \leq y) \vee (\exists x . x \leq y \wedge y + 1 \leq x)$\\ | $(\exists x . x \leq y \wedge x + 1 \leq y) \vee (\exists x . x \leq y \wedge y + 1 \leq x)$\\ | ||
- | Without lower or upper bounds, formulas is $true$\\ | + | Because there are no lower or upper bounds, these formulas are $true$\\ |
- | $\exists x . x + 0 \leq y \wedge x + 1 \leq y$ is $true$, then the entire formula is $true$ | + | ++++ |
- | ++ | + | |
If we apply this technique to a closed formula in this theory, what formulas do we obtain as a result? | If we apply this technique to a closed formula in this theory, what formulas do we obtain as a result? | ||