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:
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)