Rule of Commutation

Definition

This rule is two-fold:

• Conjunction is commutative:

$p \land q \dashv \vdash q \land p$

• Disjunction is commutative:

$p \lor q \dashv \vdash q \lor p$

Its abbreviation in a tableau proof is $\text{Comm}$.

Alternative rendition

These can alternatively be rendered as:

• $\vdash \left({p \land q}\right) \iff \left({q \land p}\right)$
• $\vdash \left({p \lor q}\right) \iff \left({q \lor p}\right)$

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

Proof

Proof by Natural Deduction

By the tableau method:

• $p \land q \vdash q \land p$:

Line		Pool	Formula	Rule	Depends upon
1		1	$p \land q$	P	(None)
2		1	$p$	$\land \mathcal E_1$	1
3		1	$q$	$\land \mathcal E_2$	1
4		1	$q \land p$	$\land \mathcal I$	3, 2

$\blacksquare$

By the same technique we can show $q \land p \vdash p \land q$.

• $p \lor q \vdash q \lor p$:

Line		Pool	Formula	Rule	Depends upon
1		1	$p \lor q$	P	(None)
2		1	$p$	A	(None)
3		2	$q \lor p$	$\lor \mathcal I_2$	2
4		1	$q$	A	(None)
5		4	$q \lor p$	$\lor \mathcal I_1$	4
6		1	$q \lor p$	$\lor \mathcal E$	1, 2-3, 4-5

$\blacksquare$

By the same technique we can show $q \lor p \vdash p \lor q$.

---

Proof by Truth Table

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

As can be seen by inspection, in both cases, the truth values under the main connectives match for all models.

$\begin{array}{|ccc||ccc|} \hline p & \land & q & q & \land & p \\ \hline F & F & F & F & F & F \\ F & F & T & T & F & F \\ T & F & F & F & F & T \\ T & T & T & T & T & T \\ \hline \end{array}$

$\blacksquare$

$\begin{array}{|ccc||ccc|} \hline p & \lor & q & q & \lor & p \\ \hline F & F & F & F & F & F \\ F & T & T & T & T & F \\ T & T & F & F & T & T \\ T & T & T & T & T & T \\ \hline \end{array}$

$\blacksquare$

Also see

• Rule of Association
• Principle of Commutation

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 3$: Theorem $\text{T24}$
• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Theorem $\text{T53}$
• E.J. Lemmon: Beginning Logic (1965): $\S 1.3$: Theorems $17, \ 19$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Exercise $1.14: \ 12 \ (4), \ (5)$
• Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.1$: Exercise $1.2: \ 2$, Example $1.15$