# How to show this predicate logic equivalence?

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

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

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