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 [2008/04/22 16:33] piskac |
sav08:simple_qe_for_dense_linear_orders [2009/04/21 19:32] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Simple QE for Dense Linear Orders ====== | ====== Simple QE for Dense Linear Orders ====== | ||
- | Example of dense linear order: rational numbers with less-than relation. Also, real numbers with less-than relation. | + | Example of dense linear order: rational numbers with less-than relation. (It works in the same way for real numbers with less-than relation.) |
===== Theory of Dense Linear Orders ===== | ===== Theory of Dense Linear Orders ===== | ||
- | Language ${\cal L} = \{ < \}$. | + | Language ${\cal L} = \{ < \}$. Atomic formulas are of two forms: |
+ | * $x=y$ | ||
+ | * $x < y$ | ||
+ | Literals are either atomic formulas or their negations. | ||
- | Formulas are formulas true in structure $(\mathbb{Q},<)$ for all values of free variables. | + | Formulas $T$ are the formulas that are closed formulas that are true in the structure $(\mathbb{Q},<)$ or rational numbers. |
===== Normal form of Formulas ===== | ===== Normal form of Formulas ===== | ||
+ | |||
+ | We have seen that it suffices to eliminate quantifiers from conjunctions of literals. | ||
+ | |||
+ | Can we assume that literals are of a special form? | ||
+ | |||
+ | **Example:** simplify these formulas: | ||
+ | * $x < y\ \land\ \lnot (y < z) \ \land\ (x \neq z)$ | ||
+ | * $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)// | ||
===== Quantifier Elimination Step ===== | ===== Quantifier Elimination Step ===== |