Disjunction of Conditional and Converse

Theorem

Given any two statements, one of them implies the other.

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

That is, given any conditional, either it is true or its converse is.

Proof

Proof by Natural deduction

This is proved by the Tableau method.

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

Line		Pool	Formula	Rule	Depends upon	Notes
1			$p \lor \neg p$	LEM	(None)
2		2	$p$	A	2	Either $p$ is true ...
3		2	$q \implies p$	SI	2	"If something is true, anything implies it."
4		2	$\left({p \implies q}\right) \lor \left({q \implies p}\right)$	$\lor \mathcal I_2$	2
5		5	$\neg p$	A	5	... or $p$ is false ...
6		5	$p \implies q$	SI	5	"If something is false, it implies anything."
7		5	$\left({p \implies q}\right) \lor \left({q \implies p}\right)$	$\lor \mathcal I_1$	7
8			$\left({p \implies q}\right) \lor \left({q \implies p}\right)$	$\lor \mathcal E$	1, 2-4, 5-7	... either way, the result follows.

$\blacksquare$

Proof by Truth Table

We apply the Method of Truth Tables to the proposition.

As can be seen by inspection, the truth values under the main connective is true for all models, proving a tautology.

$\begin{array}{|ccccccc|} \hline (p & \implies & q) & \lor & (q & \implies & p) \\ \hline F & T & F & T & F & T & F \\ F & T & T & T & T & F & F \\ T & F & F & T & F & T & T \\ T & T & T & T & T & T & T \\ \hline \end{array}$

$\blacksquare$

Sources

• Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.1$: Exercises $1.5: \ 2 \ \text{(e)}$