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

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.

• Hint: what is (p or not p)? Commented Oct 14, 2018 at 7:01

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

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.

• There is no need to use the double negation law. Actually, there is a mistake in the OP's attempt, as I explain in my answer. Commented Oct 14, 2018 at 8:37
• When can you not use the double negation law?
– Sam
Commented Jul 11, 2019 at 17:11
• @Sam Constructive logics don't have that law. More intuitively, just knowing that something isn't wrong, isn't enough for you to deduce that it's right: "Well, you're not wrong, but…" Commented Jul 11, 2019 at 17:43

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