How to convert to conjunctive normal form?

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.

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:

$$\begin{array}{ccccc|c} a & b & q & r & z & \phi\\\hline 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ \end{array}$$

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 $\begin{array}{ccccc|c}0&1&0&1&0&0\end{array}$ you get the clause $(x \vee \bar y \vee q \vee \bar r \vee z)$.

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