Derive $p\lor (p\land q)\equiv p$ from the usual boolean algebra axioms

124 Views Asked by At

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$$

1

There are 1 best solutions below

6
On BEST ANSWER

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$$