Tautology (logic)
In
The philosopher
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 is used to indicate that S is a tautology. Tautology is sometimes symbolized by "Vpq", and contradiction by "Opq". The tee symbol is sometimes used to denote an arbitrary tautology, with the dual symbol (
Tautologies are a key concept in
The definition of tautology can be extended to sentences in
History
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
In 1800, Immanuel Kant wrote in his book Logic:
The identity of concepts in analytical judgments can be either explicit (explicita) or nonexplicit (implicita). In the former case analytic propositions are tautological.
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. 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 his
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 of
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]}
Background
Propositional logic begins with propositional variables, atomic units that represent concrete propositions. A formula 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. A valuation is a function that assigns each propositional variable to either T (for truth) or F (for falsity). So by 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:.
A valuation here must assign to each of A and B 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, then A or B 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.
Definition and examples
improve it by defining technical terminology, and by adding examples. (May 2020) 
A formula of propositional logic is a tautology if the formula itself is always true, regardless of which valuation is used for the propositional variables. There are infinitely many tautologies.
In many of the following examples A represents the statement "object X is bound", B represents "object X is a book", and C represents "object X is on the shelf". Without a specific referent object X, corresponds to the proposition "all bound things are books".
 ("A or not A"), the law of excluded middle. This formula has only one propositional variable, A. Any valuation for this formula must, by definition, assign A one of the truth values true or false, and assign A the other truth value. For instance, "The cat is black or the cat is not black".
 ("if A implies B, then notB implies notA", and vice versa), which expresses the law of contraposition. For instance, "If it's bound, it is a book; if it's not a book, it's not bound" and vice versa.
 ("if notA implies both B and its negation notB, then notA must be false, then A must be true"), which is the principle known as reductio ad absurdum. For instance, "If it's not bound, we know it's a book, if it's not bound, we know it's also not a book, so it is bound".
 ("if not both A and B, then notA or notB", and vice versa), which is known as De Morgan's law. "If it is not both a book and bound, then we are sure that it's not a book or that it's not bound" and vice versa.
 ("if A implies B and B implies C, then A implies C"), which is the principle known as hypothetical syllogism. "If it's bound, then it's a book and if it's a book, then it's on that shelf, so if it's bound, it's on that shelf".
 ("if at least one of A or B is true, and each implies C, then C must be true as well"), which is the principle known as proof by cases. "Bound things and books are on that shelf. If it's either a book or it's blue, it's on that shelf".
A minimal tautology is a tautology that is not the instance of a shorter tautology.
 is a tautology, but not a minimal one, because it is an instantiation of .
Verifying tautologies
The problem of determining whether a formula is a tautology is fundamental in propositional logic. If there are n variables occurring in a formula then there are 2^{n} 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 the truth 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 a truth table that includes every possible valuation.^{[2]}
For example, consider the formula
There are 8 possible valuations for the propositional variables A, 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 shows T, the sentence in question is verified to be a tautology.
It is also possible to define a
Tautological implication
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 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.
Substitution
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 S_{A} is chosen. Then the sentence obtained by replacing each variable A in S with the corresponding sentence S_{A} is also a tautology.
For example, let S be the tautology:
 .
Let S_{A} be and let S_{B} be .
It follows from the substitution rule that the sentence:
is also a tautology.
Semantic completeness and soundness
An axiomatic system is complete if every tautology is a theorem (derivable from axioms). An axiomatic system is sound if every theorem is a tautology.
Efficient verification and the Boolean satisfiability problem
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
As an
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 . The Boolean satisfiability problem is
Tautologies versus validities in firstorder logic
The fundamental definition of a tautology is in the context of propositional logic. The definition can be extended, however, to sentences in firstorder logic.^{[9]} These sentences may contain quantifiers, unlike sentences of propositional logic. In the context of firstorder logic, a distinction is maintained between logical validities, sentences that are true in every model, and tautologies (or, tautological validities), which are a proper subset of the firstorder logical validities. In the context of propositional logic, these two terms coincide.
A tautology in firstorder logic is a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a firstorder 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 firstorder 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 firstorder logic. For example, the sentence:
is true in any firstorder interpretation, but it corresponds to the propositional sentence which is not a tautology of propositional logic.
Tautologies in NonClassical Logics
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 of intuitionistic logic:
See also
Normal forms
Related logical topics

References
 ^ Weisstein, Eric W. "Tautology". mathworld.wolfram.com. Retrieved 20200814.
 ^ ^{a} ^{b} "tautology  Definition & Facts". Encyclopedia Britannica. Retrieved 20200814.
 ^ Lewis, C I; Langford, C H (1959). Symbolic Logic (2nd ed.). Dover.
 ^ Hedman, Shawn (2004). A First Course in Logic. Oxford University Press. p. 63.
 ^ Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic. Springer. p. 64.
 ^ Enderton, Herbert (2001). Mathematical Introduction to Logic. Academic Press. p. 88.
 ^ Hinman, Peter (2010). Fundamentals of Mathematical Logic. Springer. p. 98.
 ^ See SAT solver for references.
 ISSN 00281425.
Further reading
 Bocheński, J. M. (1959) Précis of Mathematical Logic, translated from the French and German editions by Otto Bird, Dordrecht, South Holland: D. Reidel.
 ISBN 0122384520.
 .
 Wittgenstein, L. (1921). "Logischphilosophiche Abhandlung", Annalen der Naturphilosophie (Leipzig), v. 14, pp. 185–262, reprinted in English translation as Tractatus logicophilosophicus, New York City and London, 1922.
External links
 "Tautology", Encyclopedia of Mathematics, EMS Press, 2001 [1994]