Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to convert the formula: $((p \wedge \neg n) \vee (n \wedge \neg p)) \vee z$. I understand i need to apply the z to each clause, which gives: $((p \wedge \neg n) \vee z) \vee ((n \wedge \neg p) \vee z)$. I know how to simplify this, but am unsure how it will lead to the answer containing 2 clauses.

Thanks.

share|improve this question
    
Possible duplicate of math.stackexchange.com/questions/214338/… –  Petr Pudlák Oct 17 '12 at 20:06

2 Answers 2

up vote 1 down vote accepted

You can first transform $(p \land \lnot n) \lor (\lnot p \land n)$ to $(p \lor n) \land (\lnot p \lor \lnot n)$. Then your formula will be equivalent to $(p \lor n \lor z) \land (\lnot p \lor \lnot n \lor z)$. In general, however, there is no requirement on CNFs to contain only two closes.

share|improve this answer

To convert to conjugtive normal form we use the following rules:

Double Negation:

  1. $P\leftrightarrow \lnot(\lnot P)$

De Morgans Laws

  1. $\lnot(P\bigvee Q)\leftrightarrow (\lnot P) \bigwedge (\lnot Q)$

  2. $\lnot(P\bigwedge Q)\leftrightarrow (\lnot P) \bigvee (\lnot Q)$

Distributive Laws

  1. $(P \bigvee (Q\bigwedge R))\leftrightarrow (P \bigvee Q) \bigwedge (P\bigvee R)$

  2. $(P \bigwedge (Q\bigvee R))\leftrightarrow (P \bigwedge Q) \bigvee (P\bigwedge R)$

So lets expand the following

  1. $((P\bigwedge \lnot N)\bigvee (N∧\lnot P))\bigvee Z$

  2. $((((P\bigwedge \lnot N)\bigvee N)\bigwedge ((P\bigwedge \lnot N)\bigvee \lnot P)))\bigvee Z)$

  3. $(((P\bigvee N)\bigwedge (\lnot N\bigvee N ) \bigwedge (P\bigvee \lnot P)\bigwedge (\lnot N \bigvee \lnot P)) \bigvee Z)$

Then noting that $(\lnot N\bigvee N)$ and $(P\bigvee \lnot P)$ are always true we may remove them and get (It's cancelling these terms that gives a 2 term answer):

  1. $((P\bigvee N)\bigwedge (\lnot N \bigvee \lnot P)) \bigvee Z)$

  2. $((P\bigvee N\bigvee Z)\bigwedge (\lnot N \bigvee \lnot P \bigvee Z))$

This will in general not happen though and you may get more terms in your formula in CNF. Just so you know you can also check these things on Wolfram Alpha

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.