Disjunction elimination: Difference between revisions
imported>Soreningraham m Added a hatnote linking to Disjunctive syllogism since the shared name could bring readers to the wrong article. |
imported>Semaurer01 make display of expression more clear. |
||
| Line 6: | Line 6: | ||
| field = [[Propositional calculus]] | | field = [[Propositional calculus]] | ||
| statement = If a statement <math>P</math> implies a statement <math>Q</math> and a statement <math>R</math> also implies <math>Q</math>, then if either <math>P</math> or <math>R</math> is true, then <math>Q</math> has to be true. | | statement = If a statement <math>P</math> implies a statement <math>Q</math> and a statement <math>R</math> also implies <math>Q</math>, then if either <math>P</math> or <math>R</math> is true, then <math>Q</math> has to be true. | ||
| symbolic statement = <math>\ | | symbolic statement = <math> | ||
\begin{aligned} | |||
1.\quad & P \to Q \\ | |||
2.\quad & R \to Q \\ | |||
3.\quad & P \lor R \\ | |||
\therefore\quad & Q | |||
\end{aligned} | |||
</math> | |||
}} | }} | ||
{{Transformation rules}} | {{Transformation rules}} | ||
| Line 13: | Line 20: | ||
An example in [[English language|English]]: | An example in [[English language|English]]: | ||
:If I'm inside, I have my wallet on me. | :1. If I'm inside, I have my wallet on me. | ||
:If I'm outside, I have my wallet on me. | :2. If I'm outside, I have my wallet on me. | ||
:It is true that either I'm inside or I'm outside. | :3. It is true that either I'm inside or I'm outside. | ||
:Therefore, I have my wallet on me. | :Therefore, I have my wallet on me. | ||
It is the rule can be stated as: | It is the rule can be stated as: | ||
:<math>\ | :<math> | ||
\begin{aligned} | |||
1.\quad & P \to Q \\ | |||
2.\quad & R \to Q \\ | |||
3.\quad & P \lor R \\ | |||
\therefore\quad & Q | |||
\end{aligned} | |||
</math> | |||
where the rule is that whenever instances of "<math>P \to Q</math>", and "<math>R \to Q</math>" and "<math>P \lor R</math>" appear on lines of a proof, "<math>Q</math>" can be placed on a subsequent line. | where the rule is that whenever instances of "<math>P \to Q</math>", and "<math>R \to Q</math>" and "<math>P \lor R</math>" appear on lines of a proof, "<math>Q</math>" can be placed on a subsequent line. | ||
Latest revision as of 16:15, 20 September 2025
Template:Infobox mathematical statement Template:Transformation rules
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} implies a statement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q} and a statement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} also implies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q} , then if either Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} is true, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.
An example in English:
- 1. If I'm inside, I have my wallet on me.
- 2. If I'm outside, I have my wallet on me.
- 3. 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:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{aligned} 1.\quad & P \to Q \\ 2.\quad & R \to Q \\ 3.\quad & P \lor R \\ \therefore\quad & Q \end{aligned} }
where the rule is that whenever instances of "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P \to Q} ", and "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R \to Q} " and "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P \lor R} " appear on lines of a proof, "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q} " can be placed on a subsequent line.
Formal notation
The disjunction elimination rule may be written in sequent notation:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (P \to Q), (R \to Q), (P \lor R) \vdash Q}
where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vdash} is a metalogical symbol meaning that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q} is a syntactic consequence of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P \to Q} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R \to Q} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P \lor R} in some logical system;
and expressed as a truth-functional tautology or theorem of propositional logic:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (((P \to Q) \land (R \to Q)) \land (P \lor R)) \to Q}
where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} 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.