Disjunction and Implication

Theorems

Modus Tollendo Ponens

Formulation 1

$p \lor q \dashv \vdash \neg p \implies q$

Formulation 2

$\vdash \left({p \lor q}\right) \iff \left({\neg p \implies q}\right)$

Rule of Material Implication

Formulation 1

$p \implies q \dashv \vdash \neg p \lor q$

Formulation 2

$\vdash \left({p \implies q}\right) \iff \left({\neg p \lor q}\right)$

Both of the above come in negative forms:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \neg \left({p \implies q}\right)\)	\(\dashv \vdash\)	\(\displaystyle \)	\(\displaystyle \neg \left({\neg p \lor q}\right)\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \neg \left({\neg p \implies q}\right)\)	\(\dashv \vdash\)	\(\displaystyle \)	\(\displaystyle \neg \left({p \lor q}\right)\)	\(\displaystyle \)	\(\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 \)	\(\displaystyle \vdash\)	\(\displaystyle \)	\(\displaystyle \left({\neg \left({p \implies q}\right)}\right)\)	\(\iff\)	\(\displaystyle \)	\(\displaystyle \left({\neg \left({\neg p \lor q}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \vdash\)	\(\displaystyle \)	\(\displaystyle \left({\neg \left({\neg p \implies q}\right)}\right)\)	\(\iff\)	\(\displaystyle \)	\(\displaystyle \left({\neg \left({p \lor q}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \vdash\)	\(\displaystyle \)	\(\displaystyle \left({p \lor q}\right)\)	\(\iff\)	\(\displaystyle \)	\(\displaystyle \left({\left({p \implies q}\right) \implies q}\right)\)	\(\displaystyle \)	\(\displaystyle \)

They can be seen to be logically equivalent to the forms above.

Proof

By the tableau method of natural deduction:

$\neg \left({p \implies q}\right) \vdash \neg \left({\neg p \lor q}\right)$

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\neg \left({p \implies q}\right)$	Premise	(None)
2		2	$\neg p \lor q$	Assumption	(None)	Assume the opposite of what is to be proved ...
3		2	$p \implies q$	Sequent Introduction	2	Rule of Material Implication
4		1, 2	$\bot$	Principle of Non-Contradiction: $\neg \mathcal E$	3, 1	... demonstrating a contradiction
5		1	$\neg \left({\neg p \lor q}\right)$	Proof by Contradiction: $\neg \mathcal I$	2 – 4	Assumption 2 has been discharged

$\blacksquare$

By the tableau method of natural deduction:

$\neg \left({\neg p \lor q}\right) \vdash \neg \left({p \implies q}\right)$

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\neg \left({\neg p \lor q}\right)$	Premise	(None)
2		2	$p \implies q$	Assumption	(None)	Assume the opposite of what is to be proved ...
3		2	$\neg p \lor q$	Sequent Introduction	2	Rule of Material Implication
4		1, 2	$\bot$	Principle of Non-Contradiction: $\neg \mathcal E$	3, 1	... demonstrating a contradiction
5		1	$\neg \left({p \implies q}\right)$	Proof by Contradiction: $\neg \mathcal I$	2 – 4	Assumption 2 has been discharged

$\blacksquare$

Law of the Excluded Middle

This theorem depends on the Law of the Excluded Middle, by way of Rule of Material Implication.

This is one of the axioms of logic that was determined by Aristotle, and forms part of the backbone of classical (Aristotelian) logic.

However, the intuitionist school rejects the Law of the Excluded Middle as a valid logical axiom. This in turn invalidates this theorem from the system of intuitionist propositional calculus.

By the tableau method of natural deduction:

$\neg \left({\neg p \implies q}\right) \vdash \neg \left({p \lor q}\right)$

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\neg \left({\neg p \implies q}\right)$	Premise	(None)
2		2	$p \lor q$	Assumption	(None)	Assume the opposite of what is to be proved ...
3		2	$\neg p \implies q$	Sequent Introduction	2	Modus Tollendo Ponens
4		1, 2	$\bot$	Principle of Non-Contradiction: $\neg \mathcal E$	3, 1	... demonstrating a contradiction
5		1	$\neg \left({p \lor q}\right)$	Proof by Contradiction: $\neg \mathcal I$	2 – 4	Assumption 2 has been discharged

$\blacksquare$

By the tableau method of natural deduction:

$\neg \left({p \lor q}\right) \vdash \neg \left({\neg p \implies q}\right)$

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\neg \left({p \lor q}\right)$	Premise	(None)
2		2	$\neg p \implies q$	Assumption	(None)	Assume the opposite of what is to be proved ...
3		1	$\neg p \land \neg q$	Sequent Introduction	1	De Morgan's Laws: Conjunction of Negations
4		1	$\neg p$	Rule of Simplification: $\land \mathcal E_1$	3
5		1, 2	$q$	Modus Ponendo Ponens: $\implies \mathcal E$	2, 4	... from the assumption
6		1	$\neg q$	Rule of Simplification: $\land \mathcal E_2$	3
7		1, 2	$\bot$	Principle of Non-Contradiction: $\neg \mathcal E$	5, 6	... demonstrating a contradiction
8		1	$\neg \left({\neg p \implies q}\right)$	Proof by Contradiction: $\neg \mathcal I$	2 – 7	Assumption 2 has been discharged

$\blacksquare$

By the tableau method of natural deduction:

$p \lor q \vdash (p \implies q) \implies q$

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p \lor q$	Premise	(None)
2		2	$p \implies q$	Assumption	(None)
3		3	$p$	Assumption	(None)
4		2, 3	$q$	Modus Ponendo Ponens: $\implies \mathcal E$	2, 3
5		5	$q$	Assumption	(None)
6		2	$r$	Rule of Or-Elimination: $\lor \mathcal E$	1, 3 – 4, 5 – 5	Assumptions 3 and 5 have been discharged
7		1	$\left({p \implies q}\right) \implies q$	Rule of Implication: $\implies \mathcal I$	2 – 6	Assumption 2 has been discharged

$\blacksquare$

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 Law of Excluded Middle.

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$