Showing $P \land (P \lor Q) = P$ using only laws of propositions.

Question

How can I show $P \land (P \lor Q) = P$ using only laws of propositions?

I see how $P \land (P \lor Q) = P$ simplifies to just $P$ using a truth table, but I can't see how to get it using propositional calculus. The distributive law just changes it to $P \lor (P \land Q)$, leaving me essentially in the same position.

Answer 1

It is indeed true that $P \land (P \lor Q) = P$, this is called the absorption law. Sometimes this law is taken as a rule itself (for interested logicians, see the end of this answer). You mention that you are allowed to use the distributive law, and we can actually prove the absorption law with some clever use of it. We will also need the constant $\bot$, which I use to denote false. Remember that we always have $A \lor \bot = A$ and $A \land \bot = \bot$ for every proposition $A$. So now we can just write: $$ P = P \lor \bot = P \lor (Q \land \bot) = (P \lor \bot) \land (P \lor Q) = P \land (P \lor Q). $$ The rules we use here are (from left to right):

1. $P = P \lor \bot$ (this holds for all propositions, so in particular for $P$),
2. $\bot = Q \land \bot$ (this holds for all propositions, so in particular for $Q$),
3. distributive law,
4. $P = P \lor \bot$ (again).

---

The promised footnote for the interested logicians: the absorption law is in a sense more fundamental, because it is one of the axioms when defining a (bounded) lattice in the algebraic way. When you add the distributive law, you get a distributive lattice. The above shows that the absorption law can be proved in a distributive lattice, so you no longer need that axiom.

Answer 2

Here is one way to show this using natural deduction:

The equivalence will be derived using the biconditional introduction inference rule. I will consider each side of the biconditional as separate subproofs and then reference both at the end.

I consider $(P\land (P\lor Q))\to P$ on lines 1-2. I assume the antecedent $(P\land (P\lor Q))$ on line 1 and derive the consequent $P$ using conjunction elimination ($\land$E) on line 2.

I consider the other direction $P\to (P\land (P\lor Q))$ on lines 3-5. I assume the antecedent $P$ on line 3 and derive the consequent $(P\land (P\lor Q))$ using disjunction introduction ($\lor$I) on line 4 and conjunction introduction ($\land$I) on line 5.

Line 6 uses biconditional introduction on the two subproofs mentioned above referencing each subproof as a range of lines.

---

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

Answer 3

Well, the following analogy doesn't apply directly, but if you had two sets, $A$ and $C$ then $A \cap (A \cup C) = A$ $\iff$ $C\subset A$

Answer 4

To show statements are equivalent, show each implies the other. Simplification gives $\to$ while addition plus adjunction gives $\leftarrow$.