1
$\begingroup$

I have been working on an assignment exercise that asks for the conjunctive normal form (CNF) of the logic predicate $\neg (p \iff \neg q \implies r)$. So far I've managed to obtain the expression $(p \wedge (\neg q \wedge \neg r)) \vee ((q \vee r) \wedge \neg p)$ by applying conditional removals, De Morgan's law and double negative law, however I'm currently stuck in this step of the CNF conversion.

I know that the CNF for this is $(\neg q \vee \neg p) \wedge (\neg r \vee \neg p) \wedge (p \vee q \vee r)$ as I have checked it on a CNF converter; actually I have been checking all my expressions from the very first one up to the one I'm stuck in and my progress has been right so far, but I can't figure out how to proceed. I know that in general I should be aiming to distribute the disjunctions over conjunctions to obtain the CNF, but most of the examples I've seen previously deal with easier predicates.

How can I prove the following? $(p \wedge (\neg q \wedge \neg r)) \vee ((q \vee r) \wedge \neg p) \equiv (\neg q \vee \neg p) \wedge (\neg r \vee \neg p) \wedge (p \vee q \vee r)$

$\endgroup$
1
$\begingroup$

All you need is keep applying distributive law

Start from

$$(p∧(¬q∧¬r))∨(\color{blue}{(q∨r)∧¬p})$$

Apply distributive law

$$\big((\color{blue}{(q∨r)∧¬p})\vee \color{red}{p}\big) \wedge\big((\color{blue}{(q∨r)∧¬p})\vee\color{orange}{(\neg q\wedge \neg r)})\big)$$

Apply distributive law

$$\big(((q∨r)\vee \color{red}{p})∧(\underset{\top}{\underbrace{¬p\vee \color{red}{p}}})\big) \wedge ((\underset{\top}{\underbrace{(q\vee r)\vee\color{orange}{(\neg q\wedge \neg r)})}}\wedge(\color{lightgrey}{\neg p}\vee\color{orange}{(\neg q\wedge \neg r)}))$$

Note $P\wedge\top\Leftrightarrow P$

Apply distributive law

$$(p∨q∨r)∧(¬q∨\color{lightgrey}{¬p})∧(¬r∨\color{lightgrey}{¬p})$$

Rearrange the order we get $$(¬q∨¬p)∧(¬r∨¬p)∧(p∨q∨r)$$

$\endgroup$
  • $\begingroup$ thank, I finally understood these last few steps (: $\endgroup$ – MikeKatz45 Oct 26 '19 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.