Rule of Distribution

Definition

Conjunction distributes over disjunction:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p \land \left({q \lor r}\right)\)	\(\dashv \vdash\)	\(\displaystyle \left({p \land q}\right) \lor \left({p \land r}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({q \lor r}\right) \land p\)	\(\dashv \vdash\)	\(\displaystyle \left({q \land p}\right) \lor \left({r \land p}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Disjunction distributes over conjunction:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p \lor \left({q \land r}\right)\)	\(\dashv \vdash\)	\(\displaystyle \left({p \lor q}\right) \land \left({p \lor r}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({q \land r}\right) \lor p\)	\(\dashv \vdash\)	\(\displaystyle \left({q \lor p}\right) \land \left({r \lor p}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

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

Alternative rendition

These can alternatively be rendered as:

	\(\displaystyle \)	\(\displaystyle \vdash\)	\(\displaystyle \)	\(\displaystyle \left({p \land \left({q \lor r}\right)}\right)\)	\(\iff\)	\(\displaystyle \left({\left({p \land q}\right) \lor \left({p \land r}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \vdash\)	\(\displaystyle \)	\(\displaystyle \left({\left({q \lor r}\right) \land p}\right)\)	\(\iff\)	\(\displaystyle \left({\left({q \land p}\right) \lor \left({r \land p}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \vdash\)	\(\displaystyle \)	\(\displaystyle \left({p \lor \left({q \land r}\right)}\right)\)	\(\iff\)	\(\displaystyle \left({\left({p \lor q}\right) \land \left({p \lor r}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \vdash\)	\(\displaystyle \)	\(\displaystyle \left({\left({q \land r}\right) \lor p}\right)\)	\(\iff\)	\(\displaystyle \left({\left({q \lor p}\right) \land \left({r \lor p}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

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

Proof: Conjunction distributes over Disjunction

Proof by Natural Deduction

By the Tableau method:

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p \land \left({q \lor r}\right)$	P	(None)
2		1	$p$	$\land \mathcal E_1$	1
3		1	$q \lor r$	$\land \mathcal E_2$	1
4		4	$q$	A	(None)
5		1, 4	$p \land q$	$\land \mathcal I$	2, 4
6		1, 4	$\left({p \land q}\right) \lor \left({p \land r}\right)$	$\lor \mathcal I_1$	5
7		7	$r$	A	(None)
8		1, 7	$p \land r$	$\land \mathcal I$	2, 7
9		1, 7	$\left({p \land q}\right) \lor \left({p \land r}\right)$	$\lor \mathcal I_1$	8
10		1	$\left({p \land q}\right) \lor \left({p \land r}\right)$	$\lor \mathcal{E}$	3, 4-6, 7-9	Assumptions on lines 4 and 7 are now discharged.

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\left({p \land q}\right) \lor \left({p \land r}\right)$	P	(None)
2		2	$p \land q$	A	(None)
3		2	$p$	$\land \mathcal E_1$	2
4		4	$p \land r$	A	(None)
5		4	$p$	$\land \mathcal E_2$	4
6		1	$p$	$\lor \mathcal E$	1, 2-3, 4-5	Assumptions on lines 2 and 4 are now discharged.
7		7	$p \land q$	A	(None)
8		7	$q$	$\land \mathcal E_2$	7
9		7	$q \lor r$	$\lor \mathcal I_1$	7
10		10	$p \land r$	A	(None)
11		10	$r$	$\land \mathcal E_2$	10
12		10	$q \lor r$	$\lor \mathcal I_2$	11
13		1	$q \lor r$	$\lor \mathcal E$	1, 7-9, 10-12	Assumptions on lines 7 and 10 are now discharged.
14		1	$p \land \left({q \lor r}\right)$	$\land \mathcal{I}$	6, 13

Then we use the Rule of Commutation:

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\left({q \lor r}\right) \land p$	P	(None)
2		1	$p \land \left({q \lor r}\right)$	Comm	1
3		1	$\left({p \land q}\right) \lor \left({p \land r}\right)$	Dist	2	We use the Rule of Distribution that we proved above.
4		1	$\left({q \land p}\right) \lor \left({r \land p}\right)$	Comm	3

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\left({q \land p}\right) \lor \left({r \land p}\right)$	P	(None)
2		1	$\left({p \land q}\right) \lor \left({p \land r}\right)$	Comm	1
3		1	$p \land \left({q \lor r}\right)$	Dist	2	We use the Rule of Distribution that we proved above.
4		1	$\left({q \lor r}\right) \land p$	Comm	3

$\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 connectives match for all models.

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

$\left({q \lor r}\right) \land p \dashv \vdash \left({q \land p}\right) \lor \left({r \land p}\right)$ is demonstrated similarly.

$\blacksquare$

Proof: Disjunction distributes over Conjunction

Proof by Natural Deduction

By the Tableau method:

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p \lor \left({q \land r}\right) $	P	(None)
2		1	$p$	A	(None)
3		2	$p \lor q$	$\lor \mathcal I_1$	2
4		2	$p \lor r$	$\lor \mathcal I_1$	2
5		2	$\left({p \lor q}\right) \land \left({p \lor r}\right)$	$\land \mathcal I$	3, 4
6		6	$q \land r$	A	(None)
7		6	$q$	$\land \mathcal E_1$	6
8		6	$r$	$\land \mathcal E_2$	6
9		6	$p \lor q$	$\lor \mathcal I_2$	7
10		6	$p \lor r$	$\lor \mathcal I_2$	8
11		6	$\left({p \lor q}\right) \land \left({p \lor r}\right)$	$\land \mathcal I$	7, 8
12		1	$\left({p \land q}\right) \lor \left({p \land r}\right)$	$\lor \mathcal E$	1, 2-5, 6-11	Assumptions on lines 2 and 6 are now discharged.

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\left({p \lor q}\right) \land \left({p \lor r}\right)$	P	(None)
2		1	$p \lor r$	$\land \mathcal E_2$	1
3		3	$p$	A	(None)
4		3	$p \lor \left({q \land r}\right)$	$\lor \mathcal I_1$	3
5		5	$r$	A	(None)
6		1	$p \lor q$	$\land \mathcal E_1$	1
7		7	$p$	A	(None)
8		7	$p \lor \left({q \land r}\right)$	$\lor \mathcal I_1$	7
9		9	$q$	A	(None)
10		5, 9	$q \land r$	$\land \mathcal I$	9, 5
11		5, 9	$p \lor \left({q \land r}\right)$	$\lor \mathcal I_2$	10
12		1, 5	$p \lor \left({q \land r}\right)$	$\lor \mathcal E$	6, 7-8, 9-11
13		1	$p \lor \left({q \land r}\right)$	$\lor \mathcal E$	2, 3-4, 5-12

Then we use the Rule of Commutation:

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\left({q \land r}\right) \lor p$	P	(None)
2		1	$p \lor \left({q \land r}\right)$	Comm	1
3		1	$\left({p \lor q}\right) \land \left({p \lor r}\right)$	Dist	2	We use the Rule of Distribution that we proved above.
4		1	$\left({q \lor p}\right) \land \left({r \lor p}\right)$	Comm	3

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\left({q \lor p}\right) \land \left({r \lor p}\right)$	P	(None)
2		1	$\left({p \lor q}\right) \land \left({p \lor r}\right)$	Comm	1
3		1	$p \lor \left({q \land r}\right)$	Dist	2	We use the Rule of Distribution that we proved above.
4		1	$\left({q \land r}\right) \lor p$	Comm	3

$\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 connectives match for all models.

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

$\left({q \land r}\right) \lor p \dashv \vdash \left({q \lor p}\right) \land \left({r \lor p}\right)$ is demonstrated similarly.

$\blacksquare$

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Theorem $\text{T61}, \ \text{T62}$
• E.J. Lemmon: Beginning Logic (1965): $\S 1.5$: Theorem $33$, Exercise $1 \ \text{(c), (d)}$
• Alan G. Hamilton: Logic for Mathematicians (1978): $\S 1.2$: Exercise $6 \ \text{(b)}$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Exercise $1.14: 12 \ (6), \ (7)$
• Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.1$: Example $1.18$, Exercises $1.4: 2 \ \text{(q)}$