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'?


  • 1
    $\begingroup$ What happens if you use distribute $\neg p$ into $(p\land q \land \neg r)$? $\endgroup$
    – player3236
    Sep 11, 2020 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$ Sep 11, 2020 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$ Sep 11, 2020 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, 2020 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, 2020 at 5:22

2 Answers 2


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .