# How do I know the steps of CNF algorithm?

• Dec 6th 2012, 03:13 AM
andrei
How do I know the steps of CNF algorithm?
I'm solving exercises from Hedman's "First course in logic". Here is Exercise 1.21.
Quote:

Consider the following formula in DNF.
\$\displaystyle (A_1\wedge B_1)\vee(A_2\wedge B_2)\vee\dots\vee(A_n\wedge B_n)\$
Given this formula as input, how many steps will it take the CNF algorithm to halt and output a formula in CNF? Is this algorithm polynomial-time?
What a step is? Let me take an example
\$\displaystyle (A_1\wedge B_1)\vee(A_2\wedge B_2)\vee(A_3\wedge B_3)\$
Then as I understand
in step 1 I get \$\displaystyle A_1\vee A_2\vee A_3\$
in step 2 - \$\displaystyle A_1\vee A_2\vee B_3\$
in step 3 - \$\displaystyle A_1\vee B_2\vee A_3\$
in step 4 - \$\displaystyle A_1\vee B_2\vee B_3\$
in step 5 - \$\displaystyle B_1\vee ...\$
...
In total 8 steps. Have I read the formula 8 times? So I'd answer that it will take \$\displaystyle 2^n\$ steps and the algorithm is not polynomial-time. Is it correct?

Also I've been thinking as follows. I take first two conjuncts of the given formula and apply CNF algorithm to them. Then I "absorb" the third conjuct and get a new CNF. I repeat this process until the end.