Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:simple_qe_for_integer_difference_inequalities [2009/04/21 19:17] vkuncak |
sav08:simple_qe_for_integer_difference_inequalities [2009/04/22 00:04] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Simple QE for Integer Difference Inequalities ====== | ====== Simple QE for Integer Difference Inequalities ====== | ||
| + | |||
| Line 22: | Line 23: | ||
| ++++|It is formula with one free variable, $y$. | ++++|It is formula with one free variable, $y$. | ||
| - | So it must be built out of atomic formulas $y \leq y$ and $y=y$, and is therefore either true or false. | + | So it must be built out of atomic formulas $y \leq y$ and $y=y$, and is therefore it is either always true or always false, regardless of the value of $y$. It thus cannot be equivalent to the above formula. |
| ++++ | ++++ | ||
| **End.** | **End.** | ||
| Line 91: | Line 92: | ||
| $\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)$\\ | ||
| - | + | $true \vee false$\\ | |
| - | Because there are no lower or upper bounds, these formulas are $true$\\ | + | $true$ |
| ++++ | ++++ | ||