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?
How to convert to conjunctive normal form?
-
4if u take a look here http://www.wolframalpha.com/input/?i=+CNF+%28%28a+and+b%29+or+%28q+and+r+%29%29+or+z – 2012-10-15
2 Answers
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.
-
1@moose just type it on in: http://www.wolframalpha.com/input/?i=%28A+%26+B%29+%7C%7C+%28C+%26+D%29+%7C%7C+E – 2014-11-26
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.
-
3If you feel like understanding were it came from check http://www.youtube.com/watch?v=tpdDlsg4Cws – 2012-10-16