Assessment 
Biopsychology 
Comparative 
Cognitive 
Developmental 
Language 
Individual differences 
Personality 
Philosophy 
Social 
Methods 
Statistics 
Clinical 
Educational 
Industrial 
Professional items 
World psychology 
Philosophy Index: Aesthetics · Epistemology · Ethics · Logic · Metaphysics · Consciousness · Philosophy of Language · Philosophy of Mind · Philosophy of Science · Social and Political philosophy · Philosophies · Philosophers · List of lists
In propositional logic, a tautology (from the Greek word ταυτολογία) is a statement that is truthfunctionally valid—i.e. it is universally true, or true in every interpretation (or model or valuation). For example, the statement "If it rains, then it rains" is a tautology. Every theorem of propositional logic is a tautology, and so we can equivalently define 'tautology' as any theorem of propositional logic—i.e. any statement that is deducible from the empty set in some system of deduction of propositional logic, such as a natural deduction system. The term is often mistakenly applied to any validity (or theorem) of firstorder logic, though it applies only to a proper subset of such validities. The term was originally introduced by Ludwig Wittgenstein.
The negation of a tautology is clearly a contradiction, and the negation of a contradiction is clearly a tautology. Sometimes an arbitrary tautology is denoted by , and an arbitrary contradiction by , the latter of which is definable as , i.e. the negation of the former. (Of course, the former is definable as the negation of the latter.) A sentence that is neither a tautology (always true) nor a contradiction (always false) is logically contingent, i.e., possible of being true or false, depending on the interpretation of its nonlogical symbols.
Contents
Tautologies versus validities
The use of 'tautology', however, can be extended to firstorder logic since it includes propositional logic. It can be further extended to include sentences that are quantified in the following sense. Call any statement that is not a truthfunctional compound (i.e. not a conjunction, disjunction, conditional, etc.) a 'Boolean atom'. Then every atomic sentence is a Boolean atom, as is every quantified sentence—i.e. those of the form or . For example, and are Boolean atoms, while is not. Then a statement of firstorder logic is a tautology if the uniform relettering of each of its Boolean atoms yields a tautology in the propositional sense. Thus is not a tautology, since its Boolean relettering yields , while is a tautology. One could further extend this notion by taking statements to be equivalence classes of statements, each of which is closed under the property of its elements being variants of each other (e.g. ∀xP(x) is a variant of ∀yP(y), and likewise upon substituting any other variable for x in the former). Then the Boolean relettering of yields a tautology, since each disjunct falls under the same equivalence class.
Discovering tautologies
An effective procedure for checking whether a propositional formula is a tautology or not is by means of truth tables. As an efficient procedure, however, truth tables are constrained by the fact that the number of logical interpretations (or truthvalue assignments) that have to be checked increases as 2^{k}, where k is the number of variables in the formula. Algebraic, symbolic, or transformational methods of simplifying formulas quickly become a practical necessity to overcome the "bruteforce", exhaustive search strategies of tabular decision procedures.
References
See also
Normal forms
 Algebraic normal form
 Conjunctive normal form
 Disjunctive normal form
Related logical topics



Related topics
 Tautology (rhetoric), use of redundant language that adds no information.
This page uses Creative Commons Licensed content from Wikipedia (view authors). 