Quantifier Elimination - Basic Ideas

Basic Ideas

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 literals, that is, show that each formula of the form:

where each is a literal, is equivalent to a quantifier-free formula. Indeed, suppose we know how to eliminate quantifiers from conjunctions of formulae, then if is a quantifier-free formula, we can write it in disjunctive normal form

and use the fact that

is equivalent to

Finally, to eliminate a universal quantifier

where is quantifier-free, we transform into disjunctive normal form, and use the fact that is equivalent to

Read more about this topic:  Quantifier Elimination

Famous quotes containing the words basic and/or ideas:

    Justice begins with the recognition of the necessity of sharing. The oldest law is that which regulates it, and this is still the most important law today and, as such, has remained the basic concern of all movements which have at heart the community of human activities and of human existence in general.
    Elias Canetti (b. 1905)

    Heroes, whatever high ideas we may have of them, are mortal and not divine. We are all as God made us and many of us much worse.
    John Osborne (1929–1994)