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)
“Though living is a dreadful thing
And a dreadful thing is it
Life the niggard will not thank,
She will not teach who will not sing,
And what serves, on the final bank,
Our logic and our wit?”
—Philip Larkin (1922–1986)