# Negate and Simplify $p\wedge (q\vee r)\wedge(\neg p\vee\neg q\vee r)$

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

• What happens if you use distribute $\neg p$ into $(p\land q \land \neg r)$? Sep 11, 2020 at 5:02
• 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$$ Sep 11, 2020 at 5:08
• 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. Sep 11, 2020 at 5:09
• Don't the two above comments contradict one another? $p\wedge r\not\Longleftrightarrow\neg p\vee\neg r$ Sep 11, 2020 at 5:17
• Sorry, just realized Ninad is referring to the original statement and Brian is referring to its negation Sep 11, 2020 at 5:22

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

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