Negate and simplify: $p\lor q\lor(\lnot p\land \lnot q\land r)$

Question

Negate and simplify:

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

So far what I have done is:

$$\lnot[\;p\lor q\lor(\,\lnot p\land \lnot q\land r\,)\;]$$ $$\lnot p\land \lnot q\land \lnot(\;\lnot p\land \lnot q\land r\,)$$

I'm not really sure what law to use next. I was thinking that it would be DeMorgan so that I'd get:

$$\lnot p\lor \lnot q\lor \lnot\lnot p\lor \lnot\lnot q\lor \lnot r$$

But I am stumped on what I have to do after that.

Answer 1

Hint: Assuming you're in a logic where you have the inference rule $\neg \neg p \to p$, it's the case that $p \leftrightarrow \neg \neg p$. It's almost always correct to apply this rule to simplify double-negations whenever you can.

---

An alternative approach entirely: write out a truth table for the original statement, then the table for its negation, and see what you can come up with as a simplification.

Answer 2

There is an error in what you did: if you apply De Morgan to $\lnot p \land \lnot q \land \lnot (\lnot p \land \lnot q \land r)$, you get the formula $$\tag{1} \lnot p \land \lnot q \land (\lnot \lnot p \lor \lnot \lnot q \lor \lnot r)$$ and not the formula $\lnot p \lor \lnot q \lor (\lnot \lnot p \lor \lnot \lnot q \lor \lnot r)$. This is important, because now you are forced to apply distributivity to $(1)$.

A complete simplification, using the logical equivalences listed here, is the following:

\begin{align} &\lnot \big(p \lor q \lor (\lnot p \land \lnot q \land r) \big) \\ \equiv\ & \lnot p \land \lnot q \land \lnot (\lnot p \land \lnot q \land r) &&\text{De Morgan} \\ \equiv \ & \lnot p \land \lnot q \land (\lnot \lnot p \lor \lnot \lnot q \lor \lnot r) &&\text{De Morgan} \\ \equiv \ & (\lnot p \land \lnot q \land \lnot \lnot p) \lor (\lnot p \land \lnot q \land \lnot \lnot q) \lor (\lnot p \land \lnot q \land \lnot r) &&\text{distributivity} \\ \equiv \ & (\lnot p \land \lnot \lnot p \land \lnot q) \lor (\lnot p \land \lnot q \land \lnot \lnot q) \lor (\lnot p \land \lnot q \land \lnot r) &&\text{commutativity} \\ \equiv \ & (\bot \land \lnot q) \lor (\lnot p \land \bot) \lor (\lnot p \land \lnot q \land \lnot r) &&\text{negation law} \\ \equiv \ & \bot \lor \bot \lor (\lnot p \land \lnot q \land \lnot r) &&\text{domination law} \\ \equiv \ & \lnot p \land \lnot q \land \lnot r &&\text{identity law} \\ \end{align} where $\bot$ (called falsum or absurdum or contradiction) denotes a formula that is always false. So, $\lnot p \land \lnot \lnot p \equiv \bot$ because $\lnot p \land \lnot \lnot p$ is a formula of the form $P \land \lnot P$ (take $P = \lnot p$), which is clearly contradictory. Note that there is no need to use the double negation law $\lnot \lnot p \equiv p$.

Answer 3

$$p\lor q \lor (\,\lnot p\land \lnot q\land r)\equiv(p\lor q)\lor(\neg (p\lor q)\land r)\equiv1\land(p\lor q\lor r)=p\lor q\lor r$$ Negation:

$$\neg(p\lor q\lor r)\equiv\neg p\land\neg q\land\neg r$$