0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

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