tautologies

In logic, a tautology is a formula that is true under every possible interpretation. In propositional logic, a tautology is a proposition that evaluates to true under every truth assignment, equivalently a sentence φ such that ⊨ φ.

Common examples include p ∨ ¬p and p → p. More complex examples include (A ∧ B) → A or ¬(p ∧ ¬p). The constant truth ⊤ is, by definition, a tautology.

Tautologies are distinct from rhetorical tautologies in natural language, which are redundancies rather than logical truths. They are also related to analytic truths in philosophy: truths true by meaning alone. In logic, tautologies are precisely the logically valid formulas.

Identification: by truth tables, which show T for all valuations, by semantic entailment, or by a derivation in a deductive system that uses no premises. In predicate logic, a sentence is a tautology if it is true in every model and under every variable assignment.

Relation and constraints: Tautologies are the logical opposite of contradictions (always false) and of contingent truths. They form the backbone of logical laws and can serve as axioms or inference rules. The problem of deciding whether a propositional formula is a tautology is co-NP-complete.