Tautologies are self evident truths, that require no assumptions to determine their veracity. Within the study of 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

$X\; \backslash lor\; \backslash lnot\; X$,

which is a tautology, denoted $\backslash top$, because regardless of the truth value of X, one of the disjuncts is true, making the whole statement true. The symbol $\backslash top$ 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

$X\; \backslash land\; \backslash lnot\; X$

that is always false regardless of the truth values of its parts is known as a contradiction on an inconsistency and is denoted $\backslash bot$.

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

$\backslash lbrace\; X\; \backslash lor\; \backslash lnot\; X\; \backslash rbrace\; \backslash vdash\; \backslash top,\; \backslash lbrace\backslash rbrace\; \backslash vdash\; \backslash top,\; \backslash top\; \backslash vdash\; X\; \backslash lor\; \backslash lnot\; X$

Two key truths about tautology are 1) $\backslash lnot\backslash top\; \backslash vdash\; \backslash bot$ and 2) $\backslash lnot\backslash bot\; \backslash vdash\; \backslash top$. So a non-tautology is an inconsistency and a non-inconsistency is a tautology.

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

$(\backslash forall\; x)(x=5)\backslash lor\backslash lnot(\backslash forall\; x)(x=5)$

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

$X\; \backslash lor\; \backslash lnot\; X$

and this is a tautology. In contrast, the statement

$(\backslash forall\; x)\backslash big((x=5)\backslash lor\backslash lnot(x=5)\backslash big)$

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 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.

See also

---

Normal forms

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

Related 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

Mathematical logic

Тавтология (логика) | Tautologie | Tautologi | Tautologie (Logik) | Tautoloogia | Tautología | Tautologie | Tautologia | טאוטולוגיה (לוגיקה) | Tautológia | Tautologie (stijlfiguur) | Tautologi | Tautologia | Тавтология | Tautologi (språkvetenskap) | 重言式