Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav08:qe_from_conjunction_of_literals_suffices [2009/04/21 19:03] vkuncak |
sav08:qe_from_conjunction_of_literals_suffices [2009/04/21 19:04] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Quantifier Elimination from Conjunction of Literals is Sufficient ====== | ====== Quantifier Elimination from Conjunction of Literals is Sufficient ====== | ||
- | To show constructively that a theory has quantifier elimination, it suffices to show that we can eliminate an existential quantifier applied to a conjunction of [[wp>literal (mathematical logic)|literal]]s, that is, show that each formula of the form: | + | ((taken from [[wp>Quantifier Elimination]] to which it was originally contributed, so the Wikipedia sharing rights apply))To show constructively that a theory has quantifier elimination, it suffices to show that we can eliminate an existential quantifier applied to a conjunction of [[wp>literal (mathematical logic)|literal]]s, that is, show that each formula of the form: |
\[ | \[ | ||
\exists x. \bigwedge_{i=1}^n L_i | \exists x. \bigwedge_{i=1}^n L_i | ||
Line 23: | Line 23: | ||
\] | \] | ||
where $F$ is quantifier-free, we transform $\lnot F$ into disjunctive normal form, and use the fact that $\forall x. F$ is equivalent to $\lnot \exists x. \lnot F.$ | where $F$ is quantifier-free, we transform $\lnot F$ into disjunctive normal form, and use the fact that $\forall x. F$ is equivalent to $\lnot \exists x. \lnot F.$ | ||
- | |||
- | 1) taken from [[wp>Quantifier Elimination]] to which it was originally contributed, so the Wikipedia sharing rights apply | ||