Tautologies Versus Validities in First-order Logic
The fundamental definition of a tautology is in the context of propositional logic. The definition can be extended, however, to sentences in first-order logic (see Enderton (2002, p. 114) and Kleene (1967 secs. 17–18)). These sentences may contain quantifiers, unlike sentences of propositional logic. In the context of first-order logic, a distinction is maintained between logical validities, sentences that are true in every model, and tautologies, which are a proper subset of the first-order logical validities. In the context of propositional logic, these two terms coincide.
A tautology in first-order logic is a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable). For example, because is a tautology of propositional logic, is a tautology in first order logic. Similarly, in a first-order language with a unary relation symbols R,S,T, the following sentence is a tautology:
It is obtained by replacing with, with, and with in the propositional tautology .
Not all logical validities are tautologies in first-order logic. For example, the sentence
is true in any first-order interpretation, but it corresponds to the propositional sentence which is not a tautology of propositional logic.
Read more about this topic: Tautology (logic)
Famous quotes containing the words tautologies and/or logic:
“Propositions show what they say: tautologies and contradictions show that they say nothing.”
—Ludwig Wittgenstein (1889–1951)
“The American Constitution, one of the few modern political documents drawn up by men who were forced by the sternest circumstances to think out what they really had to face instead of chopping logic in a university classroom.”
—George Bernard Shaw (1856–1950)