1
$\begingroup$

So far I have

\begin{align*} \neg[p\wedge(q\vee r)\wedge(\neg p\vee\neg q\vee r)]&\Longleftrightarrow\neg p\vee\neg(q\vee r)\vee\neg(\neg p\vee\neg q\vee r)&\mbox{Demorgan's Law}\\ &\Longleftrightarrow\neg p\vee(\neg q\wedge\neg r)\vee(\neg\neg p\wedge\neg\neg q\wedge\neg r)&\mbox{Demorgan's Law}\\ &\Longleftrightarrow\neg p\vee(\neg q\wedge\neg r)\vee(p\wedge q\wedge\neg r)&\mbox{Double Negation}\\ \end{align*} At this point I'm unsure of where to go. I considered applying the Distributive Law which would give me

$$[(\neg p\vee\neg q)\wedge(\neg p\vee\neg r)]\vee(p\wedge q\wedge \neg r)$$

But I don't know if this is getting any closer to 'simplifying' the statement.

I have an obvious intuition about when an algebraic expression is fully simplified. I assume there is an analogous intuition around logical statements but I certainly don't have it. Is there a rule of thumb for this sort of thing? What would the negation of this statement look like 'fully simplified'?

Thanks

$\endgroup$
5
  • 1
    $\begingroup$ What happens if you use distribute $\neg p$ into $(p\land q \land \neg r)$? $\endgroup$ – player3236 Sep 11 '20 at 5:02
  • 3
    $\begingroup$ You could take the original expression in pieces. The $p \land$ outside suggests that the $\lnot p \lor$ inside doesn't matter so this expression will have the same truth value as $$p \land (q \lor r) \land (\lnot q \lor r)$$ But in the last two expressions, the value of $q$ doesn't matter (i.e. $(q \lor r) \land (\lnot q \lor r) = r$), which means that this expression has the same truth value as $$p \land r$$ $\endgroup$ – Ninad Munshi Sep 11 '20 at 5:08
  • 1
    $\begingroup$ Note that it’s automatically true if $\neg p$ is true. What if $p$ is true instead? Then it’s still true as long as $\neg r$ is true, whether or not $q$ is true. Thus, it appears that the expression is true precisely when at least one of $\neg p$ and $\neg r$ is true, which would make it equivalent to $\neg p\lor\neg r$. Now you have a target: try to find manipulations that yield that expression. $\endgroup$ – Brian M. Scott Sep 11 '20 at 5:09
  • $\begingroup$ Don't the two above comments contradict one another? $p\wedge r\not\Longleftrightarrow\neg p\vee\neg r$ $\endgroup$ – Gteal Sep 11 '20 at 5:17
  • 1
    $\begingroup$ Sorry, just realized Ninad is referring to the original statement and Brian is referring to its negation $\endgroup$ – Gteal Sep 11 '20 at 5:22
2
$\begingroup$

In a situation like this, with so few variables (3), and such complex expressions, the easiest approach is to dispense with all attempts at elegance and simply construct the appropriate chart of Boolean true/false values.

Let $A$ denote $(q \vee r).$
Let $B$ denote $(\neg p \vee \neg q \vee r).$
Then you are trying to negate and simplify $(p \wedge A \wedge B).$

$$\begin{array} {|c|c|c|c|c|c|c|} \hline p & q & r & A & B & (p \wedge A \wedge B) & \neg (p \wedge A \wedge B) \\ \hline t & t & t & t & t & t & f \\ \hline t & t & f & t & f & f & t \\ \hline t & f & t & t & t & t & f \\ \hline t & f & f & f & t & f & t \\ \hline f & t & t & t & t & f & t \\ \hline f & t & f & t & t & f & t \\ \hline f & f & t & t & t & f & t \\ \hline f & f & f & f & t & f & t \\ \hline \end{array}$$

Assuming that I have made no mistake, the "negate and simplify" will always be true except for the
$(p,q,r)$ truth/false values of $(t,t,t)$ and $(t,f,t)$ which
simplifies to $(\neg p \vee \neg r) = \neg(p \wedge r).$

$\endgroup$
0
$\begingroup$

Using that (Distributive law and "Glue" law): $$ a \wedge \left(b\vee c\right) = \left(a \wedge b\right)\vee\left(a \wedge c\right)$$ $$ (a\vee b) \wedge (\neg a\vee b) = b$$

We have: $$ p\wedge (q\vee r)\wedge(\neg p\vee(\neg q\vee r)) = p\wedge \left(\left((q\vee r) \wedge \neg p\right) \vee \left((q\vee r)\wedge (\neg q \vee r)\right)\right) = $$ $$ = p\wedge \left(((q\vee r) \wedge \neg p) \vee r\right) $$

Using Distributive law again we have: $$ p\wedge \left(((q\vee r) \wedge \neg p) \vee r\right) = p\wedge \left(((q\vee r) \wedge \neg p) \vee r\right) = (p \wedge (q \vee r) \wedge \neg p) \vee (p \wedge r) $$

Also, we know that: $$ a \wedge b \wedge \neg a = 0 $$ Now we have: $$ (p \wedge (q \vee r) \wedge \neg p) \vee (p \wedge r) = 0 \vee (p \wedge r) = p \wedge r$$

The answer is: $$ p\wedge (q\vee r)\wedge(\neg p\vee\neg q\vee r) = p \wedge 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.