Difference between revisions of "Tautology" - New World Encyclopedia
| Line 1: | Line 1: | ||
| − | Tautologies are statements that are always true because of their structure — they require no assumptions or evidence to determine their truth. | + | Tautologies are statements that are always true because of their structure — they require no assumptions or evidence to determine their truth. A tautology gives us no genuine information because it only repeats what we already know. |
In mathematics, ‘A = A’ is a tautology. In formal logic, the statements ‘P → P’ (interpreted in English as ‘If P then P’ or sometimes and less accurately as 'P implies P') and ‘P ≡ P’ (interpreted in English as ‘P if and only if P’ or sometimes and less accurately as 'P is logically equivalent to P’) are both tautologies. | In mathematics, ‘A = A’ is a tautology. In formal logic, the statements ‘P → P’ (interpreted in English as ‘If P then P’ or sometimes and less accurately as 'P implies P') and ‘P ≡ P’ (interpreted in English as ‘P if and only if P’ or sometimes and less accurately as 'P is logically equivalent to P’) are both tautologies. | ||
Revision as of 22:41, 2 July 2006
Tautologies are statements that are always true because of their structure — they require no assumptions or evidence to determine their truth. A tautology gives us no genuine information because it only repeats what we already know.
In mathematics, ‘A = A’ is a tautology. In formal logic, the statements ‘P → P’ (interpreted in English as ‘If P then P’ or sometimes and less accurately as 'P implies P') and ‘P ≡ P’ (interpreted in English as ‘P if and only if P’ or sometimes and less accurately as 'P is logically equivalent to P’) are both tautologies.
Tautologies versus validities
In predicate logic, a distinction is often made between tautologies and validities (or logical truths). From this perspective, a statement is considered a tautology if and only if it is a validity in propositional logic (that is, when everything within the scope of a quantifier is viewed as a black box). So for example the statement
would be a tautology because it can be rewritten in the form
and this is a tautology. In contrast, the statement
would be a validity but not a tautology, even though it is true in every possible interpretation, because there is no way to express it as a tautology in propositional logic. This distinction is not always observed.
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 truth-value assignments) that have to be checked increases as 2k, 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 "brute-force", exhaustive search strategies of tabular decision procedures.
See also
Normal forms
- Algebraic normal form
- Conjunctive normal form
- Disjunctive normal form
Related topics
|
|
|
Credits
New World Encyclopedia writers and editors rewrote and completed the Wikipedia article in accordance with New World Encyclopedia standards. This article abides by terms of the Creative Commons CC-by-sa 3.0 License (CC-by-sa), which may be used and disseminated with proper attribution. Credit is due under the terms of this license that can reference both the New World Encyclopedia contributors and the selfless volunteer contributors of the Wikimedia Foundation. To cite this article click here for a list of acceptable citing formats.The history of earlier contributions by wikipedians is accessible to researchers here:
The history of this article since it was imported to New World Encyclopedia:
Note: Some restrictions may apply to use of individual images which are separately licensed.
