4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to Math StackExchange! You will find that people are more willing to answer your question if you tell us what you have tried and where you are stuck. This shows some genuine effort from your side, as people are generally not willing to solve your homework problems for you. Also, it may help you get more tailored answers. $\endgroup$ – Mark Kamsma Aug 29 '19 at 16:35
  • $\begingroup$ Welcome to MSE! When you ask a question, please tell your question clearly and show your efforts when you are struggling in this problem. Thank you! $\endgroup$ – Isaac YIU Math Studio Aug 29 '19 at 16:36
  • $\begingroup$ I see how P AND (P OR Q) simplifies to just P using a truth table, but how do I show that using just laws? The distributive law just changes it to P OR (P AND Q), leaving me essentially in the same position. I've spent an about two hours just applying different combinations of laws, but I just don't see how to reduce the left hand side to the right hand side. $\endgroup$ – Tim The Human Aug 29 '19 at 17:33
1
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ $A\cap (A\cup C)=A$ is unconditionally true just as $P\wedge (P\vee Q)\dashv \vdash P$ is. $\endgroup$ – K B Dave Aug 29 '19 at 18:14
  • 1
    $\begingroup$ Adding to K B Dave's comment, that means that the claim in this answer is actually false. We do not have $A \cap (A \cup C) \Rightarrow C \subseteq A$. Any two sets with $C \not \subseteq A$ should do as a counterexample, e.g. $A = \mathbb{N}$ and $C = \mathbb{R}$. $\endgroup$ – Mark Kamsma Aug 29 '19 at 19:11
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That was amazing, thank you. I never would of thought to use the law of contradiction in reverse, beautiful. $\endgroup$ – Tim The Human Aug 29 '19 at 23:41
  • $\begingroup$ Little did you know you just helped me complete my DOOMSDAY DEVICE! $\endgroup$ – Tim The Human Aug 29 '19 at 23:47
2
$\begingroup$

Here is one way to show this using natural deduction:

enter image description here

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/

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.