Simplify (p v (r v q)) ∧ ~(~q ∧ ~r)

Question

I understand that ~(~q ∧ ~r) simplifies down to (q v r), but I don't understand how the answer to this question is q v r.

For (p v (r v q)), I can simplify it to be (p v r v q). I thought maybe I could use the Universal Bound Laws or Identity Laws, but neither of the two equations leftover are tautologies or contradictions. Is there a specific property that I'm missing to handle (p v r v q) ∧ (q v r).

Thanks!

Answer 1

You're missing out something really simple!

I don't know exactly how you're treating stuff formally, but note that q v r implies p v q v r and hence (p v r v q) ∧ (q v r) can be rewritten as (q v r).

In the book "How to Prove It" by Daniel Velleman this law is called an Absorption Law.

Answer 2

$a$ implies $a\vee b$, since if $a$ is true $a\vee b$ is also true.

$a\Rightarrow b$ implies $a\wedge b = a$, since if $a$ is true, $b$ is also true and thus both are true. If $a$ is false, $a\wedge b$ could only be false.

Now substitute $a$ with $q\vee r$ and $b$ with $p$ in the first rule and you get $(q\vee r)\Rightarrow (p\vee q\vee r)$.

Then you can apply the second rule, you ($q\vee r)\wedge (p\vee q\vee r) = q\vee r$

Thanks to the implication $q\vee r\Rightarrow p\vee q\vee r$, the part $p\vee q\vee r$ is actually redundant.

Answer 3

$(p \lor (r \lor q)) \land \lnot(\lnot q \land \lnot r) $

$\iff (p \lor (r \lor q)) \land (\lnot \lnot q \lor \lnot \lnot r) \hspace{1in} \text{De Morgan} $

$\iff (p \lor (r \lor q)) \land (q \lor r) \hspace{1in} \text{Double negation} $

$\iff (p \land (q\lor r)) \lor ((r\lor q) \land (q\lor r)) \hspace{1in} \text{distributive law}$

$\iff (p \land (q\lor r))\lor (q\lor r)\hspace{1in}\text{Idempotent law}$

$\iff q\lor r \hspace{1in} \text{Absorption}$

Answer 4

$(A\lor B)\land B$ is true exactly when $B$ is true , whatever the value of $A$ may be. So it is simply $B$.

Answer 5

Others have pointed out that this is an instance of the Absorption Law. But if you don't have Absorption in your allowed set of rules, you can do this:

$(p \lor q \lor r) \land (q \lor r) \overset{Identity}{\Leftrightarrow}$

$(p \lor q \lor r) \land (\bot \lor q \lor r) \overset{Distribution}{\Leftrightarrow}$

$(p \land \bot) \lor (q \lor r) \overset{Annihilation}{\Leftrightarrow}$

$\bot \lor (q \lor r) \overset{Identity}{\Leftrightarrow}$

$q \lor r$