Implication Distributes over Conjunction

Theorem

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

This can alternatively be rendered as:

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

The forms can be seen to be logically equivalent.

Proof

Proof by Natural Deduction

By the tableau method:

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p \implies \left({q \land r}\right)$	Proposition	(None)
2		2	$p$	Rule of Assumption	(None)
3		1, 2	$q \land r$	Modus Ponendo Ponens	1, 2
4		1, 2	$q$	Rule of Simplification	3
5		1, 2	$r$	Rule of Simplification	3
6		1	$p \implies q$	Rule of Implication	2, 4	Assumption of $p$ has been discharged.
7		1	$p \implies r$	Rule of Implication	2, 5	Assumption of $p$ has been discharged.
8		1	$\left({p \implies q}\right) \land \left({p \implies r}\right)$	Rule of Conjunction	6, 7

$\Box$

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\left({p \implies q}\right) \land \left({p \implies r}\right)$	Proposition	(None)
2		1	$\left({p \land p}\right) \implies \left({q \land r}\right)$	Praeclarum Theorema	1	Mostly done - just need to tidy up.
3		3	$p$	Rule of Assumption	(None)
4		3	$p \land p$	Rule of Idempotence	3
5		1, 3	$q \land r$	Modus Ponendo Ponens	2, 4
6		1	$p \implies \left({q \land r}\right)$	Rule of Implication	3, 5	Assumption of $p$ has been discharged.

$\blacksquare$

Sources

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