Constructive Dilemma
From ProofWiki
Contents |
Theorem
- $p \implies q, r \implies s \vdash p \lor r \implies q \lor s$
Its abbreviation in a tableau proof is $\textrm{CD}$.
Alternative Renditions
It can alternatively be rendered as:
- $\vdash \left({\left({p \lor r}\right) \land \left({p \implies q}\right) \land \left({r \implies s}\right)}\right) \implies \left({q \lor s}\right)$
This can be seen to be logically equivalent to the form above by application of the Extended Rule of Implication.
Proof
Proof by Natural Deduction
By the tableau method:
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $p \implies q$ | P | (None) | ||
| 2 | 2 | $r \implies s$ | P | (None) | ||
| 3 | 3 | $p \lor r$ | A | (None) | ||
| 4 | 4 | $p$ | A | (None) | ||
| 5 | 1, 4 | $q$ | $\implies \mathcal E$ | 1, 4 | ||
| 6 | 1, 4 | $q \lor s$ | $\lor \mathcal I_1$ | 5 | ||
| 7 | 7 | $r$ | A | (None) | ||
| 8 | 2, 7 | $s$ | $\implies \mathcal E$ | 2, 7 | ||
| 9 | 2, 7 | $q \lor s$ | $\lor \mathcal I_2$ | 8 | ||
| 10 | 1, 2, 3 | $q \lor s$ | $\lor \mathcal E$ | 3, 4-6, 7-9 | The assumptions on lines 4 and 7 have been discharged. | |
| 11 | 1, 2 | $p \lor r \implies q \lor s$ | $\implies \mathcal I$ | 3, 10 | The assumption on line 3 has been discharged. |
$\blacksquare$
Proof by Truth Table
We apply the Method of Truth Tables to the proposition.
As can be seen for all models by inspection, where the truth value under the main connective on the LHS is $T$, that under the one on the RHS is also $T$:
- $\begin{array}{|ccccccc||ccccccc|} \hline (p & \implies & q) & \land & (r & \implies & s) & (p & \lor & r) & \implies & (q & \lor & s) \\ \hline F & T & F & T & F & T & F & F & F & F & T & F & F & F \\ F & T & F & T & F & T & T & F & F & F & T & F & T & T \\ F & T & F & F & T & F & F & F & T & T & F & F & F & F \\ F & T & F & T & T & T & T & F & T & T & T & F & T & T \\ F & T & T & T & F & T & F & F & F & F & T & T & T & F \\ F & T & T & T & F & T & T & F & F & F & T & T & T & T \\ F & T & T & F & T & F & F & F & T & T & T & T & T & F \\ F & T & T & T & T & T & T & F & T & T & T & T & T & T \\ T & F & F & F & F & T & F & T & T & F & F & F & F & F \\ T & F & F & F & F & T & T & T & T & F & T & F & T & T \\ T & F & F & F & T & F & F & T & T & T & F & F & F & F \\ T & F & F & F & T & T & T & T & T & T & T & F & T & T \\ T & T & T & T & F & T & F & T & T & F & T & T & T & F \\ T & T & T & T & F & T & T & T & T & F & T & T & T & T \\ T & T & T & F & T & F & F & T & T & T & T & T & T & F \\ T & T & T & T & T & T & T & T & T & T & T & T & T & T \\ \hline \end{array}$
Hence the result.
$\blacksquare$
Note that the two formulas are not equivalent, as the relevant columns do not match exactly.
Sources
- Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Theorem $\text{T48}$
- E.J. Lemmon: Beginning Logic (1965): $\S 1.3$: Exercise $1 \ \text{(h)}$
- Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.1$: Exercises $1.4: 2 \ \text{(d)}$
