Principle of Commutation

Theorem

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

This can alternatively be rendered as:

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

or, as an obvious corollary:

• $\vdash \left({p \implies \left({q \implies r}\right)}\right) \iff \left({q \implies \left({p \implies r}\right)}\right)$

The two forms can be seen to be logically equivalent by application of the Rule of Implication and Modus Ponendo Ponens.

Proof

Proof by Natural Deduction

By the tableau method:

• $p \implies \left({q \implies r}\right) \vdash q \implies \left({p \implies r}\right)$:

Line		Pool	Formula	Rule	Depends upon
1		1	$p \implies \left({q \implies r}\right)$	P	(None)
2		1	$\left({p \land q}\right) \implies r$	Rule of Exportation	1
3		3	$q \land p$	A	(none)
4		3	$p \land q$	Rule of Commutation	3
5		1, 3	$r$	Modus Ponendo Ponens	4, 2
6		1	$\left({q \land p}\right) \implies r$	Rule of Exportation	3, 5	The assumption of $q \land p$ has been discharged
7		1	$q \implies \left({p \implies r}\right)$	Rule of Exportation	6

$\blacksquare$

Proof by Truth Table

We apply the Method of Truth Tables to the propositions in turn.

As can be seen for all models by inspection, where the truth values under the main connectives on the LHS is $T$, that under the one on the RHS is also $T$:

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

Hence the result.

$\blacksquare$

Also see

• Rule of Commutation

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{I}: \S 5$: Theorem $\text{T8}$
• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Theorem $\text{T107}$