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:
“It seems to me that our three basic needs, for food and security and love, are so mixed and mingled and entwined that we cannot straightly think of one without the others. So it happens that when I write of hunger, I am really writing about love and the hunger for it, and warmth and the love of it and the hunger for it ... and then the warmth and richness and fine reality of hunger satisfied ... and it is all one.”
—M.F.K. Fisher (b. 1908)
“Because it is not always easy for an adult to predict what inaccurate ideas a child may have, it can help to answer questions first with one of your own: “What do you think?” Once you find out what a child is really asking, you’ll be in a better position to give a helpful answer based on the facts.”
—Joanna Cole (20th century)