Tautology (logic)

In logic, a tautology (from the Greek word ταυτολογία) is a formula or assertion that is true in every possible interpretation. An example of a tautology is '(x equals y) or (x does not equal y)'. A less abstract example is 'The ball is green or the ball is not green'. It is either one or the other - it cannot be both and there are no other possibilities. In logic, a tautology (from the Greek word ταυτολογία) is a formula or assertion that is true in every possible interpretation. An example of a tautology is '(x equals y) or (x does not equal y)'. A less abstract example is 'The ball is green or the ball is not green'. It is either one or the other - it cannot be both and there are no other possibilities. Philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921. (It had been used earlier to refer to rhetorical tautologies, and continues to be used in that alternative sense.) A formula is satisfiable if it is true under at least one interpretation, and thus a tautology is a formula whose negation is unsatisfiable. Unsatisfiable statements, both through negation and affirmation, are known formally as contradictions. A formula that is neither a tautology nor a contradiction is said to be logically contingent. Such a formula can be made either true or false based on the values assigned to its propositional variables. The double turnstile notation ⊨ S {displaystyle vDash S} is used to indicate that S is a tautology. Tautology is sometimes symbolized by 'Vpq', and contradiction by 'Opq'. The tee symbol ⊤ {displaystyle op } is sometimes used to denote an arbitrary tautology, with the dual symbol ⊥ {displaystyle ot } (falsum) representing an arbitrary contradiction; in any symbolism, a tautology may be substituted for the truth value 'true,' as symbolized, for instance, by '1.' Tautologies are a key concept in propositional logic, where a tautology is defined as a propositional formula that is true under any possible Boolean valuation of its propositional variables. A key property of tautologies in propositional logic is that an effective method exists for testing whether a given formula is always satisfied (or, equivalently, whether its negation is unsatisfiable). The definition of tautology can be extended to sentences in predicate logic, which may contain quantifiers, unlike sentences of propositional logic. In propositional logic, there is no distinction between a tautology and a logically valid formula. In the context of predicate logic, many authors define a tautology to be 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). The set of such formulas is a proper subset of the set of logically valid sentences of predicate logic (which are the sentences that are true in every model). The word tautology was used by the ancient Greeks to describe a statement that was asserted to be true merely by virtue of saying the same thing twice, a pejorative meaning that is still used for rhetorical tautologies. Between 1800 and 1940, the word gained new meaning in logic, and is currently used in mathematical logic to denote a certain type of propositional formula, without the pejorative connotations it originally possessed. In 1800, Immanuel Kant wrote in his book Logic: Here analytic proposition refers to an analytic truth, a statement in natural language that is true solely because of the terms involved. In 1884, Gottlob Frege proposed in his Grundlagen that a truth is analytic exactly if it can be derived using logic. But he maintained a distinction between analytic truths (those true based only on the meanings of their terms) and tautologies (statements devoid of content). In 1921, in his Tractatus Logico-Philosophicus, Ludwig Wittgenstein proposed that statements that can be deduced by logical deduction are tautological (empty of meaning) as well as being analytic truths. Henri Poincaré had made similar remarks in Science and Hypothesis in 1905. Although Bertrand Russell at first argued against these remarks by Wittgenstein and Poincaré, claiming that mathematical truths were not only non-tautologous but were synthetic, he later spoke in favor of them in 1918: