LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
sav08:qe_from_conjunction_of_literals_suffices [2009/04/21 19:04]
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.$
- 
-((taken from [[wp>​Quantifier Elimination]] to which it was originally contributed,​ so the Wikipedia sharing rights apply))