2
$\begingroup$

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

$\endgroup$
3
  • 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, 2014 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, 2014 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, 2014 at 17:22

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
2
  • $\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, 2014 at 17:19
  • $\begingroup$ @amWhy Sorry, you already had my up vote :P $\endgroup$
    – Git Gud
    Jun 3, 2014 at 17:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .