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:
“Of course I lie to people. But I lie altruistically—for our mutual good. The lie is the basic building block of good manners. That may seem mildly shocking to a moralist—but then what isn’t?”
—Quentin Crisp (b. 1908)
“... I want to live and be happy. I believe that we cannot be one or the other by pushing the absurd to all its consequences. I am like everyone. To feel liberated, I sometimes wish death on my loved ones, I covet the wives forbidden to me by the laws of family and friendship. To be logical, I should then kill or possess. But I judge that these vague ideas are unimportant. I everyone tried to put them to reality, we could neither live nor be happy.”
—Albert Camus (1913–1960)