Proof by Cases/Proof Rule
Proof Rule
Proof by cases is a valid argument in types of logic dealing with disjunctions $\lor$.
This includes propositional logic and predicate logic, and in particular natural deduction.
As a proof rule it is expressed in the form:
- If we can conclude $\phi \lor \psi$, and:
- $(1): \quad$ By making the assumption $\phi$, we can conclude $\chi$
- $(2): \quad$ By making the assumption $\psi$, we can conclude $\chi$
- then we may infer $\chi$.
The conclusion $\chi$ does not depend upon either assumption $\phi$ or $\psi$.
It can be written:
- $\ds {\phi \lor \psi \quad \begin{array}{|c|} \hline \phi \\ \vdots \\ \chi \\ \hline \end{array} \quad \begin{array}{|c|} \hline \psi \\ \vdots \\ \chi \\ \hline \end{array} \over \chi} \lor_e$
Tableau Form
Let $\phi \lor \psi$ be a well-formed formula in a tableau proof whose main connective is the disjunction operator.
Let $\chi$ be a well-formed formula such that $\paren {\phi \vdash \chi}$, $\paren {\psi \vdash \chi}$.
Proof by Cases is invoked for $\phi \lor \psi$ as follows:
Pool: | The pooled assumptions of $\phi \lor \psi$ | ||||||||
The pooled assumptions of the instance of $\chi$ which was derived from the individual assumption $\phi$ | |||||||||
The pooled assumptions of the instance of $\chi$ which was derived from the individual assumption $\psi$ | |||||||||
Formula: | $\chi$ | ||||||||
Description: | Proof by Cases | ||||||||
Depends on: | The line containing the instance of $\phi \lor \psi$ | ||||||||
The series of lines from where the assumption $\phi$ was made to where $\chi$ was deduced | |||||||||
The series of lines from where the assumption $\psi$ was made to where $\chi$ was deduced | |||||||||
Discharged Assumptions: | The assumptions $\phi$ and $\psi$ are discharged | ||||||||
Abbreviation: | $\operatorname {PBC}$ |
Explanation
Proof by Cases can be expressed in natural language as follows:
We are given that either $\phi$ is true, or $\psi$ is true, or both.
Suppose we make the assumption that $\phi$ is true, and from that deduce that $\chi$ has to be true.
Then suppose we make the assumption that $\psi$ is true, and from that deduce that $\chi$ has to be true.
Therefore, it has to follow that the truth of $\chi$ follows from the fact of the truth of either $\phi$ or $\psi$.
Also known as
Proof by Cases is also known as the rule of or-elimination.
Also see
- This is a rule of inference of the following proof systems:
Technical Note
When invoking Proof by Cases in a tableau proof, use the {{ProofByCases}}
template:
{{ProofByCases|line|pool|statement|base|start1|end1|start2|end2}}
where:
line
is the number of the line on the tableau proof where Proof by Cases is to be invokedpool
is the pool of assumptions (comma-separated list)statement
is the statement of logic that is to be displayed in the Formula column, without the$ ... $
delimitersbase
is the line of the tableau proof where the disjunction being eliminated is situatedstart1
is the start line of the block of the tableau proof upon which the demonstration of the first disjunct directly dependsend1
is the end line of the block of the tableau proof upon which the demonstration of the first disjunct directly dependsstart2
is the start line of the block of the tableau proof upon which the demonstration of the second disjunct directly dependsend2
is the end line of the block of the tableau proof upon which the demonstration of the second disjunct directly depends
Sources
- 1964: Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning ... (previous) ... (next): $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 5$
- 1965: E.J. Lemmon: Beginning Logic ... (previous) ... (next): Chapter $1$: The Propositional Calculus $1$: $3$ Conjunction and Disjunction
- 2000: Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems ... (previous) ... (next): $\S 1.2.1$: Rules for natural deduction