Francais | English | Espanõl

From Wikipedia, the free encyclopedia

Contents 1 Tautologies versus validities 2 Discovering tautologies 3 References 4 See also 4.1 Normal forms 4.2 Related logical topics 4.3 Related topics

In logic, a tautology is a statement containing more than one sub-statement, that is true regardless of the truth values of its parts. For example, the statement "Either all crows are black, or not all of them are", is a tautology, because it is true no matter what color crows are. Expressing this formally, as a proposition with X representing "All crows are black" would give

<math>X \lor \lnot X</math>,

which is a tautology, denoted <math>\top</math>, because regardless of the truth value of X, one of the disjuncts is true, making the whole statement true. The symbol <math>\top</math> means a "generic" tautology in contexts where any old tautology will do, without being specific about exactly where the tautology lies.

A statement such as

<math>X \land \lnot X</math>

that is always false regardless of the truth values of its parts is known as a contradiction on an inconsistency and is denoted <math>\bot</math>.

In propositional logic, the symbol <math>\vDash</math> or <math>\vdash</math> may be placed before a sentence or formuale to indicate that it is a tautology. The blank to the left of the <math>\vdash</math> symbol means that no assumptions are required to logically deduce the material to the right of the symbol. So it is true to say:

<math>\lbrace X \lor \lnot X \rbrace \vdash \top, \lbrace\rbrace \vdash \top, \top \vdash X \lor \lnot X </math>

Two key truths about tautology are 1) <math> \lnot\top \vdash \bot </math> and 2) <math> \lnot\bot \vdash \top </math>. So not a tautology is an inconsistency and not an inconsistency is a tautology.

[edit] 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

<math>(\forall x)(x=5)\lor\lnot(\forall x)(x=5)</math>

would be a tautology because it can be rewritten in the form

<math>X \lor \lnot X</math>

and this is a tautology. In contrast, the statement

<math>(\forall x)\big((x=5)\lor\lnot(x=5)\big)</math>

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.

[edit] 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 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 "brute-force", exhaustive search strategies of tabular decision procedures.

[edit] References

[edit] See also

[edit] Normal forms

• Algebraic normal form
• Conjunctive normal form
• Disjunctive normal form

[edit] Related logical topics

Boolean algebra Boolean domain Boolean function Boolean logic

First-order logic Logical consequence Logical graph Propositional logic

Table of logic symbols Truth table Vacuous truth Zeroth order logic

[edit] Related topics

• Tautology (rhetoric), use of redundant language that adds no information.cs:Tautologie

da:Tautologi de:Tautologie et:Tautoloogia es:Tautología fr:Tautologie it:Tautologia he:טאוטולוגיה (לוגיקה) hu:Tautológia mk:Тавтологија (логика) nl:Tautologie (stijlfiguur) no:Tautologi pl:Tautologia ru:Тавтология sv:Tautologi (logik) zh:重言式