2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Hint: what is (p or not p)? $\endgroup$
    – AHusain
    Commented Oct 14, 2018 at 7:01

3 Answers 3

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 14, 2018 at 8:37
  • $\begingroup$ When can you not use the double negation law? $\endgroup$
    – Sam
    Commented Jul 11, 2019 at 17:11
  • 1
    $\begingroup$ @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…" $\endgroup$ Commented Jul 11, 2019 at 17:43
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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