Tautology (logic) - Definition and Examples

Definition and Examples

A formula of propositional logic is a tautology if the formula itself is always true regardless of which valuation is used for the propositional variables.

There are infinitely many tautologies. Examples include:

  • ("A or not A"), the law of the excluded middle. This formula has only one propositional variable, A. Any valuation for this formula must, by definition, assign A one of the truth values true or false, and assign A the other truth value.
  • ("if A implies B then not-B implies not-A", and vice versa), which expresses the law of contraposition.
  • ("if not-A implies both B and its negation not-B, then not-A must be false, then A must be true"), which is the principle known as reductio ad absurdum.
  • ("if not both A and B, then either not-A or not-B", and vice versa), which is known as de Morgan's law.
  • ("if A implies B and B implies C, then A implies C"), which is the principle known as syllogism.
  • (if at least one of A or B is true, and each implies C, then C must be true as well), which is the principle known as proof by cases.

A minimal tautology is a tautology that is not the instance of a shorter tautology.

  • is a tautology, but not a minimal one, because it is an instantiation of .

Read more about this topic:  Tautology (logic)

Famous quotes containing the words definition and/or examples:

    No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.
    Florence Nightingale (1820–1910)

    It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.
    —G.C. (Georg Christoph)