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.

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?

share|improve this question
4  
if u take a look here wolframalpha.com/input/… –  André Oct 15 '12 at 17:42

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer

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.

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

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.