Disjunction and Implication
Contents |
Theorems
This is sometimes referred to as the disjunctive syllogism or Modus Tollendo Ponens:
- $p \lor q \dashv \vdash \neg p \implies q$
This is sometimes referred to as the Rule of Material Implication:
- $\neg p \lor q \dashv \vdash p \implies q$
Both of the above come in negative forms:
| \(\displaystyle \) | \(\displaystyle \neg \left({p \implies q}\right)\) | \(\dashv \vdash\) | \(\displaystyle \neg \left({\neg p \lor q}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \neg \left({\neg p \implies q}\right)\) | \(\dashv \vdash\) | \(\displaystyle \neg \left({p \lor q}\right)\) | \(\displaystyle \) |
Disjunction is definable through implication:
- $p \lor q \dashv \vdash \left({p \implies q}\right) \implies q$
Alternative rendition
They can alternatively be rendered as:
| \(\displaystyle \vdash\) | \(\displaystyle \left({p \lor q}\right)\) | \(\iff\) | \(\displaystyle \left({\neg p \implies q}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \vdash\) | \(\displaystyle \left({\neg p \lor q}\right)\) | \(\iff\) | \(\displaystyle \left({p \implies q}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \vdash\) | \(\displaystyle \left({\neg \left({p \implies q}\right)}\right)\) | \(\iff\) | \(\displaystyle \left({\neg \left({\neg p \lor q}\right)}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \vdash\) | \(\displaystyle \left({\neg \left({\neg p \implies q}\right)}\right)\) | \(\iff\) | \(\displaystyle \left({\neg \left({p \lor q}\right)}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \vdash\) | \(\displaystyle \left({p \lor q}\right)\) | \(\iff\) | \(\displaystyle \left({\left({p \implies q}\right) \implies q}\right)\) | \(\displaystyle \) |
They can be seen to be logically equivalent to the forms above.
Proof of Modus Tollendo Ponens
Proof by Natural Deduction
By the tableau method:
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $p \lor q$ | P | (None) | ||
| 2 | 2 | $p$ | A | (None) | We pick the first of the disjuncts ... | |
| 3 | 3 | $\neg p$ | A | (None) | Assume the negation of it ... | |
| 4 | 2, 3 | $\bot$ | $\neg \mathcal E$ | 2, 3 | ... which of course is a direct contradiction ... | |
| 5 | 2, 3 | $\,\!q$ | $\bot \mathcal E$ | 4 | ... and having derived a falsehood, we can derive any statement - we pick $q$ ... | |
| 6 | 2 | $\neg p \implies q$ | $\implies \mathcal I$ | 3-5 | ... so assuming $\neg p$ implies $q$. | |
| 7 | 7 | $q$ | A | (None) | Then we pick the second of the disjuncts ... | |
| 8 | 8 | $\neg p$ | A | (None) | ... again we assume the negation of $p$ ... | |
| 9 | 7 | $q$ | Law of Identity | 7 | We still have the truth of $q$... | |
| 10 | 7 | $\neg p \implies q$ | $\implies \mathcal I$ | 8, 9 | ... thus from assuming $\neg p$ we can derive $q$. | |
| 11 | 1 | $\neg p \implies q$ | $\lor \mathcal E$ | 1, 2-6, 7-10 | Either of our disjuncts lead to the conclusion, so the proof is demonstrated. |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg p \implies q$ | P | (None) | ||
| 2 | $p \lor \neg p$ | LEM | (None) | Either $p$ is true or it's not. | ||
| 3 | 3 | $\,\!p$ | A | (None) | Suppose it is ... | |
| 4 | 3 | $p \lor q$ | $\lor \mathcal I_1$ | 3 | ||
| 5 | 5 | $\neg p$ | A | (None) | ... or suppose it's not ... | |
| 6 | 1, 5 | $\,\!q$ | $\implies \mathcal E$ | 1, 5 | ||
| 7 | 1, 5 | $p \lor q$ | $\lor \mathcal I_2$ | 6 | ||
| 8 | 1 | $p \lor q$ | $\lor \mathcal E$ | 2, 3-4, 5-7 | ... both options lead to the conclusion. |
$\blacksquare$
Note that the latter proof requires the Law of Excluded Middle.
Proof by Truth Table
As can be seen by inspection, the truth values under the main connectives match for all models.
$\begin{array}{|ccc||cccc|} \hline p & \lor & q & \neg & p & \implies & q \\ \hline F & F & F & T & F & F & F \\ F & T & T & T & F & T & T \\ T & T & F & F & T & T & F \\ T & T & T & F & T & T & T \\ \hline \end{array}$
$\blacksquare$
Proof of Rule of Material Implication
Proof by Natural Deduction
By the tableau method:
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg p \lor q$ | P | (None) | ||
| 2 | 2 | $\neg p$ | A | (None) | We pick the first of the disjuncts ... | |
| 3 | 3 | $\,\!p$ | A | (None) | Assume the negation of it ... | |
| 4 | 2, 3 | $\bot$ | $\neg \mathcal E$ | 3, 2 | ... which of course is a direct contradiction ... | |
| 5 | 2, 3 | $\,\!q$ | $\bot \mathcal E$ | 4 | ... and having derived a falsehood, we can derive any statement - we pick $q$ ... | |
| 6 | 2 | $\,\!p \implies q$ | $\implies \mathcal I$ | 3-5 | ... so assuming $p$ implies $q$. | |
| 7 | 7 | $\,\!q$ | A | (None) | Then we pick the second of the disjuncts ... | |
| 8 | 8 | $\,\!p$ | A | (None) | ... again we assume $p$ ... | |
| 9 | 7 | $\,\!q$ | Law of Identity | 7 | We still have the truth of $q$... | |
| 10 | 7 | $p \implies q$ | $\implies \mathcal I$ | 8, 9 | ... thus from assuming $p$ we can derive $q$. | |
| 11 | 1 | $p \implies q$ | $\lor \mathcal E$ | 1, 2-6, 7-10 | Either of our disjuncts lead to the conclusion, so the proof is demonstrated. |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $p \implies q$ | P | (None) | ||
| 2 | $p \lor \neg p$ | LEM | (None) | Either $p$ is true or it's not. | ||
| 3 | 3 | $\neg p$ | A | (None) | Suppose it's not ... | |
| 4 | 3 | $\neg p \lor q$ | $\lor \mathcal I_1$ | 3 | ||
| 5 | 5 | $\,\!p$ | A | (None) | ... or suppose it is ... | |
| 6 | 1, 5 | $\,\!q$ | $\implies \mathcal E$ | 1, 5 | ||
| 7 | 1, 5 | $\neg p \lor q$ | $\lor \mathcal I_2$ | 6 | ||
| 8 | 1 | $p \lor q$ | $\lor \mathcal E$ | 2, 3-4, 5-7 | ... both options lead to the conclusion. |
$\blacksquare$
Note that the latter proof requires the Law of Excluded Middle.
Proof by Truth Table
As can be seen by inspection, the truth values under the main connectives match for all models.
$\begin{array}{|ccc||cccc|} \hline p & \implies & q & \neg & p & \lor & q \\ \hline F & T & F & T & F & T & F \\ F & T & T & T & F & T & T \\ T & F & F & F & T & F & F \\ T & T & T & F & T & T & T \\ \hline \end{array}$
$\blacksquare$
Other Proofs
Proof by Natural Deduction
By the tableau method:
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg \left({p \implies q}\right)$ | P | (None) | ||
| 2 | 2 | $\neg p \lor q$ | A | (None) | Assume the opposite of what we want to prove ... | |
| 3 | 2 | $p \implies q$ | Rule of Material Implication | 2 | ... use the above result to prove the converse of the proposition ... | |
| 4 | 1, 2 | $\bot$ | $\neg \mathcal E$ | 3, 1 | ... which of course is a direct contradiction ... | |
| 5 | 1 | $\neg \left({\neg p \lor q}\right)$ | $\neg \mathcal I$ | 2-4 | ... proving the result. |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg \left({\neg p \lor q}\right)$ | P | (None) | ||
| 2 | 2 | $p \implies q$ | A | (None) | Assume the opposite of what we want to prove ... | |
| 3 | 2 | $\neg p \lor q$ | Rule of Material Implication | 2 | ... use the above result to prove the converse of the proposition (uses LEM) ... | |
| 4 | 1, 2 | $\bot$ | $\neg \mathcal E$ | 3, 1 | ... which of course is a direct contradiction ... | |
| 5 | 1 | $\neg \left({p \implies q}\right)$ | $\neg \mathcal I$ | 2-4 | ... proving the result. |
$\blacksquare$
Note that the latter proof requires the Law of Excluded Middle.
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg \left({\neg p \implies q}\right)$ | P | (None) | ||
| 2 | 2 | $p \lor q$ | A | (None) | Assume the opposite of what we want to prove ... | |
| 3 | 2 | $\neg p \implies q$ | Modus Tollendo Ponens | 2 | ... use the above result to prove the converse of the proposition ... | |
| 4 | 1, 2 | $\bot$ | $\neg \mathcal E$ | 3, 1 | ... which of course is a direct contradiction ... | |
| 5 | 1 | $\neg \left({p \lor q}\right)$ | $\neg \mathcal I$ | 2-4 | ... proving the result. |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg \left({p \lor q}\right)$ | P | (None) | ||
| 2 | 2 | $\neg p \implies q$ | A | (None) | Assume the opposite of what we want to prove ... | |
| 3 | 1 | $\neg p \land \neg q$ | DM | 1 | $\neg \left({p \lor q}\right) \vdash \neg p \land \neg q$ does not need the LEM | |
| 4 | 1 | $\neg p$ | $\land \mathcal E_1$ | 3 | ||
| 5 | 1, 2 | $\,\!q$ | $\implies \mathcal E$ | 2, 4 | ... from our assumption | |
| 6 | 1 | $\neg q$ | $\land \mathcal E_2$ | 3 | ||
| 7 | 1, 2 | $\bot$ | $\neg \mathcal E$ | 5, 6 | ... an obvious contradiction | |
| 8 | 1 | $\neg \left({\neg p \implies q}\right)$ | $\neg \mathcal I$ | 2-7 | Hence the result by proof by contradiction. |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $p \lor q$ | P | (None) | ||
| 2 | 2 | $p \implies q$ | A | (None) | ||
| 3 | 3 | $\,\!p$ | A | (None) | Suppose $p$ | |
| 4 | 2,3 | $\,\! q$ | $\implies \mathcal E$ | 2,3 | ||
| 5 | 5 | $\,\!q$ | A | (None) | ... or suppose $q$ ... | |
| 6 | 2 | $\,\!q$ | $\lor \mathcal E$ | 1, 2-4, 5-5 | ... either way, you can deduce $q$ | |
| 7 | 1 | $(p \implies q) \implies q$ | $\implies \mathcal I$ | 2-6 |
$\blacksquare$
If you are fairly certain that there are none, please remove {{proofread}} from the code.
Comment
Note that this:
- $\neg \left({\neg p \implies q}\right) \dashv \vdash \neg \left({p \lor q}\right)$
can be proved in both directions without resorting to the LEM.
All the others:
- $p \lor q \vdash \neg p \implies q$
- $\neg p \lor q \vdash p \implies q$
- $\neg \left({p \implies q}\right) \vdash \neg \left({\neg p \lor q}\right)$
are not reversible in intuitionist logic.
Proof by Truth Table
We apply the Method of Truth Tables to the propositions in turn.
As can be seen by inspection, in all cases the truth values under the main connectives match for all models.
$\begin{array}{|cccc||ccccc|} \hline
\neg & (p & \lor & q) & \neg & (\neg & p & \implies & q) \\
\hline
T & F & F & F & T & T & F & F & F \\
F & F & T & T & F & T & F & T & T \\
F & T & T & F & F & F & T & T & F \\
F & T & T & T & F & F & T & T & T \\
\hline
\end{array}$
$\blacksquare$
$\begin{array}{|cccc||ccccc|} \hline
\neg & (p & \implies & q) & \neg & (\neg & p & \lor & q) \\
\hline
F & F & T & F & F & T & F & T & F \\
F & F & T & T & F & T & F & T & T \\
T & T & F & F & T & F & T & F & F \\
F & T & T & T & F & F & T & T & T \\
\hline
\end{array}$
$\blacksquare$
Sources
- Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Theorems $\text{T45}, \ \text{T46}$
- E.J. Lemmon: Beginning Logic (1965): $\S 1.5$: Exercises $1 \ \text{(i), (j)}$
- Alan G. Hamilton: Logic for Mathematicians (1978): $\S 1.2$: Example $1.4$
- Alan G. Hamilton: Logic for Mathematicians (1978): $\S 1.2$: Exercises $4, \ 5 \ \text{(b)}$
- D.J. O'Connor and Betty Powell: Elementary Logic (1980): $\S 1.13$: Exercise $\text{(A)} \ 5$
