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

  • 1
    $\begingroup$ 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$? $\endgroup$ – Git Gud Jun 3 '14 at 17:10
  • $\begingroup$ 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. $\endgroup$ – amWhy Jun 3 '14 at 17:17
  • $\begingroup$ @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. $\endgroup$ – Git Gud Jun 3 '14 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$$

  • $\begingroup$ Great, that makes sense, thank you. Just to confirm, does this then look like valid CNF for (p ^ q) ↔ (¬p V ¬q)? $\endgroup$ – TBohnen.jnr Jun 3 '14 at 17:19
  • $\begingroup$ @amWhy Sorry, you already had my up vote :P $\endgroup$ – Git Gud Jun 3 '14 at 17:30

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.