Disjunction elimination

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, disjunction elimination^[1]^[2] (sometimes named proof by cases, case analysis, or or elimination), is the valid argument form and rule of inference that allows one to eliminate a disjunctive statement from a logical proof. It is the inference that if a statement $P$ implies a statement $Q$ and a statement $R$ also implies $Q$ , then if either $P$ or $R$ is true, then $Q$ has to be true. The reasoning is simple: since at least one of the statements P and R is true, and since either of them would be sufficient to entail Q, Q is certainly true.

If I'm inside, I have my wallet on me.

If I'm outside, I have my wallet on me.

It is true that either I'm inside or I'm outside.

Therefore, I have my wallet on me.

It is the rule can be stated as:

\frac{P \to Q, R \to Q, P \or R}{\therefore Q}

where the rule is that whenever instances of " $P \to Q$ ", and " $R \to Q$ " and " $P \or R$ " appear on lines of a proof, " $Q$ " can be placed on a subsequent line.

Formal notation

The disjunction elimination rule may be written in sequent notation:

(P \to Q), (R \to Q), (P \or R) \vdash Q

where $\vdash$ is a metalogical symbol meaning that $Q$ is a syntactic consequence of $P \to Q$ , and $R \to Q$ and $P \or R$ in some logical system;

and expressed as a truth-functional tautology or theorem of propositional logic:

(((P \to Q) \and (R \to Q)) \and (P \or R)) \to Q

where $P$ , $Q$ , and $R$ are propositions expressed in some formal system.

References

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

Disjunction elimination

Formal notation

See also

References