1
$\begingroup$

I want to simplify the below proposition

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

Taken from Discrete and Combinatorial Mathematics sec 2.2 ex. #6.

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

$\lnot[(p \land (q \lor r)) \land ((\lnot p \lor \lnot q) \lor r)] \quad $ //assoc (not sure if legal)

$\lnot(p \land (q \lor r)) \lor \lnot((\lnot p \lor \lnot q) \lor r) \quad$ //DM

$(\lnot p \lor \lnot(q \lor r)) \lor (\lnot(\lnot p \lor \lnot q) \land \lnot r) \quad$ //DM

$(\lnot p \lor (\lnot q \land \lnot r)) \lor ((p \land q) \land \lnot r) \quad$ //DM

$((\lnot p \land \lnot q) \lor (\lnot p \land \lnot r)) \lor ((p \land q) \land \lnot r) \quad$ //DIST

I'm not sure what to do at this point, maybe I should have temporary ignored the negation (I tried that before, and got nowhere).

$\endgroup$
1
  • $\begingroup$ what is "simple"? less operations or less operators or less the characters ? do you mean some normal form? $\endgroup$ Commented Jan 28, 2018 at 8:33

2 Answers 2

1
$\begingroup$

Yes, I would temporarily ignore negation.

$$\begin{array}{lcll}(p\land(q\lor r))\land(\lnot p\lor\lnot q\lor r) & \Leftrightarrow & (p\land(q\lor r)\land\lnot p)\lor(p\land(q\lor r)\land\lnot q)\lor(p\land(q\lor r)\land r)& \text{De Morgan's laws}\\ & \Leftrightarrow& \bot \lor (p\land\lnot q\land r) \lor (p\land r) & \text{Because: }(q\lor r)\land r\Leftrightarrow r\text{ and }(q\lor r)\land\lnot q\Leftrightarrow\lnot q\land r\\ & \Leftrightarrow& p\land((\lnot q\land r) \lor r)&\\ & \Leftrightarrow & p\land r \end{array}$$

and now you can add the final negation. The result should be, if I am right, $\lnot(p\land r)$, or $\lnot p\lor\lnot r$.

$\endgroup$
1
$\begingroup$

The association was legal, but you just choose the wrong literals.   You have a lone $p$ among the conjunction, so you should target the $\neg p$ inside the disjunction.   Use association and commutation.

$${\lnot\big(p \land (q \lor r) \land (\lnot p \lor \lnot q \lor r)\big) \\\lnot\Big(p\land\big(\neg p\lor(\neg q\lor r)\big)\land (q \lor r)\Big) }$$

From here distribution will lead the way.

$\endgroup$

You must log in to answer this question.

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