21
$\begingroup$

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?

$\endgroup$
1

3 Answers 3

30
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ How would you check it with Wolfram|Alpha? $\endgroup$ Nov 25, 2014 at 20:35
  • 2
    $\begingroup$ @moose just type it on in: wolframalpha.com/input/… $\endgroup$
    – hmmmm
    Nov 26, 2014 at 14:43
13
$\begingroup$

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.

$\endgroup$
1
1
$\begingroup$

The question is quite old, but I think it is worth mentioning here. De Morgan's laws and distributive property make exponentially long formulas, the alternative is to use Tseytin transformation. The resultant formula is linear in the size of the input formula.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .