Rule of inference of propositional logic
Disjunction eliminationType | Rule of inference |
---|
Field | Propositional calculus |
---|
Statement | If a statement implies a statement and a statement also implies , then if either or is true, then has to be true. |
---|
Symbolic statement | ![{\displaystyle {\frac {P\to Q,R\to Q,P\lor R}{\therefore Q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f65ca3491625a828d2ad9b539c8e6cf1929a5752) |
---|
Transformation rules |
---|
Propositional calculus |
---|
Rules of inference |
---|
- Implication introduction / elimination (modus ponens)
- Biconditional introduction / elimination
- Conjunction introduction / elimination
- Disjunction introduction / elimination
- Disjunctive / hypothetical syllogism
- Constructive / destructive dilemma
- Absorption / modus tollens / modus ponendo tollens
- Negation introduction
|
Rules of replacement |
---|
- Associativity
- Commutativity
- Distributivity
- Double negation
- De Morgan's laws
- Transposition
- Material implication
- Exportation
- Tautology
|
Predicate logic |
---|
Rules of inference |
---|
- 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
implies a statement
and a statement
also implies
, then if either
or
is true, then
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.
An example in English:
- 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:
![{\displaystyle {\frac {P\to Q,R\to Q,P\lor R}{\therefore Q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f65ca3491625a828d2ad9b539c8e6cf1929a5752)
where the rule is that whenever instances of "
", and "
" and "
" appear on lines of a proof, "
" can be placed on a subsequent line.
Formal notation
The disjunction elimination rule may be written in sequent notation:
![{\displaystyle (P\to Q),(R\to Q),(P\lor R)\vdash Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f9683b30ac695f2f9d7975e7d3bef0c907beae8)
where
is a metalogical symbol meaning that
is a syntactic consequence of
, and
and
in some logical system;
and expressed as a truth-functional tautology or theorem of propositional logic:
![{\displaystyle (((P\to Q)\land (R\to Q))\land (P\lor R))\to Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/010eb34961a7edbd8fb09fe59e5d8874f130f325)
where
,
, and
are propositions expressed in some formal system.
See also
References
- ^ "Rule of Or-Elimination - ProofWiki". Archived from the original on 2015-04-18. Retrieved 2015-04-09.
- ^ "Proof by cases". Archived from the original on 2002-03-07.