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_dense_linear_orders [2009/04/21 19:31] vkuncak |
sav08:simple_qe_for_dense_linear_orders [2009/04/21 19:34] vkuncak |
||
|---|---|---|---|
| Line 21: | Line 21: | ||
| * $x < y\ \land\ \lnot (y < z) \ \land\ (x \neq z)$ | * $x < y\ \land\ \lnot (y < z) \ \land\ (x \neq z)$ | ||
| * $x < y\ \land y < x$ | * $x < y\ \land y < x$ | ||
| + | |||
| + | If we have three concrete values for $x,y,z$, what is the form of the strongest type of a formula that we could write about them in this language? //(atomic type formula)// | ||
| + | |||
| + | Theorem: every quantifier-free formula in a language with only relational symbols is a disjunction of atomic type formulas | ||
| + | * if we know the set $T$ of axioms, we may be able to show that the atomic type formulas have a simple form | ||
| ===== Quantifier Elimination Step ===== | ===== Quantifier Elimination Step ===== | ||
| + | Quantifier elimination from atomic type formulas: | ||
| + | |||
| + | Quantifier elimination from more general formulas: | ||
| * [[http://www4.informatik.tu-muenchen.de/~nipkow/pubs/lqe.pdf|Linear Quantifier Elimination]] | * [[http://www4.informatik.tu-muenchen.de/~nipkow/pubs/lqe.pdf|Linear Quantifier Elimination]] | ||