Write $(p\land q)\leftrightarrow (\neg p\lor \neg q)$ in CNF

Question

I need to convert the below for a homework question and I am not entirely sure if it's correct. The last part is that I am not sure how to use the distributive laws in this scenario. Any guidance would be appreciated:

$ (p \land q) \leftrightarrow (\lnot p \lor \lnot q)$

Step1: Eliminate all operators except for negation, conjunction and disjunction by substituting logically equivalent formulas:

$ (p \land q) \leftrightarrow (\lnot p \lor \lnot q) $

$ ((p \land q) \to (\lnot p \lor \lnot q)) \land ((\lnot p \lor \lnot q) \to (p \land q)) $

$ (\lnot(p \land q) \lor (\lnot p \lor \lnot q)) \land (\lnot(\lnot p \lor \lnot q) \lor (p \land q)) $

Step2: Push negation inwards using De Morgan’s laws:

$ ((\lnot p \lor \lnot q) \lor (\lnot p \lor \lnot q)) \land ((\lnot\lnot p \land \lnot\lnot q) \lor (p \land q)) $

Step3: Eliminate sequences of negations by deleting double negation operators:

$ ((\lnot p \lor \lnot q) \lor (\lnot p \lor \lnot q)) \land ((p \land q) \lor (p \land q)) $

$ (\lnot p \lor \lnot q) \land (p \land q) $

Step4: Use the distributive laws to eliminate conjunctions within disjunctions:

This is where I am stuck. I am unsure if I can apply the distributive law if there is the last and in $(p \land q)$ given that it is to eliminate conjunctions within disjunctions.

Any advice would be greatly appreciated

Answer 1

You do not have a conjunction within a disjunction. You have a conjunction of a conjunction.

$$(¬p \lor ¬q) \land (p \land q) = (\lnot p \lor \lnot q) \land p \land q$$

Literals can be conjoined in conjunctive normal form.

Note that if we do distribute $p$ over the disjunction, you'll find that the proposition is, in fact, a contradiction: we would obtain $$[(p\land \lnot p) \lor (p\land \lnot q)] \land q \equiv p\land \lnot q \land q \;\equiv \;\perp$$