1
$\begingroup$

When hand-manipulating algebra DNF (sum of products) is easier than CNF (product of sums). Possibly because factoring is more difficult than expanding. So why is it the opposite for computational boolean algebra?

Perhaps one argument is that in CNF one can show that an expression is false by showing that one clause is false. But that is no different from showing that an expression is true by showing that one conjunction is true.

$\endgroup$
1
  • $\begingroup$ I suppose if we want to prove something can be true, CNF allows us to eliminate big swaths of the solution space, while DNF would do the same if we wanted to prove something can be false, but that's not what we want to prove $\endgroup$
    – user253751
    May 16, 2023 at 16:08

1 Answer 1

2
$\begingroup$

One (serious) issue is that converting to DNF is harder than solving the SAT problem itself! E.g. you can see that:

$$ x\wedge y\ \vee\ x\wedge \neg z$$

has 2 solutions, $x=\top,\ y=\top$ and $x=\top,\ z=\bot$, without doing any fancy work.

This means that converting into DNF is going to be tough, as opposed to CNF for which there are efficient algorithms. Note that in the CNF conversion, the result is not strictly equivalent but merely equisatisfiable, which is all that SAT solvers care about.

$\endgroup$
4
  • $\begingroup$ You just expand the expression and you get the DNF. I don't understand why that is tough or not possible to do in linear time. $\endgroup$ May 16, 2023 at 19:14
  • $\begingroup$ Try to expand $(A\vee B)\wedge (C\vee D)\wedge (E\vee F)$! $\endgroup$
    – cody
    May 16, 2023 at 19:28
  • $\begingroup$ It wasn't difficult, though the expanded expression is longer of course. $\endgroup$ May 16, 2023 at 21:25
  • 2
    $\begingroup$ How much larger? $\endgroup$
    – cody
    May 16, 2023 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.