Tautology (rule of inference)

Transformation rules
Propositional calculus
Rules of inference
Modus ponens / Modus tollens Biconditional introduction / elimination Conjunction introduction / elimination Disjunction introduction / elimination Disjunctive / Hypothetical syllogism Constructive / Destructive dilemma Absorption Modus ponendo tollens
Rules of replacement
Associativity Commutativity Distributivity Double negation De Morgan's laws Transposition Material implication Exportation Tautology Negation introduction
Predicate logic
Universal generalization / instantiation Existential generalization / instantiation

In propositional logic, tautology is one of two commonly used rules of replacement.^[1]^[2]^[3] The rules are used to eliminate redundancy in disjunctions and conjunctions when they occur in logical proofs. They are:

The principle of idempotency of disjunction:

P\lor P\Leftrightarrow P

and the principle of idempotency of conjunction:

P\land P\Leftrightarrow P

Where " $\Leftrightarrow$ " is a metalogical symbol representing "can be replaced in a logical proof with."

Formal notation

Theorems are those logical formulas $\phi$ where $\vdash \phi$ is the conclusion of a valid proof,^[4] while the equivalent semantic consequence $\models \phi$ indicates a tautology.

The tautology rule may be expressed as a sequent:

P\lor P\vdash P\,

and

P\land P\vdash P\,

where $\vdash$ is a metalogical symbol meaning that $P$ is a syntactic consequence of $P\lor P$ , in the one case, $P\land P$ in the other, in some logical system;

or as a rule of inference:

{\frac {P\lor P}{\therefore P}}

and

{\frac {P\land P}{\therefore P}}

where the rule is that wherever an instance of " $P\lor P$ " or " $P\land P$ " appears on a line of a proof, it can be replaced with " $P$ ";

or as the statement of a truth-functional tautology or theorem of propositional logic. The principle was stated as a theorem of propositional logic by Russell and Whitehead in Principia Mathematica as:

(P\lor P)\to P\,

and

(P\land P)\to P\,

where $P$ is a proposition expressed in some formal system.

References

↑ Hurley, Patrick (1991). A Concise Introduction to Logic 4th edition. Wadsworth Publishing. pp. 364–5.
↑ Copi and Cohen
↑ Moore and Parker
↑ Logic in Computer Science, p. 13

This article is issued from Wikipedia - version of the 3/22/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.