2

I'm reading Susanna Epp's book on discrete mathematics. In the section on logical equivalences she gives 11 laws, of which the first five are: $$Commutative: p\land q\equiv q\land p $$$$Associative: (p\land q)\land r\equiv p\land (q\land r)$$ $$Distributive: p\land (q\lor r)\equiv (p\land q)\lor(p\land r)$$$$Identity: p\land\top\equiv p$$$$Negation: p\lor \lnot p\equiv \top$$ I have only written out for $\land$, but of course there are the same laws for $\lor$. These are described as axiomatic and used to derive the other six laws. My question is how do you derive the law below from the five above? $$Absorption: p\lor (p\land q)\equiv p$$

user21820
  • 57,693
  • 9
  • 98
  • 256
Erik Eriksson
  • 843

1 Answers1

4

I feel a bit silly answering my own question, but I guess it's for anyone that is interested.

$$p\lor (p\land q)$$$$\equiv (p\land \top)\lor (p\land q)$$$$\equiv (p\land (q\lor \lnot q))\lor (p\land q)$$$$\equiv ((p\land \lnot q)\lor(p\land q))\lor (p\land q)$$$$\equiv (p\land \lnot q)\lor ((p\land q)\lor(p\land q))$$$$\equiv (p\land \lnot q)\lor (p\land q)$$$$\equiv p\land (\lnot q \lor q)$$$$\equiv p\land \top$$$$\equiv p$$

Through some insightful comments it was pointed out that I used this law without justifying it with the five axioms: $$p\lor p \equiv p$$

Here is the solution I came up with:

$$p\lor p$$$$\equiv (p\lor p)\land \top$$$$\equiv (p\lor p)\land (p\lor \lnot p)$$$$\equiv p\lor (p\land \lnot p)$$$$\equiv p\lor \bot $$$$\equiv p$$

Erik Eriksson
  • 843
  • Don't feel silly. Answering your own question is encouraged. – J.G. Oct 30 '21 at 09:24
  • Which property does your fifth $\equiv$ use to justify $r\land r\equiv r$ with $r:=p\land q$? – J.G. Oct 30 '21 at 09:31
  • It's good to answer your own question! But a step in your answer is not clear. You write that $(p \land \lnot q) \lor ((p \land q) \lor (p \land q)) \equiv (p \land \lnot q) \lor (p \land q)$. This is correct, according to the idempotency law for $\lor$. But this law doesn't appear in your list. Are you entitled to use the idempotency laws? They say $p \land p \equiv p$ and $p\lor p \equiv p$. – Taroccoesbrocco Oct 30 '21 at 09:32
  • @Taroccoesbrocco I suppose I am not allowed to use idempotency law. I shall have to think about how to prove it using the first five. Thank you both for spotting it. – Erik Eriksson Oct 30 '21 at 10:21
  • @ErikEriksson - Well done! I guess you can accept your own answer. – Taroccoesbrocco Oct 31 '21 at 09:58
  • @Taroccoesbrocco Thank you. Math constantly makes me feel stupid so when those few moments of clarity come it is cause for celebration. Back to bashing my head against new problems. Have a nice day. – Erik Eriksson Oct 31 '21 at 10:10