# How to convert to conjunctive normal form?

If i have a formula: $((a \wedge b) \vee (q \wedge r )) \vee z$, am I right in thinking the CNF for this formula would be $(a\vee q \vee r \vee z) \wedge (b \vee q \vee r \vee z)$? Or is there some other method I must follow?

-
if u take a look here wolframalpha.com/input/… –  Andre Oct 15 '12 at 17:42

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

Double Negation:

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

De Morgan's Laws

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

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

Distributive Laws

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

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

So let’s expand the following: (equivalent to the expression in question)

1. $(((A \bigwedge B) \bigvee (C \bigwedge D)) \bigvee E)$ Now using 4. we get:

2. $((A \bigwedge B) \bigvee C)\bigwedge ((A \bigwedge B) \bigvee D)) \bigvee E$ And using 4. again

3. $((((A\bigvee C) \bigwedge (B \bigvee C))\bigwedge ((A\bigvee D) \bigwedge B\bigvee D))) \bigvee E)$ which gives:

4. $(((A\bigvee C) \bigwedge (B \bigvee C))\bigvee E)\bigwedge ((A\bigvee D) \bigwedge B\bigvee D))\bigvee E)$

5. $(A\bigvee C\bigvee E) \bigwedge (B \bigvee C\bigvee E)\bigwedge (A\bigvee D\bigvee E) \bigwedge (B\bigvee D\bigvee E)$

Which is now in CNF. You can use things like Wolfram Alpha to check these as well if you wish.

-
How would you check it with Wolfram|Alpha? –  moose Nov 25 '14 at 20:35
@moose just type it on in: wolframalpha.com/input/… –  hmmmm Nov 26 '14 at 14:43

Another possibility is to make a truth table (Note, in my symantics 1=T and 0=F); it is longer but this method is fail safe. $\phi=((a\wedge b)\vee(q \wedge r))\vee z$ then:

$a$ $b$ $q$ $r$ $z$ | $\phi$

0 0 0 0 0 | 0

0 0 0 0 1 | 1

0 0 0 1 0 | 0

And so on, and for every row in which $\phi=0$ you get a "Clause" by putting the literal in the clause if he takes 0 in that row and his "not" if the literal takes 1.

For example the clause for the first line is $(x \vee y\vee q \vee r \vee z)$. the clause for the third line is $(x \vee y\vee q \vee \bar r \vee z)$. There is no clause for the second line because $\phi=1$.

For the line (0 1 0 1 0 | 0) you get the clause $(x \vee \bar y \vee q \vee \bar r \vee z)$.

Finally you put a $\wedge$ between the clauses.

-
If you feel like understanding were it came from check youtube.com/watch?v=tpdDlsg4Cws –  user44874 Oct 16 '12 at 16:37