Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
if u take a look here… – Epsilon Oct 15 '12 at 17:42
up vote 17 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|cite|improve this answer
How would you check it with Wolfram|Alpha? – Martin Thoma Nov 25 '14 at 20:35
@moose just type it on in:… – 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.

share|cite|improve this answer
If you feel like understanding were it came from check – user44874 Oct 16 '12 at 16:37

Your Answer


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.