Inmathematical logic, atautology (fromAncient Greek:ταυτολογία) is aformula that is true regardless of the interpretation of its component terms, with only thelogical constants having a fixed meaning. For example, a formula that states "the ball is green or the ball is not green" is always true, regardless of what a ball is and regardless of its colour. Tautology is usually, though not always, used to refer to valid formulas ofpropositional logic.
The philosopherLudwig Wittgenstein first applied the term to redundancies ofpropositional logic in 1921, borrowing fromrhetoric, where atautology is a repetitive statement. In logic, a formula issatisfiable if it is true under at least one interpretation, and thus a tautology is a formula whose negation is unsatisfiable. In other words, it cannot be false.
Unsatisfiable statements, both through negation and affirmation, are known formally ascontradictions. A formula that is neither a tautology nor a contradiction is said to belogically contingent. Such a formula can be made either true or false based on the values assigned to its propositional variables.
Thedouble turnstile notation is used to indicate thatS is a tautology. Tautology is sometimes symbolized by "Vpq", and contradiction by "Opq". Thetee symbol is sometimes used to denote an arbitrary tautology, with the dual symbol (falsum) representing an arbitrary contradiction; in any symbolism, a tautology may be substituted for the truth value "true", as symbolized, for instance, by "1".[1]
Tautologies are a key concept inpropositional logic, where a tautology is defined as a propositional formula that is true under any possibleBoolean valuation of itspropositional variables.[2] A key property of tautologies in propositional logic is that aneffective method exists for testing whether a given formula is always satisfied (equiv., whether its negation is unsatisfiable).
The definition of tautology can be extended to sentences inpredicate logic, which may containquantifiers—a feature absent from sentences of propositional logic. Indeed, in propositional logic, there is no distinction between a tautology and alogically 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 afirst-order formula (one formula per propositional variable). The set of such formulas is aproper subset of the set of logically valid sentences of predicate logic (i.e., sentences that are true in everymodel).
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, apejorative meaning that is still used forrhetorical tautologies. Between 1800 and 1940, the word gained new meaning in logic, and is currently used inmathematical logic to denote a certain type of propositional formula, without the pejorative connotations it originally possessed.
In 1800,Immanuel Kant wrote in his bookLogic:
The identity of concepts in analytical judgments can be eitherexplicit (explicita) ornon-explicit (implicita). In the former case analytic propositions aretautological.
Here,analytic proposition refers to ananalytic truth, a statement in natural language that is true solely because of the terms involved.
In 1884,Gottlob Frege proposed in hisGrundlagen that a truth is analytic exactly if it can be derived using logic. However, he maintained a distinction between analytic truths (i.e., truths based only on the meanings of their terms) and tautologies (i.e., statements devoid of content).
In hisTractatus Logico-Philosophicus in 1921, 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 inScience and Hypothesis in 1905. AlthoughBertrand Russell at first argued against these remarks by Wittgenstein and Poincaré, claiming that mathematical truths were not only non-tautologous but weresynthetic, he later spoke in favor of them in 1918:
Everything that is a proposition of logic has got to be in some sense or the other like a tautology. It has got to be something that has some peculiar quality, which I do not know how to define, that belongs to logical propositions but not to others.
Here,logical proposition refers to a proposition that is provable using the laws of logic.
Many logicians in the early 20th century used the term 'tautology' for any formula that is universally valid, whether a formula ofpropositional logic or ofpredicate logic. In this broad sense, a tautology is a formula that is true under allinterpretations, or that is logically equivalent to the negation of a contradiction.Tarski andGödel followed this usage and it appears in textbooks such as that of Lewis and Langford.[3] This broad use of the term is less common today, though some textbooks continue to use it.[4][5]
Modern textbooks more commonly restrict the use of 'tautology' to valid sentences of propositional logic, or valid sentences of predicate logic that can be reduced to propositional tautologies by substitution.[6][7]
Propositional logic begins withpropositional variables, atomic units that represent concrete propositions. Aformula consists of propositional variables connected by logical connectives, built up in such a way that the truth of the overall formula can be deduced from the truth or falsity of each variable. Avaluation is a function that assigns each propositional variable to either T (for truth) or F (for falsity). So by using the propositional variablesA andB, the binary connectives and representingdisjunction andconjunction respectively, and the unary connective representingnegation, the following formula can be obtained:.
A valuation here must assign to each ofA andB either T or F. But no matter how this assignment is made, the overall formula will come out true. For if the first disjunct is not satisfied by a particular valuation, thenA orB must be assigned F, which will make one of the following disjunct to be assigned T. In natural language, either both A and B are true or at least one of them is false.
 | This article may be written in a style that istoo abstract to be readily understandable bygeneral audiences. Pleaseimprove it by using words and phrases that have precise, specific meanings within a particular field, as well as by adding examples.(May 2020) |
