Converting CNF to DNF: Does it Always Work?

[gnome]

Will this method always convert a CNF formula to an equivalent DNF formula:

1. negate the ENTIRE formula
2. negate each literal
3. simplify using DeMorgan's laws

For example, given:

<br /> \begin{equation}<br /> \begin{split}<br /> A:&amp;\quad(p \vee q) \wedge (q \vee r ) \wedge (p \vee r )\notag \\<br /> &amp;\quad\overline{(\overline p \vee \overline q) \wedge (\overline q \vee \overline r) \wedge (\overline p \vee \overline r )}\notag \\<br /> &amp;\quad\overline{(\overline p \vee \overline q)} \vee \overline{(\overline q \vee \overline r)} \vee \overline{(\overline p \vee \overline r )}\notag \\<br /> B:&amp;\quad(p \wedge q) \vee (q \wedge r ) \vee (p \wedge r )\notag \\<br /> \end{split}<br /> \end{equation}<br />

A truth table shows that A and B are equivalent. But is this valid for ANY formula?

 

[Bartholomew]

No; for example, it does not work on (p + q).(q + r). You would get (p.q) + (q.r) which is not equivalent since when q is true and p and r are false, the formulas yield different truth values.

 

[gnome]

You're right. Thanks.