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 ideas, basic and/or ideas:
“It is a strange fact that freedom and equality, the two basic ideas of democracy, are to some extent contradictory. Logically considered, freedom and equality are mutually exclusive, just as society and the individual are mutually exclusive.”
—Thomas Mann (1875–1955)
“The man who is admired for the ingenuity of his larceny is almost always rediscovering some earlier form of fraud. The basic forms are all known, have all been practicised. The manners of capitalism improve. The morals may not.”
—John Kenneth Galbraith (b. 1908)
“These people who are always briskly doing something and as busy as waltzing mice, they have little, sharp, staccato ideas.... But they have no slow, big ideas. And the fewer consoling, noble, shining, free, jovial, magnanimous ideas that come, the more nervously and desperately they rush and run from office to office and up and downstairs, thinking by action at last to make life have some warmth and meaning.”
—Brenda Ueland (1891–1985)