A formula of propositional logic is atautology if the formula itself is always true, regardless of which valuation is used for thepropositional variables. There are infinitely many tautologies.
In many of the following examplesA represents the statement "objectX is bound",B represents "objectX is a book", and C represents "objectX is on the shelf". Without a specific referent objectX, corresponds to the proposition "all bound things are books".
A minimal tautology is a tautology that is not the instance of a shorter tautology.
The problem of determining whether a formula is a tautology is fundamental in propositional logic. If there aren variables occurring in a formula then there are 2n distinct valuations for the formula. Therefore, the task of determining whether or not the formula is a tautology is a finite and mechanical one: one needs only to evaluate thetruth value of the formula under each of its possible valuations. One algorithmic method for verifying that every valuation makes the formula to be true is to make atruth table that includes every possible valuation.[2]
For example, consider the formula
There are 8 possible valuations for the propositional variablesA,B,C, represented by the first three columns of the following table. The remaining columns show the truth of subformulas of the formula above, culminating in a column showing the truth value of the original formula under each valuation.
| | | | |||||
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | F | T | T | T | T |
| F | T | F | F | T | F | T | T |
| F | F | T | F | T | T | T | T |
| F | F | F | F | T | T | T | T |
Because each row of the final column showsT, the sentence in question is verified to be a tautology.
It is also possible to define adeductive system (i.e., proof system) for propositional logic, as a simpler variant of the deductive systems employed for first-order logic (see Kleene 1967, 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 withn propositional variables requires a truth table with 2n lines, which quickly becomes infeasible asn increases). Proof systems are also required for the study ofintuitionistic propositional logic, in which the method of truth tables cannot be employed because the law of the excluded middle is not assumed.
A formulaR is said totautologically imply a formulaS if every valuation that causesR to be true also causesS to be true. This situation is denoted. It is equivalent to the formula being a tautology (Kleene 1967 p. 27).
For example, let be. Then is not a tautology, because any valuation that makes false will make false. But any valuation that makes true will make true, because is a tautology. Let be the formula. Then, because any valuation satisfying will make true—and thus makes true.
It follows from the definition that if a formula is a contradiction, then tautologically implies every formula, because there is no truth valuation that causes to be true, and so the definition of tautological implication is trivially satisfied. Similarly, if is a tautology, then is tautologically implied by every formula.
There is a general procedure, thesubstitution rule, that allows additional tautologies to be constructed from a given tautology (Kleene 1967 sec. 3). Suppose thatS is a tautology and for each propositional variableA inS a fixed sentenceSA is chosen. Then the sentence obtained by replacing each variableA inS with the corresponding sentenceSA is also a tautology.
For example, letS be the tautology:
LetSA be and letSB be.
It follows from the substitution rule that the sentence:
is also a tautology.
Anaxiomatic system iscomplete if every tautology is a theorem (derivable from axioms). An axiomatic system issound if every theorem is a tautology.
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 ofautomated theorem proving.
The method oftruth tables illustrated above is provably correct – the truth table for a tautology will end in a column with onlyT, while the truth table for a sentence that is not a tautology will contain a row whose final column isF, and the valuation corresponding to that row is a valuation that does not satisfy the sentence being tested. This method for verifying tautologies is aneffective 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 adecidable set.
As anefficient procedure, however, truth tables are constrained by the fact that the number of valuations that must be checked increases as 2k, wherek 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 theBoolean satisfiability problem; the problem of checking tautologies is equivalent to this problem, because verifying that a sentenceS is a tautology is equivalent to verifying that there is no valuation satisfying. The Boolean satisfiability problem isNP-complete, and consequently, tautology isco-NP-complete. It is widely believed that (equivalently for all NP-complete problems) nopolynomial-time algorithm can solve the satisfiability problem, although some algorithms perform well on special classes of formulas, or terminate quickly on many instances.[8]
The fundamental definition of a tautology is in the context of propositional logic. The definition can be extended, however, to sentences infirst-order logic.[9] These sentences may contain quantifiers, unlike sentences of propositional logic. In the context of first-order logic, a distinction is maintained betweenlogical validities, sentences that are true in every model, andtautologies (or,tautological validities), 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 symbolsR,S,T, the following sentence is a tautology:
It is obtained by replacing with, with, and with in the propositional tautology:.
Whether a given formula is a tautology depends on the formal system of logic that is in use. For example, the following formula is a tautology of classical logic but not ofintuitionistic logic:
|
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems (list) and paradoxes | |||||||||
| Logics |
| ||||||||
| Set theory |
| ||||||||
| Formal systems (list), language and syntax |
| ||||||||
| Proof theory | |||||||||
| Model theory | |||||||||
| Computability theory | |||||||||
| Related | |||||||||
| Major fields |
| ||||
|---|---|---|---|---|---|
| Foundations | |||||
| Lists |
| ||||
Commonlogical connectives | ||
|---|---|---|
 | ||
| Functional: |  | |
|---|---|---|
| Formal: | ||
| Negation | ||
Commonlogical symbols | |
|---|---|
| International | |
|---|---|
| National | |
