3
$\begingroup$

Consider an disjunctive normal form boolean expression on $n$ variables. What is the upper bound on the number of terms in a minimal equivalent DNF expression? That is, given an arbitrary DNF expression on $n$ variables, after eliminating redundant terms, what length is it guaranteed to be under (how many $\vee$'s)?

$\endgroup$
  • 2
    $\begingroup$ Should be something like $2^{n-1}$. What did you try? I'm curious what is the motivation too. $\endgroup$ – Radu GRIGore Sep 27 '12 at 10:08
  • $\begingroup$ As @radu-grigore says it is at least $2^{n-1}$ with the parity function as an example of that. $\endgroup$ – MGwynne Sep 27 '12 at 19:39
4
$\begingroup$

The answer is $2^{n-1}$.

To see that this is a lower bound consider the n variable parity function and observe that the unique (equivalent) DNF has $2^{n-1}$ clauses, none of which are resolvable.

To see that this is an upper bound, consider any DNF and the full ordered decision tree for that DNF (i.e., tree where every leaf is at depth n and every path from the root to the leaf has all variables and in the same fixed order). Any two leafs which are siblings and which are both "true" represent resolvable clauses in the full equivalent DNF. In this way one has at least has an equivalent clause-set of size at most $2^{n-1}$ by taking for every node at level n-1 either the DNF clause given by the only true leaf child of that node (if it has one true child) or the resolvent of the two clauses corresponding to its two children (if it has two true children). That is we have at most one clause for each node at this level in the tree, I.e., $2^{n-1}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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