# How to convert a formula to CNF?

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.

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

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.

-

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

-