web.archive.org

tautology: Information and Much More from Answers.com

️Wed Jul 01 2015

In propositional logic, a tautology (from the Greek word ταυτολογία) is a sentence that is true in every valuation (also called interpretation) of its propositional variables, independent of the truth values assigned to these variables. For example, $(A \land B) \lor (\lnot A) \lor (\lnot B)$ is a tautology, because any valuation either makes A and B both true, or makes one or the other false. According to Kleene (1967, p. 12), the term was introduced by Ludwig Wittgenstein (1921).

The negation of a tautology is a contradiction, a sentence that is false regardless of the truth values of its propositional variables, and the negation of a contradiction is a tautology. A sentence that is neither a tautology nor a contradiction is logically contingent. Such a sentence can be made either true or false by choosing an appropriate interpretation of its propositional variables.

Examples

There are infinitely many tautologies. One example is

$A \lor \lnot A,$

the law of the excluded middle. A truth valuation for this formula must, by definition, assign A one of the truth value true or false, and assign $\lnot A$ the other truth value. Thus the disjunction in this law is satisfied by every valuation.

Another tautology is

$((A \land B) \to C) \Leftrightarrow (A \to (B \to C)).$

One method of verifying that every valuation causes this sentence to be true is to make a truth table that examines every possible valuation. 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 subsentences of the sentence above, culminating in a column showing the truth value of this sentence under each interpretation.

A	B	C	$A \land B$	$(A \land B) \to C$	B→C	A→(B→C)	$((A \land B) \to C) \Leftrightarrow (A \to (B \to C))$
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.

Notation

The notation $\vDash S$ is used to indicate that S is a tautology. The symbol $\top$ is sometimes used to denote an arbitrary tautology, with the dual symbol $\bot$ (falsum) representing an arbitrary contradiction.

Tautological implication

A sentence S is said to tautologically imply a sentence T if every truth valuation that causes S to be true also causes T to be true. This situation is denoted $S \vDash T$ . It is equivalent to the sentence S→T being a tautology (Kleene 1967 p. 27).

It follows from the definition that if S is a contradiction then S tautologically implies every sentence, because there is no truth valuation that causes S to be true and so the definition of tautological implication is trivially satisfied.

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 obtain by replacing each variable A in S with the corresponding sentence S_A is also a tautology.

For example, let S be $(A \land B) \lor (\lnot A) \lor (\lnot B)$ , a tautology. Let S_A be $C \lor D$ and let S_B be C→E. It follows from the substitution rule that the sentence

$((C \lor D) \land (C \to E)) \lor (\lnot (C \lor D) )\lor (\lnot (C \to E))$

is a tautology.

Verifying tautologies

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.

As an efficient procedure, however, truth tables are constrained by the fact that the number of valuations that must be checked increases as 2^k, 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 $\lnot S$ . 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.

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 obtain 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 $A \lor \lnot A$ is a tautology of propositional logic, $(\forall x ( x = x)) \lor (\lnot \forall x (x = x))$ 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:

$(((\exists x Rx) \land \lnot (\exists x Sx)) \to \forall x Tx) \Leftrightarrow ((\exists x Rx) \to ((\lnot \exists x Sx) \to \forall x Tx)).$

It is obtained by replacing A with $\exists x Rx$ , B with $\lnot \exists x Sx$ , and C with $\forall x Tx$ in the propositional tautology considered above.

Not all logical validities are tautologies in first-order logic. For example, the sentence

$(\forall x Rx) \to \lnot \exists x \lnot Rx$

is true in any first-order interpretation, but it corresponds to the propositional sentence A→B which is not a tautology of propositional logic.

Tautology and its application in Logic Synthesis

In Logic Synthesis tautology plays an important role especially for Logic Optimization. Though the problem is intractable, whether or not a function is a tautology can be efficiently answered using the Recursive Paradigm. Any binary-valued function F is a tautology if and only if its cofactors with respect to any variable and its complement are both tautologies. Hence it can be easily concluded whether or not a function F is reducible to a tautology by recursive Shannon Expansion and the application of the above theorem.

References

Enderton, H. B. (2002). A Mathematical Introduction to Logic. Harcourt/Academic Press. ISBN 0-12-238452-0
Kleene, S. C. (1967). Mathematical Logic. Reprinted 2002, Dover. ISBN 0-486-42533-9
Rechenbach, H. (1947). Elements of Symbolic Logic. Reprinted 1980, Dover. ISBN 0-486-24004-5
Wittgenstein, L. (1921). "Logisch-philosophiche Abhandlung," Annalen der Naturphilosophie (Leipzig), v. 14, pp. 185–262. Reprinted in English translation as Tractatus logico-philosophicus, New York and London, 1922.

External links

Eric W. Weisstein, Tautology at MathWorld.