Absorption Laws

Theorem

For any two propositions $p$ and $q$, we have:

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

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

These are called the Absorption Laws or Absorption Identities.

Their abbreviation in a tableau proof is $\mathrm {AL}$.

Proof by Tableau

Proceed by the Tableau method:

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p \land \left({p \lor q}\right)$	P	(None)
2		1	$p$	$\land \mathcal E_1$	1

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p$	P	(None)
2		1	$p \lor q$	$\lor \mathcal I_1$	1
3		1	$p \land \left({p \lor q}\right)$	$\land \mathcal I$	1, 2

$\blacksquare$

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p \lor \left ({p \land q}\right)$	P	(None)
2		2	$p$	A	(None)
3		3	$p \land q$	A	(None)
4		3	$p$	$\land \mathcal E_1$	3
5		1	$p$	$\lor \mathcal E$	1, 2-2, 3-4

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

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$p$	P	(None)
2		1	$p \lor \left ({p \land q}\right)$	$\lor \mathcal I_1$	1

$\blacksquare$

Proof by Truth Table

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

As can be seen by inspection, in all cases the appropriate truth values match for all models.

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

$\blacksquare$

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

$\blacksquare$

Proof by Calculation

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p \lor \left({p \land q}\right)\)	\(=\)	\(\displaystyle \left({p \land \top}\right) \lor \left({p \land q}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Conjunction with Tautology
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p \land \left({\top \lor q}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Rule of Distribution
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p \land \top\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Disjunction with Tautology
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Conjunction with Tautology

$\Box$

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p \land \left({p \lor q}\right)\)	\(=\)	\(\displaystyle \left({p \lor \bot}\right) \land \left({p \lor q}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Disjunction with Contradiction
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p \lor \left({\bot \land q}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Rule of Distribution
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p \lor \bot\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Conjunction with Contradiction
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Disjunction with Contradiction

$\blacksquare$

Notes

The name absorption laws is also used for the equivalent results in set theory: Union with Intersection and Intersection with Union.

Sources

• E.J. Lemmon: Beginning Logic (1965): $\S 1.5$: Theorems $31, 32$
• Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.1$: Exercises $1.4: 2 \ \text{(n)}$