Self-Distributive Law for Conditional
Contents |
Theorem
The following is known as the Self-Distributive Law:
- $p \implies \left({q \implies r}\right) \dashv \vdash \left({p \implies q}\right) \implies \left({p \implies r}\right)$
We also have, interestingly, this result:
- $\left({p \implies q}\right) \implies r \vdash \left({p \implies r}\right) \implies \left({q \implies r}\right)$
... but:
- $\left({p \implies r}\right) \implies \left({q \implies r}\right) \not \vdash \left({p \implies q}\right) \implies r$
Alternative rendition
These can alternatively be rendered as:
- $\vdash \left({p \implies \left({q \implies r}\right)}\right) \iff \left({\left({p \implies q}\right) \implies \left({p \implies r}\right)}\right)$
- $\vdash \left({\left({p \implies q}\right) \implies r}\right) \implies \left({\left({p \implies r}\right) \implies \left({q \implies r}\right)}\right)$
They can be seen to be logically equivalent to the forms above by application of the Rule of Implication and Modus Ponendo Ponens.
Proof
Proof by Natural Deduction
These are proved by the Tableau method.
| Line | Pool | Formula | Rule | Depends upon | |
|---|---|---|---|---|---|
| 1 | 1 | $p \implies \left({q \implies r}\right)$ | P | (None) | |
| 2 | 2 | $p \implies q$ | A | 2 | |
| 3 | 3 | $p$ | A | 3 | |
| 4 | 1, 3 | $q \implies r$ | $\implies \mathcal E$ | 1, 3 | |
| 5 | 2, 3 | $q$ | $\implies \mathcal E$ | 2, 3 | |
| 6 | 1, 2, 3 | $r$ | $\implies \mathcal E$ | 4, 5 | |
| 7 | 1, 2 | $p \implies r$ | $\implies \mathcal I$ | 3, 6 | |
| 8 | 1 | $\left({p \implies q}\right) \implies \left({p \implies r}\right)$ | $\implies \mathcal I$ | 2, 7 |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\left({p \implies q}\right) \implies \left({p \implies r}\right)$ | P | (None) | ||
| 2 | 2 | $p$ | A | 2 | ||
| 3 | 3 | $q$ | A | 3 | ||
| 4 | 3 | $p \implies q$ | SI | 3 | If something is true, anything implies it. | |
| 5 | 1, 3 | $p \implies r$ | $\implies \mathcal E$ | 1, 4 | ||
| 6 | 1, 2, 3 | $r$ | $\implies \mathcal E$ | 5, 2 | ||
| 7 | 1, 2 | $q \implies r$ | $\implies \mathcal I$ | 3-6 | ||
| 8 | 1 | $p \implies \left({q \implies r}\right)$ | $\implies \mathcal I$ | 2, 7 |
$\blacksquare$
Proof by Truth Table
We apply the Method of Truth Tables to the proposition: $p \implies \left({q \implies r}\right) \dashv \vdash \left({p \implies q}\right) \implies \left({p \implies r}\right)$
As can be seen by inspection, the truth values under the main connectives match for all models.
$\begin{array}{|ccccc||ccccccc|} \hline
p & \implies & (q & \implies & r) & (p & \implies & q) & \implies & (p & \implies & r) \\
\hline
F & T & F & T & F & F & T & F & T & F & T & F \\
F & T & F & T & T & F & T & F & T & F & T & T \\
F & T & T & F & F & F & T & T & T & F & T & F \\
F & T & T & T & T & F & T & T & T & F & T & T \\
T & T & F & T & F & T & F & F & T & T & F & F \\
T & T & F & T & T & T & F & F & T & T & T & T \\
T & F & T & F & F & T & T & T & F & T & F & F \\
T & T & T & T & T & T & T & T & T & T & T & T \\
\hline
\end{array}$
$\blacksquare$
Next we apply the Method of Truth Tables to the proposition:
- $\left({p \implies q}\right) \implies r \vdash \left({p \implies r}\right) \implies \left({q \implies r}\right)$
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}{|ccccc||ccccccc|} \hline
(p & \implies & q) & \implies & r & (p & \implies & r) & \implies & (q & \implies & r) \\
\hline
F & T & F & F & F & F & T & F & T & F & T & F \\
F & T & F & T & T & F & T & T & T & F & T & T \\
F & T & T & F & F & F & T & F & F & T & F & F \\
F & T & T & T & T & F & T & T & T & T & T & T \\
T & F & F & T & F & T & F & F & T & F & F & F \\
T & F & F & T & T & T & T & T & T & F & T & T \\
T & T & T & F & F & T & F & F & T & T & F & F \\
T & T & T & T & T & T & T & T & T & T & T & T \\
\hline
\end{array}$
$\blacksquare$
Note that the two formulas are not equivalent, as the relevant columns do not match exactly.
Hence the result:
- $\left({p \implies q}\right) \implies r \vdash \left({p \implies r}\right) \implies \left({q \implies r}\right)$
... but
- $\left({p \implies r}\right) \implies \left({q \implies r}\right) \not \vdash \left({p \implies q}\right) \implies r$
$\blacksquare$
Sources
- Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{I}: \S 5$: Theorems $\text{T6}, \ \text{T7}$
- Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Theorems $\text{T106}$
- H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Exercise $1.14: 12 \ (8)$
- E.J. Lemmon: Beginning Logic (1965): $\S 1.2$: Exercise $1 \ \text{(j)}$
