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

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

• I don't get why you can't progress. Abbreviate $p\land q$ by $s$. Can you use De Morgan on $(\neg p\lor \neg q)\land s$? Jun 3, 2014 at 17:10
• I don't get your comment, @GitGud. I think you mean "distributivity" and not DeMorgan's, and there's no use in distributing, since we want CNF. Jun 3, 2014 at 17:17
• @amWhy Yes, that's what I meant. My point being that one gets a contradiction, so you can just write $p\land \neg p$ or $(p\lor p)\land (\neg p\lor \neg p)$, depending on the definition of CNF. Jun 3, 2014 at 17:22

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

• Great, that makes sense, thank you. Just to confirm, does this then look like valid CNF for (p ^ q) ↔ (¬p V ¬q)? Jun 3, 2014 at 17:19
• @amWhy Sorry, you already had my up vote :P Jun 3, 2014 at 17:30