In propositional logic, a tautology (from the Greek word ταυτολογία) is a propositional formula that is true under any possible valuation (also called a truth assignment or an interpretation) of its propositional variables. For example, the propositional formula ("A or not-A") is a tautology, because the statement is true for any valuation of A. Examples can be more complex such as ("A and B; or not-A; or not-B"). The philosopher Ludwig Wittgenstein first applied the term to propositional logic in 1921.
A tautology's negation is a contradiction, a propositional formula that is false regardless of the truth values of its propositional variables. Such propositions are called unsatisfiable. Conversely, a contradiction's negation is a tautology. 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.
A key property of tautologies is that an effective method exists for testing whether a given formula is always satisfied (or, equivalently, whether its complement is unsatisfiable). One such method uses truth tables. The decision problem of determining whether a formula is satisfiable is the Boolean satisfiability problem, an important example of an NP-complete problem in computational complexity theory.
The notation is used to indicate that S is a tautology. The symbol is sometimes used to denote an arbitrary tautology, with the dual symbol (falsum) representing an arbitrary contradiction.
In 1800, Immanuel Kant wrote in his book Logic:
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:
During the 1930s, the formalization of the semantics of propositional logic in terms of truth assignments was developed. The term tautology began to be applied to those propositional formulas that are true regardless of the truth or falsity of their propositional variables. Some early books on logic (such as Symbolic Logic by Lewis and Langford, 1932) used the term for any proposition (in any formal logic) that is universally valid. It is common in presentations after this (such as Kleene 1967 and Enderton 2002) to use tautology to refer to a logically valid propositional formula, but to maintain a distinction between tautology and logically valid in the context of first-order logic (see below).
Propositional logic begins with propositional variables, atomic units that represent concrete propositions. A formula consists of propositional variables connected by logical connectives in a meaningful way, so that the truth of the overall formula can be uniquely deduced from the truth or falsity of each variable. A valuation is a function that assigns each propositional variable either T (for truth) or F (for falsity). So, for example, using the propositional variables A and B, the binary connectives and representing disjunction and conjunction, respectively, and the unary connective representing negation, the following formula can be obtained:
There are infinitely many tautologies. Examples include:
For example, consider the formula
It is also possible to define a deductive system (proof system) for propositional logic, as a simpler variant of the deductive systems employed for first-order logic (see Kleene 1957, Sec 1.9 for one such system). A proof of a tautology in an appropriate deduction system may be much shorter than a complete truth table (a formula with n propositional variables requires a truth table with 2nlines, which quickly becomes infeasible as n increases). Proof systems are also required for the study of intuitionistic propositional logic, in which the method of truth tables cannot be employed because the law of the excluded middle is not assumed.
A formula R is said to tautologically imply a formula S if every valuation that causes R to be true also causes S to be true. This situation is denoted . It is equivalent to the formula being a tautology (Kleene 1967 p. 27).
For example, let S be . Then S is not a tautology, because any valuation that makes A false will make S false. But any valuation that makes A true will make S true, because is a tautology. Let R be the formula . Then , because any valuation satisfying R makes A true and thus makes S true
It follows from the definition that if a formula R is a contradiction then R tautologically implies every formula, because there is no truth valuation that causes R to be true and so the definition of tautological implication is trivially satisfied. Similarly, if S is a tautology then S is tautologically implied by every formula.
There is a general procedure, the substitution rule, that allows additional tautologies to be constructed from a given tautology (Kleene 1967 sec. 3). Suppose that S is a tautology and for each propositional variable A in S a fixed sentence SA is chosen. Then the sentence obtained by replacing each variable A in S with the corresponding sentence SA is also a tautology.
For example, let S be , a tautology. Let SA be and let SB be . It follows from the substitution rule that the sentence
The problem of constructing practical algorithms to determine whether sentences with large numbers of propositional variables are tautologies is an area of contemporary research in the area of automated theorem proving.
The method of truth tables illustrated above is provably correct – the truth table for a tautology will end in a column with only T, while the truth table for a sentence that is not a tautology will contain a row whose final column is F, and the valuation corresponding to that row is a valuation that does not satisfy the sentence being tested. This method for verifying tautologies is an effective procedure, which means that given unlimited computational resources it can always be used to mechanistically determine whether a sentence is a tautology. This means, in particular, the set of tautologies over a fixed finite or countable alphabet is a decidable set.
As an efficient procedure, however, truth tables are constrained by the fact that the number of valuations that must be checked increases as 2k, where k is the number of variables in the formula. This exponential growth in the computation length renders the truth table method useless for formulas with thousands of propositional variables, as contemporary computing hardware cannot execute the algorithm in a feasible time period.
The problem of determining whether there is any valuation that makes a formula true is the Boolean satisfiability problem; the problem of checking tautologies is equivalent to this problem, because verifying that a sentence S is a tautology is equivalent to verifying that there is no valuation satisfying . It is known that the Boolean satisfiability problem is NP complete, and widely believed that there is no polynomial-time algorithm that can perform it. Current research focuses on finding algorithms that perform well on special classes of formulas, or terminate quickly on average even though some inputs may cause them to take much longer.
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:
Not all logical validities are tautologies in first-order logic. For example, the sentence