Factor Principles

Theorem

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

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

They can alternatively be rendered as:

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

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

The 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 q \vdash \left({p \land r}\right) \implies \left ({q \land r}\right)$

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p \implies q$	P	(None)
2			$r \implies r$	Law of Identity	(None)	This is a theorem so depends on nothing.
3		1	$\left({p \implies q}\right) \land \left({r \implies r}\right)$	Rule of Conjunction	1, 2
4		1	$\left({p \land r}\right) \implies \left ({q \land r}\right)$	Praeclarum Theorema	3

$\blacksquare$

And the second is like it, namely this:

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p \implies q$	P	(None)
2			$r \implies r$	Law of Identity	(None)	This is a theorem so depends on nothing.
3		1	$\left({r \implies r}\right) \land \left({p \implies q}\right)$	Rule of Conjunction	2, 1
4		1	$\left({r \land p}\right) \implies \left ({r \land q}\right)$	Praeclarum Theorema	3

$\blacksquare$

It would, of course, be possible to derive the second from the first by applying the Rule of Commutation to the conjunctions on the RHS, but this is unnecessarily fiddly for a result so obvious. The Praeclarum Theorema does all the work we need instead.

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 3$: Theorem $\text{T30}, \ \text{T31}$