<p>The answer is $2^{n-1}$.</p>

<p>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.</p>

<p>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}$.</p>

CC BY-SA 3.0
2012-09-27T20:01:48.717Z
2012-09-28T07:41:49.570Z
2012-09-28T07:41:49.570Z
MGwynne
<p>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)?</p>

CC BY-SA 3.0
2012-09-27T10:08:41.747Z
Should be something like $2^{n-1}$. What did you try? I'm curious what is the motivation too.
Radu GRIGore
CC BY-SA 3.0
2012-09-27T19:39:46.410Z
As @radu-grigore says it is at least $2^{n-1}$ with the parity function as an example of that.
MGwynne
<cc.complexity-theory><co.combinatorics><boolean-functions>
Length of a minimal DNF Boolean expression
Matthew Piziak
# Length of a minimal DNF Boolean expression

(Asked by: username_0 on 2012-09-27)

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)?

**Tags:** cc.complexity-theory, co.combinatorics, boolean-functions
> **Comments:**
> **username_1**: Should be something like $2^{n-1}$. What did you try? I'm curious what is the motivation too.  
> **username_2**: As @radu-grigore says it is at least $2^{n-1}$ with the parity function as an example of that.  

---

## 1 answers

### Answer by username_2 on 2012-09-27. Score: 5

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}$.


---